分布式统一id生成器snowflake介绍
小橘子🍊
  2019-07-17 14:56:34 2019-07-17 14:56      

前言

项目地址
好久没有写技术博客了，实在是因为自己比较忙，花了将近两个月的时间完成了两个开源小项目，这篇文章要介绍的就是其中一个，我将它的名字叫做 snowflake，是一个分布式的统一 id 生成器，能够生成 segment 和 snowflake 两种类型的 id。另外一个就是一个类似于 dubbo 的 rpc 框架 beehive，在我的 snowflake 项目中提供了内嵌模式的测试程序，它所使用的 rpc 框架就是我自己开发的 beehive，关于 beehive 我准备在我后边的文章中再作介绍，本篇就先详细介绍一下 snowflake 这个 id 生成器。

基本介绍

snowflake 是一款分布式的统一 ID 生成器，提供了两种 id 生成的方式，分段 id 和通过 snowflake 算法计算得到 id。在分段 id 的生成过程中，不同的服务器从数据库获取自己专属的 id 号段，再从该号段中来产生唯一 id，在从数据库中获取号段的过程中，通过数据库的事务机制，保证了不同的 id 服务器获取的号段是不重复的，所以能够保证全局的 id 唯一性。而 snowflake 算法计算 id 的方式稍微复杂，首先它并不是通过 id 隔段的方式来保证 id 的唯一性，而是通过各个 id 服务器的 machine id 来保证不同的服务器之间产生的 id 唯一性，此外，在单台 id 服务器之上，machine id 是唯一且不变的，要想产生唯一 id，就还需要其他的项来进行保证，snowflake 算法采用的是加上时间戳的方式，在本项目的实现中，提供了两种时间颗粒度的选择（秒和毫秒），对于计算机世界而言一秒和一毫秒而言，是很漫长的，在这样的时间颗粒度下很有可能会在同一个最小时间单元内生成多个 id，因为时间戳和 machine id 一致，所以在我们生成的 id 中，还需要一个额外的字段来保证在单位时间粒度中生成的 id 的唯一性，这就是序列号。snowflake 算法生成 id 相关的三个字段如上所述，更加详细的 id 模型请看下表：

颗粒度 时间戳 序列号 machine id
秒 占用 31 位 占用 22 位 占用 10 位
毫秒 占用 41 位 占用 12 位 占用 10 位

从上表可以看出来两种颗粒度的 id 占用的长度都是 63 位数，刚好可以使用一个长整型数据来进行存储，剩余一位没有使用，方便以后拓展使用。对于秒颗粒度而言，一年 31536000 秒占用 25 位，时间戳剩余 6 位，也就是说这种方式产生的 id 能用 64 年（非精确计算），而序列号占用 22 位，折算后可以知道理论情况下，一秒内单台 id 服务器最多能生成 4194303 个 id。对于毫秒颗粒度而言，一年 31536000000 毫秒占用 35 位，剩余 6 位，同样可以使用 64 年（非精确计算），由于时间戳长度的增加导致序列号的长度被压缩为 12 位，这样理论情况下，单台 id 服务器一毫秒内最多能产生 4096 个 id。

基本使用

内嵌服务发布模式

内嵌服务发布模式需要使用到 rpc 框架，在 snowflake 中用于产生 id 的服务接口为 top.aprilyolies.snowflake.idservice.IdService，可以看到它的实现类有两个，SegmentIdService 和 SnowflakeIdService，分别对应两种 id 的生成方式，他们的继承关系如下图：

了解这个以后，我们便知道在 rpc 框架中，需要暴露的服务名称就是这个接口的全限定名。在服务端，除了要暴露服务外，还要指定对应的服务实现，这是我是通过 spring 的 FactoryBean 机制来避免直接构建 IdService 实现类，简单来说我们在使用 rpc 框架指定服务实现类时，不是直接使用的 IdService 实现类，而是通过 FactoryBean 来构建对应的 IdService 实现类，这么说可能有点绕，还是直接看示例程序比较合适，项目的工程结构如下：

内嵌服务发布的实例程序就在 snowflake-demo 模块之下，再次说明这里我使用的是自己开发的 rpc 框架 beehive，如果你使用的是其他类型的 rpc 框架，方式也基本一致。先看服务发布端的 spring 配置文件：

