分布式id生成策略

 1、背景   

    在我们的日常业务中，常常需要一些唯一id，用来标识一个数据。例如：消息Id，文件Id，人员Id等。不同的业务场景需要的id的特性也不尽相同。so,一个优秀的业务系统在不同的场景下应该选择合适的分布式id生成策略。

2、分布式Id的特性

    （1）、全局唯一

不能出现重复的ID号，既然是唯一标识，这是最基本的要求

    （2）、递增

    递增又分为两种场景：单调递增和趋势递增；递增特性能够维护数据的新旧特性。同时对于排序等需求支持比较友好。其次，大多数场景下，业务数据的存储会对id建立唯一索引的，自增的数据对索引数据的添加性能更加高效（例如：大多数互联网公司使用的数据库是MySQL，存储引擎为innoDB，对于BTree索引来讲，数据以自增顺序来写入的话，b+tree的结构不会时常被打乱重塑，存取效率是最高的，在主键的选择上面我们应该尽量使用有序的主键保证写入性能）。

    （3）、信息安全

     由于数据是递增的，所以，恶意用户的可以根据当前ID推测出下一个，非常危险，所以，我们的分布式ID尽量做到不易被破解。如果ID是连续的，恶意用户的扒取工作就非常容易做了，直接按照顺序下载指定URL即可；如果是订单号就更危险了，竞对可以直接知道我们一天的单量。所以在一些应用场景下，会需要ID无规则、不规则。

 显然，特性2与特性3是互斥的，在特定的场景下需要权衡选择特性

3、分布式id生成方案对比

    我把生成方案分成了三大类：1、单调递增型id, 2、趋势递增型id,3、仅保持唯一的id。

（1）、单调递增型id

    对某些业务场景对id的要求保证下一个ID一定大于上一个ID，例如事务版本号、IM增量消息、排序等特殊需求，这一类业务场景就要求使用单调递增了。单调递增型id主要有两种方案：

    使用数据库的id自增策略，如 MySQL 的 auto_increment。并且可以使用两台数据库分别设置不同步长，生成不重复ID的策略来实现高可用

• 优点：数据库生成的ID绝对有序，高可用实现方式简单

• 缺点：需要独立部署数据库实例，成本高，有性能瓶颈  

    使用Redis, Redis的所有命令操作都是单线程的，本身提供像 incr 和 increby 这样的自增原子命令，所以能保证生成的 ID 肯定是唯一有序的

• 优点：不依赖于数据库，灵活方便，且性能优于数据库；数字ID天然排序，对分页或者需要排序的结果很有帮助。

• 如果系统中没有Redis，还需要引入新的组件，增加系统复杂度；需要编码和配置的工作量比较大。

   同时为防止机器宕机造成的id回退，数据的持久化也需要考虑

（2）、单调趋势递增

        这一类模式id的生成效率很高，能够适应高并发下的id生成。同时id是趋势递增的，安全性比较有保证，所以像订单id,优惠券等瞬时高并发的业务场景会采用这一类id生成算法。基于单调趋势递增的id生成策略主要有两种方案：基于数据库的号段模式，基于雪花算法（snowflake）模式.

      号段模式可以理解为从数据库批量的获取自增ID，每次从数据库取出一个号段范围，例如 (1,1000] 代表1000个ID，具体的业务服务将本号段，生成1~1000的自增ID并加载到内存。表结构如下：

CREATE TABLE id_generator (  id int(10) NOT NULL,  max_id bigint(20) NOT NULL COMMENT '当前最大id',  step int(20) NOT NULL COMMENT '号段的布长',  biz_type  int(20) NOT NULL COMMENT '业务类型',  version int(20) NOT NULL COMMENT '版本号',  PRIMARY KEY (`id`))

     等这批号段ID用完，再次向数据库申请新号段，对max_id字段做一次update操作，update max_id= max_id + step，update成功则说明新号段获取成功，新的号段范围是(max_id ,max_id +step]

update id_generator   set max_id = #{max_id+step}, version = version + 1   where version = # {version} and biz_type = XXX

    由于存在多实例并发的场景，所以使用version的乐观锁维持幂等性。这种id生成策略对数据库的访问压力比较小，同时使用多副本能良好的适应宕机的问题。

    雪花算法（Snowflake）是twitter公司内部分布式项目采用的ID生成算法，开源后广受国内大厂的好评，在该算法影响下各大公司相继开发出各具特色的分布式生成器。本文也重点介绍一下这个算法

    snowflake生成的是int64的整型数据，分别由四部分组成

• 第一个bit位（1bit）：Java中long的最高位是符号位代表正负，正数是0，负数是1，一般生成ID都为正数，所以默认为0。

• 时间戳部分（41bit）：毫秒级的时间，不建议存当前时间戳，而是用（当前时间戳 - 固定开始时间戳）的差值，可以使产生的ID从更小的值开始；41位的时间戳可以使用69年，(1L << 41) / (1000L * 60 * 60 * 24 * 365) = 69年

