Динамический шардинг

Продолжение развития идеи из моего предыдущего поста о динамическом перераспределении записей при шардинге.

Как заметил AnatoLoy, в предложенном мной решении есть один серьезный недостаток - страдает балансировка нагрузки. Однако, мне кажется, что решить эту проблему не так уж и сложно :) Нужно вместо возвращения номера сервера возвращать параметры функции (а именно - количество серверов).

Допустим у нас M серверов и мы распределяем записи по серверам используя функцию

m = n % M

, где m это номер сервера на котором хранится запись, n это целочисленный идентификатор записи (ID) , а % это операция "остаток от целочисленного деления".

То есть говоря проще, для каждой записи номер сервера мы узнаем вычисляя остаток от деления номера записи (точнее идентификатора записи) на количество серверов.

Теперь допустим нам необходимо добавить новый сервер (вообще говоря мы можем добавить их сразу несколько, но для простоты пока возьмем один). Как сделать чтобы процесс перераспределения уже существующих данных между серверами мог происходит параллельно основному обслуживанию, не останавливая основное обслуживание?

Мы запоминаем общее количество существующих записей на момент начала процесса перераспределения (назовем это количество K). Создаем специальную таблицу, в которой запоминаем это число К (или каким нибудь иным надежным образом запоминаем его в системе). Далее мы осуществляем обслуживание следующим образом - мы сразу начинаем работать так как будто мы уже осуществили перераспределение данных и у нас уже действительно работает M+1 сервер (или M + N, где N количество новых серверов, если добавляем не один сервер а сразу много). Но, разумеется, мы делаем это не для всех записей, а только для тех которые для нас "новые", то есть добавились уже после момента добавления нового сервера, то есть для тех записей у которых номер записи n >= K. Для таких записей (у которых n>=K) мы используем следующую функцию (точнее значения в той же функции):

m = n % (M + N)

, где N это количество новых (добавляемых) серверов, например N=1, если мы добавляем всего один сервер.

Параллельно с этим мы запускаем фоновый процесс перераспределения записей. Делаем мы это с "конца", то есть сначала перераспределяем записи с номерами от K-j до K, где j - количество записей перераспределяемых за одну итерацию. В принципе j может быть 1, но лучше (выгоднее) всего взять j=M+N, то есть общему количеству серверов, тем самым итерация будет охватывать сразу все сервера, но при этом на каждом сервере будет происходит миграция одной записи. Говоря проще, сначала мы перераспределяем самые последние записи на момент перед добавлением серверов, потом более ранние, и так до самых первых. Как только мы завершили одну итерацию перераспределения для j записей, мы уменьшаем К на это количество записей. То есть мы сохраняем значение K=K-j. И продолжаем процесс до тех пор пока K не станет равным нулю, то есть пока все записи не будут перераспределены между новыми и старыми серверами по новой формуле.

Конечно, реализовать такой процесс перераспределения не просто и для этого потребуется хорошее проектирование системы, учет возможных сбоев и так далее. Но в идеале, такой процесс способен осуществлять динамический рост количества серверов, без остановки обслуживания.

Еще один нюанс - на момент начала перераспределения на существующих серверах должен существовать определенный запас свободного места под новые записи пока осуществляется итерация перераспределения. Но этот требуемый свободный объем, в принципе, не очень большой - как только мы осуществим первую итерацию на сервере сразу появится немного больше свободного места (определенное количество старых записей мигрирует на новые сервера), и чем больше итераций мы успеем осуществить тем больше свободного места будет появляться. Главное успеть перераспределить пока есть место :) Разумеется, чем больше свободного места у нас еще есть на старых серверах, тем будет спокойнее на душе :)

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

Оптимальнее всего, думаю, будет объединить две эти стратегии в одну еще более сложную и комплексную. То есть в критические моменты мы осуществляем вторую стратегию, а в фоновом режиме, когда у нас есть для этого ресурсы, мы плавно осуществляем первую стратегию, причем возможно не сразу для всего общего набора серверов, а для некоего подмножества, которое может постепенно расти, вытесняя собой первую стратегию. Разумеется, такая комплексная стратегия еще больше усложняет архитектуру системы, но в идеале игра может стоить свечей :)