embed-server.xml

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
       xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
       xmlns:beehive="https://www.aprilyolies.top/schema/beehive"
       xsi:schemaLocation="http://www.springframework.org/schema/beans http://www.springframework.org/schema/beans/spring-beans.xsd https://www.aprilyolies.top/schema/beehive https://www.aprilyolies.top/schema/beehive.xsd">

    <bean class="org.springframework.beans.factory.config.PropertyPlaceholderConfigurer">
        <property name="locations" value="classpath:snowflake.properties"/>
    </bean>

    <bean id="serviceFactory" class="top.aprilyolies.snowflake.idservice.IdServiceFactory">
        <property name="machineIdProvider" value="ZOOKEEPER"/>
        <property name="idType" value="1"/>
        <property name="zkHost" value="119.23.247.86"/>
        <property name="dbUrl" value="jdbc:mysql://localhost:3306/snowflake"/>
        <property name="username" value="root"/>
        <property name="password" value="kuaile1.."/>
        <property name="serviceType" value="snowflake"/>
    </bean>

    <beehive:service id="idService" service="top.aprilyolies.snowflake.idservice.IdService"
                     ref="serviceFactory" proxy-factory="jdk" serializer="hessian" server-port="7442"/>

    <beehive:registry id="registry" address="zookeeper://119.23.247.86:2181"/>
</beans>

这里的 <beehive:service/> 标签是 beehive 用于发布服务的，它暴露的服务接口是 top.aprilyolies.snowflake.idservice.IdService 这里和我上边的说明一致。然后就是该服务的实现类指定，可以看到这里是设置的 ref="serviceFactory"，它所对应的就是那个 IdService 工厂类，因为在构建 IdService 实现类时需要指定部分参数信息，所以这里我们还指定了一系列参数，具体的作用如下：

根据生成的 id 的类型不同，参数的指定也不一样，如果你是要生成 segment 类型的 id，那么你只需要指定用于获取 id 段信息的数据库信息即可，也就是这三个。

1
2
3
<property name="dbUrl" value="jdbc:mysql://localhost:3306/snowflake"/>
<property name="username" value="root"/>
<property name="password" value="kuaile1.."/>

需要在对应的数据库中提前创建 id 分段信息表，在项目的 scripts 目录下已提供 SEGMENT_ID_TABLE.sql 文件，内容如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
SET NAMES utf8mb4;
SET FOREIGN_KEY_CHECKS = 0;

DROP TABLE IF EXISTS `SEGMENT_ID_TABLE`;
CREATE TABLE `SEGMENT_ID_TABLE` (
  `business` varchar(40) NOT NULL COMMENT '业务类型',
  `begin` bigint(40) NOT NULL COMMENT '起始ID',
  `end` bigint(40) NOT NULL COMMENT '最大ID',
  PRIMARY KEY (`business`)
) ENGINE=InnoDB DEFAULT CHARSET=latin1;

BEGIN;
INSERT INTO `SEGMENT_ID_TABLE` VALUES ('order', 519349, 524349);
INSERT INTO `SEGMENT_ID_TABLE` VALUES ('payment', 51, 5051);
COMMIT;

SET FOREIGN_KEY_CHECKS = 1;

如果你要获取的是 snowflake 算法生成的 id，那么情况稍微复杂一点点，根据 snowflake id 的构成方式，我们可以知道唯一不能直接确定的就是 machine id，它需要借助于外部的条件来保证唯一性。根据 snowflake machine id 的获取方式不同可以将其配置分为三种。

  • 从数据库中获取 machine id
    1
    2
    3
    4
    5
    <property name="idType" value="1"/>
    <property name="dbUrl" value="jdbc:mysql://localhost:3306/snowflake"/>
    <property name="username" value="root"/>
    <property name="password" value="kuaile1.."/>
    <property name="machineIdProvider" value="MYSQL"/>

从数据库中获取 machine id 需要提前在对应数据库中创建对应的 machine id 映射表，在项目的 scripts 目录下已提供 SNOWFLAKE-MYSQL-MACHINE-ID.sql 文件，内容如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
CREATE DATABASE snowflake;

