美團(tuán)（Leaf）分布式ID生成器，好用的一批！

不了解分布式ID的同學(xué)，先行去看《一口氣說出 9種 分布式ID生成方式，面試官有點(diǎn)懵了》溫習(xí)一下基礎(chǔ)知識(shí)，這里就不再贅述了

Leaf是美團(tuán)推出的一個(gè)分布式ID生成服務(wù)，名字取自德國哲學(xué)家、數(shù)學(xué)家萊布尼茨的一句話：“There are no two identical leaves in the world.”（“世界上沒有兩片相同的樹葉”），取個(gè)名字都這么有寓意，美團(tuán)程序員牛掰?。?/span>

Leaf的優(yōu)勢：高可靠、低延遲、全局唯一等特點(diǎn)。

目前主流的分布式ID生成方式，大致都是基于數(shù)據(jù)庫號(hào)段模式和雪花算法（snowflake），而美團(tuán)（Leaf）剛好同時(shí)兼具了這兩種方式，可以根據(jù)不同業(yè)務(wù)場景靈活切換。

接下來結(jié)合實(shí)戰(zhàn)，詳細(xì)的介紹一下Leaf的Leaf-segment號(hào)段模式和Leaf-snowflake模式

Leaf-segment號(hào)段模式是對(duì)直接用數(shù)據(jù)庫自增ID充當(dāng)分布式ID的一種優(yōu)化，減少對(duì)數(shù)據(jù)庫的頻率操作。相當(dāng)于從數(shù)據(jù)庫批量的獲取自增ID，每次從數(shù)據(jù)庫取出一個(gè)號(hào)段范圍，例如 (1,1000] 代表1000個(gè)ID，業(yè)務(wù)服務(wù)將號(hào)段在本地生成1~1000的自增ID并加載到內(nèi)存.。

大致的流程入下圖所示：

號(hào)段耗盡之后再去數(shù)據(jù)庫獲取新的號(hào)段，可以大大的減輕數(shù)據(jù)庫的壓力。對(duì)max_id字段做一次update操作，update max_id= max_id + step，update成功則說明新號(hào)段獲取成功，新的號(hào)段范圍是(max_id ,max_id +step]。

由于依賴數(shù)據(jù)庫，我們先設(shè)計(jì)一下表結(jié)構(gòu)：

CREATE TABLE `leaf_alloc` (
  `biz_tag` varchar(128) NOT NULL DEFAULT '' COMMENT '業(yè)務(wù)key',
  `max_id` bigint(20) NOT NULL DEFAULT '1' COMMENT '當(dāng)前已經(jīng)分配了的最大id',
  `step` int(11) NOT NULL COMMENT '初始步長，也是動(dòng)態(tài)調(diào)整的最小步長',
  `description` varchar(256) DEFAULT NULL COMMENT '業(yè)務(wù)key的描述',
  `update_time` timestamp NOT NULL DEFAULT CURRENT_TIMESTAMP ON UPDATE CURRENT_TIMESTAMP COMMENT '數(shù)據(jù)庫維護(hù)的更新時(shí)間',
  PRIMARY KEY (`biz_tag`)
) ENGINE=InnoDB DEFAULT CHARSET=utf8;

預(yù)先插入一條測試的業(yè)務(wù)數(shù)據(jù)

INSERT INTO `leaf_alloc` (`biz_tag`, `max_id`, `step`, `description`, `update_time`) VALUES ('leaf-segment-test', '0', '10', '測試', '2020-02-28 10:41:03');

• biz_tag：針對(duì)不同業(yè)務(wù)需求，用biz_tag字段來隔離，如果以后需要擴(kuò)容時(shí)，只需對(duì)biz_tag分庫分表即可

• max_id：當(dāng)前業(yè)務(wù)號(hào)段的最大值，用于計(jì)算下一個(gè)號(hào)段

• step：步長，也就是每次獲取ID的數(shù)量

• description：對(duì)于業(yè)務(wù)的描述，沒啥好說的

將Leaf項(xiàng)目下載到本地：https://github.com/Meituan-Dianping/Leaf

修改一下項(xiàng)目中的leaf.properties文件，添加數(shù)據(jù)庫配置

leaf.name=com.sankuai.leaf.opensource.test
leaf.segment.enable=true
leaf.jdbc.url=jdbc:mysql://127.0.0.1:3306/xin-master?useUnicode=true&characterEncoding=utf8
leaf.jdbc.username=junkang
leaf.jdbc.password=junkang

leaf.snowflake.enable=false

注意：leaf.snowflake.enable 與 leaf.segment.enable 是無法同時(shí)開啟的，否則項(xiàng)目將無法啟動(dòng)。

配置相當(dāng)?shù)暮唵?，直接啟?dòng)LeafServerApplication后就OK了，接下來測試一下，leaf是基于Http請(qǐng)求的發(fā)號(hào)服務(wù)， LeafController 中只有兩個(gè)方法，一個(gè)號(hào)段接口，一個(gè)snowflake接口，key就是數(shù)據(jù)庫中預(yù)先插入的業(yè)務(wù)biz_tag。

