1. Предпосылки

В наших бизнес-требованиях нам обычно нужны уникальные идентификаторы для записи идентификации некоторых наших данных:

идентификатор пользователя
Трек номер заказа
ID сообщения

Обычно мы изучаем различные стратегии генерации и выбираем наиболее подходящую стратегию в зависимости от бизнеса.Ниже я расскажу о различных стратегиях/алгоритмах, а также о некоторых их преимуществах и недостатках.

2.UUID

UUID – это сокращение от Universally Unique Identifier. Спецификация Open Software Foundation (OSF) определяет такие элементы, как MAC-адрес сетевой карты, отметку времени, пространство имен (Namespace), случайное или псевдослучайное число, время и другие элементы. Используйте эти элементы для создания UUID.

UUID состоит из 128-битного двоичного кода, обычно преобразуемого в шестнадцатеричный, а затем представленного в виде строки. В java есть класс UUID, и в его комментариях мы видим, что существует 4 разных стратегии генерации UUID:

случайно: UUID генерируется на основе случайного числа.Поскольку случайное число в Java является псевдослучайным числом, вероятность его повторения можно рассчитать. Обычно мы используем следующий код для получения UUID на основе случайного числа:
основанный на времени: UUID, основанный на времени, который обычно рассчитывается на основе текущего времени, случайного числа и локального адреса Mac.Встроенный пакет JDK не имеет этого алгоритма в некоторых UUIDUtil, таких как наш log4j.core.util, который переопределяет старшие и младшие биты UUID.
Безопасность DCE: UUID безопасности DCE.
на основе имени: UUID основан на имени, UUID рассчитывается путем вычисления MD5 имени и пространства имен.

Преимущества UUID:

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

Недостатки UUID:

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

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

3. Автоматическое увеличение первичного ключа базы данных

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

преимущество:

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

недостаток:

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

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

4.Redis

Студенты, знакомые с Redis, должны знать, что в Redis есть две команды Incr и IncrBy.Поскольку Redis является однопоточным, атомарность может быть гарантирована.

преимущество:

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

недостаток:

Поскольку Redis является базой данных KV в памяти, даже с AOF и RDB все равно будет потеря данных, что может привести к дублированию идентификаторов.
Зависит от Redis. Если Redis нестабилен, это повлияет на создание идентификатора.

Применимо: поскольку его производительность лучше, чем у базы данных, но может быть дублирование идентификаторов и нестабильность, этот фрагмент можно использовать, если он приемлем. Так же действует на определенное время, например обновление ID каждый день, потом этот ID нужно сбросить, через (Incr Today) он будет добавляться с 0 каждый день.

5.Zookeeper

Используя версию данных Znode ZK в качестве следующего кода, каждый раз, когда ожидаемый номер версии не будет получен, то есть каждый раз он будет успешным, тогда каждый раз будет возвращаться последний номер версии:

Решение Zookeeper используется редко, сильно зависит от кластера Zookeeper и имеет низкую производительность, поэтому его не рекомендуется использовать.

6. Сегментация базы данных + идентификатор сервисного кеша

Этот метод представлен в Meituan's Leaf.Подробности см. в технических статьях, опубликованных технической командой Meituan:Лист — Распределенная система генерации идентификаторов Meituan Dianping, Это решение предназначено для оптимизации автоматического увеличения первичного ключа базы данных.

biz_tag представляет каждый отдельный бизнес, max_id представляет размер, установленный каждым бизнесом, а step представляет размер шага каждого кэша proxyServer. Раньше каждый наш сервис обращался к базе данных, но теперь он нам не нужен, каждый сервис напрямую взаимодействует с нашим ProxyServer, уменьшая зависимость от базы данных. Каждый из наших прокси-серверов возвращается к базе данных и извлекает длину шага, например, сервер1 получает 1-1000, а сервер2 получает 1001-2000. Если он закончится, он снова отправится в базу данных, чтобы получить его.

преимущество:

Он имеет более высокую производительность, чем приращение первичного ключа, и может гарантировать приращение тренда.
Если БД выходит из строя, proxServer может еще некоторое время сохраняться из-за кеша.

недостаток:

Как и приращение первичного ключа, его легко угадать.
Время простоя БД, хотя и может поддерживаться в течение определенного периода времени, все равно приведет к недоступности системы.

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

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

7. Алгоритм Snowflake-Снежинка

Snowflake — это алгоритм, предложенный Twitter, целью которого является создание 64-битного целого числа:

