Вы когда-нибудь задумывались, как реализовать getUUID? Мы часто устанавливаем случайные идентификаторы для записи в таблицу. Самый распространенный способ — создать файл UUID.randomUUID. Однако многие языки программирования и облачная инфраструктура предоставили нам UUID, и иногда мы воспринимали эту функцию как должное.

Что такое глобально уникальный идентификатор?

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

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

Первая интуиция

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

Это будет отлично работать на одной машине. Однако, если мы хотим создать глобально уникальный идентификатор на другом устройстве, каждая машина может генерировать UUID одновременно и в один и тот же момент. Это не сработает.

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

Мы можем добавить вновь сгенерированную метку времени к IP-адресу машины.

Мы можем добавить вновь сгенерированную метку времени к идентификатору машины (сервера).

Мы можем добавить к вновь сгенерированной метке времени серийный номер процессора.

Достаточно ли этого для создания глобального уникального идентификатора в распределенной системе?

Что, если одна машина вызовет функцию дважды в одну и ту же наносекунду? В этом случае у нас будет дублирующаяся метка времени на устройстве.

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

Часы в компьютере не идут монотонно вперед. Если компьютер использует NTP (Протокол сетевого времени) и если часы сбиваются, он будет выполнять откат, чтобы установить правильное время.

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

Генерация времени дня для уникального идентификатора может быть медленным, есть ли более быстрый способ генерировать время?

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

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

Нам понадобится некоторое хранилище данных для хранения этих счетчиков. Однако это будет неэффективно, если нам нужно будет каждый раз извлекать счетчик с диска. Чтобы избежать записи на диск в каждом счетчике, мы можем записать первый счетчик N'th на диск. Допустим, 1000.

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

Как насчет добавочного глобального счетчика?

Мы решили генерировать уникальные идентификаторы в распределенной системе. Однако заголовок этой статьи звучит так: «Как создать добавочный глобальный счетчик в распределенной системе».

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

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

Мы можем создать службу, которая явно генерирует уникальный идентификатор. Следовательно, все машины, которые хотят сделать уникальный идентификатор, будут вызывать машину Id, и она будет возвращать идентификатор, монотонно возрастающий.

Поскольку нам нужно совершать сетевые вызовы на каждом счетчике, это убьет производительность системы. Кроме того, что, если этот сервер умрет? Тогда все службы также будут затронуты.

Должны ли мы разделить сервер, чтобы он был доступен?

Однако, если мы разделим сервер, как мы можем гарантировать, что сервер Id вернет уникальный монотонно возрастающий Id?

Еще один способ смягчить сервер Id — иметь четный сгенерированный счетчик и даже разработанный счетчик. Если нечетный сгенерированный сервер Id умирает, мы можем получить данные с четного сервера, и наоборот.

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

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

Централизованное решение — единственное решение для постоянно растущего счетчика, потому что вы хотите быть последовательным. Это компромисс согласованности и доступности в теореме CAP.

Урок выучен

Иногда самое простое решение достаточно. Достаточно иметь сервер, который генерирует монотонно увеличивающийся сервер.

Спасибо, что прочитали! Если вам понравился этот пост, не стесняйтесь подписаться на мою рассылку, чтобы получать уведомления о эссе о карьере в технологиях, интересных ссылках и контенте!

Вы можете подписаться на меня, а также подписаться на Medium, чтобы получать больше подобных сообщений.

Первоначально опубликовано на https://edward-huang.com.