Создание уникальной не угадываемой базы 36 id

Question

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

http://example.com/sd23t9

Какая хорошая и эффективная методика для их генерации с минимальным (или отсутствующим) риском коллизии при вставке их в качестве первичного ключав таблице базы данных?

РЕДАКТИРОВАТЬ:
Писквор делает отличное замечание, конечно.Я должен был упомянуть, что имел в виду минимальный риск столкновения до того, как будет достигнут предел в 36 ^ 6.

РЕДАКТИРОВАТЬ 2
Эх, что, его точка зрения иллюстрировала гораздо больше, чемкурс.Хммм.Возможно, предварительно создать таблицу с идентификаторами (как я уже читал в другом месте)?Будет ли это наиболее эффективным методом, когда я связан с 36 ^ 6 и, возможно, с непоследовательными ограничениями?

Answer 1

Set ID length. // e.g. 6
do {
  Generate a short random ID of the given length
  Collision?
   - No:
      DONE!
   - Yes:
      increase ID length
 } while true

Для любой конечной длины идентификатора всегда существует риск коллизии: исходя из вашего примера, что у вас будет [a-z0-9] {6} идентификаторов, как только у вас будет 2 176 782 336 идентификаторов, возникает коллизияна 100% гарантировано (больше нет доступных ключей).Из-за эффекта дня рождения вы будете сталкиваться намного быстрее.С таким небольшим пространством клавиш нет способа избежать коллизий - вместо этого вам потребуется какое-то восстановление после коллизий.

Вы можете генерировать ID, пока он не столкнется - но это будетстановиться все медленнее по мере заполнения пространства клавиш: представьте себе пространство клавиш [az] с уже занятыми [an] и [pz] - теперь каждый новый случайный идентификатор чаще сталкивается, чем нет;и когда вы полностью заполните пространство клавиш, цикл вообще не прекратится.

Алгоритм, который я предлагаю, может быть слишком осторожным в этом отношении: если он обнаруживает коллизию, он будет пытаться постепенно увеличивать идентификаторы (как предполагается, "collision => невозможно проверить более короткое пространство клавиш ").Несмотря на то, что это неэффективно, скорее всего, в течение нескольких итераций будет найден бесконфликтный идентификатор.

Answer 2

Немного странная идея.Почему бы не использовать перестановки?например, у вас есть набор значений [0-9a-z] при создании первого идентификатора.вы берете первую перестановку в лексикографическом порядке.потом второй и тд.чтобы сделать его менее наглядным, вы можете изменить правила лексикографического порядка.сказать «а» идет после «т» или что-то в этом роде.Вы также можете использовать кортеж вместо полной перестановки.Это обеспечит отсутствие коллизий.

На самом деле эта идея заключается в создании своего рода двусторонней хэш-функции.в основном, если вы можете каким-то образом кодировать число «1», чтобы получить что-то вроде «q8d3dw» и иметь возможность декодировать «q8d3dw» обратно в «1», вы можете быть уверены, что эта функция даст вам уникальные строки для всех значенийот 1 до 36 ^ 6.

Проблема на самом деле при выборе этой функции.Самый простой способ - связать «1» с «000000», «2» с «000001», «12» с «00000b».В основном расположите все доступные строки в лексикографическом порядке и выберите строку в позиции, которая равна идентификатору.Однако об этом легко догадаться.Итак, что вы можете сделать, это искусственно изменить правила лексикографического порядка.Скажем, вместо нормального порядка (0,1,2,3 ... a, b, c ... x, y, z) вы можете немного перемешать его и получить что-то вроде (a, 5, t, 3...).Это даст немного более запутанные результаты.Тем не менее, это все еще будет довольно предположительно, потому что первый элемент будет "aaaaaa", второй "aaaaa5", затем "aaaaat".Таким образом, вы можете еще больше изменить правила лексикографического порядка, делая их зависимыми от положения персонажа.Произнесите заказ для первого идентификатора символа (a, 5, t, 3 ...) для второго (y, 7,3, r ...) и т. Д.

Теперь я не буду публиковатьлюбой псевдокод, так как он будет довольно длинным.И я не советую вам идти по этому пути, если вы не заинтересованы в создании такого рода алгоритмов для развлечения :).Однако, если вы пойдете по этому маршруту, это может быть очень эффективным способом генерации этих идентификаторов без шансов столкновения.И я посоветую вам прочитать том 4 «Искусство компьютерного программирования» доктора Дональда Кнута.Есть много предложений по реализации таких алгоритмов.

Answer 3

@ ivan: вот реализация.

Сначала вам нужно 6 строк, вот код для их генерации:

$letters = range('a', 'z');
$numbers = range(0, 9);
$char_list = array_merge_recursive($letters, $numbers);
for ($i = 0; $i <= 5; $i++) {
    shuffle($char_list);
    echo '$mysterykey[' . $i . "] = '" . implode($char_list) . "';\n";
}

Затем вы можете использовать вывод этого в функции:

