Прозрачное перераспределение данных при добавлении нового сегмента (сервера) в шардинге

Почитал довольно интересный материал о масштабировании баз данных. Больше всего понравился метод так называемого шардинга. Это когда большую базу данных разбивают на мелкие части (части соответственно помещаются на отдельные сервера) таким образом, что всегда известно в какой из частей находится необходимая нам запись. Достигается это с помощью некой математической функции от первичного ключа - например, остаток от деления первичного ключа (или его эквивалента, например hash-функции для строк) на количество серверов. Очень хороший метод. Единственный недостаток - при добавлении нового сервера возникает необходимости полного перераспределения данных между частям.

(Пока что это был краткий пересказ прочитанной статьи, дальше идут уже мои собственные идеи)

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

Суть метода очень проста. Работать такой метод может пока только на простых синетических первичных ключах типа "автоинкремент" (ну то есть каждая новая запись имеет некий порядковый номер который больше предудущей записи, это для тех кто не совсем понимает о чем идет речь). Так вот, все что необходимо сделать при подключении очередного нового сервера шардинга, это изменить функцию распределения (вычисления номера сервера от значения первичного ключа) таким образом что после известного нам (а именно последнего перед добавлением нового сервера) значения первичного ключа N и до следующего известного значения M (которое будет равно N + K, где K - количество записей в одном сегменте шардинга), функция
будет вести себя иначе, а именно - будет возвращать не остаток от деления как раньше, а просто номер нового сервера.

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

Возможно, будут необходимы дополнительные объяснения сути моего предложения, и даже, возможно, будет необходимо нарисовать какие либо схемы. Но пока, мне кажется, приведенного выше краткого объяснения более менее достаточно, если конечно вообще понимать что такое шардинг. По-крайней мере, у меня такое впечатление. Я могу и заблуждаться, даже вообще о сути явления шардинга. Возможно даже что мой метод просто чистый бред. Всё может быть.

Конечно, это несколько усложняет алгоритм, но не настолько чтобы как то существенно снизить эффективность обработки данных. При росте количества добавленных серверов, алгоритм конечно будет еще более усложняться, но нам ничто не мешает автоматизировать функцию добавления серверов и соответсвующего изменения функции. Более того, мы можем сделать функцию динамической и менять её (функцию) паралельно с выполнением процесса перераспределения. Когда процесс перераспределения будет завершен, мы окончательно возвращаемся к классической функции "остаток от деления на количество серверов", до следующего нового сервера, когда мы опять вводим "исключение из правил" для нового сервера и запускаем процесс перераспределения. Это позволит нам добиться полностью прозрачного процесса наращивания шардинга.

Причем процесс изменения функции мы можем реализовать путем использования упомянутого в статье другого способа шардинга, а именно - использованием таблицы соотвествия "ключ-значение". Только хранить мы можем в таблице диапазоны значений ключа и соответствующие диапазонам признак что мы используем для этого диапазона - алгоритм или статическое значение для нового номера сервера. Таких диапазонов может быть несколько и такая таблица удобна именно тем что мы можем гибко и быстро менять эти диапазоны.

Сам процесс перераспределения мы тоже можем разбить на три этапа:

1. Добавление записей оттуда где они были раньше туда где они должны быть теперь (для всех сегментов) - на этом этапе у нас возникает дублирование записей но это временное явление.
2. После завершения предыдущего этапа мы можем смело переключаться на новый алгоритм поиска записей - все необходимое у нас для этого уже есть там где нам нужно (мы как раз об этом и позаботились на первом этапе).
3. На последнем этапе остается просто удалить уже не нужное оттуда где оно было раньше и тем самым устранить возникшее дублирование записей.

И самое интересное, мы можем разбить перераспределение на много мелких последовательных итераций из трех указанных выше стадий цикла: скопировали X записей, модифицировали алгоритм, удалили Х записей, скопировали X записей, модифицировали алгоритм, удалили X записей, ... и так до полного завершения перераспределения.

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

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

Если вопросы остались, рад буду попробовать на них ответить.