Распределенная схема генерации глобального идентификатора

задняя часть распределенный
Распределенная схема генерации глобального идентификатора

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

Как показано на рисунке выше, если первый заказ хранится в DB1, идентификатор заказа равен 1, а когда новый заказ хранится в DB2, идентификатор заказа также равен 1. Хотя архитектура нашей системы является распределенной, она не должна быть осведомлена на пользовательском уровне, а дублирование первичных ключей порядка явно не допускается. Так как же добиться уникальности первичного ключа для распределенных систем?

UUID

UUID (универсальный уникальный идентификатор), сокращение от Universal Unique Identifier. UUID состоит из группы 32-значных шестнадцатеричных чисел, поэтому теоретическая сумма UUID составляет 16 ^ 32 = 2 ^ 128, что примерно равно 3,4 x 10 ^ 38. То есть, если 1 триллион UUID генерируется каждую наносекунду, потребуется 10 миллиардов лет, чтобы израсходовать все UUID.

Сгенерированный UUID задается8-4-4-4-12Формат данных состоит из 32 символов и 4 дефисов '-' Обычно мы удаляем дефисы при их использовании.uuid.toString().replaceAll("-","").

В настоящее время существует 5 версий методов генерации UUID, и каждая версия имеет разные алгоритмы и разные области применения.

  • UUID на основе времени — версия 1: Обычно это рассчитывается на основе текущего времени, случайного числа и локального адреса Mac, который можно рассчитать с помощьюorg.apache.logging.log4j.core.utilв упаковкеUuidUtil.getTimeBasedUuid()использовать или другие инструменты в пакете. Поскольку используется MAC-адрес, может быть обеспечена уникальность, но MAC-адрес также раскрывается одновременно, а конфиденциальность недостаточна.

  • Защищенный UUID DCE — версия 2Алгоритм безопасного UUID DCE (Distributed Computing Environment) аналогичен алгоритму UUID на основе времени, но первые 4 позиции метки времени заменяются UID или GID POSIX. Эта версия UUID редко используется на практике.

  • UUID на основе имени (MD5) — версия 3UUID на основе имени получаются путем вычисления хэша MD5 имени и пространства имен. Эта версия UUID гарантирует: уникальность UUID, сгенерированных разными именами в одном и том же пространстве имен; уникальность UUID в разных пространствах имен; повторная генерация UUID с одним и тем же именем в одном и том же пространстве имен является одинаковой.

  • Случайный UUID — версия 4Создайте UUID на основе случайного числа или псевдослучайного числа. Вероятность того, что этот UUID будет повторяться, можно рассчитать, но возможность повторения незначительна, поэтому эта версия также является часто используемой. Эта версия используется в JDK.

  • UUID на основе имени (SHA1) — версия 5Аналогичен алгоритму UUID на основе имени, за исключением того, что для вычисления хеш-значения используется алгоритм SHA1 (Secure Hash Algorithm 1).

Метод генерации UUID, который поставляется с JDK в нашей Java, представляет собой UUID, сгенерированный версией 4 на основе случайных чисел, и UUID на основе имени в версии 3. Если вам интересно, вы можете перейти к его исходному коду.

public static void main(String[] args) {

    //获取一个版本4根据随机字节数组的UUID。
    UUID uuid = UUID.randomUUID();
    System.out.println(uuid.toString().replaceAll("-",""));

    //获取一个版本3(基于名称)根据指定的字节数组的UUID。
    byte[] nbyte = {10, 20, 30};
    UUID uuidFromBytes = UUID.nameUUIDFromBytes(nbyte);
    System.out.println(uuidFromBytes.toString().replaceAll("-",""));
}

получить результат UUID,

59f51e7ea5ca453bbfaf2c1579f09f1d
7f49b84d0bbc38e9a493718013baace6

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

  • Нелегко хранить: UUID слишком длинный, 16 байт и 128 бит, обычно представлен строкой длиной 36, что неприменимо во многих сценариях.
  • Небезопасная информация: алгоритм, генерирующий UUID на основе MAC-адреса, может привести к утечке MAC-адреса и раскрытию местоположения пользователя.
  • Неблагоприятно для индекса MySQL: при использовании в качестве первичного ключа базы данных под движком InnoDB неупорядоченность UUID может вызвать частые изменения в расположении данных и серьезно повлиять на производительность.Вы можете обратиться к знанию принципа индексирования Mysql дерево B+ .

