高QPS的基于snowflake优化的分布式唯一有序id生成器介绍



# 0. 为什么要用我们的id生成器

WE ALL KNOW,任何一个系统和应用的开发都避免不了id生成的需求,主键id、业务id、实体id……

WE ALSO KNOW,id的生成需求在一个应用的初期开发中往往不受关注,因为实现太过简单:

  • 单机应用有本地数据库帮助自动生成id
  • 分布式应用有分布式数据库如公司内部的TDDL帮助自动生成id
  • 如果你的数据不存储在数据库而是存在hbase或redis里面,没办法用数据库的自动生成主键,那还有TDDL sequence服务提供分布式id的生成要求,如果只要求id唯一,还可以用uuid生成

这么看来,id的生成需求貌似不值得大费周章的讨论,如果你这样想,那只能说明你的系统或应用太简单,既没有很高的qps也没有很强的设计,因此对id生成的要求不高,那么一个高要求的分布式id生成一般是什么样的,我想至少满足以下几个条件:

  • 全局唯一性,这是基本要求
  • 数字存储,节省空间,易于管理
  • 按时间有序,至少精确到ms
  • 无中心生成,因为中心生成会涉及到锁,性能低下且有单点故障(主备也难以避免这种风险)
  • 满足高并发高性能,比如id生成rt小于1ms,能支撑100w QPS的并发

这时候,仍有人站出来说,TDDL sequence能满足需求吧,那我要问你两个问题了:

一. tddl sequence是依赖数据库的,如果你的应用压根就没用到DB,你的数据都是存在hbase或Cassandra里,或直接存在tair里的,你会只为了生成序列id而单独部署个DB吗?代价和成本是不是太大了?应该没人干这种事吧?

二. 既然tddl sequence是依赖数据库的,就避免不了db的并发限制,每次一压测,active 10, maxActive 10, runningSqlCount 10这种数据库连接数不够的exception相信大部分人都遇到过,当然tddl sequence没有这么弱,它做了很多优化,有了步长的概念,可以一次预订几千或几万个id放在内存里慢慢取,极大的提高了效率和性能,可是在实际使用过程中还是有一堆问题,基本上都是历史遗留问题,也就是tddl sequence本来可以设计的更加出色,但由于种种原因有些地方没设计好,现在又难以改动,比如我遇到的问题有以下几个:

(1)乐观锁导致高并发不能生成id

首先我们压测时如果压到较高,比如1w qps以上时,sequence服务就会报这样的错:

[TDDL-4400][ERR_SEQUENCE] Sequence : All dataSource faild to get value

原因是tddl sequence服务实现中采用了乐观锁,乐观锁在高并发下容易失败,这是历史遗留问题,目前的解决方案是将步长调大,比如调成2w,可以大大降低上面错误出现的几率

(2)调整步长有id重复的风险

但调整步长又遇到了另外一个坑,上线之前调整没问题,上线之后调整步长就有可能出现id重复的问题。这个就要从tddl sequence那容易让人误解的id生成策略说起了。

很多人理解的都是向前预订id值,比如一开始步长是1000,初始值为0,如果一台机器把seq表改成2000,我们理解的是这台机器正在使用1000 ~ 2000之间的序列值,用完了再改seq表,但实际上我们理解反了,tddl sequence是向后预订的,一台机器把seq表改成1000,实际上代表他预定了1000-2000的值,然后另一台机器把seq表改成2000,代表他预订了2000-3000的值,即用完了预订的这段序列值后才会修改seq表,而不是先改seq表我再慢慢用,这样的原理正常情况下是没问题的,但是一旦遇到需要修改步长的情况下就有坑了,发布是需要时间的,不同机器间并不是同时发布好,比如把步长改成2w,这时候发布好了的机器会把seq表改成2w2,代表他预订了2w2-4w2,然后没发布好的步长仍是1000的那个机器又把2w2改成2w3,代表他预订了2w3-2w4的数据,这样就明显冲突了,这也是历史遗留问题之一。

这告诉我们已经上线的seq服务不要轻易改步长,你没法保证线上每台机器同时按照2w取,会存在一段时间,部分机器在用1000的步长,部分机器在用2w的步长,不过如果接受短时间内冲突或停机是可以调步长的,找个低峰期发布,冲突的概率会大大降低。

