Хочу как у YouTube

ghost404 2 февраля в 17:22 26,8k

Вы когда-нибудь задумывались как устроен ID видео на YouTube?
Возможно, вы уже знаете/нашли ответ, но, как показали обсуждения на Stack Overflow, многие понимают эту технологию неправильно. Если вам интересно изучить что-то новое, добро пожаловать под кат.


Хочу как у YouTube

Структура ID


Для начала, вспомним что из себя представляет ID видео на YouTube.
ID имеет длину 11 знаков (раньше был длиною 9 знаков).


Состоит из:


  • Латинских букв верхнего регистра [A-Z] — 26 знаков;
  • Латинских букв нижнего регистра [a-z] — 26 знаков;
  • Цифр [0-9] — 10 знаков;
  • Тире и нижнее подчеркивание [-_] — 2 знака.

Итого 64 знака.
Возможно, вы уже заметили сходство с известным многим Base64 (RFC 2045 раздел 6.8) и это неспроста. Только в стандарте Base64 используются в качестве дополнительных символов плюс и слеш [+/], а не тире и нижнее подчеркивание. Плюс и слеш зарезервированы для использования в URL, и чтобы не было проблем с использование ID в URL, YouTube заменили их более безопасными. Но вы можете использовать свои символы, об этом чуть позже.


Зачем это нужно


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


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


Тем не менее, хочу вас удивить, это не хешированное число, а просто строка. И даже не инкрементная строка, а случайно генерируемое значение по аналогии с UUID, только заметно компактней.


Это может быть сложно понять тем, кто всегда работал с инкрементными идентификаторами и полагался в этом на БД. У генерируемого идентификатора есть своё назначение, свои преимущества и недостатки перед инкрементным идентификатором.


Генерируемый идентификатор в распределенных системах


Впервые мы сталкиваемся с генерируемым идентификатором в распределенных системах.


Проблема инкрементных идентификаторов в том, что их создаёт БД. Для сохранения консистентности данных нам необходима одна master БД, которая будет генерировать их. Это повышает нагрузку на нее и затрудняет шардинг.
Некоторые решают эту проблему созданием отдельной БД или сервиса, который занимается исключительно генерацией ID. Но все усложняется, когда нам необходимо разнести сервера географически, подключить регионы.
Решение — вести локальный ID и, при периодической синхронизации с главным сервером, получать от него сквозной ID для всей системы. То есть на региональных серверах у нас будет 2 ID — локальный и сквозной.


Для решения подобных проблем и были придуманы генерируемые идентификаторы такие как UUID. За счёт большого количества комбинаций, мы добиваемся очень маленькой вероятности конфликта идентификаторов. Поэтому, мы можем доверить генерацию глобального ID конкретным инстансам приложения.


DDD и идентификаторы


Понятие Domain-driven design (DDD) хорошо описано в книгах Эрика Эванса и Вон Вернона. Общая идея DDD сводится к акцентированию внимания на нашей предметной области, стремление к проектированию систем максимально приближенных к реальному миру. Здесь же я хочу рассказать о роли идентификаторов в DDD.


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


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


В тоже время, в БД используется инкрементный ключ на вставку. Пока мы не запишем данные в БД, мы не сможем получить идентификатор для сущности. Нестыковка получается. Мы не можем создать сущность потому, что у нас нет ID, и мы не можем получить ID из БД потому, что для этого нужно записать сущность в БД.


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


Недостатки


У генерируемых идентификаторов есть и недостатки. Куда же без них.
Очевидными недостатками являются время генерации идентификатора и вероятность коллизии/конфликта идентификаторов. О вероятности конфликта мы и поговорим в следующем разделе.


Вероятность коллизии ID


Давайте вспомним курс комбинаторики и прикинем количество комбинаций. Нам потребуется формула Размещение с повторениями.


Размещение с повторениями

UUID


Для UUID количество комбинаций известно, но мы всё же рассчитаем их для сравнения.


UUID имеет вид 550e8400-e29b-41d4-a716-446655440000, имеет длину 32 символа за вычетом разделителей (-) и состоит из шестнадцатеричных цифр. Что нам дает 1632 или 2128 комбинаций. Это очень много.


У UUID много хорошего и многие им успешно пользуются. Лично мне он не нравится тем, что он ну очень длинный, занимает много места в БД и его затруднительно использовать в URL, хотя некоторых это не смущает.


YouTube ID


А теперь сравним UUID и YouTube видео ID и высчитаем количество комбинаций.


Как мы уже выяснили ранее, ID у YouTube видео состоит из 64 знаков и имеет длину 11 знаков, что нам дает 6411 или 266. Эта цифра конечно заметно меньше чем UUID, но я все равно считаю, что она достаточно большая:


