Comments 61
У меня на паре проектах используется подобный подход для генерации ID картинок, только используются только числа (BIGINT поле). Как раз по причине «чтобы получить ID из БД, нужно создать запись».
Сейчас в базе 5 545 434 картинок (около 400 Гб). Ни одной коллизии пока не наблюдал.
Проверьте при случае фрагментацию индексов, в которые этот ID включен...
А как посмотреть какие-то значения по фрагментации? Никогда не сталкивался просто, самому интересно.
Я в основном работаю с SQL Server, но принципы работы должны быть вполне общие.
Индекс — это подмножество столбцов таблицы, отсортированное определенным образом. Использование случайных ключей означает, что при вставке новой строки в индекс, она будет вставляться в его середину, что в свою очередь, с весьма большой вероятностью, приведет к page split. Т.е. через некоторое время окажется, что индекс разреженно размазан по страницам БД, а т.к. все дисковые операции работают с целыми страницами, вполне может оказаться, что для того, чтобы прочитать индекс размером N байт, потребуется прочитать 10*N байт с диска, т.к. данные лежат очень неплотно. Когда размеры данных и индексов на несколько порядков меньше, чем размер доступной памяти, это будет незаметно (все прокешируется), но когда размеры станут сравнимыми, или станут больше, чем доступно памяти, могут начаться заметные просадки производительности из-за сильной фрагментации.
чтобы прочитать индекс размером N байт, потребуется прочитать 10*N байт с диска, т.к. данные лежат очень неплотно
Это нужно какие-то спецметоды разрежения применять, чтобы такое получить. В подавляющем большинстве реализаций B, B⁺-деревьев производится оптимизация на заполнение каждой страницы индекса не менее чем на 1/2, 2/3.
Можете указать точный источник страшилки про "10*N"?
В таком сулчае можно использовать числовые, генерируемые
А что касается производительности. У меня эта таблица используется под хранение загруженных картинок (не BLOB конечно, просто информация что картинка есть и ее мета-данные) и основные задержки — это работа с файлами, чем с БД.
не в 41
Скажите, через что вы смотрите статью?
В статье написано (2341):
23<sup>41</sup>
Много таких кому некорректно выводится возведение в степень?
self::CHARS[random_int(0, 63)];
Какой ужасный способ генерировать уникальные идентификаторы. Хороший UUID имеет вероятность коллизии намного меньше расчетной за счет использования меток времени и идентификатора локальной ноды.
Это только пример. Вам ни кто не мешает заменить метод генерации уникального значения.
А тут такой облом.
Я не знаю точно каким образом формируют ID в YouTube. Я только предполагаю. Возможно это и не случайно сгенерированный значения, а что-то на основе timestamp, как в случае с Snowflake. Но я в это сомневаюсь, так как длинна ID слишком маленькая для хранения в ней timestamp, и разброс ID у виде загруженных в одно время слишком большой для последовательного timestsmp.
А вопрос генерирования по-настоящему случайных чисел выходит за рамки этой статьи.
Генерируем псевдослучайные ID а-ля Youtube
И при этом, для получения UUID чаще всего используют random_bytes(), mt_rand() и еще mt_rand() ну и openssl_random_pseudo_bytes() до кучи.
Спасибо.
Это все хорошо, но мне кажется более практичным использование Snowflake-id (используется в Twitter, Instagram, etc). Структура на картинке.
Огромный плюс: данные в бд при сортировке по id остаются отсортированными по времени.
Спасибо. Довольно занятная штука.
Я смотрю разные реализации и вижу что вместо generator используют datacenter ID и machine ID.
Я не нашел примера с generator. Что это должно быть? Случайно генерируемое число?
https://engineering.instagram.com/sharding-ids-at-instagram-1cf5a71e5a5c у инстаграма было как минимум так.
А вот на тему статьи ютубных идов, есть давно библиотека hashids о которой почему-то не упомянули.
До 1 ноября 2004 timestsmp имел длинна 40 бит, а не 41 и нужен был ещё один бит перед timestamp, чтоб ограничить длину.
Однако это приводит к новой проблеме, ибо уже 7 сентября 2039 года timestamp будет иметь длину 42 бита, что может привести к плачевным результатам.
В snowflake используется не unix-timestamp, а timestamp от некоторой собственной даты (у твиттера например — 2006-03-21 20:50:14). Так что никаких плачевных результатов быть не должно.
Безусловно можно увеличить количество бит под timestamp. Я бы ещё добавил id процесса в котором генерируется id. Если это web приложение, то оно обычно крутится не в одном процессе и есть вероятность коллизии в пределах одного сервера. Таким образом мы всё больше и больше увеличиваем длинную id.
Тут основная фича в том, что весь id — 64-битное целое. Это гораздо быстрее, чем тот же uuid.
Rand это один из вариантов, имхо для многих систем хочется иметь монотонно возрастающий идентификатор, смотри на docs.mongodb.com/manual/reference/method/ObjectId/#ObjectId
Статья заинтересовала, но как только дошел до «Domain-driven design (DDD)»…
UUID имеет вид 550e8400-e29b-41d4-a716-446655440000, имеет длину 33 символа
Откуда взялся 33 символ?))
Может быть им не надо размером бороться с коллизиями?
Всё таки выбор длины ключа стоит начинать с того, какой длинной ключа вы можете обеспечить отсутствие коллизий в вашей жизни, а уже потом смотреть что там у ютуба и почему вам надо бы больше
Об этом и статья. Определитесь с потребностями и выбирайте соответствующее решение, а не берите UUID потому, что все так делают.
Я привел формулы и расчеты специально, для того, что бы каждый мог оценить свои потребности. Может кому-то и UUID окажется маловат.
UUID фактически гарантирует уникальность результата.
Youtube гарантирует уникальность результата.
Ваше решение — ну фиг знает.
А что бы «соответствующее решение» надо откуда то узнать устраивающую меня нижнюю границу коллизий. «Это даёт нам гарантию, что первые несколько миллионов идентификаторов будут уникальными» (нет, если генерить, то одинаковыми могут оказаться хоть первые 2) — но почему у вас «несколько миллионов», а не «несколько сотен тысяч» или «несколько десятков миллионов»?
А сравнивать с ютубом по длине — просто некорректно, у них вероятность коллизии нулевая, у вас — нет.
Вот как генерируют UUID в Elasticsearch (6 байт времени + 6 байт поксоренного мак-адреса и 3 байта счётчик). И эта версия разработчиков не устраивает, поэтому они наколдовали немного по другому и теперь новые UUID будут сортироваться и лучше ужиматься.
Вот ещё вариант, который гарантирует полное использование выделенного адресного пространства без повторений. Можно использовать в БД обычные id, а юзеру выдавать зашифрованное алгоритмом значение, ну и расшифровывать обратно при вводе. Я год назад интереса ради реализовал этот алгоритм, правда, не на PHP, а на C++. Из-за работы с большими числами скорость будет заведомо ниже, чем при случайной генерации, но зато эти функции и нужны лишь на вводе/выводе, что позволяет оставить традиционную логику взаимодействия с БД и ключами.
нижнее подчеркивание
Почему все говорят нижнее подчеркивание, а не просто подчеркивание? Коль скоро оно подчеркивание, то оно по определению снизу — под текстом.
Наверное потому что просто "подчёркивание" требует какого-то префикса, но да, правильнее было бы "символ подчёркивания".
Я думаю, проблема закралась в том, что слово Underscore имеет несколько значений перевода и одно из них нижнее подчеркивание. От того в русском языке и устоялся этот термин, хотя если верить Википедии, то это Плеоназм и правильней говорить просто "подчеркивание".
А верхнее подчеркивание называется Overline или Черта сверху.
Генерируемый ID не обязательно случайный, он вполне может быть возрастающим. Пример от twitter https://github.com/twitter/snowflake
Можно сочетать достоинства обоих подходов.
Эм, вся суть статьи: youtube использует для видео случайные идентификаторы длиной в 11 символов с алфавитом из 64 знаков. Автор так же предполагает, что это не для защиты от перебора. То есть сначала озвучена всем очевидная банальность, а затем вода на 10 страниц. Ах да, ещё посчитано, чему равно 64 в 11 степени, для чего выделен целый абзац текста.
Что тут собственно обсуждать?
Итого, в системе должны генерироваться глобально-уникальные идентификаторы (с алгоритмом генерации, позволяющем обеспечивать глобально-уникальность при генерации локально "на местах"), затем для краткости представления и более удобного использования в URL, сгенерированные числовые идентификаторы должны преобразовываться в строку в формате псевдо-Base64.
На этом статью можно было бы и закончить.
Однако, из нее следует, что для генерации идентификатора используется не UUID, а что-то другое?
Тогда что именно, и почему было принято кодировать в Base64 не UUID, а какие-то другие идентификаторы?
Может, в системе разработаны алгоритмы, позволяющие уменьшить вероятность коллизий при локальной генерации по сравнению с UUID (с поправкой на то, что в системе генерируются идентификаторы меньшей разрядности, чем UUID)?
Но нет, про это ничего не сказано, вместо этого приведен код-заглушка с использованием генератора псевдослучайных чисел.
Статья имела бы смысл, если бы там реально было рассказано о недостатках UUID и о том, как был разработан алгоритм с меньшей вероятностью коллизий при распределенной генерации идентификаторов.
Тем более, что UUID действительно имеет недостатки:
- Если для генерации UUID использовать функции операционной системы, то алгоритм генерации зависит от версии ОС, что не способствует минимизации коллизий при распределенной генерации.
- В ранних версиях Windows при формировании UUID использовался MAC-адрес, что теоретически могло позволить восстановить место генерации ID, что не есть "правильно". Сейчас такого нет, но тем не менее.
- В Linux при генерации UUID происходит (возможно, уже тоже починили — нужно уточнять) обращение к некоему файлу, т.е., к файловой системе, что соответствующим образом сказывалось на производительности при массовой генерации.
Отсюда и вопрос:
может, в Youtube разработан свой, более надежный, алгоритм генерации распределенного UUID, API c с платформенно-независимой реализацией установлен на всех локальных и глобальных серверах, что позволяет реально избегать коллизий?
Об этом в статье ни слова.
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-идентификаторах, что имеется в виду?
Форма представления — это понятно.
А собственно, алгоритмы генерации какие?
длиНой
Хочу как у YouTube