Генерация не совсем глобального уникального идентификатора

Question

Я нашел несколько разных вопросов о генерации UID, но, насколько я могу судить, мои требования здесь несколько уникальны (ха).

Подводя итог: мне нужно сгенерировать очень короткий идентификатор, который будет "локально" уникальным, но не должен быть "глобально" или "универсально" уникальным. Ограничения основаны не только на эстетических или космических проблемах, но и на том факте, что они по существу используются в качестве аппаратного тега и зависят от аппаратных ограничений. Вот технические характеристики:

Жесткие требования

• Идентификатор должен содержать только десятичные цифры (базовые данные - BCD);
• Максимальная длина идентификатора составляет 12 символов (цифр).
• Должен быть сгенерирован в автономном режиме - база данных / веб-соединение не всегда доступно!

Мягкие требования

• Мы хотели бы начать с календарного года и / или месяца. Так как это приводит к потере большого количества энтропии, я не возражаю против компромисса по этому вопросу или полностью его отмену (при необходимости).
• Идентификаторы, генерируемые конкретной машиной, должны отображаться последовательно.
• идентификаторы не должны сортироваться по машине - например, совершенно нормально, чтобы машина 1 выплевывала [123000, 124000, 125000], а машина 2 выплевывала [123500, 123600, 124100 ].
• Однако, чем последовательнее выглядишь в коллективном смысле, тем лучше. Набор идентификаторов, таких как [200912000001, 200912000002, 200912000003, ...] был бы идеальным, хотя, очевидно, он не масштабируется на нескольких машинах.

Сценарий использования:

• Идентификаторы в рамках этой схемы будут генерироваться из 10, может быть, максимум 100 различных машин.
• Всего будет сгенерировано не более нескольких миллионов идентификаторов.
• Параллельность чрезвычайно низкая. Один компьютер не будет генерировать идентификаторы чаще, чем каждые 5 минут или около того. Также, скорее всего, не более 5 машин одновременно будут генерировать идентификаторы в течение одного часа или даже в один и тот же день. Я ожидаю, что в течение одного дня на данной машине будет сгенерировано менее 100 идентификаторов, а для всех машин - менее 500.
• Небольшое количество машин (3-5), скорее всего, будет отвечать за создание более 80% идентификаторов.

Я знаю, что можно закодировать временную метку с точностью до 100 мс или даже с точностью до 10 мс, используя менее 12 десятичных цифр, что более чем достаточно, чтобы гарантировать «достаточно уникальный» идентификатор для этого приложения. Причина, по которой я спрашиваю это здесь на SO, заключается в том, что я действительно хотел бы либо включить туда удобочитаемый год / месяц, либо кодировать некоторую часть информации об исходной машине, либо и то и другое.

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

(P.S. Мой "родной" язык - C #, но код на любом языке или даже псевдокод хорошо, если у кого-то есть какие-нибудь блестящие идеи.)

Обновление:

Теперь, когда у меня была возможность поспать на нем, я думаю, что на самом деле я собираюсь использовать кодировку метки времени по умолчанию и позволить отдельным установкам переключаться на последовательный идентификатор компьютера, определяя их собственный 2- или 3-значный идентификатор машины. Таким образом, клиенты, которые хотят связываться с идентификатором и упаковывать удобочитаемую информацию, могут самостоятельно выбрать способ обеспечения уникальности, и мы не несем ответственности за неправильное использование. Возможно, мы поможем, предоставив серверную утилиту для обработки идентификаторов компьютеров, если они выполняют все онлайн-установки.

Answer 1

"Причина, по которой я спрашиваю это здесь ТАК, потому что я бы очень хотел либо попробуйте включить человекочитаемый год / месяц там или закодировать некоторую часть информации о исходный компьютер или оба. "

Позвольте мне начать с того, что я уже имел дело с этим, и попытка сохранить полезную информацию в серийный номер - ПЛОХАЯ идея в долгосрочной перспективе. Серийный номер устройства должен быть бессмысленным. Также как первичный ключ записи в базе данных должен быть бессмысленным.

В тот момент, когда вы начинаете пытаться вставить реальные данные в свой серийный номер, вы просто добавляете в него BUSINESS LOGIC и будете вынуждены поддерживать их, как любой другой фрагмент кода. Будущее тебя будет ненавидеть мимо тебя. Поверь мне в этом. ; О)

