Могу ли я сделать uuid более случайным? - PullRequest
0 голосов
/ 04 июля 2011

У меня есть программа, которая отправляет сообщения отдельным процессам. Мне нужно сбалансировать нагрузку, но не очень точно, почти то же самое число в порядке. Поскольку каждое сообщение имеет поле uuid, я хочу сделать это по значению uuid. После того, как я проверил случайность uuid, я обнаружил, что она не так случайна, как я ожидал. У меня есть последний и первый около 80% разницы. Это недопустимо, поэтому я хочу знать, есть ли алгоритм, который может сделать его более случайным.

Вот мой тестовый код.

import uuid
from collections import Counter

COUNT = 3000

def b(length):
    holder = []
    for i in xrange(COUNT):
        holder.append(str(uuid.uuid4())[:length])
    return Counter(holder)

def num(part_count):
    sep = 0xffffffffffffffffffffffffffffffff / part_count
    parts = []
    for i in xrange(COUNT):
#        str_hex = str(uuid.uuid4())[:4]
        num = int(uuid.uuid4().hex,16)
        divide = num/sep
        if divide == part_count:
            divide = part_count - 1
        parts.append(divide)
    return Counter(parts)

if __name__ == "__main__":
    print num(200) 

и я получаю вывод, как это:

Counter({127L: 29, 198L: 26, 55L: 25, 178L: 24, 184L: 24, 56L: 23, 132L: 23, 143L: 23, 148L: 23, 195L: 23, 16L: 21, 30L: 21, 44L: 21, 53L: 21, 97L: 21, 158L: 21, 185L: 21, 13L: 20, 146L: 20, 149L: 20, 196L: 20, 2L: 19, 11L: 19, 15L: 19, 19L: 19, 46L: 19, 58L: 19, 64L: 19, 68L: 19, 70L: 19, 89L: 19, 112L: 19, 118L: 19, 128L: 19, 144L: 19, 156L: 19, 192L: 19, 27L: 18, 41L: 18, 42L: 18, 51L: 18, 54L: 18, 85L: 18, 87L: 18, 88L: 18, 93L: 18, 94L: 18, 104L: 18, 106L: 18, 115L: 18, 4L: 17, 22L: 17, 45L: 17, 59L: 17, 79L: 17, 81L: 17, 105L: 17, 125L: 17, 138L: 17, 150L: 17, 159L: 17, 167L: 17, 194L: 17, 3L: 16, 18L: 16, 28L: 16, 31L: 16, 33L: 16, 62L: 16, 65L: 16, 83L: 16, 111L: 16, 123L: 16, 126L: 16, 133L: 16, 145L: 16, 147L: 16, 163L: 16, 166L: 16, 183L: 16, 188L: 16, 190L: 16, 5L: 15, 6L: 15, 9L: 15, 23L: 15, 26L: 15, 34L: 15, 35L: 15, 38L: 15, 69L: 15, 73L: 15, 74L: 15, 77L: 15, 82L: 15, 86L: 15, 107L: 15, 108L: 15, 109L: 15, 110L: 15, 114L: 15, 136L: 15, 141L: 15, 142L: 15, 153L: 15, 160L: 15, 169L: 15, 176L: 15, 180L: 15, 186L: 15, 0L: 14, 1L: 14, 36L: 14, 39L: 14, 43L: 14, 60L: 14, 71L: 14, 72L: 14, 76L: 14, 92L: 14, 113L: 14, 131L: 14, 135L: 14, 157L: 14, 171L: 14, 172L: 14, 181L: 14, 189L: 14, 7L: 13, 17L: 13, 20L: 13, 24L: 13, 25L: 13, 32L: 13, 47L: 13, 49L: 13, 101L: 13, 102L: 13, 117L: 13, 121L: 13, 122L: 13, 124L: 13, 130L: 13, 151L: 13, 152L: 13, 165L: 13, 179L: 13, 14L: 12, 21L: 12, 29L: 12, 50L: 12, 63L: 12, 67L: 12, 80L: 12, 84L: 12, 90L: 12, 91L: 12, 96L: 12, 120L: 12, 129L: 12, 139L: 12, 140L: 12, 182L: 12, 193L: 12, 197L: 12, 52L: 11, 75L: 11, 78L: 11, 103L: 11, 116L: 11, 119L: 11, 134L: 11, 137L: 11, 161L: 11, 173L: 11, 12L: 10, 37L: 10, 66L: 10, 98L: 10, 100L: 10, 162L: 10, 170L: 10, 175L: 10, 177L: 10, 187L: 10, 191L: 10, 199L: 10, 48L: 9, 155L: 9, 164L: 9, 174L: 9, 10L: 8, 95L: 8, 99L: 8, 168L: 8, 8L: 7, 40L: 7, 57L: 7, 61L: 7, 154L: 6})

