# 分布式ID

## 参考

[美团技术团队博客参考](https://tech.meituan.com/2017/04/21/mt-leaf.html)

## 分布式ID

在互联网的业务系统中，涉及到各种各样的ID，如在支付系统中就会有支付ID、退款ID等。那一般生成ID都有哪些解决方案呢？特别是在复杂的分布式系统业务场景中，我们应该采用哪种适合自己的解决方案是十分重要的。下面我们一一来列举一下，不一定全部适合，这些解决方案仅供你参考，或许对你有用。

一个ID一般来说有下面几种要素：

* 唯一性：确保生成的ID是全网唯一的。
* 有序递增性：确保生成的ID是对于某个用户或者业务是按一定的数字有序递增的。
* 高可用性：确保任何时候都能正确的生成ID。
* 带时间：ID里面包含时间，一眼扫过去就知道哪天的交易。 系统时间毫秒数

### UUID

优点：

* 简单易用
* 生成取决于网卡MAC地址、时间戳、名字空间（Namespace）、随机或伪随机数、时序等元素。完全随机，不会重复

缺点

* 可读性差
* 不是递增

### 使用单表数据库主键

优点：

* 非常简单，利用现有数据库系统的功能实现，成本小，有DBA专业维护。
* ID号单调自增，可以实现一些对ID有特殊要求的业务。

缺点

* 强依赖DB，当DB异常时整个系统不可用，属于致命问题。配置主从复制可以尽可能的增加可用性，但是数据一致性在特殊情况下难以保证。主从切换时的不一致可能会导致重复发号。
* ID发号性能瓶颈限制在单台MySQL的读写性能。

### Twitter的snowflake算法

41位的时间序列，精确到毫秒，可以使用69年 10位的机器标识，最多支持部署1024个节点 12位的序列号，支持每个节点每毫秒产生4096个ID序号，最高位是符号位始终为0。 这种方案性能好，在单机上是递增的，但是由于涉及到分布式环境，每台机器上的时钟不可能完全同步，也许有时候也会出现不是全局递增的情况。

而且这个项目在2010就停止维护了，但这个设计思路还是应用于其他各个ID生成器及变种。

优点：

* 毫秒数在高位，自增序列在低位，整个ID都是趋势递增的。
* 不依赖数据库等第三方系统，以服务的方式部署，稳定性更高，生成ID的性能也是非常高的。
* 可以根据自身业务特性分配bit位，非常灵活。

缺点：

* 强依赖机器时钟，如果机器上时钟回拨，会导致发号重复或者服务会处于不可用状态。

### 美团的leaf算法

[leaf算法链接](https://tech.meituan.com/2017/04/21/mt-leaf.html)

#### Leaf-Segment

第一种Leaf-segment方案，在使用数据库的方案上，做了如下改变： - 原方案每次获取ID都得读写一次数据库，造成数据库压力大。改为利用proxy server批量获取，每次获取一个segment(step决定大小)号段的值。用完之后再去数据库获取新的号段，可以大大的减轻数据库的压力。 - 各个业务不同的发号需求用biz\_tag字段来区分，每个biz-tag的ID获取相互隔离，互不影响。如果以后有性能需求需要对数据库扩容，不需要上述描述的复杂的扩容操作，只需要对biz\_tag分库分表就行。

数据库表设计如下：

```
+-------------+--------------+------+-----+-------------------+-----------------------------+
| Field       | Type         | Null | Key | Default           | Extra                       |
+-------------+--------------+------+-----+-------------------+-----------------------------+
| biz_tag     | varchar(128) | NO   | PRI |                   |                             |
| max_id      | bigint(20)   | NO   |     | 1                 |                             |
| step        | int(11)      | NO   |     | NULL              |                             |
| desc        | varchar(256) | YES  |     | NULL              |                             |
| update_time | timestamp    | NO   |     | CURRENT_TIMESTAMP | on update CURRENT_TIMESTAMP |
+-------------+--------------+------+-----+-------------------+-----------------------------+
```

优点：

* Leaf服务可以很方便的线性扩展，性能完全能够支撑大多数业务场景。
* ID号码是趋势递增的8byte的64位数字，满足上述数据库存储的主键要求。
* 容灾性高：Leaf服务内部有号段缓存，即使DB宕机，短时间内Leaf仍能正常对外提供服务。
* 可以自定义max\_id的大小，非常方便业务从原有的ID方式上迁移过来。

缺点：

* ID号码不够随机，能够泄露发号数量的信息，不太安全。
* TP999数据波动大，当号段使用完之后还是会hang在更新数据库的I/O上，tg999数据会出现偶尔的尖刺。
* DB宕机会造成整个系统不可用。

**双buffer优化**

* 采用双buffer的方式，Leaf服务内部有两个号段缓存区segment。当前号段已下发10%时，如果下一个号段未更新，则另启一个更新线程去更新下一个号段。当前号段全部下发完后，如果下个号段准备好了则切换到下个号段为当前segment接着下发，循环往复。
* 每个biz-tag都有消费速度监控，通常推荐segment长度设置为服务高峰期发号QPS的600倍（10分钟），这样即使DB宕机，Leaf仍能持续发号10-20分钟不受影响。
* 每次请求来临时都会判断下个号段的状态，从而更新此号段，所以偶尔的网络抖动不会影响下个号段的更新。

#### Leaf-snowflake