Распределенный кэш. Часть 3.

Первая часть тут

Вторая часть тут.

В результате шардинга данные разбиваются на части (шарды) и распределяются по разным серверам.

Более того, если нужно достичь High Availability, можно создавать реплики шардов (копии данных в шарде). Это позволяет сохранять доступ к данным, даже если сервер, который содержит исходный шард, недоступен. В таком случае его реплика, которая находится на другом сервере все еще будет доступна. Эта также позволяет достичь большой производительности, если у нас приложение выполняет много параллельных чтений. При наличии реплик, чтения могут выполнятся параллельно из разных реплик данного шарда.

Шарды и их реплики распределяются по разным серверам кластера.

Стуктура данных для хранения данных внутри каждого шарда или реплики.

Нам нужно обеспечить хранение данных по типу ключ-значение (key-value) в нашем кэше. А также обеспечить быстрый доступ к данных. Операции get(key) и put(key, value) должны работать быстро и за константное время (O(1)). Поэтому подходящей структурой данной является Хэш-таблица.

Кроме того, нам нужно реализовать Eviction Policies, например LRU (least recently used). Т.е. нужно удалять данные, которые не использовались дольше всего. Для этого нам нужно ранжировать/упорядочить данные в кэше по времени доступа. Для этого подходит двусвязный список. В начале такого двусвязного списка у нас будут данные, которые использовались недавно. А в хвосте списка - те, которые использовались давно. Тогда данные будут удалятся из хвоста списка. Нам нужно объеденить эти две структуры данных в одну (Хэш-таблицу и двусвязный список). В Хэш-таблице будем хранить данные по типу ключ-значение, при этом значения будут дополнительно образовывать двусвязный список. При доступе или модификации данных мы будем модифицировать Хэш-таблицу, а также перемещать значение в начало двусвязного списка, т.к. эти данные только что были использованы. Тогда мы гарантируем, что в начале списка у нас будут данные, которые использовались недавно, а в хвосте списка - которые давно не использовались и могут быть удалены.