摘要：原理的雪花算法，使用語(yǔ)言實(shí)現(xiàn)。生成的整體上按照時(shí)間自增排序，并且整個(gè)分布式系統(tǒng)內(nèi)不會(huì)產(chǎn)生碰撞由和作區(qū)分，并且效率較高。據(jù)說(shuō)每秒能夠產(chǎn)生萬(wàn)個(gè)。

分布式系統(tǒng)中，有一些需要使用全局唯一ID的場(chǎng)景，這種時(shí)候?yàn)榱朔乐笽D沖突可以使用36位的UUID，但是UUID有一些缺點(diǎn)，首先他相對(duì)比較長(zhǎng)，另外UUID一般是無(wú)序的。

有些時(shí)候我們希望能使用一種簡(jiǎn)單一些的ID，并且希望ID能夠按照時(shí)間有序生成。

而twitter的SnowFlake解決了這種需求，最初Twitter把存儲(chǔ)系統(tǒng)從MySQL遷移到Cassandra，因?yàn)镃assandra沒(méi)有順序ID生成機(jī)制，所以開(kāi)發(fā)了這樣一套全局唯一ID生成服務(wù)。

Twitter的雪花算法SnowFlake，使用Java語(yǔ)言實(shí)現(xiàn)。

SnowFlake算法產(chǎn)生的ID是一個(gè)64位的整型，結(jié)構(gòu)如下（每一部分用“-”符號(hào)分隔）：

0 - 0000000000 0000000000 0000000000 0000000000 0 - 00000 - 00000 - 000000000000

1位標(biāo)識(shí)部分，在java中由于long的最高位是符號(hào)位，正數(shù)是0，負(fù)數(shù)是1，一般生成的ID為正數(shù)，所以為0；

41位時(shí)間戳部分，這個(gè)是毫秒級(jí)的時(shí)間，一般實(shí)現(xiàn)上不會(huì)存儲(chǔ)當(dāng)前的時(shí)間戳，而是時(shí)間戳的差值（當(dāng)前時(shí)間-固定的開(kāi)始時(shí)間），這樣可以使產(chǎn)生的ID從更小值開(kāi)始；41位的時(shí)間戳可以使用69年，(1L << 41) / (1000L 60 60 24 365) = 69年；

10位節(jié)點(diǎn)部分，Twitter實(shí)現(xiàn)中使用前5位作為數(shù)據(jù)中心標(biāo)識(shí)，后5位作為機(jī)器標(biāo)識(shí)，可以部署1024個(gè)節(jié)點(diǎn)；

12位序列號(hào)部分，支持同一毫秒內(nèi)同一個(gè)節(jié)點(diǎn)可以生成4096個(gè)ID；

SnowFlake算法生成的ID大致上是按照時(shí)間遞增的，用在分布式系統(tǒng)中時(shí)，需要注意數(shù)據(jù)中心標(biāo)識(shí)和機(jī)器標(biāo)識(shí)必須唯一，這樣就能保證每個(gè)節(jié)點(diǎn)生成的ID都是唯一的。或許我們不一定都需要像上面那樣使用5位作為數(shù)據(jù)中心標(biāo)識(shí)，5位作為機(jī)器標(biāo)識(shí)，可以根據(jù)我們業(yè)務(wù)的需要，靈活分配節(jié)點(diǎn)部分，如：若不需要數(shù)據(jù)中心，完全可以使用全部10位作為機(jī)器標(biāo)識(shí)；若數(shù)據(jù)中心不多，也可以只使用3位作為數(shù)據(jù)中心，7位作為機(jī)器標(biāo)識(shí)。

snowflake生成的ID整體上按照時(shí)間自增排序，并且整個(gè)分布式系統(tǒng)內(nèi)不會(huì)產(chǎn)生ID碰撞（由datacenter和workerId作區(qū)分），并且效率較高。據(jù)說(shuō)：snowflake每秒能夠產(chǎn)生26萬(wàn)個(gè)ID。

本機(jī)實(shí)測(cè)：100萬(wàn)個(gè)ID 耗時(shí)5秒

/**
 * 描述: Twitter的分布式自增ID雪花算法snowflake (Java版)
 * https://github.com/souyunku/SnowFlake
 *
 * @author yanpenglei
 * @create 2018-03-13 12:37
 **/
public class SnowFlake {

    /**
     * 起始的時(shí)間戳
     */
    private final static long START_STMP = 1480166465631L;

