Skip to content

Latest commit

 

History

History
78 lines (74 loc) · 8.95 KB

TASK3.md

File metadata and controls

78 lines (74 loc) · 8.95 KB
Raw

Задание 3

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

  • списка узлов-реплик List[KeyValueApi], к ним происходят обращения операций записи и чтения (RF = Replica Factor = List[KeyValueApi].size > 0)
  • timeout - максимальное время выполнения операции с KeyValueApi
  • write consistency level (WCL) - достаточное число нод, ответивших OK за время < timeout для безошибочной записи. Если обнаруживается ошибка, она возвращается клиенту.
  • read consistency level (RCL) - достаточное число нод, вернувших данные за время < timeout для безошибочного чтения. Важно, что ноды могут вернуть разные данные, тем самым обнаружив конфликт в них, координатор за счет политики разрешения конфликтов должен выбрать ту версию данных, которую он считает наиболее достоверной.

Требуется:

  • синхронизировать {your-awesome-team-fork-repo} c upstream для получения обновленных файлов https://help.github .com/articles/syncing-a-fork/, устранить конфликты в результате merge
  • сделать бранч csc-bdse-task3 где будет находиться сдаваемый материал для третьего задания
  • создать реализацию KeyValueApi, включающую:
    • получения и использование конфигурации - списка адресов нод Persistent Storage Unit (List[KeyValueApi]), timeout, WCL, RCL
    • использования специальной структуры для оборачивания сообщения клиента и записи его в нижележащие хранилища. По сути, необходимо добавить в хранимое сообщение время записи (предполагается, что используется время операции на стороне координатора) и флаг что значение удалено (см. операцию удаления ниже), то есть структуру можно описать так:
public class RecordWithTimestamp {
    private byte[] payload;
    private boolean isDeleted; // mark value as tombstone, see later
    private long timestamp;
    ...
 }
  • реализованную операцию записи put, отправляющую запросы на все List[KeyValueApi], отвечающую клиенту без ошибки если запись была произведена на не менее WCL нод, иначе - ошибка. Записываем RecordWithTimestamp с установленным временем записи и isDeleted = false;
  • реализованные операции получения get и getKeys: запросы отправляются на все List[KeyValueApi], ответ от более чем RCL нод считается безошибочным, возможно, требующим разрешения конфликтов. Если обнаружен конфликт, то он разрешается через политику:
public interface ConflictResolver {

    RecordWithTimestamp resolve(in: Set<RecordWithTimestamp>);
    Set<String> resolveKeys(in: Set<Set<String>>);
 }

предполагается, что при конфликтах данных будет выбрано наиболее поздно записанное значение (Last Write Wins), при совпадении максимального времени у нескольких нод - значение, присутствующее у большинства, если отсутствует большинство - детерминированный алгоритм выбора значения (например, по старшинству номера ноды). Важно, что в результате мы можем получить структуру с tombstone (isDeleted = true), что аналогично отсутствию ключа. Для
списков ключей (resolveKeys) объединение множеств является вполне корректным вариантом.

  • реализованную операцию удаления записи delete. Просто удалять ключ нельзя: представим кластер из 3 нод, WCL = 2, RCL = 2; честное удаление произошло на нодах 1 и 2, но не на 3, далее чтение происходит с 2 и 3 - в ответе одной ноды есть значение, другой - нет, невозможно понять что было ранее - установка значения или его удаление. Поэтому операция удаления должна реализовываться через запись структуры RecordWithTimestamp c isDeleted = true и временем (то есть фактически использовать модифицированную операцию put)
  • реализованные операции получения информации о кластере и выполнения команд. По сути получение информации = объединение таковой с нижележащих нод, обработка команд = пересылка таковых нижележащим нодам.
  • создать расширение KeyValueApiHttpClient для работы со списком нод-координаторов. Клиент работает со списком равнозначных нод-координаторов, если происходит ошибка связи с координатором 1, то перация исполняется на координаторе 2 и далее
  • создать тесты для ConflictResolver
  • создать интеграционные тесты для чтения, записи, удаления на кластере (предполагается поднимаются в контейнерах) в конфигурациях:
    • {RF = 1, WCL = 1, RCL = 1}, фактически повтор KeyValueApiHttpClientTest, KeyValueApiHttpClientNonFunctionalTest c одной нодой
    • {RF = 3, WCL = 3, RCL = 1}, одна нода отключается в ходе тестирования
    • {RF = 3, WCL = 2, RCL = 3}, одна нода отключается в ходе тестирования
    • {RF = 5, WCL = 3, RCL = 3}, одна, две ноды отключаются в ходе тестирования
  • описать в INSTALL_TASK3.md специфику сборки приложений и запуска интеграционных тестов
  • описать в README_TASK3.md что было реализовано, описание проблем, не решенных в коде и требующих дальнейшего рассмотрения, неявных моментов. Обязательно добавить название и список участников команды.
  • прислать PR {your-awesome-team-fork-repo}/csc-bdse-task3 => {your-awesome-team-fork-repo}/master (добавить alesavin, dormidon, semkagtn, 747mmHg в ревьюеры)
  • добавить ссылку на PR в топик задания 3 курса на https://compscicenter.ru

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

  • реализуется функциональность восстановления некорректных данных при чтении (read repair). Если данные различаются на разных нодах и разрешение конфликтов выбрало корректную версию, то неплохо бы асинхронно устранить конфликты, записав значение на ноды, где есть несоответствие.