как сгенерировать уникальный integer id в кластере?

Question

[Lestat]

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

Собственно смотря на www.mongodb.org/display/DOCS/Object+IDs
пока видится такой же вариант, только размер выделенных байт будет чуть меньше.


Делаем 4 части:

1) время в формате epoch (unix, posix), в общем количество секунд с 1970 года.
time = 8 bytes integer (2 ** (4 * 8) = 4294967296 variants)
import time
int(time.time())
part1 = 1314823196 /…

2) machine_id = 2 bytes integer (2 ** (4 * 2) = 256 variants)
тут видится 2 варианта,
или генерация machine_id согласно hostname, или просто некий внутренний номер, который скажем прописывается в зависимости от hostname,
т.е. можно просто machine_id = 1 / 2 / 3 … / 10
part2 = 1 / 2 / 3 /…

3) pid = 2 bytes integer (2 ** (4 * 4) = 65536 variants)
тут точные варианты проверить пока не могу, но в макоси например pid такого вида: 01318, т.е. совсем немного.
part3 = 01318 /…

4) increment = 4 bytes integer (2 ** (4 * 4) = 65536 variants)

тут сложнее,
например на 8 ядрах будут одинаковые time, machine_id, pid.
остается только increment.
тут вижу вариант использовать какой-нибудь memcached incr например,
чтобы сразу увеличить и получить данное значение атомарно.
тогда 8 потоков получат ключ 1,2,3,4,5,6,7,8 соответственно и не будет коллизий.
import memcache
cache = memcache.Client(['127.0.0.1:11211'])
cache_key = ‘cache_pid_’.format(pid_id)
cache.set(cache_key, 0)
increment_id = cache.incr(cache_key) — увеличит и возвратит новое инкрементированное поле
part4 = 1 / 2 / 3 /…

получается в итоге что-то типа такого:

1314823196 + 1 + 01318 + 1
1314823196 + 1 + 01318 + 2
1314823196 + 1 + 01318 + 3

1314823196 + 2 + 71673 + 1
1314823196 + 2 + 71673 + 2
1314823196 + 2 + 71673 + 3

…
т.е. число где-то так:
13148231962716733

если взять для хранения BIGINT то получается
-9223372036854775808 to 9223372036854775807

13 148 231 962 716 733
9 223 273 036 854 775 807

т.е. запаса много.

собственно вопрос, все ли правильно в данном методе или где-то есть ошибка или что-то возможно улучшить?

а как бы вы генерировали такую штуку?

Спасибо!

update:
хм, а еще вариант просто брать memcache increment, не знаю он на весь кластер нормально работает?

Answer 1

[lesha_penguin]

Варианты решения uniqid от лучшего к худшему:
1) Если 64bitный bigint то вообще проблем никаких: в старшие 32 бита засовываем заведомо уникальный идентификатор машины (например ip-адрес, или crc32/adler32 от hostname). а младшие 32 крутим как обычный сиквенс.
Достоинства: для любого идентификатора можно в случае «жесткого дебага» найти «откуда ноги растут» — т.е. однозначно идентифицировать тачку на которой возникла запись с исследуемым id.
2) Если есть желание убраться в 32bit (разумное желание, ведь не все хорошо работает даже в наш 64разрядный век с большими числами) лучше применять кешированый сиквенс. При запросе сиквенс увеличивается не на 1 а сразу на большое значение, например на 1000 или на 10000. Соотвественно, нода, получив от сиквенса диапазон 320000..329999 спокойно может не обращатся снова к сиквенсу, пока не израсходует этот диапазон. Плюсы: опять-таки возможно логировать. Минусы (правда устранимые резервным сиквенсом с резервным диапазоном): придется выбирать порцию отдачи.
3) Экстремальный вариант. Еще расширяем integer до 128 бит и используем хеши или что-нибудь uuid-подобное. Минус очевиден — 99.9% софта не сможет работать с таким значением как с числом.
4) Hardcode-вариант. Если вам известно, что нод будет не более чем N, каждая нода просто крутит сиквенс S а id получает по ф-ле id=S*N+n; где n-номер ноды. Плохой вариант, очень чреват нехорошими последствиями, если вдруг вы ошиблись в смелых оценках.
5) Метод проб и повторов. еще хуже, поскольку сработает если у вас записей мало и добавляются они редко и вообще надежно будет работать если источник добавления записей только один.

Comments

[Lestat]

спасибо, первый вариант очень привлекательный.
правда IP может поменяться, впрочем наверное hostname когда-нибудь тоже.

что ж, буду думать :)

[korvindest]

Думаю для того что бы не привязываться к IP или hostname достаточно где то держать таблицу корреляции (hostname/IP->Upper_id), которая будет загружаться 1 раз при старте машины. Это позволит в любой момент переименовать, добавить и удалить любой из узлов.
В остальном полностью поддерживаю lesha_penguin.

[Lestat]

спасибо )

Answer 2

[Ололёша Ололоев]

А если UUID использовать?

Comments

[Lestat]

к сожалению слишком длинно и менее красиво