@RestController
public class LeafController {
    private Logger logger = LoggerFactory.getLogger(LeafController.class);

    @Autowired
    private SegmentService segmentService;
    @Autowired
    private SnowflakeService snowflakeService;

    /**
     * 號(hào)段模式
     * @param key
     * @return
     */
    @RequestMapping(value = "/api/segment/get/{key}")
    public String getSegmentId(@PathVariable("key") String key) {
        return get(key, segmentService.getId(key));
    }

    /**
     * 雪花算法模式
     * @param key
     * @return
     */
    @RequestMapping(value = "/api/snowflake/get/{key}")
    public String getSnowflakeId(@PathVariable("key") String key) {
        return get(key, snowflakeService.getId(key));
    }

    private String get(@PathVariable("key") String key, Result id) {
        Result result;
        if (key == null || key.isEmpty()) {
            throw new NoKeyException();
        }
        result = id;
        if (result.getStatus().equals(Status.EXCEPTION)) {
            throw new LeafServerException(result.toString());
        }
        return String.valueOf(result.getId());
    }
}

訪問：http://127.0.0.1:8080/api/segment/get/leaf-segment-test，結(jié)果正常返回，感覺沒毛病，但當(dāng)查了一下數(shù)據(jù)庫表中數(shù)據(jù)時(shí)發(fā)現(xiàn)了一個(gè)問題。

通常在用號(hào)段模式的時(shí)候，取號(hào)段的時(shí)機(jī)是在前一個(gè)號(hào)段消耗完的時(shí)候進(jìn)行的，可剛剛才取了一個(gè)ID，數(shù)據(jù)庫中卻已經(jīng)更新了max_id，也就是說leaf已經(jīng)多獲取了一個(gè)號(hào)段，這是什么鬼操作？

Leaf為啥要這么設(shè)計(jì)呢？

Leaf 希望能在DB中取號(hào)段的過程中做到無阻塞！

當(dāng)號(hào)段耗盡時(shí)再去DB中取下一個(gè)號(hào)段，如果此時(shí)網(wǎng)絡(luò)發(fā)生抖動(dòng)，或者DB發(fā)生慢查詢，業(yè)務(wù)系統(tǒng)拿不到號(hào)段，就會(huì)導(dǎo)致整個(gè)系統(tǒng)的響應(yīng)時(shí)間變慢，對(duì)流量巨大的業(yè)務(wù)，這是不可容忍的。

所以Leaf在當(dāng)前號(hào)段消費(fèi)到某個(gè)點(diǎn)時(shí)，就異步的把下一個(gè)號(hào)段加載到內(nèi)存中。而不需要等到號(hào)段用盡的時(shí)候才去更新號(hào)段。這樣做很大程度上的降低了系統(tǒng)的風(fēng)險(xiǎn)。

那么某個(gè)點(diǎn)到底是什么時(shí)候呢？

這里做了一個(gè)實(shí)驗(yàn)，號(hào)段設(shè)置長度為step=10，max_id=1

當(dāng)我拿第一個(gè)ID時(shí)，看到號(hào)段增加了，1/10 

當(dāng)我拿第三個(gè)Id時(shí)，看到號(hào)段又增加了，3/10

Leaf采用雙buffer的方式，它的服務(wù)內(nèi)部有兩個(gè)號(hào)段緩存區(qū)segment。當(dāng)前號(hào)段已消耗10%時(shí)，還沒能拿到下一個(gè)號(hào)段，則會(huì)另啟一個(gè)更新線程去更新下一個(gè)號(hào)段。

簡而言之就是Leaf保證了總是會(huì)多緩存兩個(gè)號(hào)段，即便哪一時(shí)刻數(shù)據(jù)庫掛了，也會(huì)保證發(fā)號(hào)服務(wù)可以正常工作一段時(shí)間。

通常推薦號(hào)段（segment）長度設(shè)置為服務(wù)高峰期發(fā)號(hào)QPS的600倍（10分鐘），這樣即使DB宕機(jī)，Leaf仍能持續(xù)發(fā)號(hào)10-20分鐘不受影響。

優(yōu)點(diǎn)：

• Leaf服務(wù)可以很方便的線性擴(kuò)展，性能完全能夠支撐大多數(shù)業(yè)務(wù)場景。

• 容災(zāi)性高：Leaf服務(wù)內(nèi)部有號(hào)段緩存，即使DB宕機(jī)，短時(shí)間內(nèi)Leaf仍能正常對(duì)外提供服務(wù)。

缺點(diǎn)：

• ID號(hào)碼不夠隨機(jī)，能夠泄露發(fā)號(hào)數(shù)量的信息，不太安全。