Если вы попытаетесь сохранить значения даты / времени, то вы потеряете числовое пространство с недопустимыми временем / датами. Например, у вас никогда не будет ничего больше 12 в поле месяца.

Прямой счетчик времени / единицы времени был бы лучше, но для машины, которая генерирует только несколько идентификаторов в минуту, вы все равно будете тратить много места.

12 цифр не много места. Посмотрите на страницу VIN в Википедии. Места только для нескольких производителей, всего несколько тысяч автомобилей. Теперь они повторно используют VIN, потому что им не хватило места, упаковав в него смысл.

http://en.wikipedia.org/wiki/VIN

Это не означает, что ВСЕ значения в серийном номере плохие, просто держите его строго ограниченным, чтобы убедиться, что числа не совпадают.

Как то так ...

• Позиция 1-3: 999 Машины
• Позиция 4-12: порядковые номера

Это ALL , вам нужно избегать столкновений. Если вы добавляете цифру местоположения, вы попадаете в 11 мест.

Извините, если это звучит как напыщенная речь. Я много занимаюсь производством электроники и различных обрабатываемых деталей. Он никогда не заканчивался долгое время, если не было доступно много свободного пространства или вторичного тега (который -wow- обеспечивает необходимое пространство идентификаторов, упомянутое ранее)

Answer 2

Как насчет yyMMddhhmmID?

yy = two-digit year
MM = two-digit month
dd = two-digit day
hh = two-digit hour (24-hour time)
mm = two-digit minute
ID = machine-specific ID

Пример: 0912113201 с машины с ID = 01.

В качестве альтернативы (если вам не нравятся двузначные годы (Y2Klol)), как насчет yyyyMMIDxxxx?

yyyy = four-digit year
MM = two-digit month
ID = machine-specific ID
xxxx = sequentially-incremented integer

Пример: 200912010001 от машины с ID = 01.

Как вы сказали, каждая машина будет генерировать только один максимум идентификатора каждыйпять минут, это дает вам место для 8 928 (24 * 31 * 60/5 = 8928) идентификаторов в месяц, которые вписываются в xxxx.Здесь вы можете сжать год до трехзначного года yyy (например, 009), если вам нужна дополнительная цифра в последовательности xxxx или идентификатор машины.

Обе эти метки времени подходят /Идентификатор машины, как вы просили.

Нам всем нравится конкретный код:

class Machine {
    public int ID { get; private set; }
    public Machine(int id) {
        ID = id;
    }
}

 class IdentifierGenerator {
    readonly Machine machine;
    int seed;
    const int digits = 4;
    readonly int modulus;
    readonly string seedFormat;
    public IdentifierGenerator(Machine machine) {
        this.machine = machine;
        this.modulus = (int)Math.Pow(10, digits);
        this.seedFormat = new string('0', digits);
    }

    public string Generate() {
        string identifier = DateTime.Now.ToString("yyyyMM") 
                                + machine.ID.ToString("00") 
                                + seed.ToString(seedFormat);
        seed = (seed + 1) % modulus;
        return identifier;
    }
}

Machine m = new Machine(1);
IdentifierGenerator gen = new IdentifierGenerator(m);
Console.WriteLine(gen.Generate());
Console.WriteLine(gen.Generate());

Выходы:

200912010000
200912010001

Answer 3

При установке программного обеспечения также установите файл идентификатора машины / ключ реестра, который содержит уникальный числовой идентификатор. Поскольку у вас есть только несколько машин, это не должно занимать более 3 или 4 цифр. Используйте их как цифры MS. Генерируйте оставшиеся цифры последовательно, начиная с 1.

