Algorithme Snowflake implémenté par MySQL

[Recommandations d'apprentissage associées : Tutoriel vidéo MySQL]

Pourquoi utiliser l'algorithme de flocon de neige

1. L'arrière-plan du problème

De nos jours, de plus en plus d'entreprises utilisent des services distribués et des micro-services, de sorte que les bases de données correspondantes seront divisées en différents services, puis, lorsque la quantité de données augmentera, les tables seront également être divisé lorsque la table est divisée, et il y aura alors le problème de l'identification après la division de la table.

Par exemple, dans le projet précédent, l'identifiant de la clé primaire des données dans une table était auto-incrémenté. MySQL utilisait l'auto-incrémentation pour obtenir l'auto-incrémentation, tandis qu'Oracle utilisait des séquences pour y parvenir. La quantité de données dans une seule table augmente. À l'avenir, la division horizontale des tables sera nécessaire. La recommandation de développement Java d'Alibaba est de diviser les tables lorsqu'une seule table dépasse 5 millions, mais les détails dépendent toujours de l'entreprise. Si l'index est utilisé, des dizaines de millions de données dans une seule table sont également possibles. Le partitionnement horizontal des tables consiste à diviser les données d'une table en plusieurs tables. Le problème se pose alors si l'ID de clé primaire est toujours créé selon l'incrémentation automatique précédente, alors la duplication de l'ID se produira à ce moment-là. quelle solution pour résoudre le problème de distribution. Il y a un problème avec l'identifiant de la formule.

2. Solution

2.1. Table de base de données

Vous pouvez conserver une table spécifiquement dans une certaine bibliothèque, puis chaque fois qu'une table doit incrémenter son identifiant, vérifiez les enregistrements. de cette table, puis utilisez pour update pour verrouiller la table, puis ajoutez-en une à la valeur obtenue, puis renvoyez et enregistrez à nouveau la valeur dans la table. Cependant, cette méthode convient aux projets avec une concurrence relativement faible, donc à chaque fois je dois. verrouillez la montre.

2.2, redis

Étant donné que redis est monothread, vous pouvez conserver une paire clé-valeur dans redis, puis quelle table doit accéder directement à redis pour obtenir la valeur, puis ajouter un, mais c'est la même chose que ci-dessus. De plus, comme un seul thread n'a pas un support élevé pour une concurrence élevée, il ne convient qu'aux projets avec une faible concurrence.

2.3, uuid

Vous pouvez utiliser uuid comme identifiant de clé primaire unique, mais un problème avec uuid est qu'il s'agit d'une chaîne non ordonnée. Si uuid est utilisé comme clé primaire, la clé primaire. L'index clé sera invalide.

2.4. Algorithme Snowflake

L'algorithme Snowflake est une solution efficace pour les identifiants distribués. La plupart des sociétés Internet utilisent l'algorithme Snowflake, et bien sûr, certaines entreprises mettent en œuvre elles-mêmes d'autres solutions.

2. Algorithme Snowflake

1. Principe

L'algorithme Snowflake utilise un magasin de données de type long de 64 bits. l'identifiant, le bit le plus élevé stocke 0 ou 1, 0 représente un entier, 1 représente un nombre négatif, généralement 0, donc le bit le plus élevé reste inchangé, 41 bits stockent l'horodatage au niveau de la milliseconde, 10 bits stockent le code machine (y compris 5 bits datacenterId et workerId à 5 chiffres), numéro de séquence de stockage à 12 chiffres. De cette façon, le nombre maximum de machines avec un maximum de 2 à la puissance 10, soit 1024 machines, peut générer un maximum de 2 à la puissance 12 de 4096 ID par milliseconde. (Il y a une implémentation de code ci-dessous)

Mais en général, nous n'avons pas beaucoup de machines, nous pouvons donc également utiliser 53 bits pour stocker l'identifiant. Pourquoi utiliser 53 bits ?

Parce que nous traitons presque tous avec des pages Web, nous devons gérer js. La plage entière maximale prise en charge par js est de 53 bits. Si elle dépasse cette plage, la précision sera perdue dans les 53. être lu directement par js, s'il dépasse 53 chiffres, il doit être converti en chaîne pour garantir un traitement js correct. Si 53 sont stockés, 32 bits stockent l'horodatage de deuxième niveau, 5 bits stockent le code machine et 16 bits stockent la sérialisation. De cette manière, chaque machine peut produire 65 536 identifiants uniques par seconde.

2. Inconvénients

Étant donné que l'algorithme du flocon de neige repose fortement sur le temps, lorsque l'horloge du serveur est rappelée, des identifiants en double peuvent être générés. Bien sûr, presque aucune entreprise ne modifiera l'heure du serveur. La modification entraînera divers problèmes. L'entreprise préfère ajouter un nouveau serveur plutôt que de modifier l'heure du serveur, mais des circonstances particulières ne peuvent être exclues.

Comment résoudre le problème du décalage d'horloge ? Vous pouvez définir la taille du pas pour la valeur initiale de la sérialisation. Chaque fois que l'événement de rappel d'horloge est déclenché, la taille du pas initial est augmentée de 1w. Cela peut être réalisé dans la ligne 85 du code suivant et la valeur initiale du. la séquence est définie sur 10 000.

3. Implémentation du code

Implémentation du code 64 bits :

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);
 }
 }
}

