mysql로 구현된 Snowflake 알고리즘
- coldplay.xixi앞으로
- 2020-08-20 16:15:516292검색
【관련 학습 추천: mysql 동영상 튜토리얼】
1. 눈송이 알고리즘을 사용하는 이유
1. 문제의 배경
최근에는 분산형, 마이크로서비스를 사용하는 기업이 늘어나고 있으며, 이후에는 해당 데이터베이스는 서비스별로 분할되며, 데이터 양이 증가하면 테이블도 분할되며, 테이블 분할 후 ID 문제가 발생합니다.
예를 들어, 이전 단일 프로젝트에서는 테이블의 데이터 기본 키 ID가 자동 증가되었습니다. MySQL은 자동 증가를 달성하는 반면 Oracle은 이를 달성하기 위해 시퀀스를 사용했습니다. 단일 테이블이 늘어나면 완료됩니다. 수평 테이블 분할의 경우 Alibaba Java 개발에서는 단일 테이블이 500만 개보다 클 때 테이블 분할을 권장하지만 세부 사항은 여전히 비즈니스에 따라 다릅니다. 단일 테이블에서도 가능합니다. 수평 테이블 분할은 하나의 테이블의 데이터를 여러 테이블로 나누는 것인데, 이전의 자동 증가에 따라 여전히 기본 키 ID가 생성되어 있으면 이때 중복된 ID가 발생하게 됩니다. 분포를 해결하기 위해 어떤 솔루션을 고려하십시오. 공식 ID에 문제가 있습니다.
2. 솔루션
2.1. 데이터베이스 테이블
특정 라이브러리에 테이블을 유지 관리하고, ID를 늘려야 하는 테이블이 있을 때마다 이 테이블의 레코드를 확인한 다음 잠금 업데이트에 사용할 수 있습니다. 그런 다음 얻은 값에 1을 추가하고 반환한 후 해당 값을 테이블에 기록합니다. 그러나 이 방법은 동시성이 상대적으로 적은 프로젝트에 적합하므로 매번 테이블을 잠가야 합니다.
2.2, redis
redis는 단일 스레드이기 때문에 redis에서 키-값 쌍을 유지할 수 있으며, 그런 다음 어떤 테이블이 직접 redis로 가서 값을 가져온 다음 추가해야 하지만 이는 다음과 같습니다. 위의 이유는 단일 스레딩이 높기 때문입니다. 동시성 지원은 높지 않으며 동시성이 작은 프로젝트에만 적합합니다.
2.3, uuid
uuid를 고유한 기본 키 ID로 사용할 수 있지만, uuid의 문제점은 순서가 지정되지 않은 문자열이라는 점입니다. uuid를 기본 키로 사용하면 기본 키 인덱스가 유효하지 않게 됩니다.
2.4.Snowflake 알고리즘
Snowflake 알고리즘은 분산 ID에 대한 효율적인 솔루션입니다. 대부분의 인터넷 회사에서는 Snowflake 알고리즘을 사용하고 있으며, 물론 다른 솔루션을 자체적으로 구현하는 회사도 있습니다.
2. Snowflake 알고리즘
1. 원리
Snowflake 알고리즘은 64비트 길이의 데이터를 사용하여 ID를 저장합니다. 0은 정수를 나타내고 1은 음수를 나타냅니다. 일반적으로 0이므로 가장 높은 비트는 변경되지 않고 41비트는 밀리초 타임스탬프를 저장하고, 10비트는 기계 코드(5비트 datacenterId 및 5비트 작업자 ID 포함)를 저장하며, 12비트는 시퀀스 번호를 저장합니다. 이런 방식으로 최대 2의 10승을 갖는 머신 수, 즉 1024개의 머신은 밀리초당 최대 2의 12제곱인 4096개의 ID를 생성할 수 있습니다. (아래 코드 구현이 있습니다)
하지만 일반적으로 머신이 많지 않기 때문에 53 비트를 사용하여 ID를 저장할 수도 있습니다. 왜 53비트를 사용하는가?
우리는 거의 모두 웹 페이지를 다루기 때문에 js가 지원하는 최대 정수 범위는 53비트입니다. 이 범위를 초과하면 53비트 내에서 직접 읽을 수 있습니다. 53비트를 초과하는 경우 js가 올바르게 처리되도록 문자열로 변환해야 합니다. 53개가 저장되면 32비트는 두 번째 수준 타임스탬프를 저장하고, 5비트는 기계어 코드를 저장하고, 16비트는 직렬화를 저장합니다. 이러한 방식으로 각 기계는 초당 65536개의 고유 ID를 생성할 수 있습니다.
2.단점
눈송이 알고리즘은 시간 의존도가 높기 때문에 서버 시계 다이얼백이 발생하면 중복 ID가 생성될 수 있습니다. 물론, 서버 시간을 수정하는 회사는 거의 없습니다. 수정하면 여러 가지 문제가 발생할 수 있습니다. 회사에서는 서버 시간을 수정하는 것보다 새로운 서버를 추가하는 편을 선호하지만, 특별한 상황을 배제할 수는 없습니다.
시계가 다시 설정되는 문제를 해결하는 방법은 무엇입니까? 직렬화의 초기 값에 대한 단계 크기를 설정할 수 있습니다. 시계 다이얼백 이벤트가 트리거될 때마다 초기 단계 크기는 다음 코드의 85번째 줄에서 달성될 수 있습니다. 시퀀스는 10000으로 설정됩니다.
3. 코드 구현
64비트 코드 구현:
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'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();
}
//==============================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);
}
}
}보충 지식: Snowflake 알고리즘은 분산 자체 증가 ID를 구현합니다. 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; } }관련 추천:
프로그래밍 비디오 코스위 내용은 mysql로 구현된 Snowflake 알고리즘의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!