(3)多个seq服务需要手动修改默认配置

最后再说tddl sequence的一个小坑,就是我在需要使用seq生成点赞id时,我没有重新建seq表而是直接在现有的seq表里添加了一个条目表示点赞id的生成value,在使用时报错如下:Sequence : TMALL_FUN_GROUP:seq_like的值得错误,覆盖到其他范围段了!请修改数据库,或者开启adjust开关!,经咨询发现这是另外一个历史遗留问题,sequence是分多个库,每个库分段,该错误表示一个seq在不同分库里的分段值冲突了,需要手动配置adjust为true即可,如果再给一次机会,adjust默认就是true了,而不需要每次都手动配置。

综上所述,如果你的应用已经依赖DB(这里指的是线性数据库),而且并发要求没有那么高,那么可以愉快的使用tddl sequence。如果你的系统数据增长较快,预计在未来的某一天会因为db撑不住而转向其它非db的方案(一般一个表数据超过1000万就可以考虑其它方案或分库分表了),或者预计在某些时刻比如双11有超过10w以上的并发要求,那么建议你使用我们的id生成器:fun idGenerator。


# 1. fun idGenerator的特性和接入方式


1.1 特性

fun idGenerator能满足上面提到的所有需求:

  • 全局唯一性
  • 64位Long类型数字存储
  • 按时间趋势递增,能精确到ms
  • 无中心生成,不存在单点故障
  • 满足高并发高性能
  • 高性能指的是id生成效率高,鹰眼上rt <= 0.02ms,批量一次性生成1000个id的rt大概为1~2ms
  • 实际通过PAP平台压测表明单机至少能达到5w qps,由于PAP本身压测极限是16w,分布式压测在PAP下只能压到16w,此时系统毫无压力,为:cpu 7%,load 0.4,从单机至少5w qps,线上一共63台机器进行预估来看,实际qps极限预计能达到100w
  • 使用简单,不依赖于任何其它三方或二方库或平台,迁移方便

除了上面这些基本的特性外,我们的id生成器还提供一些额外的能力:

  • id可带业务属性,通过一个id你可以知道这个id的生成时间、这个id是哪个模块或实体的id(比如是点赞id还是评论id)
  • 可按需动态定制业务能力,在系统允许的情况下可以通过配置定制id在1ms内可以达到的最高并发能力

据说,有追求的应用或系统都会选择我们高QPS高效率的id生成器~


1.2 接入方式

我们提供hsf服务的接入方式,简单快速,当然也提供批量id生成接口,提高效率

接入申请:请联系@竹敏 或 @扶澈


maven依赖

<dependency>
    <groupId>com.tmall.wireless</groupId>
    <artifactId>fun-client</artifactId>
    <version>1.1-SNAPSHOT</version>
</dependency>

Copy


spring配置文件

<!-- 说明:${fun.service.version}日常下为1.0.0.daily,预发和线上为1.0.0 -->
<bean id="funIdGeneratorService" class="com.taobao.hsf.app.spring.util.HSFSpringConsumerBean" init-method="init"> 
    <property name="interfaceName" value="com.tmall.wireless.fun.client.interfaces.FunIdGeneratorService"/>
    <property name="version" value="${fun.service.version}" />
</bean>

<!-- id生成器定制参数配置,可选,一般业务都无需配置,且配置后不可更改,请慎重 -->
<bean id="idGeneratorParam" class="com.tmall.wireless.fun.client.domain.generator.IdGeneratorParam" >
    <property name="timeBaseLine" value="1481196979000"/> <!-- 不能比当前时间大,可选配置 -->
    <!-- 下面三个位数参数总和必须为13,有最小值限制,若配置必须2个一起配置 -->
    <property name="businessIdBits" value="2"/>  <!-- 取值范围[0, 5],默认为3 -->
    <property name="sequenceBits" value="10"/>   <!-- 取值范围[8, 13],默认为10 -->
</bean>

Copy

配置参数说明(无超高并发需求不建议配置)

(1)timeBaseLine参数提供无限期使用能力,一般无需配置

id生成器目前默认参数配置可以使用好几百年,虽远远足够但这表示仍有使用期限的限制(几百年后咋办?呵呵,想的不是一般多),因此提供timeBaseLine参数的配置,该参数设置的值越大(但不能大于当前时间戳),理论上能使用的期限就越多,可以无限期使用下去

