задний план
При ежедневном развитии бизнеса обычно необходимо однозначно идентифицировать некоторые данные, например, присвоить уникальный идентификатор хранилищу большого количества просканированных статей, присвоить номера заказам, размещенным пользователями, и так далее. Когда объем параллелизма невелик, идентификатор первичного ключа, который автоматически увеличивается базой данных, обычно используется в качестве уникального идентификатора. Когда объем параллелизма велик, для создания идентификаторов будут рассматриваться некоторые распределенные схемы генерации идентификаторов. Из-за некоторых особых бизнес-требований в нашем бизнесе также используется генерация распределенных идентификаторов, и были исследованы различные решения для распределенных идентификаторов. Итак, здесь мы делимся с вами некоторыми нашими исследованиями и практическим опытом оптимизации в процессе практики.Поскольку длина относительно велика, мы в основном делим ее на три статьи:
[Distributed Series 02] Принципиальный анализ платформы распределенного создания идентификаторов с открытым исходным кодом Leaf и uid-generator
[Distributed Series 03] Проблемы и улучшения оптимизации платформы генерации распределенных идентификаторов с открытым исходным кодом Leaf и uid-generator
Резюме
Эта статья является первой в [Distributed Series 01], в основном включающейВведение в схему генерации распределенного идентификатораиИсследование схемы генерации ID существующих крупных компанийдве части
1. Введение в схему генерации распределенного идентификатора
В настоящее время широко используемые схемы генерации распределенных идентификаторов в основном включают следующее:
1. Используйте алгоритм UUID для создания уникального идентификатора.
2. Используйте самоинкремент первичного ключа автономной базы данных для создания уникального идентификатора.
3. Автоинкремент первичного ключа для нескольких баз данных генерирует уникальный идентификатор. (Установите размер шага, чтобы различать разные базы данных)
4. База данных сегментируется для создания уникального идентификатора. (Например, режим сегмента в фреймворке Meituan Leaf)
5. Создайте уникальный идентификатор (например, режим «Снежинка» в кадре «Лист» группы США, Baidu Uid-Generator)
Это моя сводная таблица:
| план | преимущество | недостаток | Применимая сцена |
|---|---|---|---|
| Сгенерировать уникальный идентификатор с использованием алгоритма UUID | нет зависимостей | ID слишком длинный и не является числом | Сгенерировать идентификатор_сеанса |
| Создание уникального идентификатора с помощью автоматического увеличения первичного ключа базы данных на одном компьютере. | Легкий доступ, монотонно увеличивающийся | Эффективность генерации низкая, сильно зависит от базы данных, а id непрерывен | Он подходит для предприятий с низким параллелизмом. |
| Автоинкремент первичного ключа для нескольких баз данных генерирует уникальный идентификатор | Легкий доступ, монотонно увеличивающийся, а эффективность генерации выше, чем у автономной базы данных. | Неудобно расширить, сильную зависимость от базы данных, идентификатор непрерывный | Идентификатор генерации схемы, подходящий для подбазы данных и подтаблицы |
| Нумерация сегментов базы данных для создания уникального идентификатора | эффективный | Сильно зависит от базы данных, идентификатор непрерывен | Он подходит для бизнеса с высоким параллелизмом генерации идентификаторов, а непрерывный идентификатор не разрушит бизнес информационной безопасности. |
| Алгоритм снежинки сгенерировал уникальный идентификатор | Высокая эффективность во время работы не может зависеть от других компонентов | Неравномерное распределение идентификаторов может привести к искажению данных для некоторых предприятий. | Подходит для предприятий с высоким параллелизмом генерации идентификаторов |
1.UUID
Проще говоря, UUID — это уникальный идентификатор, сгенерированный сервером на основе такой информации, как текущее время, счетчик (счетчик) и идентификация оборудования без каких-либо внешних зависимостей (например, алгоритм, подобный Snowflake, требует наличия реестра).
преимущество
нет зависимостей
Другие технические решения зависят, например,Автоинкремент первичного ключа базы данных на одном компьютере создает идентификаторСильная зависимость от базы данных,Схема алгоритма типа SnowflakeПо крайней мере, центр регистрации требуется при запуске.Режим Snowflake фреймворка Leaf должен регулярно загружать временные метки в центр регистрации, а генерация UUID не требует каких-либо внешних зависимостей.
недостаток
ID слишком длинный и не является числом
Конечно, к расходам уникальности, то есть для приведения результатов генерируется, как правило, 32-битная строка. Поскольку строка слишком длинная, а не в цифровом формате, она не подходит в качестве основного ключа базы данных.
(Строкольный идентификатор в качестве первичного ключа, когда данные будут вставлены в кластеризованный индекс, случайно вставляются случайным образом, страницы могут вызывать разделение. Дальнейшая строка символа сравнения больше, чем стоимость цифрового типа, строка символов запроса в качестве основного идентификатора символов Числа будут ниже, чем эффективность первичного ключа типа.)
Применимая сцена
Обычно его можно использовать как временный уникальный идентификатор, например, после входа пользователя в систему генерируется UUID как идентификатор сеанса входа, который хранится в Redis в качестве ключа, а Value — это информация, связанная с пользователем.
2. Самоинкрементный первичный ключ автономной базы данных
Эта схема обычно используется для генерации идентификатора, когда объем бизнеса невелик.
преимущество
легкий доступ
Поскольку общий проект не обязательно использует эти компоненты, такие как Zookeeper, а в основном использует базу данных, доступ к проекту будет относительно простым, и не потребуется никаких дополнительных затрат на обслуживание.
Монотонно возрастающий
Он абсолютно монотонно возрастает, то есть из временной шкалы сгенерированный позже id должен быть больше сгенерированного ранее id.
недостаток
Эффективность генерации идентификатора ограничена
Поскольку генерация идентификатора зависит от самоуспечения первичного ключа автономной базы данных, она не может удовлетворить бизнес-требования большого количества параллелизма ID.
Сильная зависимость от базы данных
Когда автономная база данных не работает, идентификатор не может быть сгенерирован, что приводит к недоступности всей системы. Если база данных представляет собой архитектуру master-slave, основная база данных выходит из строя и переключается на подчиненную базу данных.Если подчиненная база данных не успела получить последнее обновление вставленного идентификатора основной базы данных, это может привести к текущему само- увеличить идентификатор подчиненной базы данных, чтобы он не был последним, таким образом создавая дубликаты идентификаторов.
идентификатор непрерывен
Если идентификатор является непрерывным, это может стать недостатком. Конкурент размещает заказ в 12 часов того же дня, а затем размещает заказ в 12 часов следующего дня. Можно сделать вывод о ежедневном порядке объем на основе разницы между идентификаторами заказов. Такие фильмы, как «Кошачий глаз», используют этот метод для генерации идентификатора фильма. Как правило, в нашем повседневном использовании, чтобы конкурентам было сложнее угадать способ, которым мы генерируем идентификатор, он обычно не начинается с 1, но фильм «кошачий глаз» начинается с 1 и является непрерывным, поэтому мы используем две точки. Метод быстро определил, что 8875 — это максимальное значение, то есть всего фильмов 8875, а поскольку он непрерывный, ползать будет удобнее. Идентификатор фильма "кошачий глаз" - также генерируется с использованием автономной базы данных, которая непрерывно и автоматически увеличивается.
https://maoyan.com/films/1
https://maoyan.com/films/2
https://maoyan.com/films/8874
https://maoyan.com/films/8875
https://maoyan.com/films/8876
（1到8875可以请求到数据，8876及后面的id
请求不到数据，没有这些id对应的电影，说明总共有8875部电影）
Если вы не выполняете дополнительную обработку (например, синхронизацию, чтобы получить текущее начальное значение автоинкремента a, а затем сгенерировать случайное число b, используйтеalter table users AUTO_INCREMENT=a+b;Команда изменяет начальное значение автоматического приращения, то есть пропускает некоторые идентификаторы. )
Применимая сцена
Он подходит для предприятий с низким параллелизмом.
3. Автоинкремент первичного ключа для нескольких баз данных генерирует уникальный идентификатор. (Установите размер шага, чтобы различать разные базы данных)
Вы можете использовать следующую команду, чтобы установить размер шага каждой таблицы автоинкремента в MySQL.Установив одинаковый размер шага для разных баз данных, можно различать идентификаторы, сгенерированные разными базами данных.
CREATE TABLE table (...) AUTO_INCREMENT = n;
alter table <table name> auto_increment=2;
Например, размер шага равен количеству баз данных, например, имеется N баз данных,
Начальное значение первой базы данных равно 0, затем сгенерированный идентификатор равен 0, N, 2N, 3N и так далее.
Начальное значение первой базы данных равно 1, затем сгенерированный идентификатор равен 1, N+1, 2N+1, 3N+1 и так далее. Таким образом, идентификаторы, генерируемые каждой базой данных, не будут конфликтовать, и каждая база данных может генерировать идентификаторы независимо.
преимущество
Идентификатор сгенерировал более высокую эффективность, чем единую базу данных, как могут одновременно использовать несколько баз данных.
недостаток
Это решает проблему, заключающуюся в том, что каждое самоувеличение равно 1. Недостаток заключается в том, что после установки размера шага неудобно увеличивать емкость, поскольку количество таблиц в подбазе данных и подтаблиц было определено.
сцены, которые будут использоваться
До того, как не было структуры для подбазы данных и подтаблицы, эти подбаза данных и подтаблица были реализованы с использованием этой схемы.
4. База данных сегментируется для создания уникального идентификатора. (Например, режим сегмента в фреймворке Meituan Leaf)
Проще говоря, как на рисунке ниже, используйте таблицу базы данных в качестве передатчика чисел, Поля в таблице описаны следующим образом:
biz_tag字段用于区分每种id应用的业务，
max_id字段记录了当前已生成的最大的id，
step字段代表每次可以获取id的数量
Каждый раз, когда проект генерации идентификатора использует следующий оператор для получения идентификатора количества шагов из базы данных, обновляет значение max_id и сохраняет идентификатор количества шагов в памяти, чтобы бизнес-сторона могла получить его через HTTP, RPC, клиент и т. д.
UPDATE leaf_alloc SET max_id = max_id + step WHERE biz_tag = #{tag}
преимущество
эффективный
Эффективность генерации идентификатора зависит от размера шага и не ограничивается количеством баз данных, как при генерации идентификатора с автоматическим приращением первичного ключа.
недостаток
Сильная зависимость от базы данных
Он по-прежнему сильно зависит от базы данных.После того, как база данных не работает, хотя система генерации идентификаторов не израсходовала идентификатор в памяти, она может поддерживать нормальную работу системы в течение определенного периода времени, но база данных недоступна. или приведет к недоступности всей системы.
идентификатор непрерывен
Легко привести к сканированию, а также конкурентам, чтобы угадать распорядок дня
5. Создайте уникальный идентификатор на основе алгоритма снежинки
snowflake — это алгоритм генерации распределенного идентификатора с открытым исходным кодом для Twitter, всего 64 бита.
Первый бит 0, дабит флага, потому что в двоичных числах первый бит равен 0, что означает, что это положительное число.
Следующие 41 бит составляют 13 бит.Millisecond Timestamp, до сентября 2039 г.
Затем следующие 10 двоичных битовworkID, который является идентификатором сервера.
Последние 12 битсерийный номер компании
Это означает, что в миллисекунду может быть сгенерировано максимум 2 идентификатора в 12-й степени, 4096, что позволяет каждой машине генерировать 4096 идентификаторов в миллисекунду и может генерировать более 4 миллионов идентификаторов в секунду.
преимущество
эффективный
Эффективность генерации идентификаторов относительно высока, и 12-я степень числа 2 может быть сгенерирована максимум за 1 мс, то есть 4096 идентификаторов.
Не зависит от других компонентов
В процессе генерации идентификатор в основном генерируется на основе метки времени, рабочего идентификатора и серийного номера.Идентификатор можно сгенерировать самостоятельно, не полагаясь на другие компоненты и полагаясь только на локальное системное время.
недостаток
Легко вызвать проблему перекоса данных
Пример: Всего в базе данных 10 идентификаторов, которые
0,25,26,27,28,29,30,31,32,100
Минимальное значение id равно 0, а максимальное значение равно 100. В соответствии с максимальным значением id за вычетом минимального значения диапазон делится на четыре сегмента, а диапазон представляет собой следующие четыре диапазона:
[0,25), 存在1个id，值分别是0
[25,50) 存在8个id，值分别是25，26，27，28，29，30，31，32
[50,75),存在0个id
[75,100] 存在1个100，值是100
Таким образом, очевидно, возникнет проблема перекоса данных, то есть количество идентификаторов в интервале [25,50) особенно велико, а количество идентификаторов в других интервалах особенно мало. Если мы используем Sqoop для импорта данных из MySQL в Hive, то в соответствии с этимid最大值减去最小值，进行范围切分Метод реализации выполняет фрагментацию данных, а затем многопоточный импорт данных.Каждый поток отвечает за данные одного фрагмента.Если данные неравномерны, время импорта будет больше.Некоторые потоки выделяют небольшой объем данных, а импорт выполняется очень быстро Объем данных, выделенных потоком, импортируется очень медленно. Общее время импорта зависит от времени самого медленного потока.
При использовании идентификатора, сгенерированного Snowflake, размер значения идентификатора зависит от метки времени при создании идентификатора.Если за определенный период времени сканируется большое количество статей для хранения, за короткий период времени создается много идентификаторов. , в то время как другие периоды времени генерируются. Количество идентификаторов очень мало. При использовании Sqoop для импорта данных будет проблема перекоса данных. Вам нужно самостоятельно разделить данные, чтобы сделать данные однородными, а затем импортировать их .
2. Исследование текущей схемы генерации ID крупных компаний
заголовки
Содержание заголовка в основном делится на статью, атлас, видео, а источник данных этих трех материалов в основном публикуется редактором и с других веб-сайтов.
Методы исследования
Это заголовок статьиуууу.headline.com/ah6841306705…
Идентификатор состоит из 19 цифр, потому что идентификатор из 19 цифр на самом деле порядка триллионов, поэтому маловероятно, что столько статей будет храниться в базе данных, а затем постепенно генерироваться по идентификатору первичного ключа базы данных, поэтому существует большая вероятность, что секс генерируется алгоритмом снежинки,
После преобразования 6841306705796530700 в двоичное число
10111 10111 10001 00110 10000 11001 11011 11101 00000 00000 00010 00001 100
Всего 63 бита, потому что исходный алгоритм снежинки — это 1 бит флага + 41-битная отметка времени в миллисекундах + 10-битный машинный бит + 12-битный серийный номер, поэтому мы берем первые 41 бит.
10111 10111 10001 00110 10000 11001 11011 11101 0
преобразовать в десятичное время получить
1631094623994
Преобразование в миллисекундную временную метку, да
2021-09-08 17:50:23
Это будущее, поэтому вряд ли будет такое решение, потому что на самом деле параллелизм ID в 1 мс вообще не нужно 2 в 12-й степени, то есть целых 4096, а количество QPS в 1с может быть несколько сотен - это особая сумма большая,
原理：每天80%的访问集中在20%的时间里，这20%时间叫做峰值时间
公式：( 总PV数 * 80% ) / ( 每天秒数 * 20% ) = 峰值时间每秒请求数(QPS)
机器：峰值时间每秒QPS / 单台机器的QPS = 需要的机器
问：每天300w PV 的在单台机器上，这台机器需要多少QPS？
答：( 3000000 * 0.8 ) / (86400 * 0.2 ) = 139 (QPS)
В соответствии с этим принципом, если предположить, что в день поступает 3 миллиона запросов, а пиковое время распределяется на пиковое время, пиковое число запросов в секунду составляет 139. И трудно каждый день получать в базу данных 3 миллиона статей, в результате чего требуется 3 миллиона идентификаторов, поэтому количество запросов в секунду на самом деле очень мало. Заголовок может использовать 1 флаговый бит + 31 отметку времени второго уровня + 32 машинных бита и биты последовательности, определенные для вас, поэтому мы берем первые 31 бит.
10111 10111 10001 00110 10000 11001 1
Преобразование в десятичное число
1592865843
Согласно преобразованию метки времени второго уровня, т.е.
2020-06-23 06:44:03
Со временем размещения статей2020-06-23 06:44:52Это очень похоже. Некоторая разница во времени может быть связана с тем, что отметка времени в идентификаторе является временем создания склада (Редактировать Нажмите кнопку «Новая статья», чтобы перейти на страницу редактирования), а в интерфейсе отображается время публикации статьи.
Подробные результаты опроса
После того, как мы извлекли некоторые идентификаторы и преобразовали их в двоичные файлы, мы предполагаем, что двоичная композиция идентификаторов31-битная метка времени второго уровня + 10-битные биты последовательности + 18-битные зарезервированные биты + 4-битные машинные биты, на самом деле посмотрите на таблицу и обнаружите, что все 18-битные зарезервированные биты000000000000100000. Он поддерживает до 32 машин генерации идентификаторов для одновременной работы, количество запросов в секунду для одной машины может достигать 1024, а общее количество запросов в секунду может достигать 32768. (В настоящее время я не знаю функции 18-битных зарезервированных битов)
Мейтуан
кошачий глаз фильм
Я предполагаю, что это реализовано за счет непрерывного самоувеличения автономной базы данных, диапазон идентификаторов от 1 до 8875, а всего фильмов 8875.
Проживание в семье Hazelnut - прерывистый саморазвитие
Обнаружено, что идентификатор имеет данные только после 2500000, и многие идентификаторы не являются непрерывными.Предполагается использовать режим Leaf-Segment для генерации идентификатора.Каждый раз, когда сегмент идентификационного номера берется из базы данных, доступный идентификатор хранится в памяти, а затем Дождитесь, пока бизнес-система запросит распространение. Кроме того, я сделал дополнительную стратегию отказа от идентификатора, чтобы сделать идентификатор прерывистым, чтобы обеспечить информационную безопасность и увеличить сложность сканирования.
- Phoenix.Meituan.com/housing/268…//нет данных
- Phoenix.Meituan.com/housing/268…// есть данные
- Phoenix.Meituan.com/housing/268…// есть данные
- Phoenix.Meituan.com/housing/268…//нет данных
- Phoenix.Meituan.com/housing/268…// есть данные
Номер заказа на вынос США
Он определенно генерируется с использованием алгоритма снежинки, но поскольку их временные биты используют разницу во времени (то есть отметку времени минус указанный момент времени), а распределение битов может выполнять дополнительную обработку, делать вывод не очень хорошо.
| выиграть | время заказа |
|---|---|
| 5026 0271 7642 2612 7 | 2018-09-02 17:46:03 |
| 6233 7340 1594 0462 | 2018-07-17 18:34:11 |
| 3962 9431 3190 0632 1 | 2018-07-15 11:52:55 |
| 2273 5322 6921 7033 5 | 2017-06-30 11:39:01 |
автомобиль домой
Используется самоувеличивающийся идентификатор.Существующие данные варьируются от 4 до 6 цифр, а текущий максимум составляет 320w+.Принцип реализации должен заключаться в том, что первичный ключ базы данных будет увеличиваться автоматически.Из-за их большого количества он должен быть размер шага установки нескольких баз данных.генерировать идентификатор.
Ниже представлена таблица статистики
| Рабочий идентификатор | URL | тип |
|---|---|---|
| 9999 | chejiahao.autohome.com.cn/info/9999 | легкий текст |
| 3200292 | номер рамы.autohome.com.capable/info/320029… | легкий текст |
| 3200293 | номер рамы.autohome.com.capable/info/320029… | видео |
| 3200294 | номер рамы.autohome.com.capable/info/320029… | статья |
| 3292759 | номер рамы.autohome.com.capable/info/329275… | список автомобилей |
| 2037191 | номер рамы.autohome.com.capable/info/203719… | аудио |
Суммировать
Я чувствую, что в настоящее время крупные компании все еще используют Snowflake в качестве решения для распределенной генерации идентификаторов.С одной стороны, он может удовлетворить требования получения идентификаторов с высокой степенью параллелизма, а с другой стороны, непрерывность идентификаторов очень низкая, что может обеспечить информационную безопасность и упростить сканирование. Кроме того, могут быть некоторые предприятия, которые имеют небольшой параллелизм, когда они только начинают, и напрямую используют первичный ключ автономной базы данных для автоматического создания идентификатора.4.数据库分段发号生成唯一idЭто решение также может соответствовать высокому уровню параллелизма, но основная причина в том, что идентификатор является непрерывным.Даже если логика отбрасывания идентификатора будет дополнительно разработана, конкуренты могут запросить один за другим информацию о количестве заказа.