• 工作机器id（10bit）：也被叫做workId，这个可以灵活配置，机房或者机器号组合都可以。

• 序列号部分（12bit），自增值支持同一毫秒内同一个节点可以生成4096个ID

  
  

     通过提前规划好workId可以实现该算法，但目前的分布式生产环境，借用了多种云计算、容器化技术，实例的个数随时会变化，还需要处理服务器时钟回退的问题，固定规划ID然后通过配置来使用snowflake的场景可行性不高，一般是自动启停，增减机器，这样就需要对snowflake进行一些改造才能更好地应用到生产环境中。mongodb 中的objectId的生成算法和Sony公司的sonyflake 是基于雪花算法改造的两个比较经典的算法

      sonyflake是Sony公司的一个开源项目，基本思路和snowflake差不多，不过位分配上稍有不同，如下图

      这里的时间只用了39个bit，但时间的单位变成了10ms，所以理论上比41位表示的时间还要久(174年)。

  Sequence ID和之前的定义一致，Machine ID其实就是节点id。sonyflake与众不同的地方在于其在启动阶段的配置参数：

func NewSonyflake(st Settings) *Sonyflake

Settings数据结构如下：

type Settings struct {    StartTime      time.Time    MachineID      func() (uint16, error)    CheckMachineID func(uint16) bool}

  StartTime选项是设置起始时间，如果不设置的话，默认是从2014-09-01 00:00:00 +0000 UTC开始。

  MachineID可以由用户自定义的函数，如果用户不定义的话，会默认将本机IP的低16位作为machine id。

  CheckMachineID是由用户提供的检查MachineID是否冲突的函数

使用起来比较简单：

func main() {    t, _ := time.Parse("2006-01-02", "2018-01-01")    settings := sonyflake.Settings{        StartTime:      t,        MachineID:      getMachineID,        CheckMachineID: checkMachineID,    }
    sf := sonyflake.NewSonyflake(settings)    id, err := sf.NextID()    if err != nil {        fmt.Println(err)        os.Exit(1)    }
    fmt.Println(id)}

    mongodb的objectid是生成的一个字节数组，使用时将字节数组进行hex编码，所以最终的id是一个string型的，这一点与snowflake是不同的。objectId也由四部分组成：1、4 bytes的时间戳；2、3 bytes hostName的md5值；3、2 bytes的进程id;  4、自增部分的数值

// NewObjectId returns a new unique ObjectId.func NewObjectId() ObjectId {  var b [12]byte  // Timestamp, 4 bytes, big endian  binary.BigEndian.PutUint32(b[:], uint32(time.Now().Unix()))  // Machine, first 3 bytes of md5(hostname)  b[4] = machineId[0]  b[5] = machineId[1]  b[6] = machineId[2]  // Pid, 2 bytes, specs don't specify endianness, but we use big endian.  b[7] = byte(processId >> 8)  b[8] = byte(processId)  // Increment, 3 bytes, big endian  i := atomic.AddUint32(&objectIdCounter, 1)  b[9] = byte(i >> 16)  b[10] = byte(i >> 8)  b[11] = byte(i)  return ObjectId(b[:])}

    其中machineId默认是有机器的hostName进行md5运算出来的，如果机器没有配置使用时间戳代替，代码如下：

func readMachineId() []byte {  var sum [3]byte  id := sum[:]  hostname, err1 := os.Hostname()  if err1 != nil {    n := uint32(time.Now().UnixNano())    sum[0] = byte(n >> 0)    sum[1] = byte(n >> 8)    sum[2] = byte(n >> 16)    return id  }  hw := md5.New()  hw.Write([]byte(hostname))  copy(id, hw.Sum(nil))  return id}

    采用进程id 可以很好的避免一个机器上多容器部署时id冲突的问题，加上操作系统对pid的销毁和创建策略，容器重启后分配的pid前后时不相同的，所以重启后的id也是不会重复的

    objectId在自增数据上也采取了其实数据随机的策略，提高了id的抗碰撞性，代码如下：

var objectIdCounter uint32 = readRandomUint32()
// readRandomUint32 returns a random objectIdCounter.func readRandomUint32() uint32 {  // We've found systems hanging in this function due to lack of entropy.  // The randomness of these bytes is just preventing nearby clashes, so  // just look at the time.  return uint32(time.Now().UnixNano())}

（3）、仅保持唯一的id。

    UUID是通用唯一识别码（Universally Unique Identifier)的缩写，开放软件基金会(OSF)规范定义了包括网卡MAC地址、时间戳、名字空间（Namespace）、随机或伪随机数、时序等元素。利用这些元素来生成UUID。

• 优点：本地生成，生成简单，性能好，没有高可用风险

• 缺点：长度过长，存储冗余，且无序不可读，查询效率低

uuid适用场景：客户端请求链路追踪reqId（每次请求服务端，使用uuid为请求设置一个唯一标识），