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

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. Если в то же время средство записи обновляет тот же идентификатор, возможно, что перед тем, как средство записи выполнит свою работу, средство чтения считывает устаревшие данные и получает задержку в возврате из вызова extDataSrc. Тем временем Writer выполняет cache.remove(id) (нет данных в кэше, поэтому ничего не удаляет) и возвращает. Затем читатель выполняет cache.put (id). Я думал, что этого можно избежать, используя временные метки, так что, когда читатель проверяет кэш, он сохраняет временную метку TR1 (после строки 2: время, когда кэш проверялся на id). Writer сохраняет 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,