雪花算法【snowflake】

雪花算法

為什麼需要分布式全局唯一ID 以及分布式ID的業務需求？

在複雜分布式系統中，往往需要對大量對資料和消息進行辨別
如在美團、支付、餐飲中系統的資料日漸增長，對資料分庫分表需要有一個唯一來辨別一條資料或消息
此時一個能夠生成全局唯一ID的系統是非常有必要的

ID生成規則部分硬性要求

全局唯一：不能出現重複的ID，要唯一辨別
趨勢遞增：在Mysql 的InnoDB引擎使用的是聚集索引，由于多數RDBMS 使用的是Btree資料結構來存儲資料，在主鍵的選擇上面我們應該盡量使用有序的主鍵保證資料寫入
單調遞增：保證下一個ID一定大于上一個ID，例如事物版本号，增量消息
資訊安全：如果ID是連續的，惡意使用者的扒取資料就非常容易來，直接按照順序下載下傳指定的URL，如果是訂單号就更危險來，競争對手可以知道我們一天的單量，是以在一些應用場景下，需要ID不規則
含時間戳：這樣就能夠在開發中快速了解這個分布式id的生成時間

ID生成系統的可用性要求

高可用：發一個擷取分布式ID的請求，伺服器就要保證99.99%的情況下給我建立一個唯一分布式ID
低延遲：發一個擷取分布式ID的請求，伺服器就是要快，極速
高QPS ：假如并發一口氣10萬個建立分布式ID請求同時殺過來，伺服器要頂的住一下子成功建立10w個分布式ID

我們平時的方案

UUID 、資料庫自增主鍵、基于Redis 生成全局ID政策

弊端

UUID 不能生成順序，遞增的資料，并且長，不是很推薦

資料庫自增，叢集多的情況下，擴容簡直就是噩夢

Redis 使用Redis INCR 和 INCRBY 實作

snowflake（雪花算法）

Twitter的分布式自增ID算法：snowflake（雪花算法）

概述

最初 Twitter把存儲系統從Mysql 遷移到 Cassandra (由Facebook 開發一套開源分布式Nosql系統) 因為Cassandra沒有順序ID生成機制，是以開發成了這樣一套全局唯一 ID生成服務

Twitter 的分布式雪花算法SnowFlake ，經測試 snowflake 每秒能産出26 萬個自增可排序的ID

twitter的SnowFlake生成ID能夠按照時間有序生成
SnowFlake 算法生成id 的結果是一個64 bit 大小的整數，為一個Long 型（轉換成字元後長度19位）
分布式系統不會産生ID碰撞（由datacenter 和 workerld 區分）并且效率較高

結構

号段解析：

1bit ，

不用，因為二進制中最高位是符号位，毫秒級，生成的id一般用整數，是以最高位 0

41bit - 時間戳，用來記錄時間戳，毫秒級，

41位可以表示 2 ^ {41}-1個數字
如果隻用來表示正整數(計算機中正整數包含0)。可以表示數值範圍：0 至 2^{41}-1 , 減1 是因為表示的數值是從0開始算的，而不是1.
也就是說 41 位可以表示 2 ^ {41}-1 個毫秒的值，裝換成機關年則（2^{41}-1）/ （1000 60 60 24 365）=69年

10bit- 工作機器ID，用來記錄工作機器ID

可以部署在 2^{10} = 1024 個節點，包括5位 datacenterId 和 5位的 workeId
5位（bit）可以表示的最大正整數是 2 ^ {5}-1 =31 , 即可以用0、1、2、3....31這32個數字，來表示不同的datacenterId 或者 workId

12 bit -序列号，序列号，用來記錄同毫秒内産生的不同的id。

12位可以表示的最大正整數是2^{12}-1 = 4095 即可以用0、1、2、34094 這 4095個數字來表示同一機器同一時間（毫秒）産生的4095個ID序号

SnowFlake可以保證

所有生成的id 按時間趨勢遞增
整個分布式系統内不會産生重複的id

源碼

twitter的雪花算法：

https://github.com/twitter-archive/snowflake

GitHub上java版的雪花算法：

https://github.com/beyondfengyu/SnowFlake/blob/master/SnowFlake.java https://github.com/souyunku/SnowFlake/blob/master/SnowFlake.java

