предисловие

В бизнес-системе Интернета задействованы различные идентификаторы, такие как идентификаторы платежей, идентификаторы возврата и т. д. в платежной системе. Каковы решения для генерации идентификаторов в целом? Особенно в сложных бизнес-сценариях распределенных систем очень важно принять подходящее решение. Давайте перечислим их по порядку, не все из них подходят, эти решения только для ознакомления, возможно они вам пригодятся.

текст

Особенности распределенных идентификаторов

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

Схема генерации распределенного идентификатора

1. UUID

Основная идея алгоритма состоит в том, чтобы объединить сетевую карту машины, местное время и случайный подсчет для генерации UUID.

Преимущества: локальная генерация, простая генерация, хорошая производительность, отсутствие высокого риска доступности.
Недостатки: длина слишком велика, хранилище избыточно, оно беспорядочно и нечитаемо, эффективность запросов низкая.

2. Идентификатор автоинкремента базы данных

Используйте стратегию автоматического увеличения идентификатора базы данных, такую как auto_increment в MySQL. Кроме того, можно использовать две базы данных для установки разной продолжительности синхронизации соответственно, а стратегию создания уникальных идентификаторов можно использовать для достижения высокой доступности.

Преимущества: Идентификаторы, сгенерированные базой данных, абсолютно упорядочены, а реализация высокой доступности проста.
Недостатки: необходимость независимого развертывания экземпляра базы данных, высокая стоимость, узкое место в производительности.

3. Генерируйте идентификаторы партиями

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

Преимущества: избегайте доступа к базе данных каждый раз, когда создается идентификатор, и оказывайте давление, повышайте производительность.
Недостатки: относится к стратегии локальной генерации, существует единая точка отказа, а идентификатор прерывается из-за перезапуска службы.

4. Redis генерирует идентификатор

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

Достоинства: Не зависит от БД, гибок и удобен, производительность у него лучше, чем у БД, числовой идентификатор естественно сортируется, что очень помогает при листании или результатах, которые нужно отсортировать.
Недостатки: если в системе нет Redis, необходимо вводить новые компоненты для увеличения сложности системы; объем работы по кодированию и настройке относительно велик.

Учитывая узкое место производительности одного узла, можно использовать Redis Cluster для повышения пропускной способности. Предположим, в кластере 5 Redis. Значения, которые можно инициализировать для каждого Redis, равны 1, 2, 3, 4, 5, а затем размер шага равен 5. Идентификаторы, сгенерированные каждым Redis:

A：1, 6, 11, 16, 21
B：2, 7, 12, 17, 22
C：3, 8, 13, 18, 23
D：4, 9, 14, 19, 24
E：5, 10, 15, 20, 25

Трудно вносить изменения в будущем, зависит от того, какую машину вы хотите загрузить. Размер шага и начальное значение должны быть определены заранее. Использование Redis Cluster также может решить проблему единой точки отказа.

Кроме того, более удобно использовать Redis для ежедневной генерации серийного номера, начиная с 0. Например, номер заказа = дата + самоинкрементный номер текущего дня. Ключ можно генерировать в Redis каждый день и накапливать с помощью INCR.

5. Алгоритм снежинки Twitter

Twitter использует zookeeper для реализации глобальной службы генерации идентификаторов Snowflake:GitHub.com/Twitter/ Скажи нет…

Как показано на рисунке выше, алгоритм Twitter Snowflake состоит из следующих частей:

1-битный знаковый бит:

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

41-битная метка времени (миллисекундный уровень):

Следует отметить, что 41-битная временная метка здесь — это не временная метка, в которой хранится текущее время, а разница между временными метками (текущая временная метка — начальная временная метка). used указывается программой, поэтому 41-битная отметка времени в миллисекундах может использоваться не более чем(1 << 41) / (1000x60x60x24x365) = 69年.

10 бит данных машины:

Включая 5 битов идентификации данных и 5 битов идентификации машины, эти 10 бит определяют максимальное количество развертываний в распределенной системе.1 << 10 = 1024узлы. Если это число превышено, сгенерированные идентификаторы могут конфликтовать.

Последовательность в 12-битных миллисекундах:

Этот 12-битный счетчик позволяет каждому узлу генерировать максимум за миллисекунду (та же машина, тот же момент)1 << 12 = 4096个ID

В сумме он составляет ровно 64 бита, что является типом Long.

Преимущества: высокая производительность, низкая задержка, упорядоченность по времени, как правило, не вызывает коллизии идентификаторов.
Недостатки: требует самостоятельной разработки и развертывания, зависит от часов машины