последний - 6, первый - 29, разница почти в 5 раз

Ответы [ 4 ]

8 голосов
/ 04 июля 2011

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

import hashlib
actually_random = hashlib.sha1(uuid).digest()
6 голосов
/ 04 июля 2011

Ваша методология тестирования не имеет никакого смысла (см. Ниже). Но сначала это реализация uuid4:

def uuid4():
    """Generate a random UUID."""

    # When the system provides a version-4 UUID generator, use it.
    if _uuid_generate_random:
        _buffer = ctypes.create_string_buffer(16)
        _uuid_generate_random(_buffer)
        return UUID(bytes=_buffer.raw)

    # Otherwise, get randomness from urandom or the 'random' module.
    try:
        import os
        return UUID(bytes=os.urandom(16), version=4)
    except:
        import random
        bytes = [chr(random.randrange(256)) for i in range(16)]
        return UUID(bytes=bytes, version=4)

И случайность, возвращаемая libuuid (вызовом ctypes), os.urandom и random.randrange, должна быть достаточной для большинства не криптографических вещей.

Редактировать : Хорошо, я думаю, почему ваша методология тестирования нарушена: подсчитываемое вами число (divide) смещено двумя способами: во-первых, результат делится число, которое не является степенью двойки (в данном случае 200), что вводит смещение по модулю. Во-вторых, if divide == part_count: divide = part_count - 1 вводит больше смещения.

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

2 голосов
/ 04 июля 2011

Ну, UUID не должен быть случайным, он должен быть уникальным: обычно он основан на имени компьютера / IP-адресе, дате и тому подобном: цель состоит не в том, чтобы сделать его случайным, а в том, чтобы убедиться, чточто два последовательных вызова предоставят два разных значения и что идентификатор с разных компьютеров не будет конфликтовать.Если вам нужна более подробная информация, вы можете взглянуть на официальную спецификацию (RFC 4122)

Теперь, если ваш балансировщик нагрузки хочет использовать это в качестве критерия для балансировки, я думаю, что ваш дизайн имеет недостатки,Если вам нужна лучшая случайность, вы можете ее хешировать (например, sha-256), тем самым разбавляя небольшую случайность среди всех битов (вот что делает хэш)

1 голос
/ 04 июля 2011

Только то, что что-то не выглядит случайным, не означает, что это не так.

Может быть, для человеческого глаза (и ума) некоторые последовательности выглядят менее случайными, чем другие, но это не так.Когда вы бросаете кости 10 раз, вероятность броска 2-5-1-3-5-1-3-5-2-6 равна броску 1-1-1-1-1-1-1-1-1-1 или 1-2-3-4-5-6-1-2-3-4.Хотя два последних примера кажутся менее случайными, это не так.

Не пытайтесь улучшить случайные генераторы, поскольку, скорее всего, вы только ухудшите вывод.

Например: Вы хотитегенерировать случайную последовательность, и вам не кажется, что один байт появляется чаще, чем другой.Следовательно, вы отклоняете все последовательности с повторяющимися байтами (или байтами, повторяемыми более n раз), чтобы обеспечить большую случайность.На самом деле, вы делаете свои последовательности менее случайными.

...