Comments 10
О том, как нам удалось реализовать выбранное решение
Судя по тому, как Авито работает сегодня, получилось не очень.
Не очень понятно почему вы посчитали скорость поиска для AnchorHash как средний, если иметь простую функцию маппинга бакета на шард, ее можно высчитывать в раниайме при этом вам было бы не обязатально вводить все шарды в эксплуатацию сразу (экономия), легко управлять распределением бакетов и при этом не иметь жесткого ограничения на кол-во шардов, которое может выстрелить в ногу через пару лет и потребовать полной и дорогостоящей переработки всей системы…
Спасибо за комментарий! Это действительно важный момент, в целом вы правы это отличный алгоритм, в статье я привёл ссылку на исследование алгоритмов и сравнение их скорости поиска, там можно почитать подробнее, если вкратце его скорость поиска на экспериментах была 2015ns vs 805ns у линейного алгоритма, поэтому отнесена в разряд "средний".
У AnchorHash также есть жёсткое ограничение в виде "якорного множества" шардов, и чем оно больше, а число "активных" шардов меньше, тем сильнее будет страдать скорость поиска шарда.
Мы сознательно выбрали простоту - линейный алгоритм понятен всей команде, легко дебажится и не привносит дополнительную сложность в систему, даже если AnchorHash отнести в разряд "высокий" по скорости, наше решение бы не изменилось. Тут однозначно можно покопать глубже и провести свои эксперименты. В данном случае я попытался рассказать что мы решили и показать ход мыслей при поиске решения и как мы делали выбор.
На тему выстрела в ногу через пару лет, есть разные пути, можно действительно провести полный решардинг, а можно сделать виртуальные шарды в будущем или придумать что-то третье, мы исходили из того, что за пару лет это в целом как раз не понадобится, а будет ожидать нас на более высоком горизонте 3-5 лет и больше.
Также в эту тему, вышла вторая часть статьи, про то как мы это сделали и как это работает через пару лет в продакшене, можете ознакомиться - Шардирование сервиса объявлений Авито Доставки. Часть II
Спасибо понятно. AnchorHash, если я ничего не путаю, подмножество направления с виртуальными бакетами (табличной функцией), один из методов быстрого поиска - разложить id на диапазон, например по 2,5 - 5 тыс (можно и 20тыс, заисит от задачи). Таким образом если мы имеем таблицу связей бакет - шард в оперативной памяти, поиск заключается в одном делении на диапазон и поиск в Map по ключу, если ключ не числовой, условно crc32 или любой другой простой хэш алгоритм. Алексей Рыбак рассказывал про это во внезапамятные времена https://highload.guide/blog/sharding-patterns-and-antipatterns.html рекомендую глянуть.
Дипломная работа это конечно интересно на уровне теории. Есть огромный пласт знаний по практическому применению разных вариантов в большом кол-ве крупных компаний именитыми инженерами, на том же https://highscalability.com/
Спасибо за статью! Если не секрет, поделитесь пожалуйста информацией:
1) какова была трудоемкость вашего решения в человеко-годах (от проектирования до развертывания)
2) почему не ydb\shardman? У них точно есть поддержка прямо сейчас, ПГсовместимы, хотя CocroaсhDb выглядит интереснее
Ответ на первый вопрос есть во второй части статьи, там можно почитать подробно - Шардирование сервиса объявлений Авито Доставки. Часть II
Если вкратце, то работа от проектирования до развёртывания заняла примерно 9 календарных месяцев, в человеко-годах/месяцах не оценивал, так как сама оценка субьективна, потребует много оговорок и будет сильно зависеть от контекста, чью работу мы будем считать и как именно считать, как говорится "не важно как проголосовали, важно как посчитали", если считать работу только нашей команды, которая этим непосредственно занималась, а человеко-месяц считать как то, что человек будет 100% возможного рабочего времени заниматься этой задачей, то я бы сказал наберётся около 3-5 человеко-месяцев.
По второму вопросу, shardman основан на postgres_fdw, мы рассматривали сам механизм postgres_fdw и отмели на этапе чтения документации, так как поняли что он даёт большой latency на запросы, в статье это также описано, встречный вопрос, shardman тут отличается от прямого использования postgres_fdw?
Возможно стоит его рассмотреть при решении подобной задачи тоже, как и ydb, мы её не рассматривали, так как намеренно ограничили себя в выборе новой бд, опираясь на уже проведённое исследование коллег сделанное годом ранее с кейсом аналогичным нашему, что бы не закопаться в исследованиях, так как срок у нас был ограниченным за который нужно было решить проблему масштабирования.
Спасибо за вопросы!
Да, нашел важные ответы во второй статье. Вашу идею я понял. Shardman - это всё тоже самое, только на стороне БД. Т.е. для прикладной разработки - это практически всё тот же постгри: многие проблемы (шардирование, коллокация, отказоустойчивость и пр.) перенесены в коробку и решаются на стороне сервиса БД, а не из прикладного кода.
От слова Шарады?
Шардирование сервиса объявлений Авито Доставки. Часть I