Python hash_ring не распределяется равномерно, каковы последовательные альтернативы хеширования? - PullRequest
Новая
       33

Python hash_ring не распределяется равномерно, каковы последовательные альтернативы хеширования?

3 голосов
/ 22 августа 2011

Я использую hash_ring пакет для распределения объектов между серверами.Я предполагал, что распределение будет равномерным, поскольку оно основано на хешах MD5.К сожалению, это не так.

Я использую случайные ключи, которые генерируются с помощью uuid.uuid4().Я убедился, что сам MD5 фактически дает равномерное распределение.Тем не менее, когда я распространяю с использованием hash_ring.HashRing, разница между большинством и наименее заполненными сегментами составляет 20-30%.

  • Можно ли улучшить равномерность распределения в hash_ring путем настройки некоторых параметров?
  • Существуют ли другие хорошие альтернативы для последовательного хеширования в Python?

Код, который я использовал для проверки равномерности распределения: 

ring = hash_ring.HashRing(range(8))
for _ in range(10):
     counters = [0]*8
     for _ in range(100000):
         counters[ring.get_node(str(uuid.uuid4()))] += 1
     print counters

который распечатан: 

[11115, 11853, 14033, 11505, 13640, 12292, 12851, 12711]
[11164, 11833, 14024, 11562, 13365, 12302, 13002, 12748]
[11354, 11756, 14017, 11583, 13201, 12231, 13135, 12723]
[11182, 11672, 13936, 11441, 13563, 12240, 13129, 12837]
[11069, 11866, 14045, 11541, 13443, 12249, 12894, 12893]
[11196, 11791, 14158, 11533, 13517, 12319, 13039, 12447]
[11297, 11944, 14114, 11536, 13154, 12289, 12990, 12676]
[11250, 11770, 14145, 11657, 13340, 11960, 13161, 12717]
[11027, 11891, 14099, 11615, 13320, 12336, 12891, 12821]
[11148, 11677, 13965, 11557, 13503, 12309, 13123, 12718]

Для сравнения я сделал непоследовательное хеширование напрямую, используя MD5: 

for _ in range(10):
    counters = [0]*8
    for _ in range(100000):
        counters[int(hashlib.md5(str(uuid.uuid4())).hexdigest(),16)%8] += 1
    print counters

с гораздо лучшими результатами: 

[12450, 12501, 12380, 12643, 12446, 12444, 12506, 12630]
[12579, 12667, 12523, 12385, 12386, 12445, 12702, 12313]
[12624, 12449, 12451, 12401, 12580, 12449, 12562, 12484]
[12359, 12543, 12371, 12659, 12508, 12416, 12619, 12525]
[12425, 12526, 12565, 12732, 12381, 12481, 12335, 12555]
[12514, 12576, 12528, 12294, 12658, 12319, 12518, 12593]
[12500, 12471, 12460, 12502, 12637, 12393, 12442, 12595]
[12583, 12418, 12428, 12311, 12581, 12780, 12372, 12527]
[12395, 12569, 12544, 12319, 12607, 12488, 12424, 12654]
[12480, 12423, 12492, 12433, 12427, 12502, 12635, 12608]

1 Ответ

8 голосов
/ 22 августа 2011

кольцо хеша жертвует "четностью" вашего тестового кода md5, чтобы поддерживать отображения при изменении количества записей. см. http://www.lexemetech.com/2007/11/consistent-hashing.html., так что различия, которые вы видите, связаны не с uuid4 или с ошибкой, а с тем, что библиотека использует алгоритм, отличный от вашего теста.

если вы изменили количество бинов в своем коде md5, вам нужно изменить модульное деление (% 8), и внезапно (почти) все отображения будут изменены. непротиворечивое хеширование позволяет избежать этого. вот почему он не может использовать тот же «очевидно однородный» подход, который вы используете.

Недостатком подхода согласованности является то, что он не совсем однороден (он зависит от хэшей бункеров, а не от хэшей объектов, которые вы кладете в бункеры, поэтому вы не получите «вечерний выход» msgstr "вы ожидаете, когда добавите больше объектов) но вы можете увеличить однородность, увеличив количество точек на кольце, увеличив число «реплик», используемых в коде.

при условии, что окончательный API соответствует значению http://amix.dk/blog/viewEntry/19367, просто установите большее значение для replicas (попробуйте удвоить его или даже просто добавив 1 - вы уже довольно плоские).

обновление: я посмотрел немного больше, и в этом посте http://amix.dk/blog/post/19369 описаны изменения, внесенные в последний код. похоже, что он использует больше реплик, чем 3 (я не совсем понимаю код, извините), и также кажется, что теперь он основан на известной "стандартной" реализации.

...