Какие есть пакеты для генерации уникальных, числовых идентификаторов длиной 10 цифр?

Question

[historydev]

У телеграм есть id пользователя и он заманчиво короткий, есть ли пакет который делает тоже самое?

P.S:
Условия:
1. ~100 id в секунду с головой
2. Кол-во машин неизвестно
3. Размер =10 цифр / =34 бит
4. Уникальность вне зависимости от местоположения генератора (машина)
5. Не имеет доступа к существующим id

Comments

[VoidVolker]

А в чём сложность использования поиска? Это вообще делается в пару строчек без всяких пакетов дополнительных.

[Lynn «Кофеман»]

Math.random()
crypto.randomЧто-нибудь()

Если очень хочется, то есть nanoid.

Но кто вообще сказал что id в телеграме рандомные?

[historydev]

VoidVolker, Не нашёл то, что искал. Если бы это делалось в "пару строчек", не было uuid и ему подобных генераторов.

[historydev]

Lynn «Кофеман», Если id autoincrement, то нужна централизованная генерация чтобы не попасть в лапы коллизий. А в распределённой системе это узкое место по очевидным причинам.
- Отсюда выводы, нужен генератор который будет выдавать уникальные идентификаторы ничего не зная о уже сгенерированных.

[Lynn «Кофеман»]

historydev,
> не было uuid
uuid это буквально одна строчка в nodejs https://nodejs.org/api/crypto.html#cryptorandomuui...

> Если id autoincrement, то нужна централизованная генерация чтобы не попасть в лапы коллизий.
и кто сказал что это не так в случае телеграма?
учитывая что у них как раз пользователи привязаны к датацентрам сделать id = префикс ДЦ + автоинкремент внутри ДЦ вообще не проблема.

> нужен генератор который будет выдавать уникальные идентификаторы ничего не зная о уже сгенерированных
ну возьмите UUID и не изобретайте велосипед. Я бы сейчас взял UUIDv7

[historydev]

Lynn «Кофеман»,
При вызове возможно, а реализация очевидно занимает больше.

@VoidVolker Это вообще делается в пару строчек

Должно сработать с префиксом, а при переезде как это выглядит?
- Есть таблица с дц?
- Каждая запись имеет поле с номером дц?
- База где-то хранит номер дц?

Мне нужно 10 цифр, а не набор километровый из символов - это не удобно.

[VoidVolker]

historydev,

Не нашёл то, что искал.

Значит плохо искали.

Если бы это делалось в "пару строчек", не было uuid и ему подобных генераторов.

Очень даже делается. Вон вам выше уже привели пример же.

А в распределённой системе это узкое место по очевидным причинам.

Дык вы бы тогда уж озвучили требования к этой вашей распределённости.

[historydev]

VoidVolker, По всей видимости, хорошо, спасибо всем.

[Wispik]

historydev,
вот один из проектов, причем не нода, а обычный js. 6 строк кода

export const uuidv4 = () => {
  return 'xxxxxxxx-xxxx-4xxx-yxxx-xxxxxxxxxxxx'.replace(/[xy]/g, function (c) {
    var r = (Math.random() * 16) | 0,
      v = c == 'x' ? r : (r & 0x3) | 0x8
    return v.toString(16)
  })
}

[pfg21]

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

[historydev]

pfg21, Я читал что подобные идентификаторы собираются из ДЦ + timestamp + счётчик в рамках текущей секунды + ещё что-то.
- И гарантия уникальности в таком случае ~60 лет.

Например 10 записей в секунду могут выглядеть так:
"40435" + 123456 + 1..10 + что-то там и получаем: 40435123457что-то-там

[pfg21]

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

[WbICHA]

Wispik, и где в этом "проекте" гарантия уникальности?

[historydev]

pfg21, Самому писать - гемор, а найти пакет - удобно.
- Да, у меня всё в одной базе и на одном хосте.

Здесь вопрос не в целесообразности, а в реализации.
- Например snowflake, но мимо потому что минималка около 45 бит.

[pfg21]