Простая реализация

public class IdWorker {
    /**
     * 起始时间戳 2017-04-01
     */
    private final long epoch = 1491004800000L;
    /**
     * 机器ID所占的位数
     */
    private final long workerIdBits = 5L;
    /**
     * 数据标识ID所占的位数
     */
    private final long dataCenterIdBits = 5L;
    /**
     * 支持的最大机器ID,结果是31
     */
    private final long maxWorkerId = ~(-1L << workerIdBits);
    /**
     * 支持的最大数据标识ID,结果是31
     */
    private final long maxDataCenterId = ~(-1 << dataCenterIdBits);
    /**
     * 毫秒内序列在id中所占的位数
     */
    private final long sequenceBits = 12L;
    /**
     * 机器ID向左移12位
     */
    private final long workerIdShift = sequenceBits;
    /**
     * 数据标识ID向左移17(12+5)位
     */
    private final long dataCenterIdShift = sequenceBits + workerIdBits;
    /**
     * 时间戳向左移22(12+5+5)位
     */
    private final long timestampShift = sequenceBits + workerIdBits + dataCenterIdBits;
    /**
     * 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095)
     */
    private final long sequenceMask = ~(-1L << sequenceBits);
    /**
     * 数据标识ID（0～31）
     */
    private long dataCenterId;
    /**
     * 机器ID（0～31）
     */
    private long workerId;
    /**
     * 毫秒内序列（0～4095）
     */
    private long sequence;
    /**
     * 上次生成ID的时间戳
     */
    private long lastTimestamp = -1L;

    public IdWorker(long dataCenterId, long workerId) {
        if (dataCenterId > maxDataCenterId || dataCenterId < 0) {
            throw new IllegalArgumentException(String.format("dataCenterId can't be greater than %d or less than 0", maxDataCenterId));
        }
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        this.dataCenterId = dataCenterId;
        this.workerId = workerId;
    }

    /**
     * 获得下一个ID (该方法是线程安全的)
     * @return snowflakeId
     */
    public synchronized long nextId() {
        long timestamp = timeGen();
        //如果当前时间小于上一次ID生成的时间戳,说明系统时钟回退过,这个时候应当抛出异常
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }
        //如果是同一时间生成的，则进行毫秒内序列
        if (timestamp == lastTimestamp) {
            sequence = (sequence + 1) & sequenceMask;
            //毫秒内序列溢出
            if (sequence == 0) {
                //阻塞到下一个毫秒,获得新的时间戳
                timestamp = nextMillis(lastTimestamp);
            }
        } else {//时间戳改变，毫秒内序列重置
            sequence = 0L;
        }
        lastTimestamp = timestamp;
        //移位并通过按位或运算拼到一起组成64位的ID
        return ((timestamp - epoch) << timestampShift) |
                (dataCenterId << dataCenterIdShift) |
                (workerId << workerIdShift) |
                sequence;
    }

    /**
     * 返回以毫秒为单位的当前时间
     * @return 当前时间(毫秒)
     */
    protected long timeGen() {
        return System.currentTimeMillis();
    }

    /**
     * 阻塞到下一个毫秒，直到获得新的时间戳
     * @param lastTimestamp 上次生成ID的时间截
     * @return 当前时间戳
     */
    protected long nextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = lastTimestamp;
        }
        return timestamp;
    } 
}

6. Baidu UidGenerator

UidGenerator — генератор распределенных идентификаторов Baidu с открытым исходным кодом, основанный на реализации алгоритма снежинки, вроде бы все в порядке. Однако ремонтопригодность отечественных проектов с открытым исходным кодом действительно вызывает беспокойство.

Для получения дополнительной информации, пожалуйста, обратитесь к официальному описанию веб-сайта:GitHub.com/Baidu/UID-a…

7. Лист Мэйтуан

Leaf — это распределенный генератор идентификаторов Meituan с открытым исходным кодом, который может обеспечить глобальную уникальность, тенденцию роста, монотонное увеличение и информационную безопасность.Также упоминается сравнение нескольких распределенных решений, но для этого также требуется промежуточное программное обеспечение, такое как база данных зависимостей и Zookeeper.

Для получения дополнительной информации, пожалуйста, обратитесь к официальному описанию веб-сайта:Специальности.Meituan.com/Mt_leaf.htm…

резюме

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

Добро пожаловать, чтобы отсканировать код и подписаться на официальный аккаунт: Zero One Technology Stack.

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