Перейти к содержанию

Лёгкая

Генератор уникальных идентификаторов

64 бита на время, номер и счёт

Условие

Шестьдесят четыре бита делят между временем, номером генератора и счётчиком, и у каждого деления есть срок годности. Случайные 64 бита при двух миллионах выдач в секунду дадут первое совпадение примерно через 45 минут, UUID не помещается в bigint, а опасны два сбоя: два генератора с одним номером и часы, которые пошли назад.

Спроектируйте выдачу уникальных идентификаторов для объектов большого сервиса: заказов, сообщений, платежей.

Сервис создаёт объект и сразу получает для него идентификатор. По идентификатору объекты сортируют по времени создания, а из самого идентификатора можно достать, когда объект создан.

Считайте, что:

  • идентификатор хранится в колонке bigint и уходит клиенту на JavaScript;
  • экземпляры создаёт и удаляет оркестратор, при выкатке новые поднимаются раньше, чем гаснут старые; экземпляр может упасть без предупреждения;
  • часы серверов синхронизируются по NTP (Network Time Protocol, протокол синхронизации времени) с расхождением до 10 мс, и иногда их переводят назад; насколько назад, заранее неизвестно;
  • экземпляр может перезапуститься за секунду.

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

Требования

Функциональные 5

  • Каждый вызов возвращает новый идентификатор, уникальный во всей системе
  • Идентификатор — целое число в 64 бита
  • Идентификаторы растут со временем: созданное позже получает номер больше; между машинами — с точностью до расхождения часов; после отката часов и перезапуска порядок может нарушаться, пока часы не вернутся к прежней отметке, но дублей нет
  • Идентификатор известен сервису до записи объекта в базу
  • Из идентификатора достаётся время создания

Нефункциональные 6

  • Ноль дублей, в том числе при перезапуске экземпляра, выкатке и откате часов; при риске дубля выдача останавливается, а не продолжается
  • Выдача идентификатора: 99% вызовов быстрее 10 мкс, то есть p99 < 10 мкс (допущение: идентификатор не добавляет заметной задержки к созданию объекта)
  • Объекты, созданные с разницей больше 10 мс, получают идентификаторы в порядке создания (допущение: расхождение часов по NTP до 10 мс)
  • Сбой любой общей службы длительностью до 5 минут не останавливает выдачу идентификаторов (допущение: время на переключение реплики и перезапуск)
  • Аварийные перезапуски экземпляров до 1 в секунду по всему парку не мешают выдаче (допущение)
  • Запас по времени — не меньше 50 лет от выбранной эпохи (допущение: срок жизни системы)

Решите задачу у доски

Интервьюер задаст вопросы по вашей схеме, проверка разберёт её по семи осям