Распределенные идентификаторы по сети
Мне нужно создать распределенную сеть объектов, говорящих друг с другом на основе идентификатора (автоматически сгенерированный, цифровой, многоразового использования). Как я могу создавать объекты на каждом узле графа, не создавая коллизий?
На данный момент я использую мастер узел для распределения идентификаторов, но это решение включает асинхронное создание объектов на других узлах, которые я хотел бы удалить. Тем более, что приложение предназначено для работы в режиме реального времени, поэтому СУБД не нужны.
Я знаю, что это довольно классическая проблема распределенных вычислений, но мне, вероятно, не хватает словарного запаса для правильного поиска.
TCP — единственный протокол, который я могу использовать, и сеть подвержена задержкам. В случае, если это имеет значение, я работаю в C ++, но я ищу алгоритм, а не библиотеку.
Решение
Вы можете использовать UUIDКак идентификаторы, они уникальны по дизайну, поэтому вам не потребуется дополнительная алгоритмическая поддержка.
Другие решения
Вместо того, чтобы мастер-узел выделял идентификатор за раз, вы могли бы назначить ему блок или диапазон идентификаторов одновременно для каждого узла. Каждый узел затем выделяет идентификаторы из этого блока по мере необходимости.
Когда узлу становится мало идентификаторов, он запрашивает другой блок у мастера. Таким образом, узлы могут создавать объекты асинхронно и при этом иметь гарантированные уникальные идентификаторы.
Я предполагаю, что при удалении объекта идентификатор возвращается в пул для повторного использования.
Другой вариант, если вы не хотите, чтобы главный узел отвечал за распределение идентификаторов, — это использовать что-то вроде локального MAC-адреса или IP-адреса, к которому добавлен счетчик, для создания идентификатора. Это требует, чтобы в сети не было дублированных IP или MAC-адресов. Этот идентификатор будет больше 16 бит.
Однако, если все узлы находятся в одной сети, например IP-адрес AA.BB.CC.DD, затем вы можете использовать DD в качестве первых 8 битов, а затем следующие 8 битов в качестве счетчика. Это даст только 256 идентификаторов на узел, что может быть недостаточно. Если подсеть меньше, то биты, доступные для счетчика, очевидно увеличиваются, и, возможно, этого достаточно для решения проблемы.
Просто создайте это случайно. при случайных значениях 128 битов вероятность столкновения настолько мала, что можно предположить, что он равен нулю. На 128-битном пространстве uuid вероятность столкновения составляет 2 ^ 64 (парадокс дня рождения)
Очевидно, вам нужен хороший источник энтропии, классический sha1(time(NULL)) это не ходят;)
что еще более важно: если узлы выбирают свой UUID случайным образом, абсолютно не требуется центральный координатор, который создает и передает UUID узлам. Каждый узел создает свой собственный UUID самостоятельно.