事故復(fù)盤：訂單ID被我們搞重復(fù)了！
介紹
在很多業(yè)務(wù)系統(tǒng)中，我們經(jīng)常會(huì)遇到生成全局唯一的分布式ID的需求，如IM系統(tǒng)，訂單系統(tǒng)等。那么生成全局唯一的分布式ID的方法有哪些呢?
UUID
- // 3eece1c6-5b57-4bce-a306-6c49e44a1f90
- UUID.randomUUID().toString()
「本地生成，生成速度快，但識(shí)別性差，沒有順序性」
可以用來標(biāo)識(shí)圖片等，不能用作數(shù)據(jù)庫主鍵
數(shù)據(jù)庫自增主鍵
「我們原來剛開始做IM系統(tǒng)的時(shí)候就單獨(dú)建了一個(gè)表來獲取自增id作為消息的ID」，單獨(dú)開一張表來獲取自增id也不會(huì)影響對消息分庫分表
Zookeeper
「每次要生成一個(gè)新Id時(shí)，創(chuàng)建一個(gè)持久順序節(jié)點(diǎn)，創(chuàng)建操作返回的節(jié)點(diǎn)序號，即為新Id，然后把比自己節(jié)點(diǎn)小的刪除即可」
這種方式能生成的Id比較少，因?yàn)閿?shù)字位數(shù)比較少
Redis
「用incr命令即可實(shí)現(xiàn)」
設(shè)置一個(gè)key為userId，值為0，每次獲取userId的時(shí)候，對userId加1再獲取
- set userId 0
- incr usrId //返回1
每獲取一次id都會(huì)和redis有一個(gè)網(wǎng)絡(luò)交互的過程，因此可以改進(jìn)為如下形式
直接獲取一段userId的最大值，緩存到本地慢慢累加，快到了userId的最大值時(shí)，再去獲取一段，一個(gè)用戶服務(wù)宕機(jī)了，也頂多一小段userId沒有用到
- set userId 0
- incr usrId //返回1
- incrby userId 1000 //返回10001
雪花算法
「雪花算法是最常見的解決方案，滿足全局唯一，趨勢遞增，因此可以用來作為數(shù)據(jù)庫主鍵」
雪花算法是由Twitter公布的分布式主鍵生成算法，它能夠保證不同進(jìn)程主鍵的不重復(fù)性，以及相同進(jìn)程主鍵的有序性。
在同一個(gè)進(jìn)程中，它首先是通過時(shí)間位保證不重復(fù)，如果時(shí)間相同則是通過序列位保證。同時(shí)由于時(shí)間位是單調(diào)遞增的，且各個(gè)服務(wù)器如果大體做了時(shí)間同步，那么生成的主鍵在分布式環(huán)境可以認(rèn)為是總體有序的，這就保證了對索引字段的插入的高效性。例如MySQL的Innodb存儲(chǔ)引擎的主鍵。
使用雪花算法生成的主鍵，二進(jìn)制表示形式包含4部分，從高位到低位分表為：1bit符號位、41bit時(shí)間戳位、10bit工作進(jìn)程位以及12bit序列號位。
「符號位(1bit)」
預(yù)留的符號位，恒為零。
「時(shí)間戳位(41bit)」
41位的時(shí)間戳可以容納的毫秒數(shù)是2的41次冪，一年所使用的毫秒數(shù)是：365 * 24 * 60 * 60 * 1000。通過計(jì)算可知：
- Math.pow(2, 41) / (365 * 24 * 60 * 60 * 1000L);
結(jié)果約等于69.73年。ShardingSphere的雪花算法的時(shí)間紀(jì)元從2016年11月1日零點(diǎn)開始，可以使用到2086年，相信能滿足絕大部分系統(tǒng)的要求。
「工作進(jìn)程位(10bit)」
該標(biāo)志在Java進(jìn)程內(nèi)是唯一的，如果是分布式應(yīng)用部署應(yīng)保證每個(gè)工作進(jìn)程的id是不同的。該值默認(rèn)為0，可通過屬性設(shè)置。
「一般情況這10bit會(huì)拆分為2個(gè)5bit」
前5個(gè)bit代表機(jī)房id，最多代表 2 ^ 5 個(gè)機(jī)房(32 個(gè)機(jī)房) 后5個(gè)bit代表機(jī)器id，每個(gè)機(jī)房里可以代表 2 ^ 5 個(gè)機(jī)器(32 臺(tái)機(jī)器)
「因此這個(gè)服務(wù)最多可以部署在 2^10 臺(tái)機(jī)器上，也就是1024臺(tái)機(jī)器」
「序列號位(12bit)」
該序列是用來在同一個(gè)毫秒內(nèi)生成不同的ID。如果在這個(gè)毫秒內(nèi)生成的數(shù)量超過4096(2的12次冪)，那么生成器會(huì)等待到下個(gè)毫秒繼續(xù)生成。
理解了實(shí)現(xiàn)思路，我們來把算法實(shí)現(xiàn)一遍
- public class SnowFlake {
- /**
- * 起始的時(shí)間戳
- */
- private final static long START_STMP = 1480166465631L;
- /**
- * 每一部分占用的位數(shù)
- */
- private final static long SEQUENCE_BIT = 12; //序列號占用的位數(shù)
- private final static long MACHINE_BIT = 5; //機(jī)器標(biāo)識(shí)占用的位數(shù)
- private final static long DATACENTER_BIT = 5;//數(shù)據(jù)中心占用的位數(shù)
- /**
- * 每一部分的最大值
- */
- private final static long MAX_DATACENTER_NUM = -1L ^ (-1L << DATACENTER_BIT);
- private final static long MAX_MACHINE_NUM = -1L ^ (-1L << MACHINE_BIT);
- private final static long MAX_SEQUENCE = -1L ^ (-1L << SEQUENCE_BIT);
- /**
- * 每一部分向左的位移
- */
- private final static long MACHINE_LEFT = SEQUENCE_BIT;
- private final static long DATACENTER_LEFT = SEQUENCE_BIT + MACHINE_BIT;
- private final static long TIMESTMP_LEFT = DATACENTER_LEFT + DATACENTER_BIT;
- private long datacenterId; //數(shù)據(jù)中心
- private long machineId; //機(jī)器標(biāo)識(shí)
- private long sequence = 0L; //序列號
- private long lastStmp = -1L;//上一次時(shí)間戳
- public SnowFlake(long datacenterId, long machineId) {
- if (datacenterId > MAX_DATACENTER_NUM || datacenterId < 0) {
- throw new IllegalArgumentException("datacenterId can't be greater than MAX_DATACENTER_NUM or less than 0");
- }
- if (machineId > MAX_MACHINE_NUM || machineId < 0) {
- throw new IllegalArgumentException("machineId can't be greater than MAX_MACHINE_NUM or less than 0");
- }
- this.datacenterId = datacenterId;
- this.machineId = machineId;
- }
- /**
- * 產(chǎn)生下一個(gè)ID
- *
- * @return
- */
- public synchronized long nextId() {
- long currStmp = getNewstmp();
- // 發(fā)生時(shí)鐘回?fù)?nbsp;
- if (currStmp < lastStmp) {
- throw new RuntimeException("Clock moved backwards. Refusing to generate id");
- }
- if (currStmp == lastStmp) {
- //相同毫秒內(nèi)，序列號自增
- sequence = (sequence + 1) & MAX_SEQUENCE;
- //同一毫秒的序列數(shù)已經(jīng)達(dá)到最大
- if (sequence == 0L) {
- currStmp = getNextMill();
- }
- } else {
- //不同毫秒內(nèi)，序列號置為0
- sequence = 0L;
- }
- lastStmp = currStmp;
- return (currStmp - START_STMP) << TIMESTMP_LEFT //時(shí)間戳部分
- | datacenterId << DATACENTER_LEFT //數(shù)據(jù)中心部分
- | machineId << MACHINE_LEFT //機(jī)器標(biāo)識(shí)部分
- | sequence; //序列號部分
- }
- private long getNextMill() {
- long mill = getNewstmp();
- while (mill <= lastStmp) {
- mill = getNewstmp();
- }
- return mill;
- }
- private long getNewstmp() {
- return System.currentTimeMillis();
- }
- public static void main(String[] args) {
- SnowFlake snowFlake = new SnowFlake(2, 3);
- for (int i = 0; i < (1 << 12); i++) {
- System.out.println(snowFlake.nextId());
- }
- }
- }
「這端代碼將workerid分為datacenterId和machineId，如果我們業(yè)務(wù)上不需要做區(qū)分的話，直接使用10位的workerid即可。」
workerid生成
我們可以通過zookeeper的有序節(jié)點(diǎn)保證id的全局唯一性，比如我通過以下命令創(chuàng)建一個(gè)永久有序節(jié)點(diǎn)
- # 創(chuàng)建一個(gè)根節(jié)點(diǎn)
- create /test ''
- # 創(chuàng)建永久有序節(jié)點(diǎn)
- create -s /test/ip-port- ''
- # 返回 Created /test/ip-port-0000000000
「ip和port可以為應(yīng)用的ip和port，規(guī)則你來定，別重復(fù)就行」
其中/test/ip-port-0000000000中的0000000000就是我們的workerid
說一個(gè)我們原來生產(chǎn)環(huán)境遇到的一個(gè)workerid重復(fù)的問題，生成workid的方式那叫一個(gè)簡潔
- // uid為zookeeper中的一個(gè)有序持久節(jié)點(diǎn)
- List<String> pidListNode = zkClient.getChildren("uid");
- String workerId = String.valueOf(pidListNode.size());
- zkClient.create("uid", new byte[0], CreateMode.PERSISTENT_SEQUENTIAL);
「你能看出來這段代碼為什么會(huì)造成workid重復(fù)嗎?」
它把uid子節(jié)點(diǎn)的數(shù)量作為workid，當(dāng)2個(gè)應(yīng)用同時(shí)執(zhí)行到第一行代碼時(shí)，子節(jié)點(diǎn)數(shù)量是一樣的，得到的workerId就會(huì)重復(fù)。
有意思的是這段代碼跑了好幾年都沒有問題，直到運(yùn)維把應(yīng)用的發(fā)版效率提高了一點(diǎn)，線上就開始報(bào)錯(cuò)了。因?yàn)閯傞_始應(yīng)用是串行發(fā)版，后來改為并行發(fā)版
「當(dāng)使用雪花算法的時(shí)候，有可能發(fā)生時(shí)鐘回?fù)?，建議使用開源的框架，如美團(tuán)的Leaf。」
雪花算法在很多中間件中都被使用過，如seata用來生成全局唯一的事務(wù)id
本文轉(zhuǎn)載自微信公眾號「Java識(shí)堂」，作者李立敏。轉(zhuǎn)載本文請聯(lián)系Java識(shí)堂公眾號。
