Вы когда-нибудь задумывались как устроен 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

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

Комментарии (61)


  1. sanchezzzhak
    02.02.2018 17:36

    сжатие числа через Base62 тоже самое делает, почему назван Base64?


    1. ghost404 Автор
      02.02.2018 17:39

      только потому, что это удобней в расчетах 64 = 26


  1. Akuma
    02.02.2018 18:17
    +1

    В целом интересная статья, хоть и довольно простая, но читать было интересно, спасибо.

    У меня на паре проектах используется подобный подход для генерации ID картинок, только используются только числа (BIGINT поле). Как раз по причине «чтобы получить ID из БД, нужно создать запись».
    Сейчас в базе 5 545 434 картинок (около 400 Гб). Ни одной коллизии пока не наблюдал.


    1. andreishe
      03.02.2018 01:39

      Проверьте при случае фрагментацию индексов, в которые этот ID включен...


      1. Akuma
        03.02.2018 02:10

        Честно говоря, не замечал проблем с производительностью. Хотя и оптимизацию таблицы не проводил… давно, не помню когда, но когда-то проводил. InnoDB.

        А как посмотреть какие-то значения по фрагментации? Никогда не сталкивался просто, самому интересно.


        1. andreishe
          04.02.2018 04:04

          Я в основном работаю с SQL Server, но принципы работы должны быть вполне общие.
          Индекс — это подмножество столбцов таблицы, отсортированное определенным образом. Использование случайных ключей означает, что при вставке новой строки в индекс, она будет вставляться в его середину, что в свою очередь, с весьма большой вероятностью, приведет к page split. Т.е. через некоторое время окажется, что индекс разреженно размазан по страницам БД, а т.к. все дисковые операции работают с целыми страницами, вполне может оказаться, что для того, чтобы прочитать индекс размером N байт, потребуется прочитать 10*N байт с диска, т.к. данные лежат очень неплотно. Когда размеры данных и индексов на несколько порядков меньше, чем размер доступной памяти, это будет незаметно (все прокешируется), но когда размеры станут сравнимыми, или станут больше, чем доступно памяти, могут начаться заметные просадки производительности из-за сильной фрагментации.


          1. netch80
            04.02.2018 13:08

            чтобы прочитать индекс размером N байт, потребуется прочитать 10*N байт с диска, т.к. данные лежат очень неплотно

            Это нужно какие-то спецметоды разрежения применять, чтобы такое получить. В подавляющем большинстве реализаций B, B?-деревьев производится оптимизация на заполнение каждой страницы индекса не менее чем на 1/2, 2/3.
            Можете указать точный источник страшилки про "10*N"?


          1. Akuma
            04.02.2018 13:12
            -1

            Звучит логично. На счет 10*N тоже не уверен, как и комментатор ниже, но все же.

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

            А что касается производительности. У меня эта таблица используется под хранение загруженных картинок (не BLOB конечно, просто информация что картинка есть и ее мета-данные) и основные задержки — это работа с файлами, чем с БД.


  1. cjbars
    02.02.2018 18:27

    А можно вас попросить вставить значки возведения в степень? А то читаешь 2341 и не понимаешь что это 23^41, а это разница в 41 порядок, что действительно очень много.


    1. WebProd
      02.02.2018 18:54

      не в 41


    1. ghost404 Автор
      02.02.2018 19:05

      Скажите, через что вы смотрите статью?
      В статье написано (2341):


      23<sup>41</sup>

      Много таких кому некорректно выводится возведение в степень?


      1. Grebenshikov
        03.02.2018 00:22

        Как минимум, все кто читают статью через iOS приложение, подозреваю.


        1. Zenitchik
          03.02.2018 00:37

          Я полагаю, это проблемы iOS приложения, а не статьи.


      1. cjbars
        03.02.2018 17:04
        -1

        Ios приложение, в принципе это действительно наши проблемы, но хотелось бы чтобы и о нас позаботились :-) напишу разработчикам приложения, может поправят


  1. antonverov
    02.02.2018 18:49
    +1

    Всё было замечательно до строчки
    self::CHARS[random_int(0, 63)];
    Какой ужасный способ генерировать уникальные идентификаторы. Хороший UUID имеет вероятность коллизии намного меньше расчетной за счет использования меток времени и идентификатора локальной ноды.


    1. ghost404 Автор
      02.02.2018 18:56
      +1

      Это только пример. Вам ни кто не мешает заменить метод генерации уникального значения.


      1. php7
        03.02.2018 14:58

        Так это самая интересная часть статьи.
        А тут такой облом.


        1. ghost404 Автор
          03.02.2018 15:00

          Я не знаю точно каким образом формируют ID в YouTube. Я только предполагаю. Возможно это и не случайно сгенерированный значения, а что-то на основе timestamp, как в случае с Snowflake. Но я в это сомневаюсь, так как длинна ID слишком маленькая для хранения в ней timestamp, и разброс ID у виде загруженных в одно время слишком большой для последовательного timestsmp.


          А вопрос генерирования по-настоящему случайных чисел выходит за рамки этой статьи.


          1. MasMaX
            05.02.2018 09:54

            Хранить timestamp не надо, достаточно просто на его основе делать ID, это повысит уникальность


    1. gresolio
      03.02.2018 17:55

      Мне тоже эта строчка что-то не внушает доверия. Раньше была более интересная статья по теме:
      Генерируем псевдослучайные ID а-ля Youtube


    1. isden
      04.02.2018 10:19

      Вот да. Мне сразу вспомнился случай, когда ловили коллизии на вроде бы случайных ID из 32 символов по аналогичной причине. Качество ГСЧ — тут ключевая вещь, иначе все эти умные формулы с википедии не имеют смысла.


    1. ghost404 Автор
      05.02.2018 12:18

      И при этом, для получения UUID чаще всего используют random_bytes(), mt_rand() и еще mt_rand() ну и openssl_random_pseudo_bytes() до кучи.


  1. YaRobot
    02.02.2018 19:43
    +1

    Вы вовремя. Как раз стал вопрос, чем заменить UUID
    Спасибо.


    1. jreznot
      02.02.2018 19:58

      Просто возьмите бинарное значение UUID и сожмите его в base64


  1. MikalaiR
    02.02.2018 20:41
    +2

    Это все хорошо, но мне кажется более практичным использование Snowflake-id (используется в Twitter, Instagram, etc). Структура на картинке. image
    Огромный плюс: данные в бд при сортировке по id остаются отсортированными по времени.


    1. ghost404 Автор
      02.02.2018 21:51

      Спасибо. Довольно занятная штука.
      Я смотрю разные реализации и вижу что вместо generator используют datacenter ID и machine ID.
      Я не нашел примера с generator. Что это должно быть? Случайно генерируемое число?


      1. MiXei4
        02.02.2018 22:04

        Подозреваю, под Generator имеется в виду тот, кто генерирует, то есть это и есть machine id или что-то аналогичное, определяющее, где был сгенерирован id.


      1. EvilFox
        02.02.2018 22:18

        Вариации самые разные.
        https://engineering.instagram.com/sharding-ids-at-instagram-1cf5a71e5a5c у инстаграма было как минимум так.

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


        1. ghost404 Автор
          02.02.2018 22:30

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

          Ну почему же? Я упомянул в статье хеширующие библиотеки.
          Кроме hashids полно других аналогичных библиотек.
          В этой статье речь не о них.


    1. devalone
      03.02.2018 13:38

      а зачем sign?


      1. ghost404 Автор
        03.02.2018 14:12

        До 1 ноября 2004 timestsmp имел длинна 40 бит, а не 41 и нужен был ещё один бит перед timestamp, чтоб ограничить длину.
        Однако это приводит к новой проблеме, ибо уже 7 сентября 2039 года timestamp будет иметь длину 42 бита, что может привести к плачевным результатам.


        1. MikalaiR
          03.02.2018 15:44

          В snowflake используется не unix-timestamp, а timestamp от некоторой собственной даты (у твиттера например — 2006-03-21 20:50:14). Так что никаких плачевных результатов быть не должно.


          1. ghost404 Автор
            03.02.2018 16:04

            Да. Я видел подобные решения, когда за дату отсчёт а берут например начало этой эпохи 2000-01-01, но это не решение проблемы, а откладывание ее. Для начала эпохи переходный момент наступит 6 сентября 2069.


        1. devalone
          03.02.2018 20:08

          Так можно же взять 64 бита, его надолго ещё хватит.


          1. ghost404 Автор
            03.02.2018 20:46

            Безусловно можно увеличить количество бит под timestamp. Я бы ещё добавил id процесса в котором генерируется id. Если это web приложение, то оно обычно крутится не в одном процессе и есть вероятность коллизии в пределах одного сервера. Таким образом мы всё больше и больше увеличиваем длинную id.


          1. MikalaiR
            04.02.2018 00:42

            Тут основная фича в том, что весь id — 64-битное целое. Это гораздо быстрее, чем тот же uuid.


  1. outcoldman
    02.02.2018 21:42

    Мелочь, но поправьте, в UUID 32, а не 33. Что дает 2^128, но с учетом что в UUID прописывается variant & version, то 2^122.

    Rand это один из вариантов, имхо для многих систем хочется иметь монотонно возрастающий идентификатор, смотри на docs.mongodb.com/manual/reference/method/ObjectId/#ObjectId

    Статья заинтересовала, но как только дошел до «Domain-driven design (DDD)»…


    1. ghost404 Автор
      02.02.2018 21:57

      Действительно. Обсчитался. Прошу прощения


  1. medvedevia
    02.02.2018 21:47

    UUID имеет вид 550e8400-e29b-41d4-a716-446655440000, имеет длину 33 символа

    Откуда взялся 33 символ?))


    1. ghost404 Автор
      02.02.2018 22:02

      Спасибо. Исправил


  1. medvedevia
    02.02.2018 21:57

    UUID это 16 байт, которые при переводе в BASE64 дадут строку длиной 24 символа, причем 2 последних всегда будут знак равно "=", которые можно отбросить, итого получится 22 символа. Автор, Вы не правы…


    1. ghost404 Автор
      02.02.2018 22:20

      Для тех кто не понял, это делается так.
      Я согласен, что можно упаковать UUID в Bse64, но мне кажется проще сразу сгенерировать Base64.
      Да и не всегда нужен такой длинный id.
      YouTube же как-то обходится 11 символами.


      1. areht
        02.02.2018 22:39

        > YouTube же как-то обходится 11 символами.

        Может быть им не надо размером бороться с коллизиями?

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


        1. ghost404 Автор
          02.02.2018 23:02

          Об этом и статья. Определитесь с потребностями и выбирайте соответствующее решение, а не берите UUID потому, что все так делают.
          Я привел формулы и расчеты специально, для того, что бы каждый мог оценить свои потребности. Может кому-то и UUID окажется маловат.


          1. areht
            03.02.2018 09:28
            +2

            > берите UUID потому, что все так делают.

            UUID фактически гарантирует уникальность результата.
            Youtube гарантирует уникальность результата.
            Ваше решение — ну фиг знает.

            А что бы «соответствующее решение» надо откуда то узнать устраивающую меня нижнюю границу коллизий. «Это даёт нам гарантию, что первые несколько миллионов идентификаторов будут уникальными» (нет, если генерить, то одинаковыми могут оказаться хоть первые 2) — но почему у вас «несколько миллионов», а не «несколько сотен тысяч» или «несколько десятков миллионов»?

            А сравнивать с ютубом по длине — просто некорректно, у них вероятность коллизии нулевая, у вас — нет.


  1. CyberSoft
    02.02.2018 22:32

    Вот как генерируют UUID в Elasticsearch (6 байт времени + 6 байт поксоренного мак-адреса и 3 байта счётчик). И эта версия разработчиков не устраивает, поэтому они наколдовали немного по другому и теперь новые UUID будут сортироваться и лучше ужиматься.


    1. sanchezzzhak
      02.02.2018 23:33

      в mongodb ObectId тоже содержит дату

      $id= "5824736fcaec5460bbfdc489";
      $timestamp = hexdec(substr($id,0,8));
      $identifier = hexdec(substr($id,8,6));
      $pid = hexdec(substr($id,14,4));
      $counter = hexdec(substr($id,18,6));


  1. Caravus
    02.02.2018 23:08


    1. ghost404 Автор
      03.02.2018 00:33

      Да. Хотел добавить это видео в статью, но не стал. Спасибо.


  1. rkfg
    03.02.2018 01:30

    Вот ещё вариант, который гарантирует полное использование выделенного адресного пространства без повторений. Можно использовать в БД обычные id, а юзеру выдавать зашифрованное алгоритмом значение, ну и расшифровывать обратно при вводе. Я год назад интереса ради реализовал этот алгоритм, правда, не на PHP, а на C++. Из-за работы с большими числами скорость будет заведомо ниже, чем при случайной генерации, но зато эти функции и нужны лишь на вводе/выводе, что позволяет оставить традиционную логику взаимодействия с БД и ключами.


  1. Dark_Purple
    03.02.2018 01:31

    нижнее подчеркивание

    Почему все говорят нижнее подчеркивание, а не просто подчеркивание? Коль скоро оно подчеркивание, то оно по определению снизу — под текстом.


    1. we1
      03.02.2018 07:44

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


    1. extempl
      03.02.2018 08:30

      Наверное потому что просто "подчёркивание" требует какого-то префикса, но да, правильнее было бы "символ подчёркивания".


      1. Zenitchik
        03.02.2018 14:41

        Мы в школе говорили «подстрочник» или «подсрачник» — кому как нравилось. Потом как-то отвыкли.


    1. ghost404 Автор
      03.02.2018 11:23

      Я думаю, проблема закралась в том, что слово Underscore имеет несколько значений перевода и одно из них нижнее подчеркивание. От того в русском языке и устоялся этот термин, хотя если верить Википедии, то это Плеоназм и правильней говорить просто "подчеркивание".


      А верхнее подчеркивание называется Overline или Черта сверху.


  1. JekaMas
    03.02.2018 11:25

    Генерируемый ID не обязательно случайный, он вполне может быть возрастающим. Пример от twitter https://github.com/twitter/snowflake
    Можно сочетать достоинства обоих подходов.


  1. LynXzp
    03.02.2018 15:00

    Чтобы ID выглядел случайным, но при этом был возрастающим и перебирал все комбинации без коллизий я использовал блочный шифр с неизменным ключом. Можно например модифицировать AES. О криптостойкости здесь речи не идет, поэтому можно снизить количество итераций, хотя он все равно быстрый. За то мой ID в 4 символа закончился бы через 16млн комбинаций. (Точнее там не base64, а более широкий алфавит, соотв. лимит выше, причем заметно, но сайт уже давно закрыл, сейчас не вспомню, написать свой base* тоже не сложно)


  1. firk
    03.02.2018 17:26

    Эм, вся суть статьи: youtube использует для видео случайные идентификаторы длиной в 11 символов с алфавитом из 64 знаков. Автор так же предполагает, что это не для защиты от перебора. То есть сначала озвучена всем очевидная банальность, а затем вода на 10 страниц. Ах да, ещё посчитано, чему равно 64 в 11 степени, для чего выделен целый абзац текста.


    Что тут собственно обсуждать?


  1. sand14
    04.02.2018 10:57

    Итого, в системе должны генерироваться глобально-уникальные идентификаторы (с алгоритмом генерации, позволяющем обеспечивать глобально-уникальность при генерации локально "на местах"), затем для краткости представления и более удобного использования в URL, сгенерированные числовые идентификаторы должны преобразовываться в строку в формате псевдо-Base64.


    На этом статью можно было бы и закончить.
    Однако, из нее следует, что для генерации идентификатора используется не UUID, а что-то другое?
    Тогда что именно, и почему было принято кодировать в Base64 не UUID, а какие-то другие идентификаторы?


    Может, в системе разработаны алгоритмы, позволяющие уменьшить вероятность коллизий при локальной генерации по сравнению с UUID (с поправкой на то, что в системе генерируются идентификаторы меньшей разрядности, чем UUID)?
    Но нет, про это ничего не сказано, вместо этого приведен код-заглушка с использованием генератора псевдослучайных чисел.


    Статья имела бы смысл, если бы там реально было рассказано о недостатках UUID и о том, как был разработан алгоритм с меньшей вероятностью коллизий при распределенной генерации идентификаторов.


    Тем более, что UUID действительно имеет недостатки:


    • Если для генерации UUID использовать функции операционной системы, то алгоритм генерации зависит от версии ОС, что не способствует минимизации коллизий при распределенной генерации.
    • В ранних версиях Windows при формировании UUID использовался MAC-адрес, что теоретически могло позволить восстановить место генерации ID, что не есть "правильно". Сейчас такого нет, но тем не менее.
    • В Linux при генерации UUID происходит (возможно, уже тоже починили — нужно уточнять) обращение к некоему файлу, т.е., к файловой системе, что соответствующим образом сказывалось на производительности при массовой генерации.

    Отсюда и вопрос:
    может, в Youtube разработан свой, более надежный, алгоритм генерации распределенного UUID, API c с платформенно-независимой реализацией установлен на всех локальных и глобальных серверах, что позволяет реально избегать коллизий?
    Об этом в статье ни слова.


  1. sand14
    04.02.2018 11:04

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

    Как можно сравнивать UUID (это прежде всего алгоритм генерации 128-битных чисел) и Base64 (форму представления?).


    Да, понятие UUID имеет и каноническую форму представления (вида 00000000-0000-0000-0000-000000000000), но его можно представить и форме Base64.
    Прежде всего это требования к алгоритму генерации.
    Если генерировать UUID так: 0, 1, 2… и записывать это как
    00000000-0000-0000-0000-000000000000
    00000000-0000-0000-0000-000000000001
    00000000-0000-0000-0000-000000000002
    то это не будут UUID.


    А когда вы пишите о неких Base64-идентификаторах, что имеется в виду?
    Форма представления — это понятно.
    А собственно, алгоритмы генерации какие?


  1. samodum
    04.02.2018 19:53

    длиНа
    длиНой