天天看点
返回

分库分表后全局ID生成方案（下）4 snowflake算法（主流方案）其它方案

4 snowflake算法（主流方案）

4.1 组成

twitter开源的分布式id生成算法，将一个64位long型id：

分库分表后全局ID生成方案（下）4 snowflake算法（主流方案）其它方案

1 bit：不用

因为二进制里第一个bit为如果是1，那么都是负数，但是我们生成的id都是正数，所以第一个bit统一0

41 bit：ms时间戳

可表示数字多达2^41 - 1，即可标识2 ^ 41 - 1个毫秒值，就是69年

10 bit：记录工作机器id

代表该服务最多可部署在2^10=1024台机器。若你的系统部署在多机房，则10位机器ID可继续划分为2～3位IDC表示（可支撑4或8个IDC机房）和7～8位机器ID（支持128-256台机器）

12 bit：记录同一个毫秒内产生的不同id序列号

2 ^ 12 - 1 = 4096，即可区分同一个毫秒内的4096个不同id

4.2 举例

64位的long型的id，64位的long => 二进制

0 | 
0001100 10100010 10111110 10001001 01011100 00 |
10001 | 
1 1001 | 
0000 00000000

2018-01-01 10:00:00

做一些计算，再换算成一个二进制，41bit存储：

0001100 10100010 10111110 10001001 01011100 00

机房id，17=》换算成一个二进制=》

10001

机器id，25=》换算成一个二进制=》

11001

snowflake算法服务，会判断一下，当前这个请求是否是，机房17的机器25，在2175/11/7 12:12:14时间点发送过来的第一个请求，如果是第一个请求

假设，在2175/11/7 12:12:14时间里，机房17的机器25，发送了第二条消息，snowflake算法服务，会发现说机房17的机器25，在2175/11/7 12:12:14时间里，在这一毫秒，之前已经生成过一个id了，此时如果你同一个机房，同一个机器，在同一个毫秒内，再次要求生成一个id，此时我只能把加1

0 | 0001100 10100010 10111110 10001001 01011100 00 | 10001 | 1 1001 | 0000 00000001

比如我们来观察上面的那个，就是一个典型的二进制的64位的id，换算成10进制就是910499571847892992。

4.3 实践

利用这个工具类，自己搞个服务，然后对每个机房的每个机器都初始化这么一个东西，刚开始这个机房的这个机器的序号就是0。

然后每次接收到一个请求，说这个机房的这个机器要生成一个id，你就找到对应的Worker，生成。

这个算法生成的时候，会：

  • 把当前毫秒放到41 bit中
  • 然后5 bit是机房id
  • 5 bit是机器id
  • 接着就是判断上一次生成id的时间如果跟这次不一样，序号就自动从0开始；要是上次的时间跟现在还是在一个毫秒内，他就把seq累加1，就是自动生成一个毫秒的不同的序号

该算法可以确保每个机房每个机器每一毫秒，最多生成4096个不重复的id。

利用这个snowflake算法，可以开发自己公司的服务，甚至对于机房id和机器id，反正给你预留了5 bit + 5 bit，你换成别的有业务含义的东西也可。

不同公司也会依据自身业务的特点对Snowflake算法做一些改造：

  • 减少序列号位数，增加机器ID位数以支持单IDC更多的机器
  • 在其中加入业务ID字段来区分不同业务。如组成规则：1位兼容位恒为0 + 41位时间信息 + 6位IDC信息（支持64个IDC）+ 6位业务信息（支持64个业务）+ 10位自增信息（每毫秒支持1024个号）

主要因为在单机房只部署一个发号器节点，且使用KeepAlive保证可用性。业务信息指的是项目中哪个业务模块使用，如用户模块生成的ID，内容模块生成的ID，把它加入进来：

  • 希望不同业务发出来的ID可以不同
  • 因为在出现问题时可以反解ID，知道哪个业务发出的ID

工程化

为业务生成全局唯一ID，一般有如下算法实现：

嵌入业务代码

