Запись и чтение сообщений без блокировки в многопоточном приложении
Имеется приложение многопоточное. Каждый поток получает одни и те же данные. Это сообщения, и у каждого сообщения есть свой айди. Один поток получает их чуть быстрее, а другой - чуть медленнее. Необходимо сохранять сообщения из разных потоков без блокировок, брать нужно только самое первое сообщение для данного айди. Известно, что все потоки получают сообщения последовательно, айди всегда идут строго по возрастанию и всегда начиная с айди, равного нулю.
Вопрос - как это можно реализовать без блокировок?
Вопрос с собеседования по С++ в компанию, которая работает в сфере High Frequency Trading
Ответы (1 шт):
Ну например Facebook/folly AtomicHashMap.
Этот контейнер повторяет во многом семантику std::map, так что аналогично std::map вы можете использовать в нем метод insert, который будет либо помещать новый айдишник в контейнер, либо возвращать результат, показывающий, что айдишник в контейнере уже имеется.
Идея, заложенная в этот контейнер называется общим термином Lock-Free.
Дело в том, что традиционные блокировки на мьютексах слишком дороги по времени, особенно на всевозможных системах с NUMA и подобных.
Поэтому, на передный план выходят атомарные операции с переменными (надеюсь, из названия понятно, что это такое), а также операции с семантикой Compare-And-Swap (Атомарно сравнить значение в памяти с аргументом A и в случае совпадения, заменить его аргументом B)
Внутри AtomicHashMap сидит как раз такая сложная конструкция-индекс, для модификации которой и используются эти примитивы.
Если еще подумать над вашей задачей, может оказаться, что ее можно решить и без сторонней помощи, опираясь как раз на факт монотонного роста айдишников сообщений и операцию CAS