Twitter的snowflake算法改進(jìn)

Twitter的snowflake算法是在分布式系統(tǒng)中一種自增ID的算法,ID能夠按照時(shí)間有序生成并且可以做到全局唯一衙熔。

算法生成的是Long類型的id赶撰,一個(gè)Long類型占8個(gè)字節(jié)蝌以,每個(gè)字節(jié)占8比特,也就是說一個(gè)Long類型占64個(gè)比特(0和1)栋荸。

Twitter是這樣分配的:正數(shù)位(占1比特)+時(shí)間戳(占41比特)+機(jī)器id(占5比特)+數(shù)據(jù)中心(占5比特)+自增值(占12比特)菇怀,總共64比特組成的一個(gè)Long類型。

  • 正數(shù)位(占1比特):由于long基本類型在Java中是帶符號(hào)的晌块,最高位是符號(hào)位爱沟,正數(shù)是0,負(fù)數(shù)是1匆背,由于id一般是正數(shù)呼伸,所以這個(gè)位一般都是0
  • 時(shí)間戳(占41個(gè)比特):毫秒數(shù),大約可以使使用69年
  • 機(jī)器id(占5個(gè)比特):即2的5次方等于32個(gè)機(jī)器
  • 數(shù)據(jù)中心id(占5個(gè)比特):即2的5次方等于32個(gè)數(shù)據(jù)中心
  • 自增值(占12比特):2的12次方等于4096钝尸。也就是說每毫秒最多可以生成4096個(gè)id括享,如果cpu生產(chǎn)id的速度大于每毫秒4096個(gè)搂根,那么需要使線程進(jìn)行等待到下一毫秒,重新計(jì)數(shù)獲取自增值铃辖。

SnowFlake的優(yōu)點(diǎn)是剩愧,整體上按照時(shí)間自增排序,并且整個(gè)分布式系統(tǒng)內(nèi)不會(huì)產(chǎn)生ID碰撞(由數(shù)據(jù)中心ID和機(jī)器ID作區(qū)分)娇斩,并且效率較高仁卷,經(jīng)測試,SnowFlake每秒能夠產(chǎn)生26萬ID左右犬第。

snowflake算法有一個(gè)弊端锦积,每毫秒重新計(jì)數(shù),空閑時(shí)間會(huì)浪費(fèi)很多id空間瓶殃。針對空閑時(shí)間會(huì)浪費(fèi)很多id空間的改進(jìn)辦法:咱們可以把時(shí)間戳的單位改為秒。使用31個(gè)比特的時(shí)間戳(秒)副签,節(jié)約了10個(gè)比特遥椿,2的31次方等于2,147,483,648秒,約為69年淆储。然后我們把節(jié)約出來的10個(gè)比特交給自增值冠场,此時(shí)自增值(12+10=22比特),即2的22次方等于4,194,304本砰。

改進(jìn)前的snowflake算法結(jié)構(gòu)為:正數(shù)位(占1比特)+時(shí)間戳(占41比特)+機(jī)器id(占5比特)+數(shù)據(jù)中心id(占5比特)+自增值(占12比特)

改進(jìn)后的snowflake算法結(jié)構(gòu)為:正數(shù)位(占1比特)+時(shí)間戳(占31比特)+機(jī)器id(占5比特)+數(shù)據(jù)中心id(占5比特)+自增值(占22比特)

改進(jìn)后的優(yōu)點(diǎn):避免空閑時(shí)間會(huì)浪費(fèi)很多id空間碴裙,支持每秒生成419萬個(gè)id。

改進(jìn)后的實(shí)現(xiàn)代碼如下:

public class SnowflakeIdWorker2nd {
    /** 開始時(shí)間截 (2019-01-01) */
    private final long twepoch = 1546272000000L;

    /** 機(jī)器id所占的位數(shù) */
    private final long workerIdBits = 5L;

    /** 數(shù)據(jù)標(biāo)識(shí)id所占的位數(shù) */
    private final long datacenterIdBits = 5L;

