雪花算法分布式ID应用|snowflake,雪花算法,代码,demo|cyj

# 雪花算法分布式ID应用

本文分享分布式ID相关内容。

## 分布式ID的需求

* 全局唯一性
* 趋势递增：MySQL InnoDB中，通过有序主键保障写入性能和查询性能。
* 数据安全：ID不是连续自然数，避免人工猜测或爬虫抓取，达到和UUID一样效果。

## 常见的实现

* MySQL 单主自增ID：Insert前无法提前获取ID，多表依赖时必须先执行Insert取ID

* MySQL 多主自增ID：除单主限制外，还需要通过自增初始值+增长步长进行控制

* UUID：空间消耗大，无规则，索引效率低

* Redis：利用INCR命令生成，依赖第三方软件会提高复杂度，容易成为性能瓶颈，Redis宕机或重启需要考虑持久化问题

* [MongoDB’s ObjectIDs](https://docs.mongodb.com/manual/reference/method/ObjectId/) ：12字节数值，由4字节时间戳(秒)+5字节随机值+3字节计数器组成

* snowflake：Twitter开源的"雪花算法"

## snowflake 雪花算法

> [Twitter：Twitter Ids(snowflake)](https://developer.twitter.com/en/docs/basics/twitter-ids)
> [Twitter Archive：snowflake](https://github.com/twitter-archive/snowflake/tree/snowflake-2010)
> [Generating unique IDs in a distributed environment at high scale](https://www.callicoder.com/distributed-unique-id-sequence-number-generator/)

Snowflake 用于在 Twitter 内部生成唯一的ID，用于 Tweets, Direct Messages, Users, Collections, Lists 等产品。

ID由 64位无符号数组成，组成结构为：

* 时间戳(timestamp)：41位，毫秒单位，可用69年
* 机器号(worker number)：10位，最大支持1024机器
* 序列号(sequence number)：12位，每毫秒支持4096个数值，TPS可达 1000ms * 4096=400W/s

下面是64位组成结构，首位为符号位(有符号数，0表示正数)，未使用。

```
|--------|--------|--------|--------|--------|--------|--------|--------|
|01111111|11111111|11111111|11111111|11111111|11111111|11111111|11111111|
|-xxxxxxx|xxxxxxxx|xxxxxxxx|xxxxxxxx|xxxxxxxx|--------|--------|--------|
|--------|--------|--------|--------|--------|--xxxxxx|xxxx----|--------|
|--------|--------|--------|--------|--------|--------|----xxxx|xxxxxxxx|
```

**Twitter提醒：由于一些编程语言(如JavaScript) 支持的数值不能超过53位，因此最好同时提供id、idstr两个字段**。

## 自实现雪花算法

对于并发量不大的中小企业来说，可以适当调整雪花算法组成结构中的位数。

例如：

> 以来来自[廖雪峰老师:分布式唯一ID生成器](https://www.liaoxuefeng.com/article/1280526512029729)

* 时间戳：TPS很难达到400W，时间戳可降到秒为单位，32位可满足68年需求
* 机器：未采用容器时机器往往达不到1024台，可用5位(32台)足够。
* 序列号：16位可到65535，6W/s的TPS已挺高
* 以上，32+5+16=53位，可避免JS问题

下面是自实现ID生成工具：

* 使用了58位，由于容器化时代，机器位使用了10位，支持1024个容器
* 机器ID根据HOSTNAME自动生成

```java

import lombok.extern.slf4j.Slf4j;

import java.net.InetAddress;
import java.net.UnknownHostException;
import java.time.LocalDate;
import java.time.ZoneId;

/**
 * 分布式ID, 基于"雪花算法", 但对各段的位数进行了调整.
 * 适合中小型企业, 单应用并发写 <= 6W/s, 集群节点(容器或虚拟机) < 1024.
 * long 型共64位, 占用58位, 首6位空闲.
 * |--------|--------|--------|--------|--------|--------|--------|--------|
 * |00000000|11111111|11111111|11111111|11111111|11111111|11111111|11111111|
 * |------xx|xxxxxxxx|xxxxxxxx|xxxxxxxx|xxxxxx--|--------|--------|--------|
 * |--------|--------|--------|--------|------xx|xxxxxxxx|--------|--------|
 * |--------|--------|--------|--------|--------|--------|xxxxxxxx|xxxxxxxx|
 * 
 * 时间戳位: 32位, 单位秒, (2的32次方=2147483647秒=68年)
 * 机器位 : 10位, 1024台虚拟机(含Docker容器)
 * 序列号位: 16位, 2的16次方=65535, 即支持单应用6W/s并发写入
 * 
 * 若要适配更高TPS, 可将时间戳调整为毫秒为单位
 *
 * @see IdUtil
 */
@Slf4j
public class SnowFlake {

/**
     * 开始时间, 2020-1-1. 时间戳位上并不存储实际的时间, 而是当前时间与开始时间的差值(秒)
     */
    private final static long START_TIMESTAMP = LocalDate.of(2020, 1, 1)
            .atStartOfDay(ZoneId.of("Z")).toEpochSecond();
    /**
     * ID结构: 32位时间戳(秒) + 10位机器 + 16位序列号
     */
    private final static long TIMESTAMP_BIT = 32;
    private final static long MACHINE_BIT = 10;
    private final static long SEQUENCE_BIT = 16;

/**
 * 最大机器号
 */
 private final static long MAX_MACHINE = 1 << MACHINE_BIT - 1;

/**
 * 最大序列号
 */
 private static final long MAX_SEQUENCE = 1 << SEQUENCE_BIT - 1;

/**
     * 机器位和时间戳左移位数.
     */
    private final static long MACHINE_LEFT = SEQUENCE_BIT;
    private final static long TIMESTAMP_LEFT = MACHINE_BIT + SEQUENCE_BIT;

/**
     * 机器标识
     */
    private static long machineId = 1;
    private static boolean machineInitialized = false;

/**
     * 序列号
     */
    private static long sequence = 0L;

/**
     * 上一次时间戳
     */
    private static long lastTimestamp = -1L;

static {
        initMachineId();
    }

/**
     * 获取分布式ID
     *
     * @return
     */
    public static long nextId() {
        return nextId(getNowSeconds());
    }

private static synchronized long nextId(long nowSeconds) {
 long currentTimestamp = nowSeconds;
 // 当前时间异常, 自动校准
 if (currentTimestamp < lastTimestamp) {
 currentTimestamp = lastTimestamp;
 }
 // 相同秒内，序列号自增
 if (currentTimestamp == lastTimestamp) {
 long nextSequence = sequence + 1;
 //同一秒的序列数已经达到最大, 获取下一秒的ID(直接使用下一秒)
 if (nextSequence >= MAX_SEQUENCE) {
 return nextId(nowSeconds + 1);
 } else {
 sequence = nextSequence;
 }
 } else {
 // 不同秒内，序列号置重置为0, 重新计数
 sequence = 0L;
 }
 lastTimestamp = currentTimestamp;
 // 当前时间与开始时间的差值
 long timeDelta = currentTimestamp - START_TIMESTAMP;
 // 各段结构拼接("|"操作)成ID
 return timeDelta << TIMESTAMP_LEFT
 | machineId << MACHINE_LEFT
 | sequence;
 }

private static long getNowSeconds() {
        return System.currentTimeMillis() / 1000;
    }

/**
 * 通过hostname初始化机器ID, 将hostname各字符累加并对machineId最大值取余
 * 虚拟主机: 可手工设置, eg:prod1 
 * 普通容器: 默认容器ID为HOSTNAME, eg: b88598ebca38
 * K8s Pod: 默认Pod ID为HOSTNAME, eg: user-service-433cf-5f6d48c7f4-8fclh
 *
 * @return
 */
 private static void initMachineId() {
 try {
 if (!machineInitialized) {
 String hostname = InetAddress.getLocalHost().getHostName();
 char[] hostnameChars = hostname.toCharArray();
 int sumOfHostname = 0;
 for (int i = 0, length = hostnameChars.length; i < length; i++) {
 sumOfHostname += hostnameChars[i];
 }
 machineId = sumOfHostname % MAX_MACHINE;
 log.info("====> Init machineId. hostname[" + hostname + "], machineId[" + machineId + "]");
 }
 } catch (UnknownHostException e) {
 log.error("====> Init machineId failure");
 e.printStackTrace();
 } finally {
 machineInitialized = true;
 }
 }

/**
     * 覆盖默认machineID
     *
     * @param mid machineId
     */
    public static void setMachineId(long mid) {
        if (mid > 0) {
            machineId = mid;
        }
    }
}
```

本文由 cyj 创作，可自由转载、引用，但需署名作者且注明文章出处。

文章标题: 雪花算法分布式ID应用

文章链接: https://chenyongjun.vip/articles/153

扫码或搜索 cyjrun 关注微信公众号, 结伴学习, 一起努力