Highload-2023: Отчёт Виталия Филиппова

Как я уже писал в прошлогоднем отчёте - самая крупная и раскрученная конференция Бунина. Финальная стоимость выросла уже аж до 64 тыр с 60, то есть годовая инфляция по версии Онтико в этот раз составила 6.66 %. :-)

Общее впечатление: Неплохо - "торжество велосипедов" в докладах, всё как мы любим, но перегруженно. Слишком много народу на эту площадку.

Реально, 3750 человек в Сколково, в котором и проходила конференция - это перебор. Если чуть более, чем средне-интересный доклад шёл в любом зале, кроме самого большого "Конгресс-холла" - сесть там было невозможно. Они пытались организовывать какие-то "расширительные бачки" в виде ретрансляций докладов рядом с залами, но это было бесполезно, ибо организовывали не прямо в коридоре, а в маленьких отдельных комнатушках. Какой толк от расширительного бачка на 10 человек, когда не влезло 50...

Второй момент - совершенно упоротая топология здания. Поиск нужного зала каждый раз превращался в квест: сначала надо попытаться понять по карте, где ты находишься, решить, в какую сторону идти и с какой стороны всё обходить, а потом ещё иногда искать отдельные лестницы на второй этаж для прохода в некоторые залы (просто подняться в произвольном месте недостаточно). При этом везде столики, стенды, толпы, поэтому даже образовывались заторы и проходы становились полудуплексными. Даже в сортирах был хайлоад. Явно не хватало процессоров на все... потоки.

При этом ещё и 11 параллельных залов. Я даже пожалел, что не заявил какую-нибудь хрень на опенсорс-трек - там такую фигню рассказывали, что я бы точно смог не хуже. Не, сама идея опенсорс-трека неплохая, но доклады бестолковые, хорошо демонстрируют механистический подход к опенсорсу: одни рассказывают, что опенсорс это хорошо, потому что признание сообщества, розовые пони и вообще, а вторые - что они попробовали давать по 100$ рандомным разработчикам модулей питона раз в неделю, и профита не обнаружили, но будут ещё пробовать. А третьи вообще вместо рассказа, КАК же они пилят этот самый опенсорс, рассказывают, что они его закрывают и продают как сборник произведений по ГК РФ - это очень важная и интересная информация, которой, конечно, до этого не было ни на одной конференции (тро-ло-ло).

День 1

Барсик

Григорий Бутейко (VK, ВКонтакте) — BARSiC — асинхронная репликация и консенсус для 70 баз данных.

Помните, я же написал выше, что конфа — торжество велосипедов. Вот, это велосипед №1, прямо с открытия.

Полная фигня, 150 полуляхов из 250. Технических деталей работы алгоритма в докладе было крайне мало, просто общая мысль — вот, им ничего готовое не подошло, Raft они почему-то сочли слишком сложным (Raft, сложным?!), поэтому сделали всё сами и на основе другого протокола — Viewstamped Replication аж от целой Бабы Лизы… то есть Барбары Лисков.

Самое смешное, что они на замену Raft-у, который им «показался слишком сложным», выбрали алгоритм, который (А) вообще не отличается от Raft по смыслу и (Б) даже сложнее, чем Raft, в деталях реализации! Это более старый алгоритм! Чувак, который придумал Raft, про этот алгоритм даже в своём диссере писал! В котором он, собственно, и придумал Raft.

Я про VR почитал уже после конфы. Единственное реальное отличие — то, что ноды голосуют не за первого заявившегося кандидата, а за кандидата с минимальным ID (IP-адресом). Всё остальное практически идентично, Raft Term = VR View и так далее. При этом у VR 10 типов сообщений вместо 4-х у Raft-а.

Развёрнутое объяснение под катом, взял отсюда

With apologies to Barbara, James, and Brian. VR introduced some great ideas, and VRR was a huge improvement in clarity. I think the industry would be in a better place now with respect to consensus if it had paid less attention to Paxos and more to VR.

You’re right, Heidi, that Raft and VR/VRR are similar, and we acknowledge this in the first page of the paper.

At a high level, you could argue they’re exactly the same. Lamport would probably call them both Paxos. Their messaging pattern is similar. Why they work is similar, and their proofs of correctness could be similar.

At a low level, you could argue they’re very different. Raft’s mechanism is compact (VRR uses 10 message types where Raft uses 4 to accomplish the same tasks). Raft spells out how to do leader election with randomized timeouts and how to avoid transferring entire logs.

And of course membership changes are entirely different.

Now (2015), there’s a huge difference in completeness. Raft has several implementations including membership changes and log compaction, some evaluation, a proof or two, my dissertation (a lot of discussion about design choices), and many online resources to help people learn. I don’t think VR/VRR is competitive with any of that currently. For example, I just searched GitHub for «Viewstamped Replication» and found only one project; searching «VRR» yields noise.

Paper-wise, I’m biased, but I think the Raft paper is more accessible to beginners. That’s because the Raft paper explains the why, and the VRR paper just tells you the what.