• DB宕機(jī)會(huì)造成整個(gè)系統(tǒng)不可用（用到數(shù)據(jù)庫的都有可能）。

  
  

Leaf-snowflake基本上就是沿用了snowflake的設(shè)計(jì)，ID組成結(jié)構(gòu)：正數(shù)位（占1比特）+ 時(shí)間戳（占41比特）+ 機(jī)器ID（占5比特）+ 機(jī)房ID（占5比特）+ 自增值（占12比特），總共64比特組成的一個(gè)Long類型。

Leaf-snowflake不同于原始snowflake算法地方，主要是在workId的生成上，Leaf-snowflake依靠Zookeeper生成workId，也就是上邊的機(jī)器ID（占5比特）+ 機(jī)房ID（占5比特）。Leaf中workId是基于ZooKeeper的順序Id來生成的，每個(gè)應(yīng)用在使用Leaf-snowflake時(shí)，啟動(dòng)時(shí)都會(huì)都在Zookeeper中生成一個(gè)順序Id，相當(dāng)于一臺(tái)機(jī)器對(duì)應(yīng)一個(gè)順序節(jié)點(diǎn)，也就是一個(gè)workId。

Leaf-snowflake啟動(dòng)服務(wù)的過程大致如下：

• 啟動(dòng)Leaf-snowflake服務(wù)，連接Zookeeper，在leaf_forever父節(jié)點(diǎn)下檢查自己是否已經(jīng)注冊過（是否有該順序子節(jié)點(diǎn)）。

• 如果有注冊過直接取回自己的workerID（zk順序節(jié)點(diǎn)生成的int類型ID號(hào)），啟動(dòng)服務(wù)。

• 如果沒有注冊過，就在該父節(jié)點(diǎn)下面創(chuàng)建一個(gè)持久順序節(jié)點(diǎn)，創(chuàng)建成功后取回順序號(hào)當(dāng)做自己的workerID號(hào)，啟動(dòng)服務(wù)。

但Leaf-snowflake對(duì)Zookeeper是一種弱依賴關(guān)系，除了每次會(huì)去ZK拿數(shù)據(jù)以外，也會(huì)在本機(jī)文件系統(tǒng)上緩存一個(gè)workerID文件。一旦ZooKeeper出現(xiàn)問題，恰好機(jī)器出現(xiàn)故障需重啟時(shí)，依然能夠保證服務(wù)正常啟動(dòng)。

啟動(dòng)Leaf-snowflake模式也比較簡單，起動(dòng)本地ZooKeeper，修改一下項(xiàng)目中的leaf.properties文件，關(guān)閉leaf.segment模式，啟用leaf.snowflake模式即可。

leaf.segment.enable=false
#leaf.jdbc.url=jdbc:mysql://127.0.0.1:3306/xin-master?useUnicode=true&characterEncoding=utf8
#leaf.jdbc.username=junkang
#leaf.jdbc.password=junkang

leaf.snowflake.enable=true
leaf.snowflake.zk.address=127.0.0.1
leaf.snowflake.port=2181

    /**
     * 雪花算法模式
     * @param key
     * @return
     */
    @RequestMapping(value = "/api/snowflake/get/{key}")
    public String getSnowflakeId(@PathVariable("key") String key) {
        return get(key, snowflakeService.getId(key));
    }

測試一下，訪問：http://127.0.0.1:8080/api/snowflake/get/leaf-segment-test

優(yōu)點(diǎn)：

• ID號(hào)碼是趨勢遞增的8byte的64位數(shù)字，滿足上述數(shù)據(jù)庫存儲(chǔ)的主鍵要求。

缺點(diǎn)：

• 依賴ZooKeeper，存在服務(wù)不可用風(fēng)險(xiǎn)（實(shí)在不知道有啥缺點(diǎn)了）

  
  

請(qǐng)求地址：http://127.0.0.1:8080/cache

針對(duì)服務(wù)自身的監(jiān)控，Leaf提供了Web層的內(nèi)存數(shù)據(jù)映射界面，可以實(shí)時(shí)看到所有號(hào)段的下發(fā)狀態(tài)。比如每個(gè)號(hào)段雙buffer的使用情況，當(dāng)前ID下發(fā)到了哪個(gè)位置等信息都可以在Web界面上查看。

對(duì)于Leaf具體使用哪種模式，還是根據(jù)具體的業(yè)務(wù)場景使用，本文并沒有對(duì)Leaf源碼做過多的分析，因?yàn)長eaf 代碼量簡潔很好閱讀。后續(xù)還會(huì)把其他幾種分布式ID生成器，依次結(jié)合實(shí)戰(zhàn)介紹給大家，歡迎大家關(guān)注。

特別推薦一個(gè)分享架構(gòu)+算法的優(yōu)質(zhì)內(nèi)容，還沒關(guān)注的小伙伴，可以長按關(guān)注一下：

長按訂閱更多精彩▼
如有收獲，點(diǎn)個(gè)在看，誠摯感謝