java版❄️雪花算法

public class SnowflakeIdWorker {
 // ==============================Fields==================
    /** 開始時間截 (2019-08-06) */
    private final long twepoch = 1565020800000L;
 
    /** 機器id所占的位數 */
    private final long workerIdBits = 5L;
 
    /** 資料辨別id所占的位數 */
    private final long datacenterIdBits = 5L;
 
    /** 支援的最大機器id，結果是31 (這個移位算法可以很快的計算出幾位二進制數所能表示的最大十進制數) */
    private final long maxWorkerId = -1L ^ (-1L << workerIdBits);
 
    /** 支援的最大資料辨別id，結果是31 */
    private final long maxDatacenterId = -1L ^ (-1L << datacenterIdBits);
 
    /** 序列在id中占的位數 */
    private final long sequenceBits = 12L;
 
    /** 機器ID向左移12位 */
    private final long workerIdShift = sequenceBits;
 
    /** 資料辨別id向左移17位(12+5) */
    private final long datacenterIdShift = sequenceBits + workerIdBits;
 
    /** 時間截向左移22位(5+5+12) */
    private final long timestampLeftShift = sequenceBits + workerIdBits + datacenterIdBits;
 
    /** 生成序列的掩碼，這裡為4095 (0b111111111111=0xfff=4095) */
    private final long sequenceMask = -1L ^ (-1L << sequenceBits);
 
    /** 工作機器ID(0~31) */
    private long workerId;
 
    /** 資料中心ID(0~31) */
    private long datacenterId;
 
    /** 毫秒内序列(0~4095) */
    private long sequence = 0L;
 
    /** 上次生成ID的時間截 */
    private long lastTimestamp = -1L;
 
     //==============================Constructors====================
    /**
     * 構造函數
     * @param workerId 工作ID (0~31)
     * @param datacenterId 資料中心ID (0~31)
     */
    public SnowflakeIdWorker(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=================================
    /**
     * 獲得下一個ID (該方法是線程安全的)
     * @return SnowflakeId
     */
    public synchronized long nextId() {
        long timestamp = timeGen();
 
        //如果目前時間小于上一次ID生成的時間戳，說明系統時鐘回退過這個時候應當抛出異常
        if (timestamp < lastTimestamp) {
            throw new RuntimeException(
                    String.format("Clock moved backwards.  Refusing to generate id for %d milliseconds", lastTimestamp - timestamp));
        }
 
        //如果是同一時間生成的，則進行毫秒内序列
        if (lastTimestamp == timestamp) {
            sequence = (sequence + 1) & sequenceMask;
            //毫秒内序列溢出
            if (sequence == 0) {
                //阻塞到下一個毫秒,獲得新的時間戳
                timestamp = tilNextMillis(lastTimestamp);
            }
        }
        //時間戳改變，毫秒内序列重置
        else {
            sequence = 0L;
        }
 
        //上次生成ID的時間截
        lastTimestamp = timestamp;
 
        //移位并通過或運算拼到一起組成64位的ID
        return ((timestamp - twepoch) << timestampLeftShift) //
                | (datacenterId << datacenterIdShift) //
                | (workerId << workerIdShift) //
                | sequence;
    }
 
    /**
     * 阻塞到下一個毫秒，直到獲得新的時間戳
     * @param lastTimestamp 上次生成ID的時間截
     * @return 目前時間戳
     */
    protected long tilNextMillis(long lastTimestamp) {
        long timestamp = timeGen();
        while (timestamp <= lastTimestamp) {
            timestamp = timeGen();
        }
        return timestamp;
    }
 
    /**
     * 傳回以毫秒為機關的目前時間
     * @return 目前時間(毫秒)
     */
    protected long timeGen() {
        return System.currentTimeMillis();
    }
 
    //==============================Test=============================================
    /** 測試 */
    public static void main(String[] args) {
        SnowflakeIdWorker idWorker = new SnowflakeIdWorker(0, 0);
        for (int i = 0; i < 10; i++) {
            long id = idWorker.nextId();
            System.out.println(Long.toBinaryString(id));
            System.out.println(id);
        }
    }
}

springboot整合雪花算法

建立項目snowflake
pom

<dependencies>
    <!--hutool 引入糊塗工具包，測試雪花算法-->
    <dependency>
        <groupId>cn.hutool</groupId>
        <artifactId>hutool-captcha</artifactId>
        <version>5.3.8</version>
    </dependency>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-web</artifactId>
    </dependency>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-actuator</artifactId>
    </dependency>
    <dependency>
        <groupId>org.projectlombok</groupId>
        <artifactId>lombok</artifactId>
        <optional>true</optional>
    </dependency>
    <dependency>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-test</artifactId>
        <scope>test</scope>
    </dependency>
</dependencies>

server:
  port: 7777

建立 utils包 IdGeneratorSnowflake 類

@Slf4j
@Component
public class IdGeneratorSnowflake {