function int_to_x36($value) {
    $mysterykey[0] = 'awkbs81t3jyg20v4qhoxzcuenr65dfimlp97';
    $mysterykey[1] = 'ut17qclz96n3msky8jwp4r25gdvhxo0biaef';
    $mysterykey[2] = 'cewszx142nph05mi9ulafbdvy36o8gq7trjk';
    $mysterykey[3] = '37hp28wjdqe5vnlzxofrsybu4im90k16agtc';
    $mysterykey[4] = 'n9a3jksl5ct0eqfzo7pvgyd4m2hiu18xrb6w';
    $mysterykey[5] = 'mq0nbk3zs529gu4tecli8j176vardxoypfwh';

    $x36 = array();
    for ($i = 5; $i >= 0; $i--) {
        $x36[$i] = 0;  
        $y = pow(36, $i);

        if ($value >= $y) {
            $z = floor($value/$y);
            $value = $value - ($z * $y);
            $x36[$i] = $z;
        }   
    }      

    $encoded = '';
    for ($i = 0; $i <= 5; $i++) {
        $encoded .= $mysterykey[$i][$x36[$i]];
    }

    return $encoded;
}

function x36_to_int($value) {
    $mysterykey[0] = 'awkbs81t3jyg20v4qhoxzcuenr65dfimlp97';
    $mysterykey[1] = 'ut17qclz96n3msky8jwp4r25gdvhxo0biaef';
    $mysterykey[2] = 'cewszx142nph05mi9ulafbdvy36o8gq7trjk';
    $mysterykey[3] = '37hp28wjdqe5vnlzxofrsybu4im90k16agtc';
    $mysterykey[4] = 'n9a3jksl5ct0eqfzo7pvgyd4m2hiu18xrb6w';
    $mysterykey[5] = 'mq0nbk3zs529gu4tecli8j176vardxoypfwh';

    $value36 = str_split($value);

    $x36 = array();
    for ($i = 0; $i <= 5; $i++) {
        $x36[$i] = strpos($mysterykey[$i], $value36[$i]);
    }

    $x = 0;
    for ($i = 5; $i >= 0; $i--) {
        $x += $x36[$i] * pow(36, $i);
    }      

    return $x;
}

Я уверен, что что-то упустил, но, похоже, работает.

Answer 4

Если сайт достаточно большой, и я имею в виду большой - как в «нам нужно сотни новых идентификаторов, назначаемых в секунду» (что будет иметь другие проблемы, например, исчерпать пространство клавиш 36 ^ 6 подгод), вы можете предварительно сгенерировать ключи и назначить их.

Ниже приведен пример псевдокода - на таком сайте с большим трафиком вам, вероятно, потребуется оптимизировать используемые алгоритмы.

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

 ID     | used
==============
 000000   0   
 000001   0   
 ...
 zzzzzz   0   

Когда вы получите запрос нановый идентификатор, выберите случайный и отметьте его как используемый (опасность! проблемы параллелизма!):

SELECT ID FROM ids WHERE RAND() LIMIT 1
UPDATE ids SET used = 1, url=what_you_want_shortened WHERE ID = whatever_you_got_from_previous_query

Вы столкнетесь с проблемами эффективности (например, с WHERE RAND(), блокировкой таблицы и т. д.),но это выполнимо.

Answer 5

Большое случайное число и хэш SHA-256, например?Вы можете сократить его позже, чтобы соответствовать вашим потребностям.

Answer 6

Если вы не против ввода .NET DLL, я создал проект, чтобы сделать именно это.Исходный код на GitHub здесь , а двоичные файлы находятся в пакете IdGenerator NuGet .

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

var generator = new Base36IdGenerator(
                numTimestampCharacters: 11, 
                numServerCharacters: 4, 
                numRandomCharacters: 5, 
                reservedValue: "", 
                delimiter: "-", 
                delimiterPositions: new[] {15, 10, 5});

// This instance would give you a 20-character Id, with an
// 11-character timestamp, 4-character servername hash, 
// and 5 character random sequence. This gives you 1.6 million
// hash combinations for the server component, and 60 million
// possible combinations for the random sequence. Timestamp is
// microseconds since epoch:
Console.WriteLine(generator.NewId());
// 040VZC6SL01003BZ00R2

// Argument name specified for readability only:
Console.WriteLine(generator.NewId(delimited: true));
// 040VZ-C6SL0-1003B-Z00R2

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

// 6-characters give you a little over 2 billion possible 
// combinations (36 ^ 6). 7 characters is about 78 billion.
Console.WriteLine(generator.GetRandomString(length: 6));

Основной принцип, лежащий в основе этого:

• Получить микросекунды с эпохи (64-разрядное число)
• Получить случайное число (64-разрядный) от 0 до (36 ^ требуемая длина) (не более 13)
• Получить хэш имени сервера (простой Sha1)
• Преобразовать каждый компонент в строку base-36
• Накладка влево с 0 до желаемой длины

Сам кодировщик Base36 от http://www.stum.de/2008/10/20/base36-encoderdecoder-in-c/.