TASK4.md

Задание 4

Необходимо реализовать KeyValueApi с функцией распределения хранимых пар ключ-значение по кластеру.
Подобное разделение называется партиционированием: все множество ключей делится на части - партиции, для хранилища в каждый момент известно на каком из составляющих его Key-value Persistent Storage Unit находится часть. Составляющие партицированный кластер ноды принято называть шардами, партиции иногда называют виртуальными нодами. Последнее происходит если число партиций сильно больше числа шардов, тогда один шард обрабатывает множество партиций. В данном задании, для упрощения, предполагается что шард обслуживает одну партицию.

Для облегчения задачи поставляется интерфейс Partitioner, описывающий преобразование ключа в партицию (для данного задания это имя шарда), и три его реализации:

• FirstLetterPartitioner, на основе интервалов начальных символов ключа
• ModNPartitioner, на основе хеш-кода ключа и деления по модулю
• ConsistentHashMd5Partitioner, на основе консистентного хеширования

Партицированный KeyValueApi, который требуется реализовать, имеет статическую конфигурацию:

• список шардов List[KeyValueApi], составляющих кластер
• timeout - максимальное время выполнения операции с шардом
• partitioner - алгоритм определения партиции-шарда из ключа (один из указанных выше)

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

• cluster1: PartitionedKeyValueApi(Set(node0, node1, node2), timeout = 3s, partitioner = ModNPartitioner)
• cluster2: PartitionedKeyValueApi(Set(node0, node2), timeout = 3s, partitioner = ModNPartitioner)

Кластер с номером 2 моделирует отказ шарда node1 в кластере с номером 1, при этом работоспособность node1 не нарушается . В cluster2 ключи, ранее принадлежавшие node1, должны быть перераспределены между node0 и node2. Важной составляющей практического задания является проверка в тестах количества ключей, перемещенных в результате "удаления" нод в кластере (в идеальном случае перемещается не более K/N ключей, где K - общее их число, N - число нод). Для практического задания значения в парах key-value не играют существенной роли, рекомендуется вариант когда в значении содержатся байтовое представление ключа.

Требуется:

• синхронизировать {your-awesome-team-fork-repo} c upstream для получения обновленных файлов https://help.github.com/articles/syncing-a-fork/, устранить конфликты в результате merge
• сделать бранч csc-bdse-task4, где будет находиться сдаваемый материал для четвертого задания
• создать реализацию партицированного KeyValueApi, включающую:
  • получения и использование конфигурации: List[KeyValueApi], timeout, partitioner
  • координатор в виде надстройки для каждой из нод с функцией маршрутизации запросов в шарды. Операции записи, чтения и удаления по ключу производятся с шардом соотнесенным с ключом. Операция получения списка ключей производит обращение ко всем шардам и объединяет результат. Операции получения информации и выполнения команд выполняют, соответственно, опрос нод кластера и отправку команды на соотнесенную с командой ноду.
  • HTTP API партицированного координатора
• создать расширение KeyValueApiHttpClient для работы со списком нод-координаторов. Клиент работает со списком равнозначных нод, если происходит ошибка связи с координатором 1, то операция исполняется на координаторе 2 и далее. Если аналогичный клиент уже реализован в задании 3, повтороной реализации не требуется.
• создать интеграционные тесты (наследуются от AbstractPartitionedKeyValueApiHttpClientTest) партицированных кластеров. В тестах получаются число потерянных в результате ребалансировки ключей и число неудаленных ключей с отказавшего шарда, эти числа сравниваются в соотношении с общим числом ключей, подсказки о границах соотношений можно найти в тестах Partitioner'ов. Предполагается, что кластера для тестов поднимаются в контейнерах, необходимо рассмотреть ситуации:
  • cluster1: PartitionedKeyValueApi(Set(node0, node1, node2), timeout = 3s, partitioner = FirstLetterPartitioner), cluster2: PartitionedKeyValueApi(Set(node0, node2), timeout = 3s, partitioner = FirstLetterPartitioner), моделирует отключение одной ноды при партиционировании по начальному символу ключа
  • cluster1: PartitionedKeyValueApi(Set(node0, node1, node2, node3, node4), timeout = 3s, partitioner = ModNPartitioner), cluster2: PartitionedKeyValueApi(Set(node0, node1, node2), timeout = 3s, partitioner = ModNPartitioner), моделирует отключение двух нод при партиционировании по modN(хеш-код ключа)
  • cluster1: PartitionedKeyValueApi(Set(node0, node1, node2), timeout = 3s, partitioner = FirstLetterPartitioner), cluster2: PartitionedKeyValueApi(Set(node0, node1, node2), timeout = 3s, partitioner = ModNPartitioner) моделирует смену схемы партиционирования
  • cluster1: PartitionedKeyValueApi(Set(node0, node1, node2), timeout = 3s, partitioner = ConsistentHashMd5Partitioner), cluster2: PartitionedKeyValueApi(Set(node0, node2), timeout = 3s, partitioner = ConsistentHashMd5Partitioner), моделирует отключение одной ноды при консистентном хешировании
• описать в INSTALL_TASK4.md специфику сборки приложений и запуска интеграционных тестов
• описать в README_TASK4.md что было реализовано, описание проблем, не решенных в коде и требующих дальнейшего рассмотрения, неявных моментов. Обязательно добавить название и список участников команды.
• прислать PR {your-awesome-team-fork-repo}/csc-bdse-task4 => {your-awesome-team-fork-repo}/master (добавить alesavin, dormidon, semkagtn, 747mmHg в ревьюеры)
• добавить ссылку на PR в топик задания 4 курса на https://compscicenter.ru

Дополнительно:

• реализация партицированного контроллера, работающего над реплицированными контроллерами из задания 3. Предполагается репликация самих партиций.