Генерация не совсем глобально Уникального идентификатора
Я нашел много различных вопросов на генерации UIDs, но насколько я могу сказать, мои требования здесь несколько уникальны (ха).
Подводить итог: Я должен генерировать очень короткий идентификатор, это "локально" уникально, но не должно быть "глобально" или "универсально" уникально. Ограничения не просто на основе эстетического или располагают проблемы с интервалами, но вследствие того, что это по существу используется в качестве аппаратного тега и является этим предметом к ограничениям аппаратных средств. Вот спецификации:
Трудные требования
- Идентификатор должен содержать только десятичные цифры (базовыми данными является 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 десятичных цифр, которого является более чем достаточно для гарантии "достаточно уникального" идентификатора для этого приложения. Причина, относительно которой я спрашиваю это здесь Так, то, потому что я действительно хотел бы или попытаться включить человекочитаемый год/месяц там или закодировать некоторую информацию об исходной машине или обоих.
Я надеюсь, что кто-то может или помочь с компромиссом на тех мягких требованиях... или объяснить, почему ни один из них не возможен, учитывая другие требования.
(P.S. Мой "собственный" язык является C#, но код на любом языке или даже псевдокодирует, прекрасен, если у кого-либо есть какие-либо блестящие идеи.)
Обновление:
Теперь, когда у меня был шанс спать на нем, я думаю, что я на самом деле собираюсь сделать, использовать метку времени, кодирующую по умолчанию и позволить отдельным установкам переключаться на последовательный машиной идентификатор путем определения их собственных 2-или 3-разрядного идентификатора машины. Тем путем клиенты, которые хотят смешать с идентификатором и пакетом в человекочитаемой информации, могут разобраться в своем собственном методе удостоверяющейся уникальности, и мы не ответственны за неправильное употребление. Возможно, мы выручаем путем обеспечения утилиты сервера для обработки идентификаторов машины, если они, оказывается, делают все установки онлайн.
9 ответов
Как насчет yyMMddhmmID?
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.
В качестве альтернативы (если вам не нравятся двузначные годы (Y2K лол)), как насчет yyyMMIDxxx?
yyyy = four-digit year
MM = two-digit month
ID = machine-specific ID
xxxx = sequentially-incremented integer
Пример: 200912010001 с машины с ID = 01.
Как Вы сказали, что каждая машина будет генерировать только один идентификатор максимум каждые пять минут, это дает Вам место для 8928 (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
"Причина, по которой я спрашиваю об этом здесь, ТАК, потому что я действительно хотел бы либо попробуйте включить человеко-читаемый год / месяц там или закодировать некоторую информацию о с в минуту, вы по-прежнему будете тратить много места.
12 цифр - это не так много. Посмотрите страницу VIN в Википедии. Место только для нескольких производителей, всего несколько тысяч машин. Сейчас они повторно используют VIN, потому что у них закончилось место из-за того, что они упаковали в них смысл.
http://en.wikipedia.org/wiki/VIN
Это не значит, что ВСЕ значения серийных номеров плохие, просто строго ограничивайте его, чтобы числа не пересекались.
Примерно так ...
- Позиция 1-3: 999 машин
- Позиция 4-12: Последовательные числа
Это ВСЕМ нужно избегать коллизий. Если вы добавляете цифру местоположения, то вы облажаетесь, когда дойдете до местоположений 11.
Извините, если это звучит как напыщенная речь. Я много занимаюсь производством электроники и различных деталей.
Я собираю вас ' повторная разработка для Windows (re: ваш комментарий о "MSI / EXE" в ответ на ответ Джейсона). Таким образом, вы можете WMI или аналогичный, чтобы получить некоторый уникальный атрибут оборудования (например, процессор или серийный номер жесткого диска или MAC-адрес сетевой карты), на основе которого будет создан уникальный идентификатор машины. Альтернативой может быть использование уникального серийного номера оборудования, которое вы разрабатываете самостоятельно (если оно есть).
Скорее всего, это будет длиннее, чем вам нужно, поэтому вы потенциально можете усечь или хэшировать его, чтобы уменьшить его до ( скажем) 16 бит или около того и используйте это в качестве идентификатора вашей машины. Очевидно,
За 24 часа происходит 864000 делений по 100 мс, поэтому привязка этого к дате может сработать 09.12.24.86400.0, но вам нужно потерять век, чтобы уместить 12 цифр, а вы этого не сделаете. Нет места для идентификаторов машин.
Идея номер один:
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.
Я предлагаю объединить несколько подходов в одном идентификаторе. Например: начните с двух цифр года, двух цифр месяца, а затем сгенерируйте случайное число со временем в качестве начального числа для следующих нескольких цифр, а затем с уникальным идентификатором машины для последней пары. Или что-то в этом роде.
«Отдельная машина не будет генерировать идентификаторы чаще, чем каждые 5 минут или около того»
Если предположить, что это правда, тогда просто используйте метку времени. (32-битное время Unix имеет 10 десятичных цифр, но оно закончится в 2038 году)
Но я думаю, что довольно оптимистично предполагать, что конфликта не будет.
«Идентификаторы, сгенерированные на определенной машине, должны отображаться последовательно».
Тогда ваш единственный вариант - использовать порядковый номер.
Что действительно не соответствует тому, что вы говорите в последующих ограничениях?
Объедините дополненную версию идентификатора узла, чтобы получить уникальные значения в кластере.
Каждая машина получает начальный идентификатор DDNNN, где DD - уникальный идентификатор машины, а NNN - текущий идентификатор, сгенерированный этой машиной в тот день. Каждая машина отслеживает идентификаторы, которые она сгенерировала в определенную дату, и выделяет следующий, когда ему нужен новый, увеличивая последний на 1. Он сбрасывает свой счетчик на 0 в начале каждого дня. Дата YYYYDOY добавляется к числу, сгенерированному каждой машиной (4-значный год, 3-значный день года). Номер гарантированно уникален, поскольку идентификатор машины уникален.
Если вам нужно больше места для большего количества машин, вы можете опустить тысячелетие из года и добавить цифру для идентификатора машины: YYYDOYDDDNNN.
При установке программного обеспечения также установите файл/регистрационный ключ с уникальным цифровым идентификатором. Так как у вас всего несколько машин, это не должно занимать более 3 или 4 цифр. Используйте их в качестве цифр MS. Генерируйте оставшиеся цифры последовательно, начиная с 1.
.