Connaissances supplémentaires : L'algorithme Snowflake implémente un ID distribué à auto-augmentation

Je ne dirai pas de bêtises, regardons simplement le code~

/**
 * <p>名称：IdWorker.java</p>
 * <p>描述：分布式自增长ID</p>
 * <pre class="brush:php;toolbar:false">
 * Twitter的 Snowflake　JAVA实现方案
 * 

* 核心代码为其IdWorker这个类实现，其原理结构如下，我分别用一个0表示一位，用—分割开部分的作用： * 1||0---0000000000 0000000000 0000000000 0000000000 0 --- 00000 ---00000 ---000000000000 * 在上面的字符串中，第一位为未使用（实际上也可作为long的符号位），接下来的41位为毫秒级时间， * 然后5位datacenter标识位，5位机器ID（并不算标识符，实际是为线程标识）， * 然后12位该毫秒内的当前毫秒内的计数，加起来刚好64位，为一个Long型。 * 这样的好处是，整体上按照时间自增排序，并且整个分布式系统内不会产生ID碰撞（由datacenter和机器ID作区分）， * 并且效率较高，经测试，snowflake每秒能够产生26万ID左右，完全满足需要。 *

* 64位ID (42(毫秒)+5(机器ID)+5(业务编码)+12(重复累加)) * * @author Polim */ public class IdWorker { // 时间起始标记点，作为基准，一般取系统的最近时间（一旦确定不能变动） private final static long twepoch = 1288834974657L; // 机器标识位数 private final static long workerIdBits = 5L; // 数据中心标识位数 private final static long datacenterIdBits = 5L; // 机器ID最大值 private final static long maxWorkerId = -1L ^ (-1L << workerIdBits); // 数据中心ID最大值 private final static long maxDatacenterId = -1L ^ (-1L << datacenterIdBits); // 毫秒内自增位 private final static long sequenceBits = 12L; // 机器ID偏左移12位 private final static long workerIdShift = sequenceBits; // 数据中心ID左移17位 private final static long datacenterIdShift = sequenceBits + workerIdBits; // 时间毫秒左移22位 private final static long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits; private final static long sequenceMask = -1L ^ (-1L << sequenceBits); /* 上次生产id时间戳 */ private static long lastTimestamp = -1L; // 0，并发控制 private long sequence = 0L; private final long workerId; // 数据标识id部分 private final long datacenterId; public IdWorker(){ this.datacenterId = getDatacenterId(maxDatacenterId); this.workerId = getMaxWorkerId(datacenterId, maxWorkerId); } /** * @param workerId * 工作机器ID * @param datacenterId * 序列号 */ public IdWorker(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; } /** * 获取下一个ID * * @return */ public synchronized long nextId() { long timestamp = timeGen(); if (timestamp < lastTimestamp) { throw new RuntimeException(String.format("Clock moved backwards. Refusing to generate id for %d milliseconds", lastTimestamp - timestamp)); } if (lastTimestamp == timestamp) { // 当前毫秒内，则+1 sequence = (sequence + 1) & sequenceMask; if (sequence == 0) { // 当前毫秒内计数满了，则等待下一秒 timestamp = tilNextMillis(lastTimestamp); } } else { sequence = 0L; } lastTimestamp = timestamp; // ID偏移组合生成最终的ID，并返回ID long nextId = ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift) | (workerId << workerIdShift) | sequence; return nextId; } private long tilNextMillis(final long lastTimestamp) { long timestamp = this.timeGen(); while (timestamp <= lastTimestamp) { timestamp = this.timeGen(); } return timestamp; } private long timeGen() { return System.currentTimeMillis(); } /** *

* 获取 maxWorkerId *

*/ protected static long getMaxWorkerId(long datacenterId, long maxWorkerId) { StringBuffer mpid = new StringBuffer(); mpid.append(datacenterId); String name = ManagementFactory.getRuntimeMXBean().getName(); if (!name.isEmpty()) { /* * GET jvmPid */ mpid.append(name.split("@")[0]); } /* * MAC + PID 的 hashcode 获取16个低位 */ return (mpid.toString().hashCode() & 0xffff) % (maxWorkerId + 1); } /** *

* 数据标识id部分 *

*/ protected static long getDatacenterId(long maxDatacenterId) { long id = 0L; try { InetAddress ip = InetAddress.getLocalHost(); NetworkInterface network = NetworkInterface.getByInetAddress(ip); if (network == null) { id = 1L; } else { byte[] mac = network.getHardwareAddress(); id = ((0x000000FF & (long) mac[mac.length - 1]) | (0x0000FF00 & (((long) mac[mac.length - 2]) << 8))) >> 6; id = id % (maxDatacenterId + 1); } } catch (Exception e) { System.out.println(" getDatacenterId: " + e.getMessage()); } return id; } }

Recommandations associées : Cours vidéo de programmation

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!