Короткие уникальные идентификаторы

Я разрабатываю HTTP-сервис с пропускной способностью до 500 миллионов запросов в день (обслуживается более чем одной независимой машиной).Короткие уникальные идентификаторы

Для каждого запроса мне нужно сгенерировать уникальный идентификатор и вернуть его пользователю. Идентификатор должен быть 100% уникальным в течение 10 минут. (Предпочтительнее 1 день, идеальны глобально уникальные идентификаторы.) Для генерации этого идентификатора не требуется связи сервера и сервера.

Глупый пример псевдо-сессии:

 
Client: GET /foo 

Server: Content-Type: text/xml 

     <root> 
      <id>ab9d1972-2844-11e0-86b2-000c29544403</id> 
      <other_data/> 
     </root>

В предыдущем поколении этого HTTP службы я использовал UUID,.

Я доволен UUID, но есть одна проблема: они слишком длинны. При таком количестве запросов этот дополнительный размер заметен в дисковых пространствах для журнальных файлов.

Каков наилучший способ создания короткого, но уникального идентификатора? Чтобы сделать что-то стоящим, я думаю, алгоритм должен производить не более половины длины UUID, будучи уникальным в течение всего дня (10 минут должны быть еще короче).

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

Update: Сформировано ID не должен требовать URI-кодирования при передаче в запросе GET.

источник

2011-01-29 Alexander Gladysh

Ленивый вопрос (извините, слишком поздно ночью, чтобы сделать математику): как долго UUID, если он закодирован с ascii85 из двоичного? –

@Alexander: Количество цифр: 'ceil (log (max_val)/log (num_different_chars))'. –

ASCII85 кодирует 4 байта в 5 символов. Тем не менее, это не * действительно * URI или не подходит для людей. (UUID - 128 бит 16 бит - 20 символов ASCII85). –

Дайте каждой машине уникальный префикс. Дайте каждой машине счетчик. Чтобы сгенерировать идентификатор, увеличьте счетчик и добавьте его значение в префикс.

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

источник

2011-01-29 00:21:08

Возможно, также сделайте каждый идентификатор трех частей: machineid-counter-randomkey, чтобы устранить атаки прогноза ID. –

Хорошая идея. Можете ли вы предложить действительно быстрый шифр? –

Кроме того: Как вы считаете, насколько короче, если он будет создан на вашем пути? –

Несколько мыслей:

500 миллионов запросов в день. В самом деле?
Используйте UUIDs.
При необходимости не используйте HTTP (поскольку это более значительные издержки) и передайте UUID в двоичной форме.
Вам нужно определенное количество байтов, чтобы гарантировать, что ваш сервер вернет действительно уникальный идентификатор.
Как насчет использования UDP?

В любом случае, какого черта вы пытаетесь сделать?

источник

2011-01-29 00:20:58 BastiBen

500M, действительно (это целевая максимальная емкость, расчетная фактическая нагрузка больше похожа на 100M). К сожалению, HTTP и TCP/IP являются обязательными. –

также, 500M/день должно быть в пределах c10k, что так удивительно в этом? –

Короткие уникальные идентификаторы

ответ

Смежные вопросы