У меня проблема с движением осколка в распределенных системах.
【Проблема】
Первоначально каждый раздел отвечает за произвольное количество шардов. (число может быть произвольным, поскольку система поддерживает перемещение сегмента из одного раздела в другой)
Затем появляется новый раздел, и система нуждается в повторной проверке. Цель состоит в том, чтобы сделать распределение осколков как можно более равномерным, то есть максимальная разница числа осколков между любыми двумя разделами не должна превышать 1, и минимизировать количество движущихся осколков.
Например, скажем, изначально было три раздела, P1, P2 и P3. P1 обработал 5 осколков, P2 обработал 3 осколка, и P3 обработал 1 осколок. Затем появляется новый раздел P4, и система переходит на новый уровень. Результатом восстановления будет то, что один раздел обрабатывает 3 шарда, а три раздела каждый обрабатывает 2 шарда. Теперь возникает вопрос, какой раздел должен обрабатывать 3 осколка. И для этого конкретного случая именно P1 должен обрабатывать 3 осколка, потому что в противном случае перемещение осколка не является минимальным.
【Мое грубое решение】
Теперь у меня есть приблизительное представление о том, что если в разделе Pi i-й самый большой шард, то новое число шардов Pi также должно быть i-м по величине номером в новых номерах шардов. Например, если исходные номера сегментов равны 10, 2, 1 в разделе P1, P2, P3 соответственно, то раздел P1 теперь должен обрабатывать 4 сегмента, а каждый раздел P2, P3, P4 (новый раздел) обрабатывает 3 сегмента.
【Мой вопрос】
Я попробовал несколько примеров, и этот алгоритм работает. Но я не уверен, правильно это или нет. Это правильно? Как это доказать? Спасибо!