Создание удобочитаемых / удобных, коротких, но уникальных идентификаторов

86
  • Необходимо обрабатывать> 1000, но <10000 новых записей в день

  • Невозможно использовать GUID / UUID, номера автоинкремента и т. Д.

  • В идеале должно состоять из 5 или 6 символов, конечно, может быть альфа

  • Хотел бы повторно использовать существующие, хорошо известные алгоритмы, если они доступны

Что-нибудь там?

Кумар
источник
Почему бы не использовать автоматически увеличивающиеся INT или BIGINT? Он, наверное, самый читаемый и легко справляется с объемом.
Malk
на вопрос выше, пытаясь сохранить максимальное количество символов 5/6 и поддерживать до 9999 новых рекордов в день
Кумар
@Kumar - Что, если вам нужно сделать более 9999 записей за один день? Предлагаемое вами решение не кажется разумным.
ChaosPandion 03
@ChaosPandion: Я думаю, что это скорее приблизительные предположения о нагрузке / трафике, чем жесткие границы. Я не уверен, зачем вам устанавливать произвольное ограничение на количество ежедневных транзакций.
Пол Сасик
Вы можете закодировать его в базу 64 и использовать это. Я не уверен, что вы могли бы уменьшить его меньше, чем это, и по-прежнему использовать читаемые символы. Но я бы сказал, что база 64 гораздо менее читабельна, чем база 32, потому что она требует добавления дополнительного квалификатора к большинству символов (заглавная f, нижняя o, нижняя o по сравнению с просто f, oo).
Malk

Ответы:

118

База 62 используется командами tinyurl и bit.ly для сокращенных URL. Это хорошо известный метод создания «уникальных», удобочитаемых идентификаторов. Конечно, вам нужно будет хранить созданные идентификаторы и проверять наличие дубликатов при создании, чтобы гарантировать уникальность. (См. Код внизу ответа)

Базовые 62 показателя уникальности

5 символов в базе 62 дадут вам 62 ^ 5 уникальных идентификаторов = 916,132,832 (~ 1 миллиард). При 10 тыс. Идентификаторов в день вы будете в порядке в течение более 91 тыс. Дней.

6 символов в базе 62 дадут вам 62 ^ 6 уникальных идентификаторов = 56 800 235 584 (56+ миллиардов). При 10 тысячах идентификаторов в день вы будете в порядке в течение 5+ миллионов дней.

Базовые 36 показателей уникальности

6 символов дадут вам 36 ^ 6 уникальных идентификаторов = 2,176,782,336 (2+ миллиарда)

7 символов дадут вам 36 ^ 7 уникальных идентификаторов = 78,364,164,096 (78+ миллиардов)

Код:

public void TestRandomIdGenerator()
{
    // create five IDs of six, base 62 characters
    for (int i=0; i<5; i++) Console.WriteLine(RandomIdGenerator.GetBase62(6));

    // create five IDs of eight base 36 characters
    for (int i=0; i<5; i++) Console.WriteLine(RandomIdGenerator.GetBase36(8));
}

public static class RandomIdGenerator 
{
    private static char[] _base62chars = 
        "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"
        .ToCharArray();

    private static Random _random = new Random();

    public static string GetBase62(int length) 
    {
        var sb = new StringBuilder(length);

        for (int i=0; i<length; i++) 
            sb.Append(_base62chars[_random.Next(62)]);

        return sb.ToString();
    }       

    public static string GetBase36(int length) 
    {
        var sb = new StringBuilder(length);

        for (int i=0; i<length; i++) 
            sb.Append(_base62chars[_random.Next(36)]);

        return sb.ToString();
    }
}

Выход:

z5KyMg
wd4SUp
uSzQtH
UPrGAT
UIf2IS

QCF9GNM5
0UV3TFSS
3МГ91ВКП
7НТРФ10Т
AJK3AJU7
Пол Сасик
источник
3
выглядит фантастически, что-нибудь без учета регистра?
Кумар
2
Если вы хотите избежать чувствительности к регистру, вы можете использовать базу 36: codeproject.com/Articles/10619/Base-36-type-for-NET-C, но чтобы получить столько перестановок в качестве базы 62, вам нужно будет использовать больше символов в вашем МНЕ БЫ. Это компромисс. Или вы можете попробовать использовать другие символы, кроме альфы, но это будет некрасиво для пользователей.
Пол Сасик
2
здесь stackoverflow.com/questions/9543892/… и большое спасибо
Кумар
11
Одна мысль. Возможно, уберите гласные, чтобы предотвратить случайное возникновение нецензурных слов. Особенно, если это публично.
Дэмиен Сойер,
4
В зависимости от того, где вы это используете (особенно если ожидается, что люди будут читать и повторно вводить коды), вы можете рассмотреть возможность исключения из рассмотрения часто путающих символов: 0 / O и I / l / 1. В некоторых случаях это можно смягчить правильным выбором шрифта, но я не могу сказать из вопроса, будет ли OP контролировать это.
GrandOpener
17

Я рекомендую http://hashids.org/, который преобразует любое число (например, идентификатор БД) в строку (с использованием соли).

Это позволяет декодировать эту строку обратно в число. Таким образом, вам не нужно хранить его в базе данных.

Имеет библиотеки для JavaScript, Ruby, Python, Java, Scala, PHP, Perl, Swift, Clojure, Objective-C, C, C ++ 11, Go, Erlang, Lua, Elixir, ColdFusion, Groovy, Kotlin, Nim, VBA, CoffeeScript и для Node.js и .NET.

