Курсовой проект 2022 года курса "Проектирование высоконагруженных систем" VK Образования.
Форкните проект, склонируйте и добавьте upstream
:
$ git clone git@github.com:<username>/2022-highload-dht.git
Cloning into '2022-highload-dht'...
...
$ git remote add upstream git@github.com:polis-vk/2022-highload-dht.git
$ git fetch upstream
From github.com:polis-vk/2022-highload-dht
* [new branch] master -> upstream/master
Так можно запустить тесты:
$ ./gradlew test
А вот так -- сервер:
$ ./gradlew run
Откройте в IDE -- IntelliJ IDEA Community Edition нам будет достаточно.
ВНИМАНИЕ! При запуске тестов или сервера в IDE необходимо передавать Java опцию -Xmx128m
.
В своём Java package ok.dht.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
из весеннего курса 2022-nosql-lsm
, либо берём референсную реализацию, если курс БД не был завершён.
Проведите нагрузочное тестирование с помощью wrk2 в одно соединение:
PUT
запросами на стабильной нагрузке (wrk2
должен обеспечивать заданный с помощью-R
rate запросов)GET
запросами на стабильной нагрузке по наполненной БД
Почему не curl
/F5, можно узнать здесь и здесь.
Приложите полученный консольный вывод wrk2
для обоих видов нагрузки.
Отпрофилируйте приложение (CPU и alloc) под PUT
и GET
нагрузкой с помощью async-profiler.
Приложите SVG-файлы FlameGraph cpu
/alloc
для PUT
/GET
нагрузки.
Объясните результаты нагрузочного тестирования и профилирования и приложите текстовый отчёт (в Markdown).
Продолжайте запускать тесты и исправлять ошибки, не забывая подтягивать новые тесты и фиксы из upstream
.
Если заметите ошибку в upstream
, заводите баг и присылайте pull request ;)
Когда всё будет готово, присылайте pull request со своей реализацией и оптимизациями на review. Не забывайте отвечать на комментарии в PR (в том числе автоматизированные) и исправлять замечания!
Вынесите обработку запросов в отдельный ExecutorService
с ограниченной очередью, чтобы разгрузить SelectorThread
ы HTTP сервера.
Проведите нагрузочное тестирование с помощью wrk2 с большим количеством соединений (не меньше 64) PUT
и GET
запросами.
Отпрофилируйте приложение (CPU, alloc и lock) под PUT
и GET
нагрузкой с помощью async-profiler.
Когда всё будет готово, присылайте pull request с изменениями, результатами нагрузочного тестирования и профилирования, а также анализом результатов по сравнению с предыдущей (синхронной) версией.
Этап 3. Шардирование (bonus deadline 2022-10-12 23:59:59 MSK, hard deadline 2022-10-19 23:59:59 MSK)
Реализуем горизонтальное масштабирование через поддержку кластерных конфигураций, состоящих из нескольких узлов, взаимодействующих друг с другом через реализованный HTTP API.
Для этого в ServiceConfig
передаётся статическая "топология", представленная в виде множества координат всех узлов кластера в формате http://<host>:<port>
.
Кластер распределяет ключи между узлами детерминированным образом. В кластере хранится только одна копия данных. Нода, получившая запрос, проксирует его на узел, отвечающий за обслуживание соответствующего ключа. Таким образом, общая ёмкость кластера равна суммарной ёмкости входящих в него узлов.
Реализуйте один из алгоритмов распределения данных между узлами, например, consistent hashing, rendezvous hashing или что-то другое по согласованию с преподавателем.
Присылайте pull request со своей реализацией поддержки кластерной конфигурации на review. Не забудьте нагрузить, отпрофилировать и проанализировать результаты профилирования под нагрузкой. С учётом шардирования набор тестов расширяется, поэтому не забывайте подмёрдживать upstream.
Реализуем поддержку хранения нескольких реплик данных в кластере для обеспечения отказоустойчивости.
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)
реплик
Присылайте pull request со своей реализацией поддержки кластерной конфигурации на review. Не забудьте нагрузить, отпрофилировать и проанализировать результаты профилирования под нагрузкой. С учётом репликации набор тестов расширяется, поэтому не забывайте подмёрдживать upstream.
Этап 5. Асинхронное взаимодействие (bonus deadline 2022-11-02 23:59:59 MSK, hard deadline 2022-11-09 23:59:59 MSK)
Переключаем внутреннее взаимодействие узлов на асинхронный java.net.http.HttpClient
.
Параллельно отправляем запросы репликам и собираем самые быстрые ответы на CompletableFuture
.
Проведите нагрузочное тестирование с помощью wrk2 в несколько соединений.
Отпрофилируйте приложение (CPU, alloc и lock) под нагрузкой и сравните результаты latency и профилирования по сравнению с неасинхронной версией.
Присылайте pull request со своей реализацией на review.
Реализуйте получение диапазона данных текущего узла с помощью HTTP GET /v0/entities?start=<ID>[&end=<ID>]
, который возвращает:
- Статус код
200 OK
- Возможно пустой отсортированный (по ключу) набор ключей и значений в диапазоне ключей от обязательного
start
(включая) до опциональногоend
(не включая) - Используйте Chunked transfer encoding
- Чанки в формате
<key>\n<value>
Диапазон должен отдаваться в потоковом режиме без формирования всего ответа в памяти.
После прохождения модульных тестов, присылайте pull request с изменениями.