алгоритмы определения ноды в шардинге

grigori

( ͡° ͜ʖ ͡°)
Команда форума
Какие есть алгоритмы расчета номера шарда чтобы можно было расширять кластер?


* если выбираем шард по остатку от деления, для добавления ноды надо перераспределить все данные.
* если шард определяется не вычислением, надо где-то держать список соответствий, а это требует пары управляющих нод, как в Google FS, к тому же это дополнительный поиск на каждое обращение.

Есть еще варианты?
 

fixxxer

К.О.
Партнер клуба
Центральная база (с парой слейвов) обычно все равно нужна - хотя бы для аутентификации, я хранил маппинг в ней же и ходил в нее через handlersocket, это довольно быстро. Но на больших (очень больших) объемах это может работать уже не очень хорошо, ну и все же SPOF.
Есть еще варианты?
а) держать список соответствий избыточно локально везде, где он нужен - прямо в файловой системе, в .php файлах, все сляжет в opcode cache. Чтобы список был покороче и обновлять его надо было пореже, определять соответствие не для каждого userid (или по чему там шардится), а для диапазона оных.
б) если хочется алгоритмически - ketama hash. Перераспределения все равно будут - но будут сведены к минимуму.
 

Вурдалак

Продвинутый новичок
В порядке бреда :)

1) таскать id ноды прямо с id-шником.
2) (sequential id) иметь стратегию, которая тупо знает всю историю решардинга: до такого id такой алгоритм, до такого-то — такой. Суть в том, что можно добавить ноду и выкатить код с новой стратегией, которая учитывает ноду для «будущего» id. Можно указать заведомо большой id (+100000, например), а после раскладки этой стратегии увеличить sequential id до нужного значения, тогда для новых id-шников будет учитываться новая нода.

Но вариант с доп. запросом самый практичный.
 

Breeze

goshogun
Команда форума
Партнер клуба
ketama есть изкоробки в php-memcaced
Ketama для кеша хорошо, но не для инфы, где физически данные юзера лежат.
Мне нравится такой список, как fixxxer описал, там жирного юзера можно всегда перетащить на другой шард, либо вообще группу смигрировать куда надо.
А минимизировать обращения к центральной базе как раз кешом с кетамой :)

Собсно про это @DiMA на своих МК вроде рассказывал.
 

fixxxer

К.О.
Партнер клуба
Ketama для кеша хорошо, но не для инфы, где физически данные юзера лежат.
"Как есть" - не подойдет, но если задасться целью построения системы с автоматическим решардингом, вполне реализуемо, просто надо хранить еще и предыдущий вариант и обрабатывать ситуацию shard migration in progress. Но особого смысла не вижу, кроме как разве что "искоробочное" решение делать.
 

MiksIr

miksir@home:~$
Ну да, я что-то на своей волне был как раз, и про мемкеш подумалось, как раз ковыряюсь.
В общем похожая задача, свелась она к статическому мапингу, но не id -> server, а хеш от него. Заранее задается размер хеш таблицы "с запасом" и мапинг каждого хеша на сервер ;)
Потом, при необходимости, просто кускуи мигрируются с изменением мапинга на сервер.
 

Breeze

goshogun
Команда форума
Партнер клуба
с автоматическим решардингом
главное не забыть commit в конце сделать :)

Я встречал такое распределение:

Товарищи накромсали 1024 таблиц-шардов, номер шарда вычислялся по userid, а дальше смотрели список на какой из 16 серверов ходить за шардом.
 

fixxxer

К.О.
Партнер клуба
Ну да, и коммит, и ролбэк в случае чего, и per-shard сейвпоинты наверное :) замороченный вариант, да
 

grigori

( ͡° ͜ʖ ͡°)
Команда форума
Центральная база для аутентификации, маппинг в ней же. Но на больших (очень больших) объемах это может работать уже не очень хорошо, ну и все же SPOF.
это принцип работы open stack swift, там sqlite, а spof решается коммитом на минимум 2х нодах, но скорость просто удручающая
определять соответствие не для каждого id, а для диапазона оных.
это хорошая идея
если хочется алгоритмически - ketama hash
https://goo.gl/esWncm
нее, так далеко мне улетать не надо
 

fixxxer

К.О.
Партнер клуба
Можно использовать идею с диапазонами и с распределенным nosql-хранилищем: масштабирование чтения решается тупой добивкой слейвов и кэшированием, а двухфазный коммит в кластере при разбиении на диапазоны будет достаточно редким событием, чтобы это стало проблемой.
 

grigori

( ͡° ͜ʖ ͡°)
Команда форума
> двухфазный коммит в кластере при разбиении на диапазоны будет достаточно редким событием, чтобы это стало проблемой.
очень даже проблема, когда front-серверов 50, живут они в виртуалках, и поднимаются-тушатся регулярно под нагрузку,
это проблемы контроля целостности и поиск источника при поднятии нового worker-а

для меня это вопрос общего плана, не только масштабировать медленное чтение - еще, например, решение проблемы деградации по одновременным коннектам redis
 
Последнее редактирование:

fixxxer

К.О.
Партнер клуба
При достаточно крупных диапазонах, достаточном числе slave (r/o) нод и упреждающем создании новых диапазонов - вот не понимаю как это вообще будет проблемой. В опенстеке тормозит? Да опенстек вообще оверинжириренное говно.
У тебя там шардинг по какому id?
 
Последнее редактирование:

grigori

( ͡° ͜ʖ ͡°)
Команда форума
я тебя понял, конечно, ты о постоянном хранилище с растущим объемом и последовательным ID, а я про разные случаи

например, случай такой: нужно некий период времени - от часа до суток, хранить сложно предсказуемый объем данных кусочками - сейчас 10 гб, а в перспективе может быть 200, причем, не в розовых мечтах, и потом все эти данные надо обработать и выкинуть, рассказать детали могу только в телеграмме :)

чем-то напоминает анализ логов, хоть и другое - тут бы clickHouse, но нет его, и не будет,
у swift в кривых руках latency на запись 1.5 сек
в редисах можно, но надо закладывать добавление нод,

и это не единственная задача, где надо размазывать по нодам
 
Последнее редактирование:

MiksIr

miksir@home:~$
Почему бы не попробовать для начала готовые решения? Есть Redis Enterprise. Можно еще посмотреть couchbase, там эти vbucket-ы из коробки.
 

grigori

( ͡° ͜ʖ ͡°)
Команда форума
в вопросе редиса смотрю на sentinel, но обсудить хотел какие есть варианты, задача не одна
 
Сверху