Answer 4

Я понял, что вы разрабатываете для Windows (перечитайте ваш комментарий о «MSI / EXE» в ответ на ответ Джейсона). Таким образом, вы можете использовать интерфейс WMI или аналогичный, чтобы получить какой-то уникальный аппаратный атрибут (например, серийный номер процессора или жесткого диска или MAC-адрес сетевой карты), на котором будет основан уникальный идентификатор компьютера. Альтернативой также может быть использование уникального серийного номера оборудования, которое вы сами разрабатываете (если оно есть).

Скорее всего, это будет дольше, чем вам нужно, поэтому вы можете потенциально обрезать или хэшировать его, чтобы уменьшить его (скажем) до 16 бит или около того, и использовать его в качестве идентификатора вашей машины. Очевидно, что это может привести к коллизиям, но небольшое количество машин (~ 100) означает, что это маловероятно, а использование усеченного вывода криптографического хэша (скажем, MD5) делает это еще меньше.

Затем, поскольку у вас есть (наиболее вероятно, уникальный) идентификатор машины, вы можете генерировать практически уникальные идентификаторы, используя подходы, перечисленные в других ответах.

Answer 5

Используйте MAC-адрес устройства в качестве идентификатора МАШИНЫ. Вы можете использовать это для кодирования вашей временной метки, то есть через XOR, или можете добавить / добавить ее к сгенерированному сериализованному коду.

Answer 6

«Один компьютер не будет генерировать идентификаторы чаще, чем каждые 5 минут или около того» * ​​1001 *

Предполагая, что это правда, просто используйте отметку времени. (32-битное время Unix имеет 10 десятичных цифр, но закончится в 2038 году)

Но я думаю, что довольно оптимистично предположить, что столкновения не будет.

«Идентификаторы, генерируемые конкретным компьютером, должны отображаться последовательно.»

Тогда единственный вариант - использовать порядковый номер.

Что на самом деле не соответствует тому, что вы говорите в последующих ограничениях?

Объединение дополненной версии идентификатора узла для получения уникальных значений в кластере.

Answer 7

Каждая машина получает начальный идентификатор DDNNN, где DD - это уникальный идентификатор машины, а NNN - текущий идентификатор, сгенерированный этой машиной в тот день. Каждая машина отслеживает идентификаторы, которые она сгенерировала в определенную дату, и выделяет следующую, когда ей нужна новая, увеличивая последнюю на 1. Она сбрасывает свой счетчик на 0 в начале каждого дня. Дата YYYYDOY добавляется к числу, сгенерированному каждой машиной (4-значный год, 3-значный день года). Номер гарантированно уникален, потому что идентификатор машины уникален.

Если вам нужно больше места для большего количества машин, вы можете опустить тысячелетие за год и добавить цифру для идентификатора машины: YYYDOYDDDNNN.

Answer 8

Мое предложение было бы объединить несколько подходов в один идентификатор. Например: начните с двухлетних цифр, двухмесячных цифр, а затем сгенерируйте случайное число со временем в качестве начального числа для следующих нескольких цифр и затем с уникальным идентификатором машины для последней пары. Или что-то в этом роде.

Answer 9

Идея номер один:

YYMMDDmmnnnn

, где

YY is two digit year
MM is two digit month
DD is two digit day
mm is a two digit code unique to that machine (00 - 99)
nnnn is a sequential four digit code for that machine on that day.

~~

Идея номер два:

mmmmnnnnnnnn

Где

mmmm is four digit code unique to the machine
nnnnnnnn is a sequential number.

Answer 10

За 24 часа есть 864000 тиков 100 мс, так что привязка к дате может сработать 09.12.24.86400.0, но вы должны потерять столетие, чтобы уместиться в 12 цифр, и у вас нет места для идентификаторов машин .