2024-highload-dht

Курсовой проект 2024 года курса «Разработка high-load систем» Корпоративной магистерской программы «Распределённые веб-сервисы / Web scale systems».

Этап 1. HTTP + storage (deadline 2024-02-21 23:59:59 MSK)

Fork

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

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

Make

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

$ ./gradlew test

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

$ ./gradlew run

Develop

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

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

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

Используйте свою реализацию Dao из предыдущего курса 2023-nosql-lsm или референсную реализацию, если своей нет.

Проведите нагрузочное тестирование с помощью wrk2 в одно соединение:

• PUT запросами на стабильной нагрузке (wrk2 должен обеспечивать заданный с помощью -R rate запросов) ниже точки разладки
• GET запросами на стабильной нагрузке по наполненной БД ниже точки разладки

Нагрузочное тестирование и профилирование должны проводиться в одинаковых условиях (при одинаковой нагрузке на CPU). А почему не curl/F5, можно узнать здесь и здесь.

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

Отпрофилируйте приложение (CPU и alloc) под PUT и GET нагрузкой с помощью async-profiler. Приложите SVG-файлы FlameGraph cpu/alloc для PUT/GET нагрузки.

Объясните результаты нагрузочного тестирования и профилирования и приложите текстовый отчёт (в Markdown). Все используемые инструменты были рассмотрены на лекции -- смотрите видео запись.

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

Report

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

Этап 2. Асинхронный сервер (soft deadline 2024-02-29 18:29:59 MSK, hard deadline 2024-03-06 23:59:59 MSK)

Вынесите обработку запросов в отдельный ExecutorService с ограниченной очередью, чтобы разгрузить SelectorThreadы HTTP сервера. Подумайте о параметрах ExecutorService (тип и размер очереди, количество потоков, обработка переполнений очереди и ошибок при обработке запросов) -- результаты всех экспериментов опишите в отчёте. Проанализируйте, стало ли лучше, чем раньше?

Проведите нагрузочное тестирование с помощью wrk2 с большим количеством соединений (не меньше 64) PUT и GET запросами.

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

Report

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

Этап 3. Шардирование (soft deadline 2024-03-14 18:29:59 MSK, hard deadline 2024-03-20 23:59:59 MSK)

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

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

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

Report

Когда всё будет готово, присылайте pull request с изменениями, результатами нагрузочного тестирования и профилирования, а также анализом результатов по сравнению с предыдущей (нераспределённой) версией. На всех этапах оценивается и код, и анализ (отчёт) -- без анализа полученных результатов работа оценивается минимальным количеством баллов. Не забывайте отвечать на комментарии в PR (в том числе автоматизированные) и исправлять замечания! С учётом шардирования набор тестов расширяется, поэтому не забывайте подмёрдживать upstream.

Этап 4. Репликация (soft deadline 2024-03-28 18:29:59 MSK, hard deadline 2024-04-03 23:59:59 MSK)

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

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

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

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

• HTTP GET /v0/entity?id=<ID>[&ack=<ACK>&from=<FROM>] -- получить данные по ключу <ID>. Возвращает:

  • 200 OK и данные, если ответили хотя бы ack из from реплик
  • 404 Not Found, если ни одна из ack реплик, вернувших ответ, не содержит данные (либо самая свежая версия среди ack ответов -- это tombstone)
  • 504 Not Enough Replicas, если не получили 200/404 от ack реплик из всего множества from реплик

• HTTP PUT /v0/entity?id=<ID>[&ack=<ACK>&from=<FROM>] -- создать/перезаписать (upsert) данные по ключу <ID>. Возвращает:

  • 201 Created, если хотя бы ack из from реплик подтвердили операцию
  • 504 Not Enough Replicas, если не набралось ack подтверждений из всего множества from реплик

• HTTP DELETE /v0/entity?id=<ID>[&ack=<ACK>&from=<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) реплик

Этап 5. Асинхронное взаимодействие (soft deadline 2024-04-11 18:29:59 MSK, hard deadline 2024-04-17 23:59:59 MSK)

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

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

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

Report

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

Этап 6. Range-запросы (soft deadline 2024-04-25 18:29:59 MSK, hard deadline 2024-05-01 23:59:59 MSK)

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

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

Диапазон должен отдаваться в потоковом режиме без формирования всего ответа в памяти. Проверить корректность можно, запросив весь диапазон данных предварительно наполненной БД размером больше Java Heap.

Report

После прохождения модульных тестов, присылайте pull request с изменениями. Наполните БД большим объёмом данных и отпрофилируйте cpu, alloc и lock при получении range всей базы одним запросом curl'ом. Присылайте отчёт с анализом результатов и оптимизаций.

Этап 7. Бонусный (hard deadline 2024-05-15 23:59:59 MSK)

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

• Развёрнутая конструктивная обратная связь по курсу: достоинства и недостатки курса, сложность тем, предложения по улучшению
• Кластерные range-запросы с учётом шардирования и репликации
• Read repair при обнаружении расхождений между репликами
• Expire: возможность указания времени жизни записей
• Server-side processing: трансформация данных с помощью скрипта, запускаемого на узлах кластера через API
• Нагрузочное тестирование при помощи Y!CSB
• Нагрузочное тестирование при помощи Yandex.Tank
• Регулярный автоматический фоновый compaction (модульные и нагрузочные тесты)
• Hinted handoff по аналогии с Cassandra
• Устранение неконсистентностей между репликами по аналогии с Cassandra nodetool repair, например, на основе Merkle Tree
• Блочная компрессия данных на основе LZ4/zSTD/...
• Что-нибудь своё?

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