drop table if exists MYSQL_MACHINE_ID_PROVIDER;

create table MYSQL_MACHINE_ID_PROVIDER
(
    ID bigint not null,
    IP varchar(64) default null,
    primary key (ID),
    unique key UK_IP (IP)
);

drop procedure if exists initMysqlMachineIdProvider;

DELIMITER //
create procedure initMysqlMachineIdProvider()
begin
    declare count int;
    set count = 0;
    set autocommit = false;

    LOOP_LABLE:
        loop
            insert into MYSQL_MACHINE_ID_PROVIDER(ID) values (count);
            set count = count + 1;
            if count >= 1024 then
                leave LOOP_LABLE;
            end if;
        end loop;

    commit;
    set autocommit = true;
end;
//
DELIMITER ;

call initMysqlMachineIdProvider;

  • 从 zookeeper 获取 machine id

    1
    2
    3
    <property name="idType" value="1"/>
    <property name="zkHost" value="119.23.247.86"/>
    <property name="machineIdProvider" value="ZOOKEEPER"/>

  • 从本地配置文件获取 machine id（不建议，需要在 classpath 下创建 snowflake.properties 配置文件并指定 snowflake.machine.id=1023 属性值，它将作为 machine id，在集群环境下，需要保证这个值唯一）

    1
    2
    <property name="idType" value="1"/>
    <property name="machineIdProvider" value="PROPERTY"/>

这里的 idType 就是指的 snowflake 算法生成的 id 的颗粒度（即在怎样的单位时长内，生成的 id 是单调有序的），0 代表在一秒内，生成的 id 是单调有序递增的，而 1 则代表在一毫秒的时间内，生成的 id 是单调有序递增的。

在服务端的配置完成后，剩下的就是直接引用发布的服务了，配置很简单，我这里只是贴出来，不做说明。

embed-client.xml

1
2
3
4
5
6
7
8
9
10
11
<?xml version="1.0" encoding="UTF-8"?>
<beans xmlns="http://www.springframework.org/schema/beans"
       xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
       xmlns:beehive="https://www.aprilyolies.top/schema/beehive"
       xsi:schemaLocation="http://www.springframework.org/schema/beans http://www.springframework.org/schema/beans/spring-beans.xsd https://www.aprilyolies.top/schema/beehive https://www.aprilyolies.top/schema/beehive.xsd">

    <beehive:registry id="registry" address="zookeeper://119.23.247.86:2181"/>

    <beehive:reference id="idService" service="top.aprilyolies.snowflake.idservice.IdService" load-balance="poll"
                       serializer="hessian" read-timeout="1000" retry-times="2"/>
</beans>

在实例程序中，我已经指定了 IdService 类型为 snowflake，且 machine id 的获取方式为 ZOOKEEPER，所以不需要使用到数据库，而且我指定的 zookeeper 地址为我的阿里云地址，正常情况下，我会开启 zookeeper 服务，这样你直接运行 server 端和 client 端程序就能看到结果。

独立运行模式

独立运行模式采用手动直接构建 IdService 的方式，这种方式更加灵活，我们只需要指定几个和 id service 相关的参数，然后就能通过 IdServiceFactory 类来拿到 IdService 实例，至于怎么使用这个 IdService，完全由你决定，就像我在项目中给出的两个 restful 风格的 id 生成方式，一个是通过 Springboot 构建的 web 应用来进行访问，另外一个就是通过 Netty 服务器来提供访问支持。参数的配置方式和内嵌服务发布模式完全一致，只不过是一个配置文件是 xml，一个配置文件是 properties。

就直接那 netty 的实例程序来说明吧，我们根本就是要得到 IdService 的实例，在 IdServiceFactory 类中提供了一个公有静态方法 public static IdService buildIdService(ClassLoader classLoader, String serviceType, String confPath) ，我们可以直接通过该方法来获取 IdService 实例，三个参数需要指定，classloader 类加载器，需要保证这个类加载器能够加载到你的配置文件，serviceType 服务类型，固定为 segment 或者 snowflake，指定其它参数会报错，最后一个就是你的配置文件路径，里边的内容如下：