I also think the leader election algorithm in the original VR is better than in VRR. I discuss this in the related work in my dissertation. The original VR has the view manager tell the new leader to start, yes, but it doesn’t have to transmit any log entries. And I still don’t feel great about the leader being a function of the view (term) number. It feels misleading, since of course different servers might be in different views, especially during leader changes. But I haven’t implemented or evaluated that approach.

We (John and I) actually didn’t know about the VRR paper until after we had started Raft. I think the earliest time someone mentioned it to us was three days before our first paper submission on Raft, in September 2012, buried in an email with a bunch of other pointers. Would we have used VRR instead of creating Raft if we knew abut it in time? I’m not sure, but it definitely would have been a better starting point for us.

Know of any performance evaluation between these two protocols? Nope. Normal-case operation would be the same, so you’d probably have to compare leader changes. And I feel like that depends on the details of how you «optimize» VRR, so I don’t know if it’d be apples-to-apples.

Hope I haven’t offended anyone, and hope this helps, Diego

Причём аргументы, согласно которым им не подошли готовые решения, меня лично вообще не убедили. Какое-то расхождение данных и метаданных при использовании внешнего сервиса консенсуса… не, ну писать просто надо нормально, что значит — расхождение. Я же юзаю etcd в Vitastor, брат жив. Ну ладно я, ещё пример — TiDB юзает встраиваемый etcd, брат тоже жив. Всё ещё мало? Patroni/Stolon испокон веков юзают Consul/etcd. Ceph OSD хранят метаданные в Ceph Monitor-ах. Какое расхождение?!

Хоть бы исходники открыли, ё-моё, хоть какая-то польза была бы от этого барсика. А то ну написали тесты, ну пофаззили, ну дополнительно верифицировали на TLA+, ну молодцы. Но какой во всём этом толк, если рядом лежит штук 10 «вот таких же, только меньше, но других», тоже хорошо оттестированных за все эти годы Raft-ов…

Производительность Go

Никита Галушко (VK, ВКонтакте) — Выжимаем из Go максимум производительности

В принципе стандартные вещи, даже не так их много было:

• Мелкие объекты — до 32 байт — оптимизируются
• Интерфейсы медленнее из-за виртуальных вызовов
• Если в массивах срабатывает проверка границ (не срабатывает BCE) — код замедляется
• for по индексам быстрее, чем for по range (подозрительно, stackoverflow говорит обратное — что они не отличаются)
• Работа со строками хорошо оптимизирована для частых сценариев

Как привлекать людей в опенсорс-проекты

Ксения Романова (Positive Technologies) — Сообщества вокруг технологии: почему быть бесплатным недостаточно

Девушка связана с Apache Ignite и фондом Apache (туда ещё проекты умирать часто сдают), сейчас работает у позитивов.

Я не уверен, что доклад был именно о том, как я его окрестил, ибо изложение было довольно размытым. Но мне кажется, что это самое близкое. По-моему, она пыталась развивать стереотип о том, что опенсорс — это «бесплатные руки», и надо лучше искать эти бесплатные руки, лучше общаться с людьми и помогать им включиться в проект. «Как бы нам заполучить бесплатных разработчиков». :-)

С моей точки зрения — это утопия, хоть я и адепт опенсорса. Времени всем не хватает, видение развития проекта у каждого своё (1 программист пишет программу за 1 месяц, 2 — за 2 месяца), лидеры проекта душнят в пулреквестах, поэтому не стоит рассчитывать, что вы сможете найти серьёзный пул контрибьюторов среди сообщества. Проекты типа Linux — это очень редкие и крутые исключения из правил, так почти никто не умеет. Хотя, кстати, в её родном фонде Apache линукс ещё не факт, что свершился бы — они же не принимают правки от компаний.

Всё остальное в докладе — шелуха. Вот… сообщества… технологии… привлекать людей… модель «воронка»… модель «орбита»… людям это надо для чего-то там… компаниям это надо для чего-то там… 80% кода в опенсорс-проектах пишут единичные «герои»… Контрибьюторы классифицируются по 2 осям — качеству кода и любви к проекту… (тут я вообще чуть не взоржал)

Из интересного — в конце спросил у неё, а зачем компании сдают проекты в фонд Apache, в чём выгода. Так как, по-моему, проекты туда обычно сдают помирать, на кладбище. Для справки — апачи забирают все права на проект себе и даже потом правки от компаний не принимают — отправлять патчи могут только отдельные физлица-разработчики, даже если они все работают в одной компании. Она ответила, что сдают ради помощи в развитии, типа гайдлайнов/руководств по жизненному циклу проекта и ради готовой инфраструктуры разработки. Ну понятно — Apache пытается строить «завод опенсорса» и на этом в процессе делать деньги. Но вот для сдающей компании особой выгоды, мне кажется, всё-таки нет, так что скорее всего обычно действительно просто «сдают в отстойник».

Дата скетчи

Сергей Жемжицкий (SberDevices) — Data Sketches — как съесть слона целиком (даже если он бесконечный)