генерация базы данных

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

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

Возьмите MySQL в качестве примера, используйте настройку поляauto_increment_incrementиauto_increment_offsetЧтобы идентификатор увеличивался автоматически.

  • auto_increment_offset: указывает, что поле автоинкремента начинается с этого числа, и его диапазон значений составляет 1 .. 65535.
  • auto_increment_increment: Указывает приращение поля автоинкремента каждый раз, его значение по умолчанию — 1, а диапазон значений — 1 .. 65535.

Предполагая, что есть три машины, начальное значение идентификатора таблицы заказов в DB1 равно 1, начальное значение таблицы заказов в DB2 равно 2, а начальное значение таблицы заказов в DB3 равно 3, а их шаги приращения равны все 3. Тогда диапазоны генерации их ID показаны на следующем рисунке:

Очевидным преимуществом этого метода является то, что сама база данных не требует других ресурсов, а номер ID монотонно увеличивается, что позволяет реализовать некоторые сервисы, предъявляющие особые требования к ID.

Но недостатки тоже очевидны.Во-первых, сильно зависит от БД, и вся система недоступна при аварийной БД. Хотя настройка репликации master-slave может максимально повысить доступность, в особых случаях сложно гарантировать согласованность данных. Несоответствия во время переключения ведущий-ведомый могут привести к повторной нумерации. Кроме того, узкое место производительности нумерации идентификаторов ограничено производительностью чтения и записи одного MySQL.

Реализовано с помощью Redis

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

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

Чтобы избежать слишком большого долгосрочного самоувеличивающегося числа, его можно использовать в сочетании с текущей меткой времени.Кроме того, для обеспечения параллелизма и многопоточности бизнеса Redis + Lua можно использовать для кодирования для обеспечения безопасности.

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

Конечно, использование Redis сейчас очень распространено, поэтому, если другие компании внедрили кластер Redis, вы можете рассмотреть возможность использования Redis для использования ресурсов.

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

Snowflake, алгоритм снежинки — это распределенный алгоритм генерации идентификаторов, исходный код которого открыт Twitter.Он делит 64-битные биты на несколько частей, разделяя пространство имен, и каждая часть представляет различное значение. 64-битное целое число в Java имеет тип Long, поэтому идентификатор, сгенерированный алгоритмом SnowFlake в Java, хранится в long.

  • Первый бит занимает 1 бит, и его значение всегда равно 0, что можно рассматривать как знаковый бит, который не используется.
  • 41-бит, начинающийся со второго бита, является меткой времени, а 41-битные биты могут представлять 2 ^ 41 число, каждое число представляет миллисекунды, тогда доступный период времени алгоритма снежинки равен (1L360024*365) = 69 лет.
  • 10-битные биты в середине могут представлять количество машин, то есть 2^10 = 1024 машины, но в общем случае такую ​​машину мы развертывать не будем. Если у нас есть спрос на IDC (Internet Data Center), мы также можем разделить 10-битный на 5-битный для IDC и 5-битный для рабочей машины. Таким образом, может быть представлено 32 IDC, и каждый IDC может иметь машины 32. Конкретное подразделение может быть определено в соответствии со своими потребностями.
  • Последний 12-битный бит представляет собой автоматически увеличивающуюся последовательность, которая может представлять 2^12 = 4096 чисел.

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

СнежинкаТвиттер официальный оригиналОн написан на языке Scala. Его могут прочитать студенты, изучавшие язык Scala. Ниже приводится метод написания версии для Java.

package com.jajian.demo.distribute;

/**
 * Twitter_Snowflake<br>
 * SnowFlake的结构如下(每部分用-分开):<br>
 * 0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000 <br>
 * 1位标识，由于long基本类型在Java中是带符号的，最高位是符号位，正数是0，负数是1，所以id一般是正数，最高位是0<br>
 * 41位时间截(毫秒级)，注意，41位时间截不是存储当前时间的时间截，而是存储时间截的差值（当前时间截 - 开始时间截)
 * 得到的值），这里的的开始时间截，一般是我们的id生成器开始使用的时间，由我们程序来指定的（如下下面程序IdWorker类的startTime属性）。41位的时间截，可以使用69年，年T = (1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69<br>
 * 10位的数据机器位，可以部署在1024个节点，包括5位datacenterId和5位workerId<br>
 * 12位序列，毫秒内的计数，12位的计数顺序号支持每个节点每毫秒(同一机器，同一时间截)产生4096个ID序号<br>
 * 加起来刚好64位，为一个Long型。<br>
 * SnowFlake的优点是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞(由数据中心ID和机器ID作区分)，并且效率较高，经测试，SnowFlake每秒能够产生26万ID左右。
 */