1
2
3
4
5
6
7
snowflake.machine.id=1023
snowflake.machine.id.provider=ZOOKEEPER
snowflake.id.type=0
snowflake.zookeeper.host=119.23.247.86
snowflake.database.url=jdbc:mysql://localhost:3306/snowflake
snowflake.database.username=root
snowflake.database.password=kuaile1..

跟上边介绍的一样，里边的配置不是非得全写，根据自己的需求指定几条必须的参数即可。该方法的返回值就是 IdService 实例，就像示例程序的 SnowflakeChannelHandler 返回的那样。

1
2
3
4
5
// SnowflakeIdService 实例
private static final IdService snowIdService = IdServiceFactory.buildIdService(SnowflakeChannelHandler.class.getClassLoader(), "snowflake", "snowflake.properties");
// SegmentIdService 实例
private static final IdService segIdService = IdServiceFactory.buildIdService(SnowflakeChannelHandler.class.getClassLoader(), "segment", "snowflake.properties");

测试运行

内嵌服务发布模式测试

因为测试程序依赖了我开发的 beehive rpc 框架，这个在 maven 中央仓库无法直接下载，需要先手动进行安装该依赖，具体方法就是执行如下指令，这样在你的本地 maven 仓库就会存在该依赖了。

1
2
3
git clone https://github.com/AprilYoLies/beehive.git
cd beehive
mvn clean install -Dmaven.test.skip=true

然后启动服务端，执行 nowflake-demo/embed-server 模块下 top.aprilyolies.snowflake.EmbedServer 类的 main 方法，如果启动成功，那么就表示服务已发布。

接着启动客户端，执行 snowflake-demo/embed-client 模块下 top.aprilyolies.snowflake.EmbedClient 类的 main 方法，如果出现如下结果，就表示服务调用成功。

1
2
3
4
5
6
7
8
9
10
14108116920565761
14108116970897409
14108116979286017
14108116983480321
14108116991868929
14108116996063233
14108117004451841
14108117008646145
14108117017034753
14108117021229057

独立运行模式测试

独立运行模式提供了两个 Server 端，随便启动一个就行，以 NettyServer 为例，执行 snowflake-server/snowflake-netty 模块下 top.aprilyolies.snowflake.SnowflakeServer 类的 main 方法，如果启动成功，就会日志打印请求的路径如下：

1
2
3
210 [main] INFO top.aprilyolies.snowflake.SnowflakeServer - Snowflake netty server started on port 6707.
210 [main] INFO top.aprilyolies.snowflake.SnowflakeServer - Get segment id by http://localhost:6707/snowflake/seg/business-name
210 [main] INFO top.aprilyolies.snowflake.SnowflakeServer - Get snowflake id by http://localhost:6707/snowflake/snow

访问两个链接中的任意一条就会得到对应的 id。

TODO-LIST

  • 在通过 snowflake 算法生成 id 时，由于需要通过时间戳来生成 id，这就有可能会因为某一个机器的时间发生回拨，导致这台机器产生出重复的 id，有两种解决办法，一个是在每次生成 id 时，都检查一次当前时间戳是否比上一次生成 id 的时间戳小，如果条件成立，就拒绝 id 生成，这种方式的好处是，在服务不重启的情况下也能检查出这种问题，缺陷是获取当前时间戳和时间比对是一个耗时操作，会导致吞吐量下降。另外一种方式是每隔一小段时间向数据库中写入当前机器生成 id 的时间戳，在服务重启时需要先检查当前时间戳是否比上一次生成 id 的时间戳小，如果成立，则拒绝启动服务，这种做法能够避免服务重启时的时间回拨问题，但是如果服务是在运行中，发生时间回拨，这种方式将会产生错误。

  • 在 segment 方式生成 id 的过程中，代码是使用的硬编码方式将 step 值写死，对于不同的应用场景，可能该步进值并不合适，最好是系统能够根据两次获取 id 段的时间差来自动调整步进值，这样能够动态的缓解 id 段服务数据库的压力。

  • 可以再为系统增加一个可视化管理界面，能够直观的看到不同业务的 id 段使用情况，以及 id 段缓存的使用情况。