73 786 976 294 838 206 464

Чтобы хоть как-то осознать это число, представьте, что для получения всех возможных значений идентификаторов длиной 11 символов и создавая идентификатор каждую наносекунду, вам потребуется 2 339 лет.


А для того, чтобы получить такое же количество комбинаций как у UUID нам потребуется 2128 = 6421 строка длиною 21 символов, то есть почти в 2 раз короче UUID (37 символов). А если мы возьмём идентификатор такой же длины как у UUID, то мы получим 6437 = 2222 против 2128 у UUID.
Самое главное преимущество такого подхода в том, что мы сами управляем количеством комбинаций путем изменения длины строки.


Не сложно догадаться, что можно сделать идентификатор еще более компактным взяв большее множество знаков. Например, взяв множество из 128 знаков и тогда, идентификатор длиной 18 знаков даст нам 12818 = 2126 комбинаций, что сравнимо с UUID. Но это экономит нам всего несколько символов, а проблем добавляет целую кучу. Увеличивая количество используемых знаков мы сталкиваемся с проблемой использования зарезервированных знаков или с проблемой расхождения кодировки знаков. Поэтому я рекомендую ограничится 64 знаками и играться только с длиной идентификатора.


Для расчета вероятности коллизии воспользуемся формулой из статьи про UUID на Википедии.



она же



Где
N — количество возможных вариантов.
n — число сгенерированных ключей.


Возьмем идентификатор длиною 11 знаков, как у YouTube, что даст нам N = 6411 = 266 и соответственно мы получим:


p(225) ≈ 7.62*10-6
p(230) ≈ 0.0077
p(236) ≈ 0.9999


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


Генерация ID


И наконец-то код. Генерируется ID элементарно.


class Base64UID
{

    private const CHARS = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_-';

    public static function generate(int $length): string
    {
        $uid = '';
        while ($length-- > 0) {
            $uid .= self::CHARS[random_int(0, 63)];
        }

        return $uid;
    }
}

Использование:


$uid = Base64UID::generate(11); // iKtwBpOH2Ew

DDD


А теперь прикинем как это может использоваться в вашей предметной области при использовании DDD подхода. Допустим, мы хотим использовать наш новый ID в сущности Статья. Для начала создадим ValueObject для идентификатора статьи, чтобы однозначно идентифицировать принадлежность идентификатора к статье.


class ArticleId
{
    private $id;

    public function __construct(string $id)
    {
        $this->id = $id;
    }

    public function id(): string
    {
        return $this->id;
    }

    public function __toString(): string
    {
        return $this->id;
    }
}

Теперь создадим интерфейс сервиса предметной области для получения ID. Сервис нам нужен для инкапсуляции генерации ID и подмены при необходимости.


interface ArticleIdGenerator
{
    public function nextIdentity(): ArticleId
}

Создадим имплементацию конкретного сервиса генератора ID статьи, использующий наш новый генератор случайных идентификаторов.


class Base64ArticleIdGenerator implements ArticleIdGenerator
{
    public function nextIdentity(): ArticleId
    {
        return new ArticleId(Base64UID::generate(11));
    }
}

Теперь мы можем создать сущность Статьи с идентификатором.


class Article
{
    private $id;

    public function __construct(ArticleIdGenerator $generator)
    {
        $this->id = $generator->nextIdentity();
    }

    public function id(): ArticleId
    {
        return $this->id;
    }
}

Пример использования:


$generator = new Base64ArticleIdGenerator();
$article = new Article($generator);
echo $article->id(); // iKtwBpOH2Ew

Заключение


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


А вы используете генерируемые идентификаторы? Расскажите в комментариях.


PS: Для тех кому лень писать свое, есть готовая библиотека под PHP 5.3+
PSS: Для расчетов могу порекомендовать этот онлайн калькулятор.


Update 02-02-2018


Цель этой статьи показать принцип, преимущества и недостатки генерируемых идентификаторов, а не принизить заслуги UUID или выдвинуть Base64 как лучшее решение.


Update 05-02-2018


Подведем небольшой итог обсуждения в комментариях.


medvedevia очень верно подметил, что UUID можно упаковать в base64, за что ему спасибо. Упакованный UUID, на выходе даст нам строку длиною 22 символа, что уже заметно компактней.


$uuid = '550e8400-e29b-41d4-a716-446655440000';
$uuid = str_replace('-', '', $uuid);
$uuid = hex2bin($uuid);
$uuid = base64_encode($uuid);
$uuid = str_replace('=', '', $uuid);

// VQ6EAOKbQdSnFkRmVUQAAA
var_dump($uuid);