historydev, хых, тогда сразу бы прописал условия что генератор не имеет доступа к другим идентификатором и тогда uuid и подобные выиграли бы сразу с уничтожающим счетом :) ибо они под ентое самое и создавались.
причем сразу готовенькой библиотекой с утилитами, скомпилированной и допиленной от багов.
а причем здесь снежинка ?? она по другие условия писалась и потому косяков тянет за собой.
каждый инструмент имеет свои плюсы и минусы.
у тебя прописанных условий кот наплакал. что думаешь сюда прибежали все провидцы с рентв и уселись решать те замыслы который ты только подумал ??

[historydev]

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

[pfg21]

historydev, вот уже интереснеее :)

Answer 1

[Everything_is_bad]

У телеграм есть id пользователя и он заманчиво короткий

там тупо автоинкремент

Comments

[historydev]

"Какие ваши доказательства?"

[Wispik]

historydev, Какие доказательства для очевидной вещи?
У Дурова так и в вк было. Что-то уникальное надо придумывать когда в id и цифры и буквы( тот же uuid4). А когда просто числа это чисто воды автоинкремент

Answer 2

[Vamp]

Я не знаю какой конкретный алгоритм у телеграма, но в простой централизованный инкремент я не верю. Слишком очевидный ботлнэк.

Я читал что подобные идентификаторы собираются из ДЦ + timestamp + счётчик в рамках текущей секунды + ещё что-то.
- И гарантия уникальности в таком случае ~60 лет.

Твиттер придумал такой алгоритм и назвал его snowflake id. Там используется timestamp + machine id + счетчик в рамках одной миллисекунды. Уверен, телеграм использует генератор с подобным алгоритмом. Он быстрый, не требует централизованного управления (кроме назначения machine id, но это делается один раз в момент введения машины в эксплуатацию и может делаться даже вручную) и генерирует идентификаторы размером 64 бита (влезает в mysql тип bigint).

Есть парочка пакетов с реализацией этого алгоритма - snowflake-id, snowflakify.

Comments

[historydev]

snowflake слишком большой и если уменьшить кол-во бит - теряется гарантия уникальности.
- Читал задолго до вопроса.

[Vamp]

historydev, напишите требования. Алгоритм можно достаточно гибко тюнить под них.

Сколько идентификаторов в секунду вас устроит? Сколько генерящих машин будет максимум?

[historydev]

Vamp,
1. 100 в секунду с головой
2. Машины неизвестны
3. Размер 10 цифр / 34 бит

[Vamp]

historydev, с такими вводными snowflake исчерпает идентификаторы за год. Слишком мало бит на метку времени.

С другой стороны, 100 в сек - это ерунда, для которой хватит и централизованного автоинкремента. Если уж хотите распределённости, делите диапазон между машинами. Например:

Машина 1: 1 - 2 499 999 999
Машина 2: 2 500 000 000 - 4 999 999 999
Машина 3: 5 000 000 000 - 7 499 999 999
Машина 4: 7 500 000 000 - 9 999 999 999

И пусть каждая машина последовательно генерит в своём диапазоне.

[historydev]

Vamp,
100 * 60 * 60 * 24 * 365 = 3_153_600_000
3_153_600_000 / 9_999_999_999 = ~0.31

~3 года - по моим грубым подсчётам, не учитывавшими рандом и дц.

[Vamp]

historydev, это расчет на автоинкремент. Для snowflake будет немного иначе:
Счётчик на 100 - 7 бит
Machine id - 2 бита (на 4 машины)
Для метки времени остаётся 34 - 7 - 2 = 25 бит, что даёт всего 33554431 секунд (388 дней).

[historydev]

Vamp, Если ограничить до одного в секунду можно из ~33 миллионов получить ~2 миллиарда и получается:
2^(34 - 3) = 2147483648
2147483648 / (60 * 60 * 24 * 365) = ~68 лет?

[Vamp]

historydev, с такой скоростью для счётчика даже бита не нужно выделять. Раз уж в пределах секунды может быть только один идентификатор, то сама эта секунда и станет идентификатором. Поэтому 2 ^ (34 - 2) ≈ 136 лет