Patchouli design

# Распределенный децентрализованный кэш Patchouli

## Проблемы, которые решает данная система

Высоконагруженные системы, обрабатывающие и сохраняющие большие объемы данных, нуждаются в отказоустойчивости и распределении нагрузки. Для выполнения этих требований используются такие техники, как шардирование и репликация. Этим процедурам подвергаются микросервисы, системы управления базами данных, брокеры сообщений и системы кэширования. Среди систем кэширования есть 2 основные: **Redis** и **memcached**.

К достоинствам **Redis** можно отнести поддержку встроенных структур данных для хранения информации (списков, множеств, словарей и т.д.) и поддержку *TTL* для ключей. К сожалению, у нее также есть и существенные недостатки. К ним относятся однопоточность и сложность шардирования и репликации, нестабильность работы в кластере.

К достонствам **memcached** можно отнести то, что она легко кластеризуется и является многопоточной. Но при этом её функционал ограничен, она не поддерживает структур данных, транзакций и **TTL**. При этом решение о том, на какой ноде должно находиться значение конкретного ключа, принимает клиентская программа (или клиентская библиотека, используемая в этой программе).

При этом ни в одной из вышеупомянутых систем не поодерживается разделение данных, содержащихся под одним ключом, на несколько нод. Кроме того, ни одна из этих систем не поддерживает *пространств имен*. Таким образом, все ключи для всех клиентов хранятся в одной единой области и всегда присутствует риск того, что данные одного клиента могут быть изменены другим.

## Фичи, которые следует реализовать

- централизованное (*master-slave*) и децентрализованное (*master-master*) шардирование;

- репликация;

- пространства имен (*namespaces*);

- *TTL* на ключи и элементы структур данных;

- структуры данных: словарь, множество, которые можно шардировать (разделить на части, которые расположить на разных нодах);

- транзакции, которые исполняют серии интсрукцию как одну атомарную инструкцию.

## Методы доступа и протоколы

- **gRPC** API;

- **HTTP** API;

- **TCP** API.

## Сохранение данных на диск

Система должна уметь делать дамп данных в постоянное хранилище. Он должен осуществляться по запросу или по заданному расписанию. Должна быть возможность сделать/настроить дамп для каждого отдельного ключа, содержащегося в кэше.

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

## Реализация хранилища данных

Хранилище данных в оперативной памяти состоит из 3-ёх областей:

- область хранения ключей словарей;

- область хранения ключей неупорядоченных множеств;

- область хранения ключей, под которыми хранятся обычные атомарные значения (последовательности байтов);

Каждый ключ структуры данных и словаря имеет TTL - time to live, время жизни. Если оно отрицательно, ключ и сохранённое по нему значение никогда не удаляются из кэша. Иначе ключ находится в кэше ровно столько времени, сколько прописано в TTL.

Каждый словарь или множество состоит из определённого количества хэш-таблиц (bucket'ов), в каждой из которых хранятся ключи или элементы определённого диапазона хэшей. Каждый bucket имеет мьютекс и блокируется при конкурентном доступе к нему. Таким образом, не нужно блокировать весь словарь или множество полностью - только его часть. В какой именно bucket вставлять ключ, определяется остатком от деления хэша ключа на количество bucket'ов.

Ключ, под которым записано атомарное значение (простая байтовая последовательность), также имеет TTL и мьютекс.

## Реализация TTL

TTL реализуется с помощью таких средств языка программирования **Go**, как функция `time.AfterFunc` и объект типа `*time.Timer`, возвращаемый ей. Как только таймер срабатывает, ключ и данные, сохранённые под ним, удаляются из кэша. Сохранение таймера необходимо, чтобы можно было отменить TTL.

Таймеры для ключей словарей и множеств хранятся в bucket'ах. Таймеры для ключей с атомарными данными хранятся в отдельной области. Элемент, для которого сработал таймер TTL, блокируется и удаляется.

## Реализация пространств имён

Пространства имён необходимы, чтобы не возникало конфликтов при обращений к данным. К примеру, 2 разных микросервиса могут иметь одинаковые ключи и записывать данные в один и тот же кластер **Patchouli**. Чтобы не испортить данные друг друга, они должны создавать ключи в разных пространствах имён.

Внутренне пространства имён реализованы как префиксы перед ключами. Например, `"customers.counter"` - это ключ `"counter"`, находящийся в пространстве имён `"customers"`. Пользователю необязательно указывать пространство имён при каждом доступе к ключу - достаточно просто выбрать его в начале работы.

## Реализация шардирования и репликации

Шард - это группа узлов **Patchouli**, отвечающая за хранение определённой части данных единой коллекции. Так, например, если у нас есть множество элементов `{1, 2, 3, 4, 5, 6, 7, 8}` и кластер **Patchouli** из двух шардов, то на одном шарде могут располагаться элементы `{1, 3, 6, 8}`, а на другом - `{2, 4, 5, 7}`. Шарды необходимы для распределения нагрузки в кластере.

Шарды состоят из реплик. Реплика - это узел **Patchouli**, входящий в шард. У каждой реплики в рамках одного шарда данные одинаковые. Репликация необходима для обеспечения отказоустойчивости. Если шард состоит из нескольких реплик, то падение одной реплики не приведёт к отказу всего шарда.

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

Конфигурирование мастер-сервера происходит либо через конфигурационный **XML**-файл, либо через переменные окружения.

## Реализация транзакций

Транзакция - это серия инструкций, которая исполняется как одна единая, атомарная (в рамках паралеллизма) инструкция. Транзакции позволяют изменять данные в нескольких областях с сохранением целостности.

Как только пользователь инициирует транзакцию, все ключи и bucket'ы, затрагиваемые ей, блокируются, и после выполнения инструкций происходит разблокировка. Транзакцию можно выполнять как на мастер-сервере, так и на подчинённом сервере, но в последнем случае не будут учитываться данные на других шардах.