今天給大家分享一篇關于雪花算法的文章,希望對你有所幫助!
Twitter-Snowflake算法産生的背景相當簡單，為了滿足Twitter每秒上萬條消息的請求，每條消息都必須配置設定一條唯一的id，這些id還需要一些大緻的順序（友善用戶端排序），并且在分布式系統中不同機器産生的id必須不同。
Snowflake算法核心
把時間戳，工作機器id，序列号組合在一起。
除了最高位bit标記為不可用以外，其餘三組bit占位均可浮動，看具體的業務需求而定。預設情況下41bit的時間戳可以支援該算法使用到2082年，10bit的工作機器id可以支援1023台機器，序列号支援1毫秒産生4095個自增序列id。下文會具體分析。
Snowflake – 時間戳
這裡時間戳的細度是毫秒級，具體代碼如下，建議使用64位linux系統機器，因為有vdso，gettimeofday()在使用者态就可以完成操作，減少了進入核心态的損耗。
| 1 2 3 4 5 6 | |
預設情況下有41個bit可以供使用，那麼一共有T（1llu << 41）毫秒供你使用配置設定，年份 = T / (3600 * 24 * 365 * 1000) = 69.7年。如果你隻給時間戳配置設定39個bit使用，那麼根據同樣的算法最後年份 = 17.4年。
Snowflake – 工作機器id
嚴格意義上來說這個bit段的使用可以是程序級，機器級的話你可以使用MAC位址來唯一标示工作機器，工作程序級可以使用IP+Path來區分工作程序。如果工作機器比較少，可以使用配置檔案來設定這個id是一個不錯的選擇，如果機器過多配置檔案的維護是一個災難性的事情。
這裡的解決方案是需要一個工作id配置設定的程序，可以使用自己編寫一個簡單程序來記錄配置設定id，或者利用Mysql auto_increment機制也可以達到效果。
工作程序與工作id配置設定器隻是在工作程序啟動的時候互動一次，然後工作程序可以自行将配置設定的id資料落檔案，下一次啟動直接讀取檔案裡的id使用。
PS：這個工作機器id的bit段也可以進一步拆分，比如用前5個bit标記程序id，後5個bit标記線程id之類:D
Snowflake – 序列号
序列号就是一系列的自增id（多線程建議使用atomic），為了處理在同一毫秒内需要給多條消息配置設定id，若同一毫秒把序列号用完了，則“等待至下一毫秒”。
| 1 2 3 4 5 6 7 8 | |
總體來說，是一個很高效很友善的GUID産生算法，一個int64_t字段就可以勝任，不像現在主流128bit的GUID算法，即使無法保證嚴格的id序列性，但是對于特定的業務，比如用做遊戲伺服器端的GUID産生會很友善。另外，在多線程的環境下，序列号使用atomic可以在代碼實作上有效減少鎖的密度。
java版本
/**
* Twitter的分布式自增ID雪花算法snowflake
* @author MENG
* @create 2018-08-23 10:21
**/
public class SnowFlake {
/**
* 起始的時間戳
*/
private final static long START_STMP = 1480166465631L;
//private final static long START_STMP = 1480166465631L;
/**
* 每一部分占用的位數
*/
private final static long SEQUENCE_BIT = 12; //序列号占用的位數
private final static long MACHINE_BIT = 5; //機器辨別占用的位數
private final static long DATACENTER_BIT = 5;//資料中心占用的位數
/**
* 每一部分的最大值
*/
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; //資料中心
private long machineId; //機器辨別
private long sequence = 0L; //序列号
private long lastStmp = -1L;//上一次時間戳
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;
}
/**
* 産生下一個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) {
//相同毫秒内，序列号自增
sequence = (sequence + 1) & MAX_SEQUENCE;
//同一毫秒的序列數已經達到最大
if (sequence == 0L) {
currStmp = getNextMill();
}
} else {
//不同毫秒内，序列号置為0
sequence = 0L;
}
lastStmp = currStmp;
return (currStmp - START_STMP) << TIMESTMP_LEFT //時間戳部分
| datacenterId << DATACENTER_LEFT //資料中心部分
| machineId << MACHINE_LEFT //機器辨別部分
| 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(1, 1);
long start = System.currentTimeMillis();
for (int i = 0; i < 1000000; i++) {
System.out.println(snowFlake.nextId());
}
System.out.println(System.currentTimeMillis() - start);
}
} PHP版本:
//https://learnku.com/articles/32575
//defined('BASEPATH') or exit('No direct script access allowed');
/**
*
* 雪花全局唯一 ID 生成類
* 修改了機器id和序列号自動擷取 理論上毫秒可生成 1024*4096個唯一id
* 組成: <毫秒級時間戳+機器id+序列号>
* 41bit的時間戳 可以支援該算法使用到2082年，
* 10bit的機器id 可以支援1023台機器，
* 12bit序列号 可以支援1毫秒産生4095個自增序列id
*
*/
class Snowflake
{
const EPOCH = 1479533469598; //開始時間,固定一個小于目前時間的毫秒數
//const EPOCH = 1479533; //開始時間,固定一個小于目前時間的毫秒數
const max12bit = 4095;
const max41bit = 1099511627775;
static $LAST_TIME_MID = 0; // 上次的機器id
static $SEQUENCE_NUM = 0; //
public static function createOnlyId()
{
// 時間戳 42位元組
$time = floor(microtime(true) * 1000);
// 目前時間 與 開始時間 內插補點
$time -= self::EPOCH;
// 二進制的 毫秒級時間戳
$base = decbin(self::max41bit + $time);
// 擷取序列數
self::get_num();
// 擷取機器id
self::get_mid();
// 機器id 10 位元組
$machineid = str_pad(decbin(self::$LAST_TIME_MID), 10, "0", STR_PAD_LEFT);
// 序列數 12位元組
$random = str_pad(decbin(self::$SEQUENCE_NUM), 12, "0", STR_PAD_LEFT);
// 拼接
$base = $base . $machineid . $random;
if (strpos(PHP_OS, "WIN") !== false)
{
//win下會科學計數 格式化
return number_format(bindec($base), 0, '', ''); //輸出16位id 4369796497932289
}
return bindec($base); // 輸出19位id 4940315248386113537
}
//機器id 10位元組 1-1023
public static function get_mid()
{
if (self::$SEQUENCE_NUM >= 4095)
{
self::$LAST_TIME_MID++;
if (self::$LAST_TIME_MID > 1023)
{
self::$LAST_TIME_MID = 0;
}
}
}
//12位元組 1-4095
public static function get_num()
{
self::$SEQUENCE_NUM++;
if (self::$SEQUENCE_NUM > 4095)
{
self::$SEQUENCE_NUM = 0;
}
}
}
for($i=1;$i<=100000;$i++)
{
var_dump(Snowflake::createOnlyId());
// string(19) "5018983989168308224"
}