1 бит: обычно бит знака, не обрабатывается
41bit: Используется для записи метки времени. Здесь можно записать 69 лет. Если установлено время начала, например, в этом году 2018, то можно использовать 2089. Что мне тогда делать? Если эту систему можно использовать в течение 69 лет, я считаю, что эта система подвергалась рефакторингу много раз.
10 бит: 10 бит используется для записи идентификатора машины.Всего может быть записано 1024 машины.Как правило, первые 5 цифр представляют центр обработки данных, а последние 5 цифр — идентификатор машины центра обработки данных.
12 бит: циклический бит, используемый для генерации разных идентификаторов в течение одной миллисекунды, 12 бит могут записывать до 4095, то есть максимум 4095 могут быть записаны за одну миллисекунду на одной и той же машине, а избыток должен ждать следующая миллисекунда.

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

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

В настоящее время мы можем разумно разделить 62-битные согласно приведенному выше сценарию.QPS вырастет до миллиона в течение нескольких лет, поэтому каждая миллисекунда - это запрос уровня тысячи.В настоящее время, если есть 10 машин, каждая машина может выполнять стоуровневый запрос.Для обеспечения расширения следующие циклические биты могут быть ограничены до 1024, что составляет 2 ^ 10, тогда достаточно 10 циклических битов.

Когда машина развернута в трех местах, мы можем использовать 3 бита для указания местоположения компьютерного зала.В настоящее время есть машины 10.Чтобы обеспечить расширение до 100 машин, мы можем использовать 7 бит 128 для указания бита времени Бит времени по-прежнему 41 бит, поэтому осталось 64-10-3.-7-41-1 = 2 бита, осталось 2 бита для расширения.

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

7.1 Простая снежинка

public class IdWorker{

    private long workerId;
    private long datacenterId;
    private long sequence = 0;
    /**
     * 2018/9/29日，从此时开始计算，可以用到2089年
     */
    private long twepoch = 1538211907857L;

    private long workerIdBits = 5L;
    private long datacenterIdBits = 5L;
    private long sequenceBits = 12L;

    private long workerIdShift = sequenceBits;
    private long datacenterIdShift = sequenceBits + workerIdBits;
    private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    // 得到0000000000000000000000000000000000000000000000000000111111111111
    private long sequenceMask = -1L ^ (-1L << sequenceBits);

    private long lastTimestamp = -1L;


    public IdWorker(long workerId, long datacenterId){
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }
    public synchronized long nextId() {
        long timestamp = timeGen();
        //时间回拨，抛出异常
        if (timestamp < lastTimestamp) {
            System.err.printf("clock is moving backwards.  Rejecting requests until %d.", lastTimestamp);
            throw new RuntimeException(String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds",
                    lastTimestamp - timestamp));
        }

        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0;
        }

        lastTimestamp = timestamp;
        return ((timestamp - twepoch) << timestampLeftShift) |
                (datacenterId << datacenterIdShift) |
                (workerId << workerIdShift) |
                sequence;
    }

    /**
     * 当前ms已经满了
     * @param lastTimestamp
     * @return
     */
    private long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    private long timeGen(){
        return System.currentTimeMillis();
    }

    public static void main(String[] args) {
        IdWorker worker = new IdWorker(1,1);
        for (int i = 0; i < 30; i++) {
            System.out.println(worker.nextId());
        }
    }

}

Реализация алгоритма снежинки определена выше, а nextId является ключом к нашей генерации алгоритма снежинки.

7.2 Предотвращение обратного вызова часов

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

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

Отклонить напрямую, сгенерировать исключение, зарегистрировать и уведомить RD, чтобы откатить часы.
Используя бит расширения, мы обсуждали выше, что количество битов в разных бизнес-сценариях может использоваться не так много, тогда мы можем использовать бит расширения.Например, когда время относительно велико, мы можем напрямую Бит расширения добавляется 1. 2-битный бит расширения позволяет нам иметь 3 больших обратных вызова часов, которых обычно достаточно.Если он превышает три раза, мы все равно выбираем исключение и журнал.

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

Наконец

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

Наконец, сделайте рекламу.Если вы считаете, что в этой статье есть статья для вас, вы можете подписаться на мой технический общедоступный аккаунт или присоединиться к моей группе технического обмена для большего количества технических обменов. За последнее время автор собрал много свежих обучающих материалов,видео и материалов интервью.Вы можете получить их после подписки.Ваше внимание и пересылка-самая большая поддержка для меня,О(∩_∩)О.