该参数一般无需配置,如果非要配,建议选择业务上线的时间,比如我的业务近期接入了id生成器并预估2016.12.30号上线,那么在上线之前可以将timeBaseLine配置成2016.12.30转换为毫秒的13位时间戳值,即1483027200000

(2)businessIdBits参数提供同一应用不同业务的区分能力

如果你一个系统内有多个业务都要接入id生成器,而且还希望各个id有区分的能力或者说多个业务之间的id需要独立不能重复,那么考虑配置这个参数,在生成id方法时入参加上业务识别码

默认值为3,说明一个系统内可以区分8个业务,对一般系统来说都完全足够,你可以调小或者设置为0,好把位数让给下面并发位数

(3)sequenceBits参数提供1毫秒内并发能力

默认值为10,表示1ms内最高并发为1024,即1s并发1024000,一般系统都远远达不到这个极限值,因此只有当系统并发量非常大才建议配置这个参数,比如设置成11、12、13等,建议调高不要调低


一个使用示例

public class IdGeneratorSimpleTest {

    @Resource
    public FunIdGeneratorService funIdGeneratorService; 

    private static final Logger logger = LoggerFactory.getLogger(IdGeneratorSimpleTest.class);

    public void testNextId() {
        // 你的业务代码
        try {
            long id = funIdGeneratorService.nextId();
            // 如果需要区分不同业务可加入业务区分码入参
//          long id = funIdGeneratorService.nextId(1); 
                // 批量id生成,一次批量有最大数控制
//          List<Long> ids = funIdGeneratorService.batchNextId(20); 
        } catch (FunException e) {
            logger.error("funIdGeneratorService.nextId exception, cause: ", e);;
        }
        // 你的业务代码
    }

}

Copy


四个id生成方法,可按需选择

        /**
     * 生成唯一id
     * 
     * @return
     * @throws FunException
     */
    long nextId() throws FunException;

    /**
     * 生成唯一id,可根据businessId来区分要求相互独立、互不重复的不同业务id生成
     * 
     * @param businessId
     * @return
     * @throws FunException
     */
    long nextId(int businessId) throws FunException;

    /**
     * 生成唯一id,可根据generatorParam来配置生成器参数
     * 
     * @return
     * @throws FunException
     */
    long nextId(IdGeneratorParam generatorParam) throws FunException;

    /**
     * 生成唯一id
     * 可根据businessId来区分要求相互独立、互不重复的不同业务id生成
     * 可根据generatorParam来配置生成器参数
     * 
     * @param businessId
     * @return
     * @throws FunException
     */
    long nextId(int businessId, IdGeneratorParam generatorParam) throws FunException;

    /**
     * 批量id生成
     *
     * @param size
     * @return
     * @throws FunException
     */
    List<Long> batchNextIds(int size) throws FunException;

Copy


高级使用示例(无超高并发需求不建议使用)

public class IdGeneratorTest {

    @Resource
    public FunIdGeneratorService funIdGeneratorService; 

    @Resource
    public IdGeneratorParam idGeneratorParam;

    private static final Logger logger = LoggerFactory.getLogger(IdGeneratorTest.class);

    public void testNextId() {
        // 你的业务代码
        try {
            long id = funIdGeneratorService.nextId(idGeneratorParam);
//          long id = funIdGeneratorService.nextId(1, idGeneratorParam);
        } catch (FunException e) {
            logger.error("funIdGeneratorService.nextId exception, cause: ", e);;
        }
        // 你的业务代码
    }

}

Copy


# 2. fun idGenerator的原理

我们id的生成算法借鉴了Twitter的Snowflake雪花算法,Snowflake是由64位Long类型数据分成3组生成:1bit(不用)+41bit毫秒级时间戳+10bit工作机器id+12位序列号,生成算法很简单,给我们带来了一些启发,让我们知道id生成可以考虑的元素如下:


1. 时间戳元素,选取秒数或毫秒数,可以是时间全量值也可以是增量值(比如从上线2016.11后的差值)

