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

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

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

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

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

2 ответа

Решение

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

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

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

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

  • 4 байтовых секунды с эпохи Unix
  • 3-х байтовый идентификатор машины
  • 2-байтовый идентификатор процесса
  • Счетчик 3 байта

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

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

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

Источник

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

обзор

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

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

Итак, давайте рассмотрим это в контексте "мобильного клиента".

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

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

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

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

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

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

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

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

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

Источник
Другие вопросы по тегам