    /** 支持的最大機(jī)器id点额,結(jié)果是31 (這個(gè)移位算法可以很快的計(jì)算出幾位二進(jìn)制數(shù)所能表示的最大十進(jìn)制數(shù)) */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);

    /** 支持的最大數(shù)據(jù)標(biāo)識(shí)id舔株,結(jié)果是31 */
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);

    /** 序列在id中占的位數(shù) */
    private final long sequenceBits = 22L;

    /** 機(jī)器ID向左移22位 */
    private final long workerIdShift = sequenceBits;

    /** 數(shù)據(jù)標(biāo)識(shí)id向左移27位(22+5) */
    private final long datacenterIdShift = sequenceBits + workerIdBits;

    /** 時(shí)間截向左移32位(5+5+22) */
    private final long timestampLeftShift = sequenceBits + workerIdBits
            + datacenterIdBits;

    /** 生成序列的掩碼,這里為4194303 */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);

    /** 工作機(jī)器ID(0~31) */
    private long workerId;

    /** 數(shù)據(jù)中心ID(0~31) */
    private long datacenterId;

    /** 秒內(nèi)序列(0~4194303) */
    private long sequence = 0L;

    /** 上次生成ID的時(shí)間截 */
    private int lastTimestamp = -1;

    // ==============================Constructors=====================================
    /**
     * 構(gòu)造函數(shù)
     * 
     * @param workerId
     *            工作ID (0~31)
     * @param datacenterId
     *            數(shù)據(jù)中心ID (0~31)
     */
    public SnowflakeIdWorker2nd(long workerId, long datacenterId) {
        if (workerId > maxWorkerId || workerId < 0) {
            throw new IllegalArgumentException(String.format(
                    "worker Id can't be greater than %d or less than 0",
                    maxWorkerId));
        }
        if (datacenterId > maxDatacenterId || datacenterId < 0) {
            throw new IllegalArgumentException(String.format(
                    "datacenter Id can't be greater than %d or less than 0",
                    maxDatacenterId));
        }
        this.workerId = workerId;
        this.datacenterId = datacenterId;
    }

    // ==============================Methods==========================================
    /**
     * 獲得下一個(gè)ID (該方法是線程安全的)
     * 
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        int timestamp = timeGen();

        // 如果當(dāng)前時(shí)間小于上一次ID生成的時(shí)間戳还棱,說明系統(tǒng)時(shí)鐘回退過這個(gè)時(shí)候應(yīng)當(dāng)拋出異常
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(String.format(
                    "Clock moved backwards.  Refusing to generate id for %d milliseconds",
                    lastTimestamp - timestamp));
        }

        // 如果是同一時(shí)間生成的载慈,則進(jìn)行秒內(nèi)序列
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            // 秒內(nèi)序列溢出
            if (sequence == 0) {
                // 阻塞到下一個(gè)秒,獲得新的時(shí)間戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        // 時(shí)間戳改變,秒內(nèi)序列重置
        else {
            sequence = 0L;
        }

        // 上次生成ID的時(shí)間截
        lastTimestamp = timestamp;

        // 移位并通過或運(yùn)算拼到一起組成64位的ID
        return ((timestamp - twepoch) << timestampLeftShift) //
                | (datacenterId << datacenterIdShift) //
                | (workerId << workerIdShift) //
                | sequence;
    }

    /**
     * 阻塞到下一個(gè)秒珍手,直到獲得新的時(shí)間戳
     * 
     * @param lastTimestamp
     *            上次生成ID的時(shí)間截
     * @return 當(dāng)前時(shí)間戳
     */
    protected int tilNextMillis(int lastTimestamp) {
        int timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }

    /**
     * 返回以秒為單位的當(dāng)前時(shí)間
     * 
     * @return 當(dāng)前時(shí)間(秒)
     */
    protected int timeGen() {
        String timestamp = String.valueOf(System.currentTimeMillis() / 1000);
        return Integer.valueOf(timestamp);
    }

    // ==============================Test=============================================
    /** 測試 */
    public static void main(String[] args) {
        SnowflakeIdWorker2nd idWorker = new SnowflakeIdWorker2nd(0, 0);
        for (int i = 0; i < 1000; i++) {
            long id = idWorker.nextId();
            System.out.println(Long.toBinaryString(id));//轉(zhuǎn)為Bit办铡,前面的0省略掉
            System.out.println(id);
        }
    }
}
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市琳要,隨后出現(xiàn)的幾起案子寡具,更是在濱河造成了極大的恐慌,老刑警劉巖稚补,帶你破解...
    沈念sama閱讀 219,539評(píng)論 6 508
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件童叠,死亡現(xiàn)場離奇詭異,居然都是意外死亡课幕,警方通過查閱死者的電腦和手機(jī)拯钻,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 93,594評(píng)論 3 396
  • 文/潘曉璐 我一進(jìn)店門帖努,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人粪般,你說我怎么就攤上這事拼余。” “怎么了亩歹?”我有些...
    開封第一講書人閱讀 165,871評(píng)論 0 356
  • 文/不壞的土叔 我叫張陵匙监,是天一觀的道長。 經(jīng)常有香客問我小作,道長亭姥,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 58,963評(píng)論 1 295
  • 正文 為了忘掉前任顾稀,我火速辦了婚禮达罗,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘静秆。我一直安慰自己粮揉,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 67,984評(píng)論 6 393
  • 文/花漫 我一把揭開白布抚笔。 她就那樣靜靜地躺著扶认,像睡著了一般。 火紅的嫁衣襯著肌膚如雪殊橙。 梳的紋絲不亂的頭發(fā)上辐宾,一...
    開封第一講書人閱讀 51,763評(píng)論 1 307
  • 那天,我揣著相機(jī)與錄音膨蛮,去河邊找鬼叠纹。 笑死,一個(gè)胖子當(dāng)著我的面吹牛敞葛,可吹牛的內(nèi)容都是我干的吊洼。 我是一名探鬼主播,決...
    沈念sama閱讀 40,468評(píng)論 3 420
  • 文/蒼蘭香墨 我猛地睜開眼制肮,長吁一口氣:“原來是場噩夢啊……” “哼冒窍!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起豺鼻,我...
    開封第一講書人閱讀 39,357評(píng)論 0 276
  • 序言:老撾萬榮一對情侶失蹤综液,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后儒飒,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體谬莹,經(jīng)...
    沈念sama閱讀 45,850評(píng)論 1 317
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,002評(píng)論 3 338
  • 正文 我和宋清朗相戀三年,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了附帽。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片埠戳。...
    茶點(diǎn)故事閱讀 40,144評(píng)論 1 351
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡,死狀恐怖蕉扮,靈堂內(nèi)的尸體忽然破棺而出整胃,到底是詐尸還是另有隱情,我是刑警寧澤喳钟,帶...
    沈念sama閱讀 35,823評(píng)論 5 346
  • 正文 年R本政府宣布屁使,位于F島的核電站,受9級(jí)特大地震影響奔则,放射性物質(zhì)發(fā)生泄漏蛮寂。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 41,483評(píng)論 3 331
  • 文/蒙蒙 一易茬、第九天 我趴在偏房一處隱蔽的房頂上張望酬蹋。 院中可真熱鬧,春花似錦抽莱、人聲如沸范抓。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,026評(píng)論 0 22
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽尉咕。三九已至叠蝇,卻和暖如春璃岳,著一層夾襖步出監(jiān)牢的瞬間,已是汗流浹背悔捶。 一陣腳步聲響...
    開封第一講書人閱讀 33,150評(píng)論 1 272
  • 我被黑心中介騙來泰國打工铃慷, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留,地道東北人蜕该。 一個(gè)月前我還...
    沈念sama閱讀 48,415評(píng)論 3 373
  • 正文 我出身青樓犁柜,卻偏偏與公主長得像,于是被迫代替她去往敵國和親堂淡。 傳聞我的和親對象是個(gè)殘疾皇子馋缅,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,092評(píng)論 2 355

