2019-highload-dht

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

Этап 1. HTTP + storage (deadline 2019-10-05)

Fork

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

$ git clone git@github.com:<username>/2019-highload-dht.git
Cloning into '2019-highload-dht'...
...
$ git remote add upstream git@github.com:polis-mail-ru/2019-highload-dht.git
$ git fetch upstream
From github.com:polis-mail-ru/2019-highload-dht
 * [new branch]      master     -> upstream/master

Make

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

$ gradle test

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

$ gradle run

Develop

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

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

В своём Java package ru.mail.polis.service.<username> реализуйте интерфейс Service и поддержите следующий 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.

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

Реализацию DAO берём из весеннего курса 2019-db-lsm, либо запиливаем adapter к уже готовой реализации LSM с биндингами на Java (например, RocksDB, LevelDB или любой другой).

Проведите нагрузочное тестирование с помощью wrk в одно соединение. Почему не curl/F5, можно узнать здесь и здесь.

Попрофилируйте (CPU и alloc) под нагрузкой с помощью async-profiler и проанализируйте результаты.

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

Report

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

Этап 2. Многопоточность (deadline 2019-10-12)

Обеспечьте потокобезопасность реализации DAO с помощью synchronized, а лучше -- с использованием примитивов java.util.concurrent.*. Прокачаться можно с руководством Java Concurrency in Practice.

Сконфигурируйте HTTP сервер, чтобы он обрабатывал запросы с помощью пула из нескольких потоков.

Проведите нагрузочное тестирование с помощью wrk в несколько соединений.

Отпрофилируйте приложение (CPU, alloc и lock) под нагрузкой с помощью async-profiler и проанализируйте результаты.

Report

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

Этап 3. Асинхронный сервер (deadline 2019-10-19)

Реализуйте асинхронный HTTP сервер на основе one-nio.

Проведите нагрузочное тестирование с помощью wrk в несколько соединений с разными видами запросов.

Попрофилируйте приложение (CPU, alloc и lock) под нагрузкой с помощью async-profiler и проанализируйте результаты.

Реализуйте получение диапазона данных с помощью HTTP GET /v0/entities?start=<ID>[&end=<ID>], который возвращает:

• Статус код 200 OK
• Возможно пустой отсортированный (по ключу) набор ключей и значений в диапазоне ключей от обязательного start (включая) до опционального end (не включая)
• Использует Chunked transfer encoding
• Чанки в формате <key>\n<value>

Диапазон должен отдаваться в потоковом режиме без формирования всего ответа в памяти.

Report

Когда всё будет готово, присылайте pull request с изменениями, результатами нагрузочного тестирования и профилирования, а также анализом результатом по сравнению с предыдущей (блокирующей) версией.

Этап 4. Шардирование (deadline 2019-10-26)

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

gradle run теперь стартует Cluster из трёх нод.

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

Реализуйте один из алгоритмов распределения данных между узлами, например, consistent hashing и rendezvous hashing.

Report

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

Этап 5. Репликация (deadline 2019-11-09)

Реализуем поддержку хранения нескольких реплик данных в кластере для обеспечения отказоустойчивости.

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) реплик

Report

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

Этап 6. Асинхронный клиент (deadline 2019-11-16)

Переключаем внутреннее взаимодействие узлов на асинхронный java.net.http.HttpClient. Параллельно отправляем запросы репликам и собираем подтверждения на CompletableFuture.

Проведите нагрузочное тестирование с помощью wrk в несколько соединений.

Отпрофилируйте приложение (CPU, alloc и lock) под нагрузкой с помощью async-profiler и сравните результаты latency и профилирования по сравнению с неасинхронной версией.

Присылайте pull request со своей реализацией на review.

Этап 7. Нагрузочное тестирование (deadline 2019-11-23)

Освоим Яндекс.Танк.

Пишем простой генератор патронов:

• Лента с PUTами с уникальными ключами
• Лента с PUTами с частичной перезаписью ключей (вероятность 10%)
• Лента с GETами существующих ключей с равномерным распределением (стреляем по наполненной БД)
• То же самое, но со смещением распределения GETов к недавно добавленным ключам (частый случай на практике)
• Наконец, лента со смешанной нагрузкой с 50% PUTы новых ключей и 50% GETы существующих ключей (равномерное распределение)

Генерируем патроны для стрельбы не меньше 5 мин (не забываем про JIT и прогрев JVM процесса).

Логинимся и настраиваем клиент. Не забываем получить и вписать свой токен для overload, а также указать свой IP машины в load.yaml, чтобы танк смог получить доступ к API. Возможно, потребуется отключить логгирование входящих запросов на нодах, чтобы выжать из кластера максимум.

Перезапускаем кластер из трёх нод с помощью ./gradlew run перед каждой стрельбой. Обстреливаем разными лентами на плавно возрастающей линейной нагрузке, чтобы найти точку разладки. После этого стреляем разными лентами постоянной нагрузкой (line + const) на 30% ниже точки разладки, чтобы определить стабильную latency системы.

Присылайте PR с исходниками генератора патронов, подробным отчётом с описанием предельной пропускной способности системы и гистограммы времён ответа на стабильной нагрузке для каждого типа ленты патронов и анализом результатов.

Бонусный этап (deadline 2019-12-07)

Индивидуальные фичи, которые позволяют получить дополнительные баллы (10-30):

• Expire: возможность указания времени жизни записей
• Hints: сохранение модификаций для недоступных нод (hints) и доставка hints, как только нода станет доступной
• Server-side processing: трансформация данных с помощью скрипта (например, на JavaScript), запускаемого на узлах кластера через API
• Read-repair: починка данных на нодах, по какой-то причине пропустивших модификации и отдающих устаревшее значение
• Background Compaction: автоматический запуск compaction по мере накопления SSTables
• Write-Ahead Log (WAL): запись модификаций в лог перед ответом клиенту, ротация WAL по мере flush и их проигрывание после рестарта
• Нагрузочное тестирование при помощи Y!CSB
• Распределённые range запросы: streaming и объединение данных со всех нод кластера без OutOfMemory
• Предложите что-то своё

Одна бонусная фича на одного человека. Если хотите реализовать какую-то фичу, подумайте, как именно, и согласуйте с преподавателем.

Реализация любой фичи подразумевает написание дополнительных модульных тестов, демонстрирующих корректность реализации.