    private long workerId = 0;  //第幾号機房
    private long datacenterId = 1;  //第幾号機器
    private Snowflake snowflake = IdUtil.createSnowflake(workerId, datacenterId);

    @PostConstruct  //構造後開始執行，加載初始化工作
    public void init(){
        try{
            //擷取本機的ip位址編碼
            workerId = NetUtil.ipv4ToLong(NetUtil.getLocalhostStr());
            log.info("目前機器的workerId: " + workerId);
        }catch (Exception e){
            e.printStackTrace();
            log.warn("目前機器的workerId擷取失敗 ----> " + e);
            workerId = NetUtil.getLocalhostStr().hashCode();
        }
    }

    public synchronized long snowflakeId(){
        return snowflake.nextId();
    }

    public synchronized long snowflakeId(long workerId, long datacenterId){
        Snowflake snowflake = IdUtil.createSnowflake(workerId, datacenterId);
        return snowflake.nextId();
    }

    //測試
    public static void main(String[] args) {
        System.out.println(new IdGeneratorSnowflake().snowflakeId());   //1277896081711169536
    }
}

建立service包 OrderService 接口與 service.impl包 OrderServiceImpl 實作OrderService的接口

public interface OrderService {

    String getIDBySnowFlake();
}

@Service
public class OrderServiceImpl implements OrderService {

    @Autowired
    private IdGeneratorSnowflake idGenerator;

    public String getIDBySnowFlake() {
        //建立線程池（5個線程）
        ExecutorService threadPool = Executors.newFixedThreadPool(5);

        for (int i = 1; i <= 20; i++) {
            threadPool.submit(() -> {
                System.out.println(idGenerator.snowflakeId());
            });
        }

        threadPool.shutdown();

        return "hello snowflake";
    }
}

建立 controller 包 OrderController

@RestController
public class OrderController {

    @Autowired
    private OrderService orderService;

    @RequestMapping("/snowflake")
    public String index(){
        return orderService.getIDBySnowFlake();
    }

}

主啟動類

@SpringBootApplication
public class MainApp {
    public static void main(String[] args) {
        SpringApplication.run(MainApp.class, args);
    }
}

啟動項目浏覽器輸入

http://localhost:7777/snowflake

優缺點

解決時鐘回撥問題

百度開源的分布式唯一ID生成器 UidGenerator
美團開源的分布式ID生成系統 Leaf

個人部落格： http://blog.yanxiaolong.cn/

雪花算法【snowflake】

雪花算法

ID生成規則部分硬性要求

ID生成系統的可用性要求

我們平時的方案

snowflake（雪花算法）

概述

結構

源碼

springboot整合雪花算法

優缺點

繼續閱讀

Dijkstra--簡易版（最短路徑）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

spark/scala關于【資源檔案】加載方法概述外部檔案加載方案測試資源檔案打包入jar包中小結

NOSQL安全攻擊

mybatis_入門程式Mybatis入門

mysql使用source指令導入.sql檔案

AOP程式設計_Android優雅權限架構(1)概念基礎，2021金三銀四前言正文大綱正文

登入plsql 報錯 the account is locked --使用者被鎖

Effective Java 8:通用程式設計

SequoiaDB巨杉資料庫C++驅動概述

OOM三種類型

工廠模式-三種類型

【遞歸】高效率求2的n次幂

win10本地scala和spark安裝安裝scala安裝spark

scala (3) Function 和 Method

hdu7108哈希