В целом неплохой доклад про алгоритмы семейства Data Sketches. Ну в смысле для меня неплохой, ибо я про эти алгоритмы не знал. Я так понимаю, это новое собирательное название для уже некоторое время существующего класса алгоритмов — потоковых статистических алгоритмов.

TLDR — всё это реализовано в библиотеке Apache DataSketches на Java и C++, бери и юзай. Даже в ClickHouse припилено уже.

В докладе затронуты алгоритмы:

• Подсчёт числа уникальных элементов в потоке (Count-Distinct): HLL (HyperLogLog), CPC (Compressed Probability Counting), Theta Sketch
  • HLL: число уникальных примерно равно 2^(максимальное число идущих подряд нулей в начале хешей всех элементов + 1).
  • CPC: число уникальных примерно равно 2^(максимальное число идущих подряд нулей в конце хешей всех элементов, кроме хешей из всех нулей).
  • Theta Sketch: вроде бы это обобщение алгоритма K минимальных значений. Типа, мапим каждое значение в хеш, равномерно распределённый в диапазоне чисел (0, 1). Сохраняем K+1 минимальных значений таких хешей. После чего число уникальных будет примерно равно K/(k+1-ый минимальный хеш). Вот статья про эту тету https://github.com/apache/datasketches-website/blob/master/docs/pdf/ThetaSketchFramework.pdf
• Частота встречаемости элемента: CountMin Sketch, Misra-Gries
  • CountMin: берём несколько независимых хеш-функций, делаем таблицу — на каждый хеш 1 строка, и заданное K колонок. На каждое значение считаем все хеши и увеличиваем на 1 соответствующую хешу колонку в строчке этого хеша. Потом, чтобы оценить частоту встречаемости элемента, берём минимум от значений ячеек, соответствующих всем его хешам.
  • Misra-Gries: по ходу подсчёта сохраняем K самых часто встречаемых элементов и считаем их частоты. Если же встречаем элемент, не входящий в K, увеличиваем на 1 отдельный счётчик «всех остальных», уменьшаем на 1 все частоты K элементов, удаляем элементы с нулевыми частотами. Далее частоту встречаемости любого элемента принимаем за (счётчик «всех остальных» + счётчик самого элемента).
• Квантили/гистограммы: куча странных названий, я себе из всего выписал Manku-Rajagopalan-Lindsay (MRL), но в суть расчёта докладчик уже не погружался.

Катаем гусей

Павел Левдик (Yandex Infrastructure) — Внутри S3

Доклад про Яндексовую реализацию S3. Глобально всё просто — взят уже готовый надёжный распределённый сторадж для данных, взят шардированный и реплицированный PostgreSQL, одно скрещено с другим и вот вам, пожалуйста, S3.

Шардирование раньше было только в виде чанков — диапазонов имён объектов в бакете. Чтобы таскать чанки с шарда на шард — мувер, чтобы порождать новые чанки почкованием — сплиттер. И то, и то — через двухфазный коммит. Но была проблема, что в такой схеме определённые паттерны нагрузки не размазывались по всему кластеру БД. Например, если юзер всегда писал новые объекты в конец бакета — эти вставки всегда попадали в один чанк и, соответственно, шард. Или, например, если юзер сначала делал алфавитный листинг всех объектов, а потом последовательно читал их — такая нагрузка тоже в каждый момент времени попадала только в один шард БД.

Поэтому сделали хеш-чанки (диапазоны хешей имён объектов) и такая нагрузка тоже стала размазываться. Был даже график, на котором это было видно наглядно — до переключения на ханки нагрузка шла постоянно то в 1 шард, то во 2, то в 3 и т. п., а после — равномерно во все три. То есть, все три покрашенные разными цветами линии нагрузки в разные шарды сошлись на одном уровне. Кто-то из зала не понял, что на графике изображены не листинги, а обычная нагрузка (то ли GET, то ли PUT), и спросил, так это что же, теперь листинги грузят все шарды? По факту с этим проблем нет, так как, во-первых, запрос листинга в S3 ограничен 1000 записей, во-вторых, и до перехода на ханки запросы листинга часто попадали в несколько шардов — в тех случаях, когда нельзя точно сказать, что 1000 записей можно вернуть из 1 шарда, а в-третьих, с ханками число шардов, на которые размазан каждый бакет, тоже регулируется, просто оно увеличивается сразу в 2 раза.

Ещё было про счётчики и то, что они считаются через очередь. Ну ещё из интересного (для конкурентов :D) — цифры, например, 120к rps в облаке (2x за год), типичный крупный клиент > 1 ПБ и > 1 млрд объектов, и > 1000 rps.

Кстати, ещё Паша не упоминал, что там в PostgreSQL есть хранимки и они весьма неплохо работают. Но про это есть старый пост на хабре: https://habr.com/ru/companies/yandex/articles/417241/

День 2

Как разрабатывается опенсорс в АЛЬТ

(никак...)

Устройство индексов в почте mail.ru

Вот наконец и третья часть архитектуры mail.ru. Но вот эту часть — можно я не буду у себя нигде повторять, можно же, правда? :-)