在不使用锁的情况下保持数据一致性的任何方法

Question

我正在尝试为从外部数据源获取的数据实现缓存。我试图弄清楚我是否可以避免所有锁并使用时间戳来确保过时的数据永远不会插入缓存中。是否已经为此制定了机制？我举个例子：

    // Reader thread does
   1 Data readData(id) {
   2       Data data = cache.get(id);
   3       if(data == null)
   4           data = extDataSrc.readData(id);
   5       cache.put(id, data);   
   6       return data;    }
    // Writer thread does
   7 void updateData(id, Data data) {
   8        extDataSrc.updateData(id, data);
   9        cache.remove(id); 
   10 }

所以现在没有锁，当id在缓存中不存在时，读者可能会调用extDataSrc。如果同时编写器更新相同的 id，则在编写器提交之前，读取器可能会读取过时的数据，并延迟从 extDataSrc 调用返回。同时，编写器执行cache.remove（id）（缓存中没有数据，因此不会删除任何内容）并返回。然后读取器执行cache.put（id）。我认为这可以通过使用时间戳来避免，这样当读取器检查缓存时，它会保存时间戳 TR1（在第 2 行之后：检查缓存是否有 id 的时间）。编写器在执行删除后保存 TW1（第 9 行：更新时间之后）。读取器在执行第 4 行后，再次保存 TR2（在第 4 行之后：当读取完成并且即将开始缓存更新时）。在这里，如果 TR2> TW1，它会跳过 cache.put，因为其他线程在读取缓存后进行了更新。

因此，TR1 = 100，TW1 = 105，TR2 = 110 =>跳过cache.put。

有什么意义吗？

Answer 1

看看：

• 读写器锁定
• RCU 数据结构

Answer 2

我建议在执行extDataSrc.readData(id)时在缓存中放置一个临时同步对象。首先，如果 2 个读取器线程请求相同的项目，则第二个线程不需要发出冗余请求，而只需等待第一个发出的请求。其次，当编写器看到请求正在进行时，它可以简单地将其数据放入缓存中并向读取器提供数据。当readData完成后，它必须检查编写器是否已满足请求（缓存项是数据，而不是临时对象），并简单地丢弃extDataSrc中的（过时的）数据。

而不是使用时间戳，我会在数据对象中使用版本号 - 即使有多个进程写入同一extDataSrc，它也可以工作。