“Тонкая блокировка” в хэш-таблицах

#алгоритм #многопоточность

В чем суть "тонкой блокировки" в хэш-таблицах и как её реализовать?
    

Ответы

Ответ 1

Суть в том, что с каждым входом (цепочкой синонимов хэш-функции) связывают свой mutex. 

Реализация на Си тривиальна:

struct hash_entry {
   pthread_mutex_t mutex;
   struct hash_item *list; // если, например, используете односвязный список
};


При создании таблицы

struct hash_entry table[HASH_SIZE];


устанавливаете table[i].list в NULL и вызываете pthread_mutex_init(&table[i].mutex,
0); (если нет особых требований к атрибутам мьютекса).



Update

После комментария от @VladD решил добавить немного рассуждений на тему параллельной
работы с хэш-таблицей.

В принципе для действий, затрагивающих всю таблицу, можно добавить rwlock (см., например,
man pthread_rwlock_init и др. man для pthread_rwlock...). Тогда функции, требующие
"тонкой блокировки" будут вызывать

  pthread_rwlock_t tablock;
  ...
  pthread_rwlock_rdlock(&tablock); // совместная блокировка таблицы
  int i = hash_func(key, keylen) % HASH_SIZE;
  pthread_mutex_lock(&table[i].mutex); // блокировка цепочки
  // действия с цепочкой синонимов
  ... 
  pthread_mutex_unlock(&table[i].mutex);
  pthread_rwlock_unlock(&tablock);


а функции, которые затрагивают всю таблицу 

  pthread_rwlock_wrlock(&tablock); // монопольная блокировка таблицы
  // действия с таблицей
  ... 
  pthread_rwlock_unlock(&tablock);


т.е. получаем схему писатель-читатели с вложенной монопольной блокировкой цепочек
коллизий.

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

Реально, если не удается вообще уйти (а к этому всегда надо стремиться (KISS-принцип))
от многопоточной работы  с таблицей, выгодней просто блокировать ее всю, независимо
от вида операций, поскольку обычно цепочки синонимов короткие и большинство операций
с элементами таблицы весьма быстрые.

Еще одним доводом в пользу такого подхода может быть тривиальная экономия памяти
(размер объекта pthread_mutex_t 40 байт на 64-bit X_86), которая (как это ни странно,
на первый взгляд) часто приводит к ускорению программы (поскольку доступ к памяти может
быть раз в 100 медленней доступа к кэшу).

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