2017-highload-kv

Курсовой проект 2017 года курса "Проектирование высоконагруженных систем" в Технополис.

Этап 1. HTTP API + хранилище (deadline 2017-10-10)

Fork

Форкните проект, склонируйте и добавьте upstream:

$ git clone git@github.com:<username>/2017-highload-kv.git
Cloning into '2017-highload-kv'...
remote: Counting objects: 34, done.
remote: Compressing objects: 100% (24/24), done.
remote: Total 34 (delta 2), reused 34 (delta 2), pack-reused 0
Receiving objects: 100% (34/34), 11.43 KiB | 3.81 MiB/s, done.
Resolving deltas: 100% (2/2), done.
$ git remote add upstream git@github.com:polis-mail-ru/2017-highload-kv.git
$ git fetch upstream
From github.com:polis-mail-ru/2017-highload-kv
 * [new branch]      master     -> upstream/master

Make

Так можно запустить тесты:

$ gradle test

А вот так -- сервер:

$ gradle run

Develop

Откройте в IDE -- IntelliJ IDEA Community Edition нам будет достаточно.

ВНИМАНИЕ! При запуске тестов или сервера в IDE необходимо передавать Java опцию -Xmx1g.

В своём Java package ru.mail.polis.<username> реализуйте интерфейс KVService и поддержите следующий HTTP REST API протокол:

HTTP GET /v0/entity?id=<ID> -- получить данные по ключу <ID>. Возвращает 200 OK и данные или 404 Not Found.
HTTP PUT /v0/entity?id=<ID> -- создать/перезаписать (upsert) данные по ключу <ID>. Возвращает 201 Created.
HTTP DELETE /v0/entity?id=<ID> -- удалить данные по ключу <ID>. Возвращает 202 Accepted.

Возвращайте реализацию интерфейса в KVServiceFactory.

Продолжайте запускать тесты и исправлять ошибки, не забывая подтягивать новые тесты и фиксы из upstream. Если заметите ошибку в upstream, заводите баг и присылайте pull request ;)

Report

Когда всё будет готово, присылайте pull request со своей реализацией на review. Не забывайте отвечать на комментарии в PR и исправлять замечания!

Этап 2. Кластер (deadline 2017-11-07)

Реализуем поддержку кластерных конфигураций, состоящих из нескольких узлов, взаимодействующих друг с другом через реализованный HTTP API. Для этого в KVServiceFactory передаётся "топология", представленная в виде множества координат всех узлов кластера в формате http://<host>:<port>.

Кроме того, HTTP API расширяется query-параметром replicas, содержащим количество узлов, которые должны подтвердить операцию, чтобы она считалась выполненной успешно. Значение параметра replicas указывается в формате ack/from, где:

ack -- сколько ответов нужно получить
from -- от какого количества узлов

Таким образом, теперь узлы должны поддерживать расширенный протокол (совместимый с предыдущей версией):

HTTP GET /v0/entity?id=<ID>[&replicas=ack/from] -- получить данные по ключу <ID>. Возвращает:
- 200 OK и данные, если ответили хотя бы ack из from реплик
- 404 Not Found, если ни одна из ack реплик, вернувших ответ, не содержит данные (либо данные удалены хотя бы на одной из ack ответивших реплик)
- 504 Not Enough Replicas, если не получили 200/404 от ack реплик из всего множества from реплик
HTTP PUT /v0/entity?id=<ID>[&replicas=ack/from] -- создать/перезаписать (upsert) данные по ключу <ID>. Возвращает:
- 201 Created, если хотя бы ack из from реплик подтвердили операцию
- 504 Not Enough Replicas, если не набралось ack подтверждений из всего множества from реплик
HTTP DELETE /v0/entity?id=<ID>[&replicas=ack/from] -- удалить данные по ключу <ID>. Возвращает:
- 202 Accepted, если хотя бы ack из from реплик подтвердили операцию
- 504 Not Enough Replicas, если не набралось ack подтверждений из всего множества from реплик

Если параметр replicas не указан, то в качества ack используется значение по умолчанию, равное кворуму от количества узлов в кластере, а from равен общему количеству узлов в кластере, например:

1/1 для кластера из одного узла
2/2 для кластера из двух узлов
2/3 для кластера из трёх узлов
3/4 для кластера из четырёх узлов
3/5 для кластера из пяти узлов

Выбор узлов-реплик (множества from) для каждого <ID> является детерминированным:

Множество узлов-реплик для фиксированного ID и меньшего значения from является строгим подмножеством для большего значения from
При PUT не сохраняется больше копий данных, чем указано в from

Фактически, с помощью параметра replicas клиент выбирает, сколько копий данных он хочет хранить, а также уровень консистентности при выполнении последовательности операций для одного ID.

Таким образом, например, обеспечиваются следующие инварианты (список не исчерпывающий):

GET с 1/2 всегда вернёт данные, сохранённые с помощью PUT с 2/2 (даже при недоступности одной реплики при GET)
GET с 2/3 всегда вернёт данные, сохранённые с помощью PUT с 2/3 (даже при недоступности одной реплики при GET)
GET с 1/2 "увидит" результат DELETE с 2/2 (даже при недоступности одной реплики при GET)
GET с 2/3 "увидит" результат DELETE с 2/3 (даже при недоступности одной реплики при GET)
GET с 1/2 может не "увидеть" результат PUT с 1/2
GET с 1/3 может не "увидеть" результат PUT с 2/3
GET с 1/2 может вернуть данные несмотря на предшествующий DELETE с 1/2
GET с 1/3 может вернуть данные несмотря на предшествующий DELETE с 2/3
GET с ack равным quorum(from) "увидит" результат PUT/DELETE с ack равным quorum(from) даже при недоступности < quorum(from) реплик

Так же как и на Этапе 1 присылайте pull request со своей реализацией поддержки кластерной конфигурации на review. Набор тестов будет расширяться, поэтому не забывайте подмёрдживать upstream и реагировать на замечания.

Этап 3. Нагрузочное тестирование и оптимизация (deadline 2017-12-05)

TBD

Bonus (deadline 2017-12-19)

Фичи, которые позволяют получить дополнительные баллы:

10М ключей: нетривиальная реализация хранения данных
Consistent Hashing: распределение данных между узлами устойчивое к сбоям
Streaming: работоспособность при значениях больше 1 ГБ (и -Xmx1g)
Conflict resolution: отметки времени Лампорта или векторные часы
Expire: возможность указания времени жизни записей
Server-side processing: трансформация данных с помощью скрипта, запускаемого на узлах кластера через API
Предложите своё

Если решите реализовать что-то бонусное, обязательно сначала обсудите это с преподавателем.

MrOlolo/2017-highload-kv