Вероятность столкновения ObjectId и UUID в большой распределенной системе

Учитывая, что UUID rfc 4122 (16 байт) намного больше, чем MongoDB ObjectId (12 байт), я пытаюсь выяснить, как их вероятность столкновения сравнивается.



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



По сравнению с обычным случаем, когда все идентификаторы генерируются a небольшое количество клиентов:




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

  • идентификаторы генерируются из гораздо большей клиентской базы

  • каждый клиент имеет более низкую скорость генерации идентификаторов

651   2  

2 ответов:

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

Это звучит как очень плохая архитектура для меня. Вы используете двухуровневую архитектуру? Зачем мобильным клиентам иметь прямой доступ к БД? Вы действительно хотите полагаться на сетевую безопасность?

Во всяком случае, некоторые рассуждения о вероятности столкновения:

Ни UUID ни ObjectId не полагаются на их чистый размер, то есть оба не являются случайными числами, но они следуют схеме, которая пытается систематически уменьшить вероятность столкновения. В случае объектов их структура :

  • 4 байта секунд с момента unix эпохи
  • 3-байтовый идентификатор машины
  • 2 байта id процесса
  • счетчик 3 байт
Это означает, что, в отличие от UUIDs, ObjectIds монотонны (за исключением одной секунды), что, вероятно, является их наиболее важным собственность. Монотонные индексы приведут к тому, что B-дерево будет заполнено более эффективно, оно позволяет выполнять подкачку по id и позволяет "сортировку по умолчанию" по id, чтобы сделать ваши курсоры стабильными, и, конечно, они несут легкую для извлечения метку времени. Это оптимизации, о которых вы должны знать, и они могут быть огромными.

Как вы можете видеть из структуры остальных 3 компонентов, коллизии становятся очень вероятными, если вы делаете > 1K вставок/с в одном процессе (на самом деле это невозможно, даже с сервера), или если число машин переваливает за 10 (см. проблему дня рождения), или если число процессов на одной машине становится слишком большим (опять же, это не случайные числа, но они действительно уникальны на машине, но они должны быть сокращены до двух байт).

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

24  
2014-03-24 12:46:59

Давайте посмотрим на спецификацию для "ObjectId" из документации :

Обзор

ObjectId-это 12-байтовый тип BSON, построенный с использованием:

  • 4-байтовое значение, представляющее секунды, прошедшие с эпохи Unix,
  • 3-байтовый идентификатор машины,
  • 2-байтовый идентификатор процесса и
  • 3-байтовый счетчик, начинающийся со случайного значения.

Поэтому рассмотрим это в контексте "мобильного клиент".

Примечание: контекст здесь неозначает использование "прямого" подключения "мобильного клиента" к базе данных. Что должен не быть сделано. Но генерацию " _id " Можно сделать довольно просто.

Итак, пункты:

  1. Значение для "секунд с момента начала эпохи". Это будет довольно случайным на запрос. Так что минимальное воздействие столкновения только на этот компонент. Хотя и в "секундах".

  2. Тот самый "идентификатор машины". Таким образом, этот является другим клиентом, генерирующим значение _id. Это исключает возможность дальнейшего "столкновения".

  3. "идентификатор процесса". Так что там, где это доступно затравке ( а она должна быть), то сгенерированный _id имеет больше шансов избежать столкновения.

  4. "случайная величина". Таким образом, другой "клиент" каким-то образом сумел сгенерировать все те же значения, что и выше, и все же сумел сгенерировать то же самое случайное значение.

Суть в том, что если , что не является достаточно убедительным аргументом, чтобы переварить, то просто предоставьте свои собственные записи "uuid" в качестве значений "первичного ключа".

Но ИМХО, это должно быть справедливым убедительным аргументом, чтобы считать, что аспекты столкновения здесь очень широки. Мягко говоря.

Полная тема, вероятно, просто немного "слишком широкая". Но я надеюсь, что это сдвинет рассмотрение немного больше прочь от "совсем маловероятно" и перейдем к чему-то более конкретному.

11  
2014-03-24 12:44:18

Comments

    Ничего не найдено.
Click here to cancel reply.