时间戳元素是为了满足按时间有序,这里考虑粒度控制,是只需在秒级别上保持有序即可,还是需要在毫秒级别上保持有序,或者必须全部有序(最小粒度)。如果选择只需在秒的级别上保证顺序,即意味着后一秒的ID肯定比前一秒的大,但同一秒内可能后取的ID比前面的ID小。考虑到峰值速度,秒的粒度比毫秒的粒度限制更小。时间增量还是全量主要考虑空间限制和简便性,增量的位数更少且能表示更多的年份,比如42位时间戳全量能表示到2109年,如果是从2016.11.11开始的增量能表示到2156年,鉴于增量的优势我们选择增量毫秒时间戳

风险是同一毫秒不同服务器生成的id可能存在前后顺序错乱的情况,由于控制在毫秒级别,这种短暂的不一致性系统可以接受


2. 机器本身标识符

分布式环境下,如果用一台中心服务器来生成id容易造成单点热点问题,因此需要每台服务器独立部署id生成器并本地生成,不同服务器的id生成器根据机器标识区分,机器标识可以选择ip地址、mac地址甚至进程id等

我们选择ipv4地址来做区分,可将ip地址转成Long类型并选择其中的某几位作为标识符


3. 业务或服务区分

我们的id生成器并不只服务于一个业务,可能多个业务或服务都需要用到,比如点赞和评论都要用,或者其它系统或应用的业务也可以接入进来使用,这就需要id能对业务线做区分

虽然有些场景下不同的业务生成的id可以相互重复,比如评论id和点赞id可以是一样的,但是也有需要生成相互独立不能重复的多个业务id,这里考虑通用性设计,需要区分业务或服务。另一方面,这样也方便id管理,看到一个id就知道是来自哪个业务


4. 业务本身信息,比如userId、点赞次数这样的业务绑定信息

id里将一些重要的业务信息进行编码解码,在某些场景下可以极大的提高性能,不过我们的id生成器需要设计成通用的独立的组件甚至微服务,不能自带与业务强耦合的信息,因此这点我们不会考虑


5. 自增序列号计数器

不管是秒级别还是毫秒级别甚至微妙级别,一个id肯定满足不了需求(高并发下1ws也可能有多个id生成的需求),因此需要*秒级别下的递增序列号

8位毫秒内的序列号表示单机下1ms可以同时并发生成256个id,如果有N台服务器,意味着1s内可以并发生成256000 * N个id,可以满足大部分业务场景

在跨毫秒时,序列号通常会选择归0,从0开始递增,这样在低qps的情况下会生成很多序列号为0的ID,导致最终生成的ID分布后不均匀,这样以后需要根据id取模分表时就会出现问题。解决方法是,序列号不要每次都归0,而是归一个0到9的随机数

综上所述,最终确定的id生成算法如下图所示:

分布式唯一id生成策略

这样参考twitter的snowflake算法设计的64位分布式id生成器,可以保证:

  • 全局唯一,将毫秒数放在最高位,保证生成的id是趋势递增
  • 同一机器生成的id绝对递增有序
  • 不同业务线生成的id相互独立、互不重复


问题解惑

id整体顺序保障依赖的是最高位的毫秒数,如果各个服务器时间不同步,这个快一毫秒,那个慢一毫秒,不就不能保证不同毫秒间一定有序了吗?

解答:对,如果服务器时间不同步,就只能保证各自服务器生成id有序,无法保证不同毫秒间的有序性,因此服务器时间校准是必须做的,幸运的是,阿里内部服务器都已经通过NTP服务做了时间校准,不仅仅能保障毫秒级别的一致性,所以无需担心这个问题


# 3. fun idGenerator使用注意事项

  1. 我们生成的id只能保证毫秒级别的有序,也就是说同一毫秒在不同机器上生成的id可能是无序的,如果你不能接受这一点就不要使用

  2. 我们生成的id最终位数有点长,根据配置的不同生成的最终id位数不同,可能为15位、16位或17位,这本身没有任何问题,但却有一个客户端使用上的坑:
  3. js库里的json解析超过16位的数字类型会溢出从而丢失精度,具体可见:here,这是因为js库最多只能处理53位的long类型数据(js的坑),因此建议在前端和Android客户端(iOS的json解析没有此bug)使用id时务必使用string类型进行处理(跟服务端无关,服务端仍使用long类型处理数据),否则就存在风险


# 4. 参考资料


评论区
Rick ©2018