Алгоритм URL YouTube?

Question

Как вы будете генерировать уникальные URL-адреса видео, которые использует YouTube?

Пример:

• http://www.youtube.com/watch?v=CvUN8qg9lsk

Answer 1

YouTube использует кодировку Base64 для создания идентификаторов для каждого видео. Символы, участвующие в создании идентификаторов, состоят из

(A-Z) + (a-z) + (0-9) + (-) + (_). (64 символа).

Используя кодировку Base64 и только до 11 символов, они могут генерировать 73+ уникальных идентификаторов Quintilian. Насколько это большой пул идентификаторов?

Ну, для всех на земле достаточно снимать видео каждую минуту в течение 18000 лет.

И они достигли такого огромного количества, используя только 11 символов (64 * 64 * 64 * 64 * 64 * 64 * 64 * 64 * 64 * 64 * 64), если им нужно больше идентификаторов, они просто должны будут добавить 1 больше символов для их идентификаторов.

Так что, когда видео загружается на YouTube, они в основном случайным образом выбирают из 73+ вариантов Quintilian и смотрят, снято ли оно уже или нет. Если оно не используется, в противном случае ищите другое.

См. Это видео для подробного объяснения.

Answer 2

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

Этот пост отДжефф Этвуд - хороший обзор темы.

И - это онлайн-калькулятор хешей, с которым можно играть.

Answer 3

Нет необходимости использовать хеш. Вероятно, это просто квазислучайное 64-битное значение, пропущенное через base64 или какой-либо эквивалент.

Под квазислучайным я подразумеваю, что это просто взаимно однозначное отображение с подсчитанными целыми числами, просто перемешанное.

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

Обычный base64 добавил бы в конце равно, но в этом случае это подразумевается, потому что размер известен. Сопоставление символов может легко быть чем-то помимо стандарта.

Answer 4

Ссылка Элая на статью Джеффа, на мой взгляд, не имеет значения.Сокращение URL-адреса - это не то же самое, что представление идентификатора миру.Вместо этого лучше было бы преобразовать существующий целочисленный идентификатор в другой radix .

Пример в PHP:

$id = 9999;
//$url_id = base_convert($id, 10, 26+26+10); // PHP doesn't like this
$url_id = base_convert($id, 10, 26+10); // Works, but only digits + lowercase

К сожалению, PHP поддерживает толькона базу 36 (цифры + алфавит).База 62 будет поддерживать алфавит как в верхнем, так и в нижнем регистре.

---

Люди говорят об этих других системах:

• Случайное число / буквы - Почему?Если вы хотите, чтобы люди не видели следующее видео (id + 1), просто сделайте его приватным.На таком веб-сайте, как youtube, где он активно показывает любое имеющееся видео, зачем использовать случайные идентификаторы?
• Хеширование идентификатора - эта концепция дизайна действительно воняет.Думаю об этом;Таким образом, у вас есть идентификатор, гарантированный вашим программным обеспечением DBM, чтобы быть уникальным, и вы хэшируете его (вводя коэффициент столкновения)?Назовите мне одну причину, по которой даже стоит подумать об этой идее.
• Использование идентификатора в URL - Если честно, я тоже не вижу никаких проблем с этим, хотя он станет большим, когда на самом деле вы сможете это сделать.выразить то же число с меньшим количеством букв (отсюда и мое решение).
• Использование Base64 - Base64 ожидает байты данных, буквально что угодно, от нуля до пробела.Зачем использовать эту функцию, если ваши данные состоят из числа (то есть из 10 различных символов вместо 256)?

Answer 5

Лучше всего, вероятно, просто генерировать случайные строки и отслеживать (например, в БД), какие строки вы уже использовали, чтобы не дублировать их.Это очень легко реализовать и не может завершиться ошибкой, если правильно реализовано (без дубликатов и т. Д.).

Answer 6

Вы можете создать GUID и использовать его в качестве идентификатора для видео. Гиды вряд ли столкнутся.

Answer 7

Вы можете использовать любую библиотеку или некоторые языки, например, python предоставляет ее в стандартной библиотеке.

Пример:

import secrets


id_length = 12
random_video_id = secrets.token_urlsafe(id_length)

Answer 8

Я предлагаю использовать идеальную хеш-функцию:

Идеальная функция хеширования для удобочитаемых кодов заказа

Как показывает принятый ответ, возьмите число, затем примените последовательность «биективных» (или обратимых) операций к числу, чтобы получить хешированное число.

Вводимые номера должны быть в последовательности: 0, 1, 2, 3 и т. Д.

Answer 9

Не думаю, что параметр URL v имеет какое-либо отношение к контенту (свойства видео, заголовок, описание и т. Д.).

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

Answer 10

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

Случайно выбирая и исчерпывая все значения из набора, выполняется в ожидаемое время O(nlogn): Что такое значение O для наивного случайного выбора из конечного набора?

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