Von MySQL implementierter Snowflake-Algorithmus

[Verwandte Lernempfehlungen: MySQL-Video-Tutorial]

1. Warum den Snowflake-Algorithmus verwenden

1. Der Hintergrund des Problems

Heutzutage nutzen immer mehr Unternehmen verteilte Microservices, dann die Die entsprechende Datenbank wird für verschiedene Dienste aufgeteilt. Wenn dann die Datenmenge zunimmt, werden auch die Tabellen aufgeteilt, und nach der Aufteilung der Tabellen kommt es zur Ausgabe von IDs.

Beim vorherigen Einzelprojekt wurde die Daten-Primärschlüssel-ID in einer Tabelle automatisch inkrementiert, während Oracle Sequenzen verwendete, um dies zu erreichen Für die horizontale Tabellenaufteilung empfiehlt die Java-Entwicklung von Alibaba die Aufteilung von Tabellen, wenn eine einzelne Tabelle größer als 5 Millionen ist. Die Einzelheiten hängen jedoch immer noch vom Unternehmen ab in einer einzelnen Tabelle ist ebenfalls möglich. Die horizontale Tabellenaufteilung besteht darin, die Daten einer Tabelle in mehrere Tabellen aufzuteilen. Wenn die Primärschlüssel-ID weiterhin gemäß der vorherigen automatischen Inkrementierung erstellt wird, müssen Sie dies tun Überlegen Sie, welche Lösung zur Lösung der Verteilung erforderlich ist. Es liegt ein Problem mit der Formel-ID vor.

2. Lösung

2.1. Datenbanktabelle

Sie können eine Tabelle speziell in einer bestimmten Bibliothek verwalten und dann die Datensätze dieser Tabelle jedes Mal überprüfen, unabhängig davon, welche Tabelle ihre ID erhöhen muss, und sie dann zur Aktualisierungssperre verwenden Fügen Sie dann eins zum erhaltenen Wert hinzu und zeichnen Sie den Wert nach der Rückkehr in die Tabelle auf. Diese Methode eignet sich jedoch für Projekte mit relativ geringer Parallelität, sodass die Tabelle jedes Mal gesperrt werden muss. 2.2, Redis oben, da Single-Threading hoch ist. Die Parallelitätsunterstützung ist nicht hoch und nur für Projekte mit geringer Parallelität geeignet.

2.3, uuid

Sie können uuid als eindeutige Primärschlüssel-ID verwenden, aber ein Problem mit uuid besteht darin, dass es sich um eine ungeordnete Zeichenfolge handelt. Wenn uuid als Primärschlüssel verwendet wird, ist der Primärschlüsselindex ungültig.

2.4. Der Snowflake-Algorithmus ist eine effiziente Lösung für verteilte IDs. Die meisten Internetunternehmen verwenden den Snowflake-Algorithmus, und natürlich gibt es Unternehmen, die selbst andere Lösungen implementieren.

2. Snowflake-Algorithmus

1. Prinzip

Der Snowflake-Algorithmus verwendet 64-Bit-lange Daten zum Speichern von IDs. 0 steht für eine Ganzzahl und 1 für eine negative Zahl. Im Allgemeinen ist es 0, sodass das höchste Bit unverändert bleibt. 41 Bit speichern den Millisekunden-Zeitstempel, 10 Bit speichern den Maschinencode (einschließlich 5-Bit-Datencenter-ID und 5-Bit-Worker-ID) und 12 Bit speichern die Sequenznummer. Auf diese Weise kann die maximale Anzahl an Maschinen mit maximal 2 hoch 10, also 1024 Maschinen, maximal 2 hoch 12 von 4096 IDs pro Millisekunde erzeugen. (Code-Implementierung unten)

Aber im Allgemeinen haben wir nicht so viele Maschinen, daher können wir auch 53 Bit zum Speichern der ID verwenden. Warum 53 Bit verwenden?

Da wir uns fast alle mit Webseiten befassen, müssen wir uns mit js befassen. Der von js unterstützte maximale Ganzzahlbereich beträgt 53 Bit und kann direkt gelesen werden von js. Wenn es 53 Bit überschreitet, muss es in eine Zeichenfolge konvertiert werden, um sicherzustellen, dass js korrekt verarbeitet wird. Wenn 53 gespeichert werden, speichern 32 Bit den Zeitstempel der zweiten Ebene, 5 Bit speichern den Maschinencode und 16 Bit speichern die Serialisierung. Auf diese Weise kann jede Maschine 65536 eindeutige IDs pro Sekunde erzeugen.

2. Nachteile

Da der Snowflake-Algorithmus stark von der Zeit abhängig ist, können beim Rückruf der Serveruhr doppelte IDs generiert werden. Natürlich wird fast kein Unternehmen die Serverzeit ändern. Das Unternehmen würde lieber einen neuen Server hinzufügen, als die Serverzeit zu ändern, aber besondere Umstände können nicht ausgeschlossen werden.

Wie kann das Problem der Uhrrückstellung gelöst werden? Sie können die Schrittgröße für den Anfangswert der Serialisierung festlegen. Bei jedem Auslösen des Clock-Dialback-Ereignisses wird die Anfangsschrittgröße um 1 W erhöht. Dies kann in Zeile 85 des folgenden Codes und des Anfangswerts erreicht werden Die Sequenz ist auf 10000 eingestellt. 3. Codeimplementierung Code~

package com.yl.common;
/**
 * 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 SnowflakeIdWorker {

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

 /** 机器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 SnowflakeIdWorker(long workerId, long datacenterId) {
 if (workerId > maxWorkerId || workerId < 0) {
 throw new IllegalArgumentException(String.format("worker Id can&#39;t be greater than %d or less than 0", maxWorkerId));
 }
 if (datacenterId > maxDatacenterId || datacenterId < 0) {
 throw new IllegalArgumentException(String.format("datacenter Id can&#39;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();
 }

 //==============================Test=============================================
 /** 测试 */
 public static void main(String[] args) {
 SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);
 
 for (int i = 0; i < 100; i++) {
 long id = idWorker.nextId();
 System.out.println(id);
 }
 }
}

Verwandte Empfehlungen:

Programmiervideokurs

Das obige ist der detaillierte Inhalt vonVon MySQL implementierter Snowflake-Algorithmus. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!