This repository has been archived by the owner. It is now read-only.
Курсовой проект 2017 года курса "Проектирование высоконагруженных систем"
Clone or download
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
Failed to load latest commit information.
gradle/wrapper
src
.gitignore
.travis.yml
LICENSE
README.md
build.gradle.kts
gradlew
settings.gradle

README.md

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)

На этом этапе нам предстоит:

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

Окружение

План-минимум -- поднять 3 локальных узла:

$ ./gradlew run

План-максимум -- поднять 3 узла в отдельных контейнерах/приложениях.

Что измеряем

  • Пропускную способность (успешные запросы/сек)
  • Задержку (обязательно мс/запрос в среднем, а также желательно 90% и 99%-перцентили)
  • Не менее 1 мин

Нагрузка

  • Обязательно только PUT (c/без перезаписи) с replicas=2/3 и replicas=3/3
  • Обязательно только GET (на большом наборе ключей с/без повторов) с replicas=2/3 и replicas=3/3
  • Желательно смесь PUT/GET 50/50 (с/без перезаписи) с replicas=2/3 и replicas=3/3

Каждый вид нагрузки тестируем в режимах 1/2/4 потока/соединения.

Если готовы по-взрослому, то адаптируйте Yahoo! Cloud Serving Benchmark к своему хранилищу и получите бонусные баллы.

Нагрузочное тестирование

curl

Smoke test, только в один поток и статистику нужно считать самим, но низкий порог входа, чтобы начать:

$ for i in $(seq 0 1000000); do time curl -X PUT -d value$i http://localhost:8080/v0/entity?id=key$i; done
...

wrk

Более изощрённые виды нагрузки, в т.ч. с Keep-Alive и многопоточно, но необходимо пописать на Lua. См. сайт проекта и примеры скриптов.

Выглядеть может так:

$ wrk --latency -c4 -d5m -s scripts/put.lua http://localhost:8080
Running 5m test @ http://localhost:8080
  2 threads and 4 connections
  Thread Stats   Avg      Stdev     Max   +/- Stdev
    Latency     1.80ms    8.37ms 345.00ms   99.61%
    Req/Sec     1.56k   238.51     2.20k    74.12%
  Latency Distribution
     50%    1.09ms
     75%    1.33ms
     90%    2.59ms
     99%    7.41ms
  928082 requests in 5.00m, 83.20MB read
Requests/sec:   3093.04
Transfer/sec:    283.93KB
$ wrk --latency -c4 -d1m -s scripts/get.lua http://localhost:8080
Running 1m test @ http://localhost:8080
  2 threads and 4 connections
  Thread Stats   Avg      Stdev     Max   +/- Stdev
    Latency     1.48ms    1.84ms  47.85ms   97.07%
    Req/Sec     1.55k   297.86     2.04k    58.75%
  Latency Distribution
     50%    1.18ms
     75%    1.40ms
     90%    1.66ms
     99%    9.95ms
  185247 requests in 1.00m, 21.16MB read
Requests/sec:   3085.96
Transfer/sec:    360.95KB

Yandex.Tank

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

Профилирование

Чтобы сузить область поиска, можно попробовать протестировать чисто сетевую часть, используя простую in-memory реализацию хранилища.

jvisualvm

Входит в состав JDK и поддерживает профилирование. Если возникает ошибка при запуске профилирования, укажите опцию JVM -Xverify:none.

Java Mission Control

Также входит в состав JDK и бесплатен для разработки, но не забудьте включить Java Flight Recorder.

async-profiler

Бесплатный и с открытым исходным кодом. См. сайт проекта.

Report

Присылайте PR, в который входят commit'ы с оптимизациями по результатам профилирования, а также файл LOADTEST.md, содержащий результаты нагрузочного тестирования и профилирования до и после оптимизаций (в виде дампов консоли, скриншотов и/или графиков).

Bonus (deadline 2017-12-19)

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

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

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