Слава
источник
1
Можете ли вы предоставить какие-либо другие варианты, аналогичные вашему предложению? - - Это очень интересно. Я хотел бы знать, есть ли в PostgreSQL такие параметры по умолчанию.
Лео Леопольд Герц 준영
1
Вот его версия для .NET , но не могли бы вы объяснить, как он работает без необходимости хранить его в базе данных? Могу ли я генерировать только уникальные случайные числа без ввода чисел и без соли?
Shaijut
@Slawa Мне нужно что-то вроде хешей для .NET, но окончательный хеш будет храниться в db в столбце с фиксированной длиной, можно ли сказать, что всегда генерировать хеш с максимальной длиной N?
Anon Dev
6

У меня были те же требования, что и у ОП. Я просмотрел доступные библиотеки, но большинство из них основаны на случайности, и я этого не хотел. На самом деле я не мог найти ничего, что не было бы основано на случайном и все еще очень короткое ... Так что я закончил свой собственный, основанный на методе, который использует Flickr , но модифицированный, чтобы требовать меньшей координации и допускать более длительные периоды автономной работы.

Короче говоря:

  • Центральный сервер выдает блоки идентификаторов по 32 идентификатора каждый.
  • Генератор локального идентификатора поддерживает пул блоков идентификатора для генерации идентификатора каждый раз, когда он запрашивается. Когда в пуле заканчивается, он извлекает с сервера дополнительные блоки идентификаторов, чтобы снова заполнить его.

Недостатки:

  • Требуется централизованная координация
  • Идентификаторы более или менее предсказуемы (меньше, чем обычные идентификаторы БД, но они не случайны)

Преимущества

  • Остается в пределах 53 бит (максимальный размер Javascript / PHP для целых чисел)
  • очень короткие идентификаторы
  • База 36 закодирована так, что людям очень легко читать, писать и произносить
  • Идентификаторы могут генерироваться локально в течение очень долгого времени, прежде чем снова потребуется связь с сервером (в зависимости от настроек пула)
  • Теоретически шансов столкновений нет

Я опубликовал как библиотеку Javascript для клиентской стороны, так и реализацию сервера Java EE. Внедрение серверов на других языках также должно быть простым.

Вот проекты:

suid - Распределенные сервисные уникальные идентификаторы, короткие и удобные

suid-server-java - реализация Suid-сервера для стека технологий Java EE.

Обе библиотеки доступны по либеральной лицензии Creative Commons с открытым исходным кодом. Надеюсь, это поможет кому-то другому в поиске коротких уникальных идентификаторов.

Стейн де Витт
источник
Не могли бы вы сравнить stackoverflow.com/a/29372036/54964 с вашим предложением suid?
Лео Леопольд Герц,
1
Он основан на случайных числах. На самом деле, это довольно здорово. Но ваши удостоверения личности не будут такими короткими, как могут быть. Я написал SUID, чтобы начать нумерацию с 1, поэтому вы начнете с очень коротких идентификаторов. Подумайте, 3 или 4 символа. Кроме того, у него есть некоторые другие приятные преимущества - иметь (примерно) постепенно упорядоченные идентификаторы, помимо того, что они начинаются с действительно коротких.
Stijn de Witt
3

Я использовал базу 36, когда решил эту проблему для приложения, которое разрабатывал пару лет назад. Мне нужно было сгенерировать удобочитаемый разумно уникальный номер (во всяком случае, в текущем календарном году). Я решил использовать время в миллисекундах от полуночи 1 января текущего года (чтобы каждый год метки времени могли дублироваться) и преобразовал его в число с основанием 36. Если разрабатываемая система сталкивалась с фатальной проблемой, она генерировала число с основанием 36 (7 символов), которое отображалось конечному пользователю через веб-интерфейс, который затем мог передать возникшую проблему (и номер) сотруднику службы технической поддержки (который затем можно было бы использовать его, чтобы найти точку в журналах, где началась трассировка стека). Число вроде 56af42g7пользователю бесконечно легче читать и передавать, чем временная метка, например 2016-01-21T15: 34: 29.933-08: 00, или случайный UUID, например 5f0d3e0c-da96-11e5-b5d2-0a1d41d68578 .

Уоррен Смит
источник
4
Не могли бы вы предоставить псевдокод в структурированной форме для вашего предложения? Звучит интересно.
Лео Леопольд Герц 준영
0

Мне очень нравится простота кодирования GUID с использованием формата Base64 и усечения завершающего ==, чтобы получить строку из 22 символов (требуется одна строка кода, и вы всегда можете преобразовать ее обратно в GUID). К сожалению, он иногда включает символы + и /. Хорошо для базы данных, не очень хорошо для URL-адресов, но это помогло мне оценить другие ответы :-)

С https://www.codeproject.com/Tips/1236704/Reducing-the-string-Length-of-a-Guid Кристиана ван Бергена

Мы обнаружили, что преобразование Guid (16 байтов) в представление ASCII с использованием Base64 привело к полезному и все еще уникальному идентификатору сообщения, состоящему всего из 22 символов.

var newGuid = Guid.NewGuid();
var messageID = Convert.ToBase64String(newGuid.ToByteArray());

var message22chars = Convert.ToBase64String(Guid.NewGuid().ToByteArray()).Substring(0,22);

Например: Guid 'e6248889-2a12-405a-b06d-9695b82c0a9c' (длина строки: 36) получит представление Base64: 'iYgk5hIqWkCwbZaVuCwKnA ==' (длина строки: 24)

Представление Base64 заканчивается символом '=='. Вы можете просто обрезать их, не влияя на уникальность. Оставляя вам идентификатор длиной всего 22 символа.

Экус
источник