即分布在业务服务器中。

  • 好处

    业务代码在使用时无需跨网络调用，性能好些，但需更多机器ID位数支持更多业务服务器。

    由于业务服务器数很多，难保证机器ID唯一性，所以需引入ZooKeeper等分布式一致性组件保证每次机器重启时，都能获得唯一机器ID。

作为独立的服务部署

即发号器服务。业务在使用发号器的时候就需要多一次的网络调用，但是内网的调用对于性能的损耗有限，却可以减少机器ID的位数，如果发号器以主备方式部署，同时运行的只有一个发号器，那么机器ID可以省略，这样可以留更多的位数给最后的自增信息位。即使需要机器ID，因为发号器部署实例数有限，那么就可以把机器ID写在发号器的配置文件里，这样即可以保证机器ID唯一性，也无需引入第三方组件了。微博和美图都是使用独立服务的方式来部署发号器的，性能上单实例单CPU可以达到两万每秒。

Snowflake算法设计的非常简单且巧妙，性能上也足够高效，同时也能生成具有全局唯一性、单调递增性和有业务含义的ID，但是它也有一些缺点，最大缺点就是依赖系统时间戳，一旦系统时间不准，就有可能生成重复ID。

所以如果我们发现系统时钟不准，就可以让发号器暂时拒绝发号，直到时钟准确。

如果请求发号器的QPS不高，比如说发号器每毫秒只发一个ID，就会造成生成ID的末位永远是1，那么在分库分表时如果使用ID作为分区键就会造成库表分配的不均匀。解决：

  • 时间戳不记录毫秒而是记录秒，这样在一个时间区间里可以多发出几个号，避免出现分库分表时数据分配不均
  • 生成的序列号的起始号可以做一下随机，这一秒是21，下一秒是30，这样就会尽量的均衡了

生产都使用变种的Snowflake算法，这些改造：

  • 让算法中的ID生成规则符合自己业务的特点
  • 解决诸如时间回拨等问题

如果我们发现系统时钟不准，就可以让发号器暂时拒绝发号，直到时钟准确为止。我们的程序本身就是运行在系统中的，如何来判断系统中的时间是否准确呢？

可以暂时记录上次发好的时间，然后和这次的时间比较。

假设通过容器化来部署发号器，且同时会有多个发号器容器运行，那这个 worker Id 如何生成。容器自身的 id 是一串很长的16进制，无法转换为 worker id 吧？难道也需要引入 zookeeper？有没有其他简单可行的方案？

容器ID太长了。其实引入zk也还好，对于zk是弱依赖，只是启动的时候拉一下机器ID。

其它方案

百度开源的UidGenerator

（仅支持单机部署）使用Snowflake算法，单机QPS可达600万。项目说明：

https://github.com/baidu/uid-generator/blob/master/README.zh_cn.md

。

美团Leaf（分布式ID生成系统）

QPS近5万。项目地址：

https://tech.meituan.com/2017/04/21/mt-leaf.html

微信序列号生成器

文档地址：

https://www.infoq.cn/article/wechat-serial-number-generator-architecture
  1. 递增但不连续的数字序列解决方案。
  2. 设计目标QPS1000万以上。
  3. 通过在递增过程中使用“步长”将每秒磁盘写入由1000万级降至1万。
  4. 设计原理相对于Snowflake更通俗易懂。
  5. 可以使用hash的负载均衡策略组建集群。
  6. 缺点：需要自己实现集群中机器增减后更新负载均衡策略的逻辑。

Java版最简单Demo

使用spring boot搭建一个web工程，使用Controller调用Service实现数字递增

Service类

import org.springframework.stereotype.Service;

import javax.annotation.PostConstruct;
import java.util.concurrent.atomic.AtomicLong;

@Service
public class GeneratorService {

private AtomicLong id;

@PostConstruct
private void init(){
id = new AtomicLong(0);
}

public long getId(){
return id.incrementAndGet();
}
}

单机测试QPS 3万（测试工程、测试脚本在同一机器运行。）

