海量数据的查询缓存问题

现在面临一张用户使用记录表，可能达到千万级的数据量，用户在基本操作完成后（插入数据），都会查询下记录。用户本身的使用记录数不多，而且也能通过时间来控制查询的条数，但是我们用的是MEMCACHED相对数据进行缓存，但是遇到了一个问题。
个人认为缓存仅仅作为一种附属品而存在，是为了提高性能，应该不深入到业务逻辑里面。缓存服务器的shutdown也不应该影响主业务的执行。
缓存的应用在频繁访问数据，而且更新不是特别频繁的数据上才能达到很好的效果。存入库里的数据不会出现更新的情况，只有用户增加和删除相应使用记录的情况。
这里我有个问题:如果当前用户的查询已经在缓存中存在，但是用户插入一条记录，这个时候是要更新缓存，或者是将原有缓存清除。
1.如果更新缓存：这种方式就会存在更新缓存失败的情况，而此时也不能让库中数据回滚（干扰业务），但是用户再次查询就会到缓存中获取。数据不一致的情况出现。
2.如果将原有缓存清除，也会遇到清除失败的情况，此时也会遇到不一致。

缓存有个失效策略和失效时间，但是我们这个项目大量依赖于缓存，而且设置为缓存设置为不失效。所以才会在很多地方都是来操作缓存更新字段，但是一旦更新缓存失败，数据就永远也对应不上了。对此我强烈的反对此做法，但是决定不了什么。

所以请问各位在利用缓存处理海量数据问题上有什么好的方法来做？