Meteor Id сокращение столкновения доказательство - PullRequest
Новая
       51

Meteor Id сокращение столкновения доказательство

1 голос
/ 19 мая 2019

Метеор использует свой внутренний Случайный пакет для генерации Монго-идентификаторов для документов, где используемый набор символов определяется как: 

var UNMISTAKABLE_CHARS = "23456789ABCDEFGHJKLMNPQRSTWXYZabcdefghijkmnopqrstuvwxyz";

В описании метода для Random.id также указано:

Возвращает уникальный идентификатор, такой как "Jjwjg6gouWLXhMGKW", который, вероятно, будет уникальным во всем мире.

, который определен для длины Id по умолчанию (17 символов; каждый из UNMISTAKABLE_CHARS).

Теперь я хотел бы использовать только первые N символов идентификатора для сокращения моих URL-адресов (включая идентификаторы для динамической загрузки страниц, для которых требуется определенный документ, который определяется идентификатором).

Так что, если мой оригинальный идентификатор 

`v5sw59HEdX9KM5KQE`

Я хотел бы использовать, например (рассмотрим здесь случайное N = 5): 

{
  _id:"v5sw59HEdX9KM5KQE",
  short: "v5sw5"
}

в качестве схемы документа и получить соответствующий документ по этому идентификатору, используя { short } в качестве запроса в моем Mongo.Collection.

Теперь у меня вопрос , сколько символов достаточно для предотвращения коллизии , если нужно учитывать количество документов (таким образом, идентификаторов) от 5000 до 10000.

Примечание: У меня есть несколько инструментов для расчета энтропии, и все эти значения (набор символов, длина оригинальных идентификаторов, количество документов) передо мной, но я не знаю, как это сделать все, чтобы безопасно рассчитать N.

Ответы [ 3 ]

2 голосов
/ 19 мая 2019

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

В вашем примере вы усекаете идентификатор, тем самым создавая явную связь между вашим более коротким идентификатором и исходным идентификатором документа.

Звучит так, как будто git сокращает хеш коммита: Как Git (Hub) обрабатывает возможные столкновения из коротких SHA?

Вы могли бы пойти по аналогичному пути, то есть сначала определить начальную длину по умолчанию, которая является разумной, чтобы избежать вероятного столкновения (как объяснено в ответе Питера О.), но явно проверьте уникальность на стороне сервера и увеличьте длину любого новая сокращенная версия в случае столкновения, пока она снова не станет уникальной.

2 голосов
/ 20 мая 2019

Я бы сказал, что если вы хотите избежать коллизий в небольшой коллекции, то вы не хотите использовать случайные идентификаторы, но либо идете с полностью детерминированными идентификаторами, либо по крайней мере уменьшаете случайность до чего-то большегоконтролируется.В соответствии с этим, другой вариант, который вы должны рассмотреть, - это использовать MONGO для idGeneration в вашей коллекции .Эти идентификаторы генерируются по известному рецепту .Соответственно, вы можете взять символы 1-4 и 12 этого идентификатора и получить гарантию на отсутствие коллизий хешей, если в одну секунду создается не более N документов, где N - количество символов, используемых в MongoID (которые яне знаю от руки).

2 голосов
/ 19 мая 2019

Генерация случайных идентификаторов уже создает риск, по крайней мере теоретически, создания дублирующего идентификатора.Для длины MongoID по умолчанию (при условии, что их 55 17 ), вероятность наличия дублированного MongoID достигает 50% после генерации почти 731156 миллиардов случайных MongoID (см. « Проблема дня рождения »)."), поэтому вероятность дублирования на практике незначительна для большинства приложений.

Сокращение случайного идентификатора еще больше усугубит проблему столкновения.В этом случае для длины идентификатора в 5 символов (в результате 55 5 или 503284375 различных идентификаторов) вероятность наличия дублированного MongoID достигает 50% после генерации всего около 26415 случайных идентификаторов.

Поскольку кажется, что вы не можете контролировать, как генерируются MongoID, так же легко, как вы можете контролировать, как генерируются сокращенные «уникальные идентификаторы» , вы можете сделать следующее:

  • Создайте документ, в котором каждому MongoID присваивается уникальный номер (например, монотонно увеличивающийся счетчик).
  • Чтобы числа, назначенные таким образом, выглядели «случайными», передайте каждое число так называемому линейному конгруэнтному генератору с «полным периодом», чтобы получить уникальное, но «рандомизированное» число в пределах периода генератора.
  • Числа (закодированные аналогично строкам MongoID) могут затем служить короткими идентификаторами для ваших целей.

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

Если вы хотите пойти по пути использования сокращенных MongoID, см. « День рождения » для формул, которые можно использовать для оценки количества случайных чисел.принимает риск столкновения, чтобы оставаться терпимым.

Для получения дополнительной информации о том, как Meteor генерирует MongoID, см. также этот вопрос ;один из его ответов включает способ, с помощью которого MongoDB может генерировать MongoID на сервере, а не Meteor на клиенте.Похоже, что Meteor не проверяет уникальность сгенерированных им MongoID перед тем, как вставить их в документ.

...