硬件信息：CPU 2.7 GHz Intel Core i7 | 内存 16 GB 2133 MHz LPDDR3

测试工具：JMeter

4.3 实现 

public class IdWorker {

    private long workerId;
    private long datacenterId;
    private long sequence;

    public IdWorker(long workerId, long datacenterId, long sequence) {
        // sanity check for workerId
        // 这儿不就检查了一下，要求就是你传递进来的机房id和机器id不能超过32，不能小于0
        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));
        }
        System.out.printf(
                "worker starting. timestamp left shift %d, datacenter id bits %d, worker id bits %d, sequence bits %d, workerid %d",
                timestampLeftShift, datacenterIdBits, workerIdBits, sequenceBits, workerId);

        this.workerId = workerId;
        this.datacenterId = datacenterId;
        this.sequence = sequence;
    }

    private long twepoch = 1288834974657L;

    private long workerIdBits = 5L;
    private long datacenterIdBits = 5L;

    // 这个是二进制运算，就是 5 bit最多只能有31个数字，也就是说机器id最多只能是32以内
    private long maxWorkerId = -1L ^ (-1L << workerIdBits);

    // 这个是一个意思，就是 5 bit最多只能有31个数字，机房id最多只能是32以内
    private long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
    private long sequenceBits = 12L;

    private long workerIdShift = sequenceBits;
    private long datacenterIdShift = sequenceBits + workerIdBits;
    private long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
    private long sequenceMask = -1L ^ (-1L << sequenceBits);

    private long lastTimestamp = -1L;

    public long getWorkerId() {
        return workerId;
    }

    public long getDatacenterId() {
        return datacenterId;
    }

    public long getTimestamp() {
        return System.currentTimeMillis();
    }

    public synchronized long nextId() {
        // 这儿就是获取当前时间戳，单位是毫秒
        long timestamp = timeGen();

        if (timestamp < lastTimestamp) {
            System.err.printf("clock is moving backwards.  Rejecting requests until %d.", lastTimestamp);
            throw new RuntimeException(String.format(
                    "Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }

        if (lastTimestamp == timestamp) {
            // 这个意思是说一个毫秒内最多只能有4096个数字
            // 无论你传递多少进来，这个位运算保证始终就是在4096这个范围内，避免你自己传递个sequence超过了4096这个范围
            sequence = (sequence + 1) & sequenceMask;
            if (sequence == 0) {
                timestamp = tilNextMillis(lastTimestamp);
            }
        } else {
            sequence = 0;
        }

        // 这儿记录一下最近一次生成id的时间戳，单位是毫秒
        lastTimestamp = timestamp;

        // 这儿就是将时间戳左移，放到 41 bit那儿；
        // 将机房 id左移放到 5 bit那儿；
        // 将机器id左移放到5 bit那儿；将序号放最后12 bit；
        // 最后拼接起来成一个 64 bit的二进制数字，转换成 10 进制就是个 long 型
        return ((timestamp - twepoch) << timestampLeftShift) | (datacenterId << datacenterIdShift)
                | (workerId << workerIdShift) | sequence;
    }

    private long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    private long timeGen() {
        return System.currentTimeMillis();
    }

    // ---------------测试---------------
    public static void main(String[] args) {
        IdWorker worker = new IdWorker(1, 1, 1);
        for (int i = 0; i < 30; i++) {
            System.out.println(worker.nextId());
        }
    }

}

41 bit，就是当前毫秒单位的一个时间戳

然后5 bit是你传递进来的一个机房id（但是最大只能是32以内）

5 bit是你传递进来的机器id（但是最大只能是32以内）

剩下的那个10 bit序列号，就是如果跟你上次生成id的时间还在一个毫秒内，那么会把顺序给你累加，最多在4096个序号以内

存储 负载均衡 算法 java 测试技术 容器 spring java最短路算法 java算法单链表 java无向图最短路算法 java一致性哈希算法 java冒泡排序算法
上一篇: DOM4J -（XML解析包）
下一篇: Java异常类及处理

继续阅读