Репозиторий с заданием по курсам:
- Теория распределенного хранения и обработки данных
- Высокопроизводительная и распределенная обработка данных
Вопросы задавать в Slack.
Целью практической части нашего курса является создание распределённого key-value хранилища (далее просто хранилище).
Replication Factor: 3, quorum: 2, язык разработки: go, для взаимодействия между компонентами используется gRPC.
Хранилище состоит из трех основных компонент:
- Node -- узлы, на которых хранятся данные
- Frontend -- точка входа в хранилище
- Router -- узел, в котором хранится схема хранилища
Предполагается, что хранилище будет запускаться в конфигурации, содержащей не менее трёх Node, один Router, и один или несколько Frontend.
В качестве ключа используется uint32, в качестве значения -- произвольный набор байт.
Основной документацией к хранилищу являются тесты, содержащиеся в репозитории и godoc (node, router, frontend).
Хранилище позволяет выполнить следующие операции:
- Put(key, value) -- добавление элемента
- Delete(key) -- удаление элемента
- Get(key) -- получение элемента
Рассмотрим подробнее эти операции.
Frontend выполняет следующие действия:
- Отправляет запрос NodesFind(key) в Router.
- Параллельно кладет значение value по ключу key в каждый из node, которые вернул запрос NodesFor(key, nodes).
Если NodesFor(key) возвращает ошибку, то ошибка немедленно возвращается клиенту. Если NodesFor(key) прошел успешно, то результат возвращается клиенту после того, как завершатся все запросы из шага 2.
Delete работает по аналогии с Put.
Frontend выполняет следующие действия:
- Отправляет запрос NodesFind(key) в Router.
- Параллельно отправляет Delete(key) в каждый из node, которые вернул запрос NodesFor(key, nodes).
Если NodesFor(key) возвращает ошибку, то ошибка немедленно возвращается клиенту. Если NodesFor(key) прошел успешно, то результат возвращается клиенту после того, как завершатся все запросы из шага 2.
При первом Get запросе Frontend отправляет запрос List() в Router для получения списка обслуживаемых Nodes. Если List() запрос возвращает ошибку, то запрос должен быть повторен через специальный таймаут. До момента успешного завершения List() запроса в Router ни один Get() не может быть выполнен.
Далее предполагается, что List() запрос выполнен, и во Frontend уже сохранен список обслуживаемых Nodes.
Frontend выполняет следующие действия для выполнения запроса Get(key):
- Вызывает метод NodesFind(key, nodes) -- локальный запрос без похода в Router (nodes -- список обслуживаемых Nodes).
- Параллельно отправляет запрос Get(key) в каждый из Node, которые вернул вызов метода NodesFor(key).
Результат возвращается клиенту, как только два из запросов в Node завершатся с одинаковым результатом, либо после того, как все три запроса завершатся с разным результатом.
Для вычисления узлов, на которых должны хранится данные по данному ключу key используется разновидность метода HRW.
Для каждой пары key, node (node -- элемент nodes) вычисляется хэш.
После этого nodes сортируется в соответствии со значением хэш (в убывающем порядке). Если для различных пар key,node значение хэшей совпало, то данные пары сортируются в соответствии с лексикографическим порядком node (в убывающем порядке).
Каждый Node отправляет специальные запросы heartbeats к Router через равные интервалы времени. Если какой-либо Node не отправлял запросы в течении значения, задаваемого в конфигурации Router, то данный Node считается недоступным.
Необходимо реализовать методы помеченные комментарием TODO: implement.
Запрещается удалять/изменять существующий код, кроме методов, помеченных комментарием TODO: implement.
Разрешается добавление кода в существующие файлы и добавление новых файлов в репозиторий.
Задание состоит из трех частей.
Необходимым условием сдачи части является прохождение всех тестов относящихся к этой части.
Список частей (в скобочках команда для запуска тестов):
- Node (
make test-node) - Router (
make test-router) - Frontend + Integration Tests (
make test-fe && make test-integration)
Количество частей, сданных студентом влияет на финальную оценку за курс.
Если сдана первая часть, то максимальная оценка, на которую претендует студент -- уд.
Если сданы первые две части, то максимальная оценка, на которую претендует студент -- хор.
Если сданы все части, то студент претендует на оценку отл.
Сдача первой части является необходимым и достаточным условием допуска к экзамену.
Для того чтобы сдать задание, нужно отправить Pull Request.
Первичное тестирование производится автоматически с использованием системы Travis CI.
Описание Pull Request должно содержать фамилию, имя, номер группы студента, сдающего задание.
После проверки преподавателем Pull Request будет присвоена одна из меток (label):
- ok - все хорошо
- refactor - необходим рефакторинг
- error - есть ошибки