Однако, UUID все ещё длинный и имеет ряд других недостатков описанных sand14, за что ему отдельное спасибо.


В качестве альтернативы можно рассмотреть Snowflake ID, предложенный MikalaiR. Его успешно используют в Twitter и Instagram.
Snowflake ID представляет из себя 64 битный номер:


  • Sign (1 бит) — необходим для определения границ timestamp;
  • Timestamp (41 бит) — дата генерации id в микросекундах;
  • Generator (10 бит) — id сервиса генерирующего id. Обычно разделяют на 2 — Datacenter ID (5 бит) и Machine ID (5 бит);
  • Sequence (12 бит) — инкрементируемое число.

Sequence инкрементируется в тех случаях, когда timestamp генерируемого id, совпадает с timestamp последнего сгенерированного id. Своего рода защита от коллизии на локальном уровне.


Довольно простая схема получается. Плюсами Snowflake ID будут:


  • Компактней чем UUID;
  • Постоянно растущий id, за счёт использования timestamp;
  • Высокая степень защиты от коллизий;
  • Не использует генератор случайных чисел
  • Конфигурируется вручную, что позволяет генерировать Snowflake id быстрее чем UUID.

А теперь поговорим о недостатках Snowflake:


Первая проблема заключается в том, что приложение, генерирующее id, может работать на одном сервере в разных процессах. В результате мы можем получить коллизию уже в пределах одного сервера. Использовать id процесса при генерации id нельзя по ряду причин.
Решение, либо выносить генерацию id в микросервис, либо заставить мастер процесс, запускающий дочерние процессы с приложением, передавать в дочерние процессы какой-то id, который уже можно будет использовать в алгоритме.


Вторая проблема, это раскрытие информации о инфраструктуре проекта. Количество серверов и количество датацентров.


Третья проблема заключается в использовании timestamp. Время величина бесконечная и загоняя его в рамки мы обрекаем себя на провал.
Как я уже написал в комментариях, уже сейчас длина timestamp составляет 41 бит и уже в 2039 длина составит 42 бита. Мы получим переполнение места и генерация id начнется с нуля, то есть мы будем получать id, такие же как и 69 лет назад. А когда длина timestamp составит 43 бита (2248 год) мы получим переполнение Integer.


Twitter может пренебречь этой проблемой, так как он может просто не хранить твиты столько времени, но это применимо не для всех.


Есть так же несколько решений. Как сказал MikalaiR, можно изменить дату начала отсчёт времени, например на начало эпохи 2000-01-01, что отложит неизбежное ещё на 30 лет.
Более правильное решение предложил devalone. Можно перераспределить биты и увеличить место под timestamp, например до 45 бит, что отложит переломный момент до 3084 года, а переполнение Integer мы получим только в 4199 году.


Пример генерации Snowflake id:


$last_time = 0;
$datacenter = 1;
$machine = 1;
$sequence = 0;
$offset = 0;
// можно изменить начало отсчёта даты
//$offset = strtotime('2000-01-01 00:00:00') * 1000;

$time = floor(microtime(true) * 1000) - $offset;

if (!$last_time || $last_time == $time) {
    $sequence++;
}

var_dump(sprintf('%b', $time));

$id = 1 << (64 - 1);
$id |= $time << (64 - 1 - 41);
$id |= $datacenter << (64 - 1 - 41 - 5);
$id |= $machine << (64 - 1 - 41 - 5 - 5);
$id |= $sequence << (64 - 1 - 41 - 5 - 5 - 12);

// или в одну строчку
//$id = 1 << 63 | $time << 22 | $datacenter << 17 | $machine << 12 | $sequence;

var_dump(sprintf('%b', $id));

// упаковываем в base64
$id = dechex($id);
$id = hex2bin($id);
$id = base64_encode($id);
$id = str_replace('=', '', $id);

var_dump($id); // oT561auCEAE

Казалось бы, вот он YouTube id, но нет. Если вы сгенерируете несколько id, то вы увидите, что они почти не отличаются, а последние 4 символа вообще константа.


oT5+eFUCEAE
oT5+eU8CEAE
oT5+ekkCEAE

Для сравнения, id видео загруженных на YouTube с разницей в несколько секунд.


fxEbFmSBuIM
et34RK4qLy8
3oypcgF-LJQ

Сравнив идентификаторы в бинарном представлении можно так же убедится, что Snowflake id имеет значительно больше сходств чем YouTube


1010000100111110011111100111100001010101000000100001000000000000 // oT5+eFUCEAE
1010000100111110011111100111100101001111000000100001000000000000 // oT5+eU8CEAE
1010000100111110011111100111101001001001000000100001000000000000 // oT5+ekkCEAE

