[Техпоп] Инкрементальные и строковые идентификаторы

На DTF в качестве идентификаторов пользователей используются последовательные числа (1, 2, 3…). А на Youtube используются более сложные строковые идентификаторы (8X2kIfS6fb8, qIcTM8WXFjk). Рассмотрим, зачем они нужны, как мне это пригодилось на практике и как я узнал, что на DTF 256134 зарегистрированных пользователя.

С этой темой я познакомился благодаря видео Тома Скотта. Поэтому если вы его видели, то часть этого текста будет вам знакома, так как я местами просто пересказываю видео.

Когда мы храним данные в базах данных, мы используем уникальные идентификаторы (ID), чтобы легко читать данные из базы и записывать в нее. Самый простой и популярный вариант идентификаторов — это автоматически инкрементируемые числовые идентификаторы. Например, когда мы записываем первого пользователя, у него получается идентификатор 1. Когда пишем следующего, у него будет идентификатор 2. И так далее. Каждый раз это число инкрементируется, т.е. увеличивается на единицу.

DTF использует инкрементальные ID для хранения пользователей, статей, подсайтов, комментариев и, вероятно, много чего еще. DTF (и другие сайты Комитета) не стесняются открыто показывать эти идентификаторы. Например, эта ссылка откроет профиль пользователя с ID 1:

Это Редакция DTF — учетная запись, которая была сделана первой. ID 2 и 3 принадлежат Сергею Бабаеву и Леониду Сиротину — основателям современного DTF. 4 — Владислав Цыплухин, на момент основания DTF был главой Комитета. Сейчас не знаю, чем занимается, но он все еще в Комитете.

И так далее. Каждый новый пользователь получает следующий номер. Мой ID — 354. Это значит, что я 354-й зарегистрировавшийся пользователь на DTF. Я зарегистрировался в первый день официального открытия нового DTF, сразу же как прочитал анонс на vc.ru 27 июля 2016 года. Есть, чем гордиться. На самом деле это заметно только в одном месте: если смотреть, кто плюсанул/минусанул пост или комментарий, то там пользователи упорядочены по ID. Поэтому я там почти всегда первый:

Таким же образом можно найти самого последнего пользователя. На момент написания статьи, таким пользователем является Фортунато Родригес — у него ID 256134. Т.е. на DTF 256134 зарегистрированных пользователей. На самом деле чуть меньше, так как подсайты используют ту же последовательность идентификаторов — об этом я напишу в одном из своих следующих постов.

Для сравнения, на vc.ru зарегистрировано 541130 пользователей, а на tjournal.ru — 328843.

Инкрементальные идентификаторы — это просто и удобно, но почему тогда Youtube использует не их, а случайно сгенерированные строки из 11 символов? Например, это ссылка на видео с ID 8X2kIfS6fb8:

Почему так сложно? У этого есть две основных причины.

1. У Youtube очень много серверов, а новые видео создаются каждую секунду. Очень сложно синхронизировать серверы так, чтобы они четко увеличивали ID на единицу и чтобы два каких-нибудь сервера случайно не получили бы одинаковое число. Поэтому они используют какой-то более сложный алгоритм генерации идентификаторов для распределенных систем. Например, Twitter использует самописную систему Snowflake, которая генерирует идентификаторы не на основе глобальной последовательности, а на основе времени, идентификатора сервера и локальной последовательности в рамках одного сервера. Кстати, похожий алгоритм мы использовали на моей прошлой работе.

2. Инкрементальные идентификаторы — это большая дыра в безопасности. Я легко могу посмотреть всех пользователей на DTF, просто перебирая идентификаторы один за другим. Здесь нет никакой приватной информации, поэтому Комитет может не переживать по этому поводу. Но очень плохо, если такие идентификаторы используются, например, в какой-нибудь платежной системе. На хабре есть статья с несколькими хорошими примерами, почему это плохо.

В случае Youtube это тоже проблема. Некоторые видео закрыты и имеют доступ только по ссылке. Если мы можем просто перебрать все идентификаторы, мы можем найти все такие закрытые видео. Но так как там используются строки из 11 символов, которые дают огромное количество возможных идентификаторов, мы можем очень долго перебирать их и так и не наткнуться хоть на какое-нибудь видео. Правда, им нужно отфильтровать идентификаторы, которые содержат какие-нибудь слова, ведь никто не хочет, чтоб в идентификаторе его видео было какое-нибудь оскорбление. Но даже если убрать такие ID, их останется очень много.

У нас в игре у игроков есть профили. Например, так выглядит мой профиль:

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

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

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

Вторая проблема инкрементального ID в профиле — это то, что чем раньше зарегистрировался игрок, тем меньше у него номер. В игре, где люди кастомизируют своих персонажей и украшают свой профиль, меньший номер может реально стать предметом гордости, и люди начнут просто мериться цифрами, которые даже не от них зависят. Раньше люди даже красивые 5- и 6-значные номера ICQ продавали, так что не известно, к чему это может привести в игре.

Поэтому, было решено написать алгоритм, который преобразует инкрементальные идентификаторы в строковые идентификаторы фиксированной длины. У этой задачи есть 3 подзадачи:

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

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

#техпоп #приходько_техпоп