Инициализировать дорогостоящее значение в карте с минимальным конфликтом блокировок (C ++)

Question

Предположим, у нас есть карта, которая используется несколькими потоками. Он представляет собой узел в некоторой иерархической структуре (скажем, каталог в файловой системе), который хранится на диске. Построение значения дорого как во времени, так и в памяти. Это классическая проблема «инициализации по требованию», с изюминкой: мы инициализируем значения на карте, когда есть запрос поиска, но мы не хотим блокировать карту whole , пока мы делаем это для того, чтобы другие потоки имели доступ к уже созданным значениям. В этом приложении поиск существующих значений будет намного более распространенным, чем несуществующие.

Попытка 1 : захватить блокировку записи на карте, проверить наличие ключа, вернуть, если имеется, в противном случае построить значение, вставить в карту.

Оценка : Это предотвращает доступ других потоков к карте во время создания значения. Поскольку чтения очень распространены и очень быстрые, это проявится как ужасный скачок задержки: не хорошо.

Попытка 2 : захватить блокировку чтения на карте, проверить наличие ключа, вернуть, если имеется, в противном случае снять блокировку чтения, создать значение, захватить блокировку записи, проверить наличие, если нет, вставить карту, если она есть, удалить вновь созданное значение.

Оценка : Теперь мы не несем скачок в задержке чтения, но мы можем закончить ненужным построением нескольких представлений в памяти одного и того же значения (когда несколько потоков пытаются найти один и тот же Неограниченное значение одновременно). Проблема в том, что мы не хотим этого: эти значения действительно дороги в создании. Кроме того, они могут начать запускать события или выполнять операции ввода-вывода, что означает, что теперь нам приходится иметь дело с проектом, который позволяет существовать эфемерным, но в то же время тяжелым экземплярам Value: дополнительной головной боли лучше избегать.

Попытка 3 : использовать двухуровневые замки. Захватить блокировку чтения на карте, ключ поиска, вернуть, если имеется, в противном случае снять блокировку чтения на карте, захватить блокировку записи на карте, проверить заполнитель, захватить блокировку чтения заполнителя, если имеется, в противном случае создать заполнитель, захватить блокировку записи, вставить на карту, снимите блокировку записи на карте, создайте значение, замените заполнитель на значение, снимите блокировку записи с заполнителя.

Оценка : Вставка заполнителя в карту при построении значения гарантирует, что только один поток попытается его выполнить, что решает проблемы Попытки 2. Однако этот дизайн оставляет открытым вопрос: что форма этот заполнитель должен взять? Ответ не тривиален. Во-первых, если он содержит блокировку и потоки ожидают его, становится трудно его удалить (Как вы знаете, что никто не удерживает блокировку заполнителя? Вы можете захватить ее, конечно, но тогда вы держите ее так , опять же, вы не можете удалить его). Во-вторых, могут быть поиски ключей, для которых не существует значения на диске. Если мы вставим заполнитель для каждой попытки поиска (даже для тех, которые в конечном итоге потерпят неудачу), то кто будет их очищать? Наконец, с двумя уровнями блокировок код становится довольно уродливым: сначала мы берем блокировку чтения, проверяем, затем получаем блокировку записи, перепроверяем, и нам нужно сделать это как на уровне карты, так и на уровне отдельных заполнителей (легко чтобы создать тупики, я могу это засвидетельствовать).

Этот маленький ребенок продолжает появляться, и я не могу найти элегантное решение. Попытка 3 - самая близкая мне попытка удовлетворить мои условия производительности, но она уродлива и подвержена ошибкам, когда вы приступаете к грязным деталям. Буду очень признателен за любые идеи или предложения.

Answer 1

Похоже, цель состоит в том, чтобы сделать возможным быстрое выполнение поиска существующих объектов за счет создания новых объектов.Вот решение, которое сделает это за вас.

Вам нужно хранить две карты в памяти, обе в конечном итоге будут иметь одинаковое содержимое.Вам также понадобится мьютекс для записи и чтения: - curReadMap * - curWriteMap * - writeMutex - readMutex

Эти два указателя важны, мы их поменяем местами.Теперь, чтобы прочитать имеющееся у вас значение (грубый псевдокод):

  lock( readMutex )
  value = checkValueIn( curReadMap, key )
  unlock()
  if( value ) return value

Если вы не найдете значение, вы можете ввести секцию записи

  lock( writeMutex )
  value = checkValueIn( curWriteMap, key ) //double check now
  if( value ) return value

  value = createNewValue()
  putIn( curWriteMap, key, value )

  lock( readMutex )
  swap( curWriteMap, curReadMap )
  unlock( readMutex )

  putIn( curWriteMap, key, value ) //update old map now as well
  unlock( writeMutex )

В этой схемеТипичный читатель несет только стоимость блокировки одного мьютекса и поиска на карте.Они только несут стоимость создания, если объект не найден.Замена указателей карты также обеспечивает минимальное время блокировки readMutex.

Answer 2

Ваша проблема со схемой # 3 заключается в том, как отслеживать объекты-заполнители.Если вы готовы отказаться от некоторого параллелизма, вы можете сделать это проще - выделите одну блокировку, которая будет сериализовать создание значений для каждой карты.Затем идет:

lookup(map, key):
  1. Grab read lock on map
  2. lookup key in map, unlock & return if present
  3. grab lock on map.create_serializer
  4. lookup key in map, unlock & return if present
  5. release read lock on map
  6. create value for key
  7. grab write lock on map
  8. insert (key,value) into map
  9. release write lock on map
 10. release lock on map.create_serializer

create_serializer гарантирует, что не более одного потока создает объекты для размещения на этой карте одновременно.Несколько потоков, одновременно ищущих один и тот же отсутствующий ключ, будут сериализованы на шаге 3 - первый продолжит строить значение, а остальные найдут это значение, уже встроенное на шаге 4.

Это будет (излишне)сериализовать различные значения создания для одной и той же карты, но в остальном удовлетворяет вашим критериям.