13 521
правка
Изменения
Нет описания правки
** HLL: число уникальных примерно равно 2^(максимальное число идущих подряд нулей в начале хешей всех элементов + 1).
** CPC: число уникальных примерно равно 2^(максимальное число идущих подряд нулей в конце хешей всех элементов, кроме хешей из всех нулей).
** Theta Sketch: вроде бы это обобщение алгоритма K минимальных значений. Типа, мапим каждое значение в хеш, равномерно распределённый в диапазоне чисел (0, 1). Сохраняем K+1 минимальных значений таких хешей. После чего число уникальных будет примерно равно K/(kK+1-ый минимальный хеш). Вот статья про эту тету https://github.com/apache/datasketches-website/blob/master/docs/pdf/ThetaSketchFramework.pdf— кстати, в докладе он принцип работы этого алгоритма не объяснил, это я уже тут для отчёта докурил :-)
* Частота встречаемости элемента: CountMin Sketch, Misra-Gries
** CountMin: берём несколько независимых хеш-функций, делаем таблицу — на каждый хеш 1 строка, и заданное K колонок. На каждое значение считаем все хеши и увеличиваем на 1 соответствующую хешу колонку в строчке этого хеша. Потом, чтобы оценить частоту встречаемости элемента, берём минимум от значений ячеек, соответствующих всем его хешам.
'''Павел Левдик (Yandex Infrastructure) — Внутри S3'''
Доклад про Яндексовую реализацию S3(гусь/goose — это go+s3, название сервера). Глобально всё просто — взят уже готовый надёжный распределённый сторадж для данных, взят шардированный и реплицированный PostgreSQL, одно скрещено с другим и вот вам, пожалуйста, S3.
Шардирование раньше было только в виде чанков — диапазонов имён объектов в бакете. Чтобы таскать чанки с шарда на шард — мувер, чтобы порождать новые чанки почкованием — сплиттер. И то, и то — через двухфазный коммит. Но была проблема, что в такой схеме определённые паттерны нагрузки не размазывались по всему кластеру БД. Например, если юзер всегда писал новые объекты в конец бакета — эти вставки всегда попадали в один чанк и, соответственно, шард. Или, например, если юзер сначала делал алфавитный листинг всех объектов, а потом последовательно читал их — такая нагрузка тоже в каждый момент времени попадала только в один шард БД.
Поэтому сделали хеш-чанки (диапазоны хешей имён объектов) и такая нагрузка тоже стала размазываться. Был даже график, на котором это было видно наглядно — до переключения на ханки нагрузка шла постоянно то в 1 шард, то во 2, то в 3 и т. п., а после — равномерно во все три. То есть, все три покрашенные разными цветами линии нагрузки в разные шарды сошлись на одном уровне. Кто-то из зала не понял, что на графике изображены не листинги, а обычная нагрузка (то ли GET, то ли PUT), и спросил, так это что же, теперь листинги грузят все шарды? По факту с этим проблем нет, так как, во-первых, запрос листинга в S3 ограничен 1000 записей, во-вторых, и до перехода на ханки запросы листинга часто попадали в несколько шардов — в тех случаях, когда нельзя точно сказать, что 1000 записей можно вернуть из 1 шарда, а в-третьих, с ханками число шардов, на которые размазан каждый бакет, тоже регулируется, просто оно увеличивается регулируется делением/умножением сразу в 2 раза.
Ещё было про счётчики и то, что они считаются через очередь. Ну ещё из интересного (для конкурентов :D) — цифры, например, 120к rps в облаке (2x за год), типичный крупный клиент > 1 ПБ и > 1 млрд объектов, и > 1000 rps.
== Петабайт в УДБ на ХДД ==
'''Антон Барабанов (Яндекс) — Петабайт в YDB over HDD в процессингах Яндекс. Метрики'''
Ну, реально пока не петабайт, а 500 ТБ, но, типа, скоро будет петабайт. Но всё равно норм. При потоке записи 20 гбит/сек. 300 дисков в инсталляции. Суть — пробовали YDB на HDD. Справилось оно в их применении в целом неплохо, правда, как обычно, всю автоматику поотрубали — распределение запросов написали своё и данные тоже сами раскладывают по отдельным дневным табличкам.
Само применение — слияние визитов за сутки в метрике. То есть, на входе большой поток посещений сайтов и покупок (или других действий), на выходе надо посещения сцепить с действием, чтобы было понятно, что конверсия произошла. Для оффлайн-покупок аналогично, но дольше период — не сутки, а 20-30 дней, и данные сливает в метрику заливает сам магазин постфактум, возможно даже вручную. Жёстких требований реального времени нет, но некоторые есть — надо, чтобы считалось 10-15 минут, а не сутки.
С YDB сначала наткнулись на проблему потребления RAM, добавлять пришлось и RAM и CPU, так как сказали, что есть жёсткие профили виртуалок во внутреннем «облаке». В итоге CPU на 90% простаивают. Потом YDB не справилось с чтением блоков с HDD, так как читаем читает целыми блоками и только потом понимает, что нужных данных в блоке нет, а bloom фильтр работает по полному первичному ключу, а они запрашивают по одному ID юзера. Для борьбы с этим ключи положили на SSD, данные визитов оставили на HDD. Ещё натыкались на то, что автосплит партиций по нагрузке приводил к большой нагрузке из-за compaction — сначала нагрузка растёт, партиции разделяются, потом нагрузка падает, они сливаются. Всё жрёт compaction/.
На вопрос «почему не YT(saurus)» ответили «так сложилось» + YT-шники им не были готовы предоставить такой кластер :-). Не Clickhouse потому, что Clickhouse плохо работает с синхронной репликацией.
