Любой способ согласования данных без использования блокировок?

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 } 

Так что теперь без замков, возможно, что когда идентификатор не присутствует в кэше, читатель вызывает extDataSrc. Если в то же время автор обновляет один и тот же идентификатор, возможно, что до того, как писатель совершит ошибку, читатель считывает устаревшие данные и получает задержку при возврате из вызова extDataSrc. Тем временем автор выполняет cache.remove (id) (никаких данных в кеше, поэтому ничего не удаляет) и возвращается. Затем Reader выполняет cache.put (id). Я думал, что этого можно избежать, используя временные метки, чтобы, когда читатель проверяет кеш, он сохраняет временную метку TR1 (после строки 2: время, когда кеш был проверен на идентификатор). Writer сохраняет TW1 после выполнения удаления (после строки 9: время обновления). Читатель после выполнения строки 4 снова сохраняет TR2 (после строки 4: когда чтение завершено и обновление кеша начнется). Здесь, если TR2> TW1, он пропускает cache.put, потому что другой поток выполнил обновление после чтения кеша.

Итак, TR1 = 100, TW1 = 105, TR2 = 110 => skip cache.put.

Имеет смысл?

Answer 1

Посмотрите:

• Readers-writers lock
• RCU data structure

Answer 2

рекомендую поставить временный объект Syncronization в кэше, а extDataSrc.readData(id) выполняется. Во-первых, если 2 потока читателей запрашивают один и тот же элемент, второй поток не должен выдавать избыточный запрос, а просто ждет первого выданного запроса. Во-вторых, когда автор видит, что запрос выполняется, он может просто поместить свои данные в кеш и подать читателям. Когда readData завершен, он должен проверить, удовлетворен ли запрос автором (элемент кэша - это данные, а не временный объект) и просто отбрасывать (устаревшие) данные с extDataSrc.

И вместо того, чтобы использовать временные метки, я бы использовал номера версий в объектах данных - он работал бы, даже если есть несколько процессов, записывающих то же самое extDataSrc.