Лёгкая
Генератор уникальных идентификаторов
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 лет от выбранной эпохи (допущение: срок жизни системы)
Решите задачу у доски
Интервьюер задаст вопросы по вашей схеме, проверка разберёт её по семи осям