推薦閱讀更多精彩內(nèi)容

  • “之前一篇文章萤悴,我們聊了一下分庫分表相關(guān)的一些基礎(chǔ)知識(shí),具體可以參見:《支撐日活百萬用戶的高并發(fā)系統(tǒng)皆的,應(yīng)該如何設(shè)計(jì)...
    JAVA架構(gòu)嘮嗑閱讀 1,000評(píng)論 0 0
  • 前言 在互聯(lián)網(wǎng)的業(yè)務(wù)系統(tǒng)中覆履,涉及到各種各樣的ID,如在支付系統(tǒng)中就會(huì)有支付ID、退款I(lǐng)D等硝全。那一般生成ID都有哪些...
    Java大生閱讀 3,272評(píng)論 0 4
  • 資本主義的大眾控制工具—廣告栖雾,剝奪了我們真實(shí)的渴望,從而賣給我們產(chǎn)品伟众,讓我們物質(zhì)上更貧窮析藕,心理上更枯竭——阿多諾
    喝水多頭疼閱讀 189評(píng)論 0 0
  • 從來都是懦弱無能之人才會(huì)做逃兵 2019年3月25日 17:19 記 子思:這個(gè)產(chǎn)品就像我...
    咯啊椒雪迦軒校勘學(xué)閱讀 202評(píng)論 0 0
  • 與神性共進(jìn)餐 “荷歐波諾波諾”“你創(chuàng)造了你的現(xiàn)實(shí)”“在你的生命中赂鲤,如若有誰是你不喜歡的噪径,那么是你創(chuàng)造了這個(gè)現(xiàn)實(shí)。如...
    三瀛堂閱讀 520評(píng)論 0 0