    /**
     * 每一部分占用的位數(shù)
     */
    private final static long SEQUENCE_BIT = 12; //序列號(hào)占用的位數(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; //序列號(hào)
    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();
        if (currStmp < lastStmp) {
            throw new RuntimeException("Clock moved backwards.  Refusing to generate id");
        }

        if (currStmp == lastStmp) {
            //相同毫秒內(nèi)，序列號(hào)自增
            sequence = (sequence + 1) & MAX_SEQUENCE;
            //同一毫秒的序列數(shù)已經(jīng)達(dá)到最大
            if (sequence == 0L) {
                currStmp = getNextMill();
            }
        } else {
            //不同毫秒內(nèi)，序列號(hào)置為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;                             //序列號(hào)部分
    }

    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);

        long start = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            System.out.println(snowFlake.nextId());
        }

        System.out.println(System.currentTimeMillis() - start);


    }
}

循環(huán)生成的ID，運(yùn)行結(jié)果如下：

170916032679263329
170916032679263330
170916032679263331
170916032679263332
170916032679263333
170916032679263334
170916032679263335
170916032679263336
170916032679263337
170916032679263338
170916032679263339
170916032679263340
170916032679263341
170916032679263342

Github:https://github.com/souyunku/SnowFlake

Spring Cloud（一）服務(wù)的注冊(cè)與發(fā)現(xiàn) Eureka

Spring Cloud（二）Consul 服務(wù)治理實(shí)現(xiàn)

Spring Cloud（三）服務(wù)提供者 Eureka + 服務(wù)消費(fèi)者（rest + Ribbon）

Spring Cloud（四）服務(wù)提供者 Eureka + 服務(wù)消費(fèi)者 Feign

Spring Cloud（五）斷路器監(jiān)控(Hystrix Dashboard)

Spring Cloud（六）服務(wù)網(wǎng)關(guān) zuul 快速入門

Spring Cloud（七）服務(wù)網(wǎng)關(guān) Zuul Filter 使用

Spring Cloud（八）高可用的分布式配置中心 Spring Cloud Config

Spring Cloud（九）高可用的分布式配置中心 Spring Cloud Config 集成 Eureka 服務(wù)

Spring Cloud（十）高可用的分布式配置中心 Spring Cloud Config 中使用 Refresh

Spring Cloud（十一）高可用的分布式配置中心 Spring Cloud Bus 消息總線集成（RabbitMQ）

源碼 + 教程

Github:https://github.com/souyunku/spring-boot-examples

Docker Compose 1.18.0 之服務(wù)編排詳解

Docker CE 安裝 初窺 Dockerfile 部署 Nginx

Docker Container 容器操作

Docker Hub 倉(cāng)庫(kù)使用，及搭建 Docker Registry

Docker Registry Server 搭建,配置免費(fèi) HTTPS 證書(shū)，及擁有權(quán)限認(rèn)證、TLS 的私有倉(cāng)庫(kù)

Docker Registry 企業(yè)級(jí)私有鏡像倉(cāng)庫(kù)Harbor管理WEB UI, 可能是最詳細(xì)的部署

Docker 部署 SpringBoot 項(xiàng)目整合 Redis 鏡像做訪問(wèn)計(jì)數(shù) Demo

Docker Maven Plugin 生成 Docker 鏡像 push 到 DockerHub上

搭建 Apache RocketMQ 單機(jī)環(huán)境

手把手教你 MongoDB 的安裝與詳細(xì)使用（一）

手把手教你 MongoDB 的安裝與詳細(xì)使用（二）

搭建 MongoDB分片（sharding） / 分區(qū) / 集群環(huán)境

搭建 SolrCloud 集群服務(wù)

搭建 Solr 單機(jī)服務(wù)

搭建 RabbitMQ 集群服務(wù)

搭建 RabbitMQ 單機(jī)服務(wù)

Mycat 讀寫(xiě)分離 數(shù)據(jù)庫(kù)分庫(kù)分表 中間件 安裝部署，及簡(jiǎn)單使用

離線部署 CDH 5.12.1 及使用 CDH 部署 Hadoop 大數(shù)據(jù)平臺(tái)集群服務(wù)

作者：鵬磊

出處：http://www.ymq.io

版權(quán)歸作者所有，轉(zhuǎn)載請(qǐng)注明出處

Wechat：關(guān)注公眾號(hào)，搜云庫(kù)，專注于開(kāi)發(fā)技術(shù)的研究與知識(shí)分享