public class SnowflakeDistributeId {


    // ==============================Fields===========================================
    /**
     * 开始时间截 (2015-01-01)
     */
    private final long twepoch = 1420041600000L;

    /**
     * 机器id所占的位数
     */
    private final long workerIdBits = 5L;

    /**
     * 数据标识id所占的位数
     */
    private final long datacenterIdBits = 5L;

    /**
     * 支持的最大机器id，结果是31 (这个移位算法可以很快的计算出几位二进制数所能表示的最大十进制数)
     */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

    /**
     * 支持的最大数据标识id，结果是31
     */
    private final long maxDatacenterId = -1L ^ (-1L << 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位(5+5+12)
     */
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;

    /**
     * 生成序列的掩码，这里为4095 (0b111111111111=0xfff=4095)
     */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    /**
     * 工作机器ID(0~31)
     */
    private long workerId;

    /**
     * 数据中心ID(0~31)
     */
    private long datacenterId;

    /**
     * 毫秒内序列(0~4095)
     */
    private long sequence = 0L;

    /**
     * 上次生成ID的时间截
     */
    private long lastTimestamp = -1L;

    //==============================Constructors=====================================

    /**
     * 构造函数
     *
     * @param workerId     工作ID (0~31)
     * @param datacenterId 数据中心ID (0~31)
     */
    public SnowflakeDistributeId(long workerId, long datacenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format("worker Id can't be greater than %d or less than 0", maxWorkerId));
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(String.format("datacenter Id can't be greater than %d or less than 0", maxDatacenterId));
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }

    // ==============================Methods==========================================