1010000100111110011111100111100001000001000000100001000000000000 // сумма

0111111100010001000110110001011001100100100000011011100010000011 // fxEbFmSBuIM
0111101011011101111110000100010010101110001010100010111100101111 // et34RK4qLy8
0000000011011110100011001010100101110010000000010100101100100101 // 3oypcgF-LJQ

0000000000010000000010000000000000100000000000000000100000000001 // сумма

Я все ещё склонен думать, что YouTube использует случайно или псевдослучайно сгенерированные значения.


Update 21-02-2018


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


Генерация случайных знаков


$length = 11;
$chars = '0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ_-';
$uid = '';
while ($length-- > 0) {
    $uid .= $chars[random_int(0, 63)];
}
var_dump($uid); // 4rnQMtJ4HRw

Плюсы


  • Управляемость длиной идентификатора
  • Нет ограничений в длине идентификатора
  • Возможно изменить самими символами в наборе символов
  • Возможно изменить количество символов в наборе
  • За счёт нескольких вызовов random_int() уменьшается вероятность локальных коллизий

Минусы


  • Несколько вызовов random_int() негативно сказывается на производительности

Побайтовая генерация ID


$length = 64;
$uid = '';
while ($length-- > 0) {
    $uid .= random_int(0, 1);
}
$uid = bindec($uid);
$uid = dechex($uid);
$uid = hex2bin($uid);
$uid = base64_encode($uid);
$uid = str_replace(['=', '+', '/'], ['', '-', '_'], $uid);
var_dump($uid); // tDiGk9YyWAA

Плюсы


  • Управляемость длиной идентификатора
  • Более частый вызов random_int(), по сравнению с предыдущим вариантом, уменьшает вероятность локальных коллизий.

Минусы


  • Теряется возможность изменить сами символы в наборе символов
  • Теряется возможность изменить количество символов в наборе
  • Идентификатор ограничен 64 битами
  • Несколько вызовов random_int() негативно сказывается на производительности

Случайные числа и временная метка


$time = floor(microtime(true) * 1000);
$prefix = random_int(0, 0b111111111);
$suffix = random_int(0, 0b111111111);
$uid = 1 << (9 + 45 + 9);
$uid |= $prefix << (9 + 45);
$uid |= $time << 9;
$uid |= $suffix;
$uid = dechex($uid);
$uid = hex2bin($uid);
$uid = base64_encode($uid);
$uid = str_replace(['=', '+', '/'], ['', '-', '_'], $uid);
var_dump($uid); // vELDchIFvk0

Плюсы


  • Уменьшается вероятность коллизии за счет использования временной метки

Минусы


  • Теряется возможность изменить сами символы в наборе символов
  • Теряется возможность изменить количество символов в наборе
  • Идентификатор ограничен 64 битами
  • Затруднительно управлять длиной идентификатора
  • Как и в случае с Snowflake, идентификаторы получаются схожими

Случайные числа и плавающая временная метка


$time = floor(microtime(true) * 1000);

$prefix_length = random_int(1, 18);
$prefix = random_int(0, bindec(str_repeat('1', $prefix_length)));

$suffix_length = 18 - $prefix_length;
$suffix = random_int(0, bindec(str_repeat('1', $suffix_length)));

$uid = 1 << ($suffix_length + 45 + $prefix_length);
$uid |= $prefix << ($suffix_length + 45);
$uid |= $time << $suffix_length;
$uid |= $suffix;
$uid = dechex($uid);
$uid = hex2bin($uid);
$uid = base64_encode($uid);
$uid = str_replace(['=', '+', '/'], ['', '-', '_'], $uid);
var_dump($uid); // 4WG5MmC3SQo

Плюсы


  • Идентификаторы получаются менее схожими, чем в предыдущем примере, даже при использовании одной временной метки.

Минусы


  • Теряется возможность изменить сами символы в наборе символов
  • Теряется возможность изменить количество символов в наборе
  • Идентификатор ограничен 64 битами
  • Затруднительно управлять длиной идентификатора
  • Из-за непостоянной позиции временной метки, коллизия все же возможна

Генерация случайных байт


$uid = random_bytes(8);
$uid = base64_encode($uid);
$uid = str_replace(['=', '+', '/'], ['', '-', '_'], $uid);
var_dump($uid); // BOjs1VmavxI

Плюсы


  • Наиболее короткое и простое решение из всех
  • Нет ограничений в длине идентификатора

Минусы


  • Теряется возможность изменить сами символы в наборе символов
  • Теряется возможность изменить количество символов в наборе
  • Усложнено управление длиной конечного идентификатора

PS: Поправьте меня в комментариях если я что-то упустил.

Проголосовать:
+22
Сохранить: