Алгоритм разбиения файлов между серверами

Question

Я хочу распространять файлы на нескольких серверах и иметь их с очень небольшими накладными расходами. Поэтому я думал о следующем наивном алгоритме:

Если у каждого файла есть уникальный идентификационный номер: 120151 Я думаю о сегментировании файлов с помощью оператора modulo (%). Это работает, если я знаю, что количество серверов заранее:

Пример 2 серверов (стенды для русских серверов):

server 1 : ID % 2 = 0 (contains even IDs) 
    server 2 : ID % 2 = 1 (contains odd IDs) 

Однако, когда мне нужно масштабировать это и добавить больше серверов, мне придется повторно -shuffle файлы, чтобы подчиняться новым правилам алгоритма, и мы этого не хотим.

Пример:

Say добавить сервер 3 в смеси, потому что не может справиться с нагрузкой. Сервер 3 будет содержать файлы, которые соблюдают следующие критерии:
server 3 : ID%3 = 2

Шаг 1 является для перемещения файлов с сервера 1 и сервера 2, где ID%3 = 2. Однако, я должен переместить некоторые файлы между сервером 1 и сервером 2, так что происходит следующее:

server 1 : ID%3 = 0 
server 2 : ID%3 = 1 

Что оптимальный путь для достижения этой цели?

Answer 1

Резюмируя свои требования:

1. Каждый сервер должен хранить (почти) равное количество файлов.
2. Вы должны быть способны определить, какой сервер хранит данный файл, основанный только на идентификаторе файла, в O (1).
3. При добавлении файла требования 1 и 2 должны выполняться.
4. При добавлении сервера вы хотите перенести некоторые файлы на него со всех существующих серверов, чтобы выполнялись требования 1 и 2.

Ваша стратегия при добавлении 3-го сервера (х ID ​​файла):

x%6 Old New 
0 0  0 
1 1  1 
2 0 --> 2 
3 1 --> 0 
4 0 --> 1 
5 1 --> 2 

Альтернативная стратегия:

x%6 Old New 
0 0  0 
1 1  1 
2 0  0 
3 1  1 
4 0 --> 2 
5 1 --> 2 

Чтобы найти сервер после изменения:

0: x%6 in [0,2] 
1: x%6 in [1,3] 
2: x%6 in [4,5] 

Добавление 4-го сервера:

x%12 Old New 
0 0  0 
1 1  1 
2 0  0 
3 1  1 
4 2  2 
5 2  2 
6 0  0 
7 1  1 
8 0 --> 3 
9 1 --> 3 
10 2  2 
11 2 --> 3 

Чтобы найти сервер после изменения:

0: x%12 in [0,2, 6] 
1: x%12 in [1,3, 7] 
2: x%12 in [4,5,10] 
3: x%12 in [8,9,11] 

При добавлении сервера, вы всегда можете создать новую функцию (на самом деле несколько альтернативных функций). Значение делителя для n серверов равно lcm (1,2, ..., n), поэтому it grows very fast.

Обратите внимание, что вы не указали, удалены ли файлы, и если вы планируете его обрабатывать.

Answer 2

Мой подход заключается в использовании согласованного хеширования. Материал из Википедии:

В соответствии хеширование представляет собой особый вид хэширования таким образом, что, когда хэш таблицы изменяется и используются в соответствии хеширования, только K/N ключи должны быть переназначены в среднем, где К числу ключей, а n - количество слотов.

Основная идея заключается в следующем:

1. Подумайте серверов, как расположены на кольце, по приказу их server_id
2. Каждый сервер назначается равномерно распределенной (случайный) идентификатор, например server_id = SHA(node_name).
3. Каждому файлу одинаково присвоен равномерно распределенный идентификатор, например. file_id = SHA(ID), где ID приведен в вашем примере.
4. Выберите сервер, который является «ближайшим» к файлу_ид, то есть где server_id > file_id (начните выбирать с наименьшего server_id).
5. Если нет такого узла, есть обертка вокруг на кольце

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

Таким образом, вы получите сохранить O (1) доступ, и добавление/удаление прямо вперед и не требует перестановок всех файлов:

а) добавление нового сервера, новый узел получает все файлы от следующего узла на кольце с идентификаторами ниже, чем новый сервер

б) удаление сервера, все его файлы приведены к следующему узлу на кольце

Том Уайт graphically illustrated overview объясняет более подробно.