    /**
     * 获得下一个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 (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            //毫秒内序列溢出
            if (sequence == 0) {
                //阻塞到下一个毫秒,获得新的时间戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        //时间戳改变，毫秒内序列重置
        else {
            sequence = 0L;
        }

        //上次生成ID的时间截
        lastTimestamp = timestamp;

        //移位并通过或运算拼到一起组成64位的ID
        return ((timestamp - twepoch) << timestampLeftShift) //
                | (datacenterId << datacenterIdShift) //
                | (workerId << workerIdShift) //
                | sequence;
    }

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

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

Код теста выглядит следующим образом

public static void main(String[] args) {
    SnowflakeDistributeId idWorker = new SnowflakeDistributeId(0, 0);
    for (int i = 0; i < 1000; i++) {
        long id = idWorker.nextId();
//      System.out.println(Long.toBinaryString(id));
        System.out.println(id);
    }
}

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

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

Многие другие алгоритмы снежинки также разработаны на основе этой идеи, а затем улучшены, чтобы избежать ее дефектов.Режим снежинки в Baidu UidGenerator и Meituan распределенная система генерации идентификаторов Leaf, представленная позже, все разработаны на основе снежинки.

Baidu-UidGenerator

UidGenerator от BaiduЭто генератор уникальных идентификаторов Baidu с открытым исходным кодом, основанный на языке Java, и в него были внесены некоторые улучшения на основе алгоритма снежинки. UidGenerator работает в проектах приложений в виде компонентов, поддерживает настраиваемые биты workerId и стратегии инициализации и подходит для таких сценариев, как автоматический перезапуск и дрейф экземпляров в виртуализированных средах, таких как Docker.

Что касается реализации, UidGenerator предоставляет два способа создания уникальных идентификаторов, а именно DefaultUidGenerator и CachedUidGenerator.Официальная рекомендация — использовать CachedUidGenerator, если есть соображения производительности.

Uidgenerator по-прежнему делит 64-битные биты на несколько частей, разделив пространство имен, но его метод разделения по умолчанию отличается от снежинки снежинки. По умолчанию он разделен на формат 1-28-22-13. Вы можете настроить количество битов, занятых каждым полем в соответствии с ситуацией и характеристиками вашего бизнеса.

  • Первый бит по-прежнему занимает 1 бит, и его значение всегда равно 0.
  • 28 битов, начиная со второго бита, являются отметкой времени, а 28-битные биты могут представлять 2^28 чисел.Уже не в миллисекундах, а в секундах, доступно каждое число, представляющее секунды (1L24365) ≈ 8,51 года.
  • Средний workId (центр обработки данных + рабочая машина, может быть составлен другими способами) состоит из 22-битных битов, которые могут представлять 2^22 = 4194304 рабочих ID.
  • Наконец, автоинкрементная последовательность формируется 13-битными битами, которые могут представлять 2^13 = 8192 числа.

Среди них workId (идентификатор машины) может поддерживать запуск машины примерно до 420 Вт. Встроенная реализация выделяется базой данных при запуске (имя таблицы WORKER_NODE).Стратегия выделения по умолчанию является одноразовой, а стратегия повторного использования может быть предоставлена ​​позже.

DROP TABLE IF EXISTS WORKER_NODE;
CREATE TABLE WORKER_NODE
(
ID BIGINT NOT NULL AUTO_INCREMENT COMMENT 'auto increment id',
HOST_NAME VARCHAR(64) NOT NULL COMMENT 'host name',
PORT VARCHAR(64) NOT NULL COMMENT 'port',
TYPE INT NOT NULL COMMENT 'node type: ACTUAL or CONTAINER',
LAUNCH_DATE DATE NOT NULL COMMENT 'launch date',
MODIFIED TIMESTAMP NOT NULL COMMENT 'modified time',
CREATED TIMESTAMP NOT NULL COMMENT 'created time',
PRIMARY KEY(ID)
)
 COMMENT='DB WorkerID Assigner for UID Generator',ENGINE = INNODB;

Реализация DefaultUidGenerator

DefaultUidGenerator — это обычный метод генерации, основанный на метках времени, машинных битах и ​​серийных номерах. Он очень похож на алгоритм снежинки. Он только генерирует исключения для обратных вызовов часов. Есть лишь несколько отличий, таких как измерение в секундах вместо миллисекунд и поддержка виртуализированных сред, таких как Docker.

protected synchronized long nextId() {
    long currentSecond = getCurrentSecond();

    // Clock moved backwards, refuse to generate uid
    if (currentSecond < lastSecond) {
        long refusedSeconds = lastSecond - currentSecond;
        throw new UidGenerateException("Clock moved backwards. Refusing for %d seconds", refusedSeconds);
    }

    // At the same second, increase sequence
    if (currentSecond == lastSecond) {
        sequence = (sequence + 1) & bitsAllocator.getMaxSequence();
        // Exceed the max sequence, we wait the next second to generate uid
        if (sequence == 0) {
            currentSecond = getNextSecond(lastSecond);
        }

    // At the different second, sequence restart from zero
    } else {
        sequence = 0L;
    }

    lastSecond = currentSecond;

    // Allocate bits for UID
    return bitsAllocator.allocate(currentSecond - epochSeconds, workerId, sequence);
}

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

<bean id="defaultUidGenerator" class="com.baidu.fsg.uid.impl.DefaultUidGenerator" lazy-init="false">
    <property name="workerIdAssigner" ref="disposableWorkerIdAssigner"/>

    <!-- Specified bits & epoch as your demand. No specified the default value will be used -->
    <property name="timeBits" value="29"/>
    <property name="workerBits" value="21"/>
    <property name="seqBits" value="13"/>
    <property name="epochStr" value="2016-09-20"/>
</bean>

Реализация CachedUidGenerator

Официально рекомендуемый метод генерации CachedUidGenerator с более высокой производительностью — использовать RingBuffer для кэширования сгенерированного идентификатора. Каждый элемент массива становится слотом. Емкость RingBuffer, по умолчанию используется максимальное значение последовательности в алгоритме Snowflake (2^13 = 8192). Его можно расширить с помощью конфигурации boostPower, чтобы повысить пропускную способность чтения и записи RingBuffer.

Указатель хвоста и указатель курсора используются для чтения и записи слотов в кольцевых массивах:

  • Хвостовой указатель Указывает максимальный порядковый номер, созданный производителем (этот порядковый номер начинается с 0 и продолжает увеличиваться). Хвост не может превышать Cursor, то есть производители не могут закрывать неиспользованные слоты. Когда Tail догнал curosr, PutRejectPolicy можно указать через rejectPutBufferHandler

  • Указатель курсора Указывает минимальный порядковый номер, потребляемый Потребителем (последовательность порядковых номеров такая же, как последовательность Источника). Курсор не может превышать Tail, то есть не может потреблять неиспользуемые слоты. Когда Cursor догнал хвост, TakeRejectPolicy можно указать через rejectTakeBufferHandler

CachedUidGenerator использует двойной RingBuffer, Uid-RingBuffer используется для хранения Uid, Flag-RingBuffer используется для хранения состояния Uid (может ли он быть заполнен, может ли он быть использован).

Поскольку элементы массива размещаются в памяти непрерывно, кэш-память ЦП может быть увеличена до максимума для повышения производительности. Но в то же время это приведет к проблеме «ложного обмена» FalseSharing, По этой причине метод заполнения CacheLine принят в Tail, указателе курсора и Flag-RingBuffer.

Время заполнения кольцевого буфера

  • Инициализировать предварительное заполнение Когда RingBuffer инициализируется, весь RingBuffer предварительно заполняется.

  • Мгновенное заполнение При потреблении сразу проверяются оставшиеся свободные слоты (хвост-курсор), если он меньше установленного порога, то свободные слоты будут заполнены. Порог можно настроить с помощью paddingFactor, см. конфигурацию CachedUidGenerator в разделе «Быстрый запуск».

  • цикл заполнения Благодаря потоку расписания незанятые слоты регулярно заполняются. Его можно настроить через scheduleInterval, чтобы применить функцию заполнения времени и указать интервал расписания.

Лист Мейтуан

Leaf — сервис распределенной генерации идентификаторов, запущенный базовой платформой исследований и разработок Meituan. Название взято из знаменитого высказывания Лейбница, немецкого философа и математика: "В мире нет двух одинаковых листьев", это невозможно в мире есть два одинаковых листа.

Leaf также предоставляет два метода генерации ID: схему базы данных Leaf-segment и схему Leaf-snowflake.

Решение для базы данных сегментов листьев

Схема базы данных Leaf-segment основана на вышеописанной схеме использования базы данных, и в нее внесены следующие изменения:

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

  • Различные требования к нумерации для каждого бизнесаbiz_tagИдентификаторы каждого biz-тега изолированы друг от друга и не влияют друг на друга. Если вам нужно расширить базу данных в будущем, если у вас есть требования к производительности, вам не нужны сложные операции расширения, описанные выше, а нужно только подбазу данных и подтаблицу для biz_tag.

Структура таблицы базы данных выглядит следующим образом:

CREATE TABLE `leaf_alloc` (
  `biz_tag` varchar(128)  NOT NULL DEFAULT '' COMMENT '业务key',
  `max_id` bigint(20) NOT NULL DEFAULT '1' COMMENT '当前已经分配了的最大id',
  `step` int(11) NOT NULL COMMENT '初始步长，也是动态调整的最小步长',
  `description` varchar(256)  DEFAULT NULL COMMENT '业务key的描述',
  `update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '更新时间',
  PRIMARY KEY (`biz_tag`)
) ENGINE=InnoDB;

Если раньше для получения идентификатора нужно было каждый раз писать в базу данных, то сейчас достаточно задать достаточно большой шаг, например 1000. Только тогда, когда будет использовано 1000 номеров, база данных будет снова прочитана и записана. Частота чтения и записи БД снижена с 1 до 1/шаг.Общая архитектура показана на следующем рисунке:

В то же время, чтобы решить TP999 (минимальное время, необходимое для удовлетворения сетевых запросов 999/1000), Leaf-сегмент имеет большие колебания данных, когда числовой сегмент израсходован, он все равно будет зависать на вводе-выводе обновление базы данных TP999 Данные будут иметь случайные всплески, что обеспечивает оптимизацию двойного буфера.

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

Для того, чтобы добиться неблокировки в процессе выборки БД сегмента номера, не нужно блокировать поток запроса при выборке БД сегмента номера, то есть когда сегмент номера израсходован до определенного момента, следующий сегмент номера асинхронно загружается в память, и нет необходимости ждать, пока сегмент номера будет исчерпан, чтобы обновить сегмент номера. Это может значительно снизить индекс TP999 системы. Подробная реализация показана на следующем рисунке:

В режиме двойного буфера служба Leaf имеет два буфера сегментов. Когда выдано 10% текущего сегмента номера, если следующий сегмент номера не обновляется, запускается другой поток обновления для обновления следующего сегмента номера. После доставки всего текущего сегмента, если следующий сегмент готов, он переключится на следующий сегмент для текущего сегмента, а затем доставит, и цикл повторится.

  • Каждый biz-тег имеет мониторинг скорости потребления.Обычно рекомендуется, чтобы длина сегмента была установлена ​​на 600-кратное число запросов в секунду (10 минут) числа запросов в секунду в период пиковой нагрузки, чтобы даже если БД не работает, Leaf может продолжать выдавать номера за 10-20 минут не затрагиваясь. .

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

Есть еще некоторые проблемы с этой схемой.Это все еще зависит от стабильности БД, и необходимо принять метод резервного копирования master-slave для повышения доступности БД.Кроме того, идентификатор, сгенерированный Leaf-сегментом Схема увеличивается в тренде, поэтому можно рассчитать идентификационный номер.Например, в случае генерации идентификатора заказа можно грубо рассчитать ежедневный объем заказа компании, вычитая идентификационный номер заказа, что невыносимо.

Лист-снежинка решение

Схема Leaf-snowflake полностью соответствует битовому дизайну схемы Snowflake.Для выделения workerID введена функция постоянных последовательных узлов Zookeeper для автоматической настройки wakerID для узлов-снежинок. Это позволяет избежать проблемы, заключающейся в том, что стоимость ручной настройки слишком высока при большом масштабе службы.

Листик-снежинка запускается по следующим шагам:

  • Запустите сервис Leaf-snowflake, подключитесь к Zookeeper и проверьте, зарегистрирован ли он под родительским узлом leaf_forever (есть ли дочерний узел в этом порядке).
  • Если вы зарегистрировались, чтобы получить свой собственный workerID (идентификационный номер типа int, сгенерированный узлом последовательности zk), запустите службу.
  • Если он не был зарегистрирован, создайте постоянный узел последовательности под родительским узлом.После успешного создания порядковый номер извлекается как собственный номер workerID, и служба запускается.

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

Как упоминалось выше, в алгоритмах, подобных снежинкам, существует проблема возврата часов, Лист-снежинка решает проблему возврата часов, проверяя собственное системное время иleaf_forever/${self}Узел записывает время для сравнения, а затем инициирует действие тревоги.

Официальное предложение Meituan заключается в том, что из-за его сильной зависимости от часов он более чувствителен к требованиям времени.Синхронизация NTP также вызовет откат второго уровня, когда машина работает.Рекомендуется напрямую отключить синхронизацию NTP. Или когда часы перезванивают, он просто не предоставляет услуги и возвращает ERROR_CODE напрямую, и ждет, пока часы догонят. Или выполните повторную попытку, а затем сообщите об этом в систему аварийной сигнализации, или автоматически удалите свой собственный узел и аварийный сигнал после обнаружения обратного вызова часов.

Что касается производительности, согласно официальным данным, текущая производительность Leaf составляет почти 5 Вт/с в QPS и 1 мс в TP999 на машине 4C8G.

Суммировать

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

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

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

И вы можете изменить время жизни и параллелизм, разделив три (метка времени, идентификатор машины, порядковый номер) на разные биты.

Например, для приложений, которые не требуют высокой степени параллелизма и рассчитаны на длительное использование, можно увеличить количество бит метки времени и уменьшить количество бит последовательности. Например, настройте его как {"workerBits":23,"timeBits" :31,"seqBits":9} , он может поддерживать 28 узлов для непрерывной работы в течение 68 лет при общем параллелизме 14400 UID/с.

Для приложений, в которых узлы часто перезапускаются и предполагается, что они будут использоваться в течение длительного времени, вы можете увеличить количество рабочих битов и временных меток, а также уменьшить количество битов последовательности. Например, настройте его как {"workerBits":27 ,"timeBits":30,"seqBits":6 }, он может поддерживать 37 узлов для непрерывной работы в течение 34 лет при общей скорости параллелизма 2400 UID/с.

Ссылаться на:

  1. blog.csdn.net
  2. GitHub.com/Baidu/UID-a…
  3. tech.meituan.com
  4. mp.weixin.qq.com

Категории