分散式系統的主鍵生成方案對比

来源:https://www.cnblogs.com/jingdongkeji/archive/2023/09/18/17711470.html
-Advertisement-
Play Games

UUID(通用唯一識別碼)是由32個十六進位數組成的無序字元串,通過一定的演算法計算出來。為了保證其唯一性,UUID規範定義了包括網卡MAC地址、時間戳、名字空間(Namespace)、隨機或偽隨機數、時序等元素,以及從這些元素生成UUID的演算法。一般來說,演算法可以保證任何地方產生的任意一個UUID都... ...


UUID

​UUID(通用唯一識別碼)是由32個十六進位數組成的無序字元串,通過一定的演算法計算出來。為了保證其唯一性,UUID規範定義了包括網卡MAC地址、時間戳、名字空間(Namespace)、隨機或偽隨機數、時序等元素,以及從這些元素生成UUID的演算法。一般來說,演算法可以保證任何地方產生的任意一個UUID都不會相同,但這個唯一性是有限的,只在特定的範圍內才能得到保證。

​ UUID的一個非常明顯的特點就是本身較長,格式是這樣的:

xxxxxxxx-xxxx-Mxxx-xxxx-xxxxxxxxxxxx
467e8542-2275-4163-95d6-7adc205580a9

其中M位置,代表版本號,由於UUID的標準實現有5個版本,所以只會是1、2、3、4、5;

各版本介紹

UUID現有的5種版本,是根據不同的使用場景劃分的,而不是根據精度,所以Version5並不會比Version1精度高,在精度上大家都能保證唯一性,重覆的概率近乎於0

總結:

  1. 使用UUID,每個人都可以創建不與其它人衝突的唯一值,在所有空間和時間上都可以被視為唯一的標識。
  2. UUID可單機自行生成,且生成速度快,QPS高,各個語言都有對應的生成供直接調用使用。
  3. 如果只是需要生成一個唯一ID,可以使用V1或V4。v1基於時間戳和Mac地址,這些ID有一定的規律,而且會暴露你的Mac地址。v4是完全隨機(偽)的。
  4. 如果對於相同的參數需要輸出相同的UUID,你可以使用V3或V5。

Version1: 基於時間戳及MAC地址的實現

​其中包括了48位的MAC地址和60位的時間戳。且v1為了保證唯一性,當時間精度不夠時,會使用13~14位的clock sequence來擴展時間戳,比如:當UUID的生產成速率太快,超過了系統時間的精度。時間戳的低位部分會每增加一個UUID就+1的操作來模擬更高精度的時間戳,換句話說,就是當系統時間精度無會區分2個UUID的時間先後時,為了保證唯一性,會在其中一個UUID上+1。所以UUID重覆的概率幾乎為0,時間戳加擴展的clock sequence一共有74bits,(2的74次方,約為1.8後面加22個零),即在每個節點下,每秒可產生1630億不重覆的UUID。

但由於v1中最後的12位是網卡的MAC地址,會導致隱私問題以及安全問題,這是這個版本UUID受到批評的地方。

Version2: DCE安全的UUID

​ DCE(Distributed Computing Environment)安全的UUID和基於時間的UUID演算法相同,但會把時間戳的前4位置換為POSIX的UID或GID。這個版本的UUID在實際中較少用到。

Version3: 5 基於名稱空間和名字

​ v3和v5都是通過計算namespace和名稱的哈希值生成的。不同的點在於v3使用的hash演算法為MD5,v5使用SHA-1。因為演算法中沒有不確定的部分,所以當namespace與名稱確定時,得到的UUID都是確定唯一的。比如:

$ uuid -n 3 -v3 ns:URL www.jd.com
7e963853-8fce-3085-bb2c-8424745d73a2
7e963853-8fce-3085-bb2c-8424745d73a2
7e963853-8fce-3085-bb2c-8424745d73a2

演算法實現中會將namespace和輸入參數拼接在一起,計算hash結果,再進行截斷格式化等操作來保證唯一性。

Version4: 基於隨機數

​v4的UUID中4位代表版本,2-3位代表variant。餘下的122-121位都是全部隨機的。即有2的122次方(5.3後面36個0)個UUID。一個標準實現的UUID庫在生成了2.71萬億個UUID會產生重覆UUID的可能性也只有50%的概率。這相當於每秒產生10億的UUID,持續85年,而把這些UUID都存入文件,每個UUID占16bytes,總需要45EB(exabytes),比目前最大的資料庫(PB)還要大很多倍。

在java中使用v4:

# java 1.5+ 
# java.util.UUID

for (int i = 0; i < 3; i++) {
	String uuid = UUID.randomUUID().toString();
	System.out.println(uuid);
}

生成的UUID如下:

8bca474b-214d-4ce8-8446-b99f30147f94
c38588cf-a1c4-4758-9d86-b2ee5552ae59
febf5a46-bd1b-43f8-89a8-d5606e5d1ce0

由於這個版本使用非常簡單,因此使用最為廣泛。

SnowFlake演算法

雪花演算法,是 Twitter 開源的分散式 ID 生成演算法。雪花演算法中利用了時間戳,機器ID,以及同毫秒內的不同序列號來保證分散式生成ID的唯一性

雪花演算法總結

1.時間戳在高位,自增序列在低位的特征可以保證整個ID的趨勢是遞增有序的。

2.但由於其依賴機器時鐘,如果機器時鐘回撥,可能會導致重覆ID生成。其在分散式環境下,每台機器上的時鐘不可能完全同步,有時候會出現不是全局遞增的情況。

SnowFlake演算法生成id的結果是一個64bit大小的整數,它的結構如下圖:

  • 1bit,不用。二進位中最高位為1的都是負數,但是我們生成的id一般都使用整數,所以這個最高位固定是0
  • 41bit,用來記錄時間戳(毫秒)。41位可以表示 2^{41}-1 個數字,如果只用來表示正整數(電腦中正數包含0),可以表示的數值範圍是 0 至 2^{41}-1,也就是說41位可以表示 2^{41}-1 個毫秒的值,轉化成單位年則是 (2^{41} - 1) / (1000*60*60*24*365) = 69 年。
  • 10bit,用來記錄工作機器id。可以部署在 2^{10} = 1024 個節點,包括 5位 datacenterId 和 5位 workerId,5位(bit)可以表示的最大正整數是 2^{5}-1 = 31,即可以用 0、1、2、3、....、31 這 32 個數字,來表示不同的 datecenterId 或 workerId。
  • 12位,序列號,用來記錄同毫秒內產生的不同ID;12bit 可以表示的最大正整數是 2^{12}-1 = 4095 ,即可以用 0、1、2、3、....4094 這 4095 個數字,來表示同一機器同一時間截(毫秒)內產生的 4095 個 ID 序號。

有序主鍵 or 隨機主鍵 ?

​使用UUID這些隨機ID生成演算法作為MySQL主鍵的生成方案呢?答案是:不可以!

​眾所周知,當MySQL數據表使用InnoDB作為存儲引擎時,每一個索引都對應一個B+樹,若表定義了主鍵(沒有時,MySQL則會自動生成不可見的自增主鍵),主鍵對應的索引就是聚簇索引,表的所有數據都存儲在聚簇索引上。索引中鍵值的邏輯順序決定了表中相應行的物理順序(索引中的數據物理存放地址和索引的順序是一致的)。可以這麼理解:只要是索引是連續的,那麼數據在存儲介質上的存儲位置也是連續的。

​基於以上特性,由於自增鍵的值是有序的,插入數據時,Innodb 會把每一條記錄都存儲在上一條記錄的後面。當達到頁面的最大填充因數時候(innodb預設的最大填充因數是頁大小的15/16,會留出1/16的空間留作以後的修改),會進行如下操作:下一條記錄就會寫入新的頁中,一旦數據按照這種順序的方式載入,主鍵頁就會近乎於順序的記錄填滿,提升了頁面的最大填充率,不會有頁的浪費;且由於新插入的行一定會在原有的最大數據行下一行,mysql定位和定址很快,不會為計算新行的位置而做出額外的消耗。

​而UUID相對於有序的自增ID,它的值是毫無規律可言的,新行的主鍵不一定要比之前數據主鍵的值大,所以innodb無法做到總是把新行插入到索引的最後,而是需要為新行尋找新的合適的位置從而來分配新的空間。這個過程需要做很多額外的操作,而且最終分佈散亂的數據會導致以下問題:

  1. 寫入的目標頁很可能已經刷新到磁碟上並且從緩存上移除,或者還沒有被載入到緩存中,innodb在插入之前不得不先找到並從磁碟讀取目標頁到記憶體中,這將導致大量的隨機IO;
  2. 因為寫入是亂序的,innodb不得不頻繁的做頁分裂操作,以便為新的行分配空間,頁分裂導致移動大量的數據,一次插入最少需要修改三個頁以上,且由於頻頁分裂,頁會變得稀疏並被不規則的填充,最終會導致數據會有碎片;
  3. 在把值載入到聚簇索引(innodb預設的索引類型)以後,有時候會需要做一次OPTIMEIZE TABLE來重建表並優化頁的填充,這將又需要一定的時間消耗。

作者:京東零售 金越

來源:京東雲開發者社區 轉載請註明來源


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 1、下載相關安裝包 CentOS-7 所有rpm包的倉庫地址:http://mirror.centos.org/centos/7/os/x86_64/Packages/ perl-5.16.3-297.el7.x86_64.rpm快速下載地址: http://mirror.centos.org/ce ...
  • 本文基於內核 5.4 版本源碼討論 之前有不少讀者給筆者留言,希望筆者寫一篇文章介紹下 mmap 記憶體映射相關的知識體系,之所以遲遲沒有動筆,是因為 mmap 這個系統調用看上去簡單,實際上並不簡單,可以說是非常複雜的一個系統調用。 如果想要給大家把 mmap 背後的技術本質,正確地,清晰地還原出來 ...
  • 痞子衡嵌入式半月刊: 第 80 期 這裡分享嵌入式領域有用有趣的項目/工具以及一些熱點新聞,農曆年分二十四節氣,希望在每個交節之日準時發佈一期。 本期刊是開源項目(GitHub: JayHeng/pzh-mcu-bi-weekly),歡迎提交 issue,投稿或推薦你知道的嵌入式那些事兒。 上期回顧 ...
  • 1. 三管齊下 1.1. 不做、少做、快速地做 1.2. 如果查詢太大,服務端會拒絕接收更多的數據並拋出相應錯誤 1.3. 如果查詢寫得很糟糕,即使庫表結構再合理、索引再合適,也無法實現高性能 1.4. 查詢優化、索引優化、庫表結構優化需要齊頭併進,一個不落 1.5. Percona Toolkit ...
  • 1、背景描述 在真實業務場景下,Linux伺服器一般位於內網,所以無法直接訪問互聯網資源; 特別是安裝資料庫的Linux伺服器,在網路方面的管控只會更加嚴格; 因此,需要提前下載好相關資源,再傳輸到內網Linux伺服器進行安裝; 2、下載Mysql的安裝包 下載地址:https://dev.mysq ...
  • 起因: 上周安裝完mysql後,成功新建了資料庫,一切都是正常的,於是就先擱置一旁。今天周一過來,卻突然發現無法連接mysql了。 過程: 第一反應是服務沒有啟動,畢竟重啟了電腦,說不定是服務沒有自動啟動,於是打開了服務管理器,卻發現沒有mysql對應的服務。既然沒有,那我就自己手動創建一個,找到m ...
  • Ubuntu20.04安裝Mysql8主從 一.主資料庫安裝 1.下載安裝包並初始化資料庫 # 進入目錄 cd /opt # 下載安裝包 wget https://dev.mysql.com/get/Downloads/MySQL-8.0/mysql-8.0.20-linux-glibc2.12-x ...
  • 本文分享自華為雲社區《DTSE Tech Talk | 第43期:數倉數據可靠保證——物理細粒度備份恢復》,作者:華為雲社區精選。 大數據時代,數據對企業的重要性不言而喻,如果發生數據丟失或因為誤操作而造成數據丟失,將對企業的經營決策帶來不可估量的損失。本期《備份恢復全掌握,數倉數據更安全》的主題直 ...
一周排行
    -Advertisement-
    Play Games
  • 下麵是一個標準的IDistributedCache用例: public class SomeService(IDistributedCache cache) { public async Task<SomeInformation> GetSomeInformationAsync (string na ...
  • 這個庫提供了在啟動期間實例化已註冊的單例,而不是在首次使用它時實例化。 單例通常在首次使用時創建,這可能會導致響應傳入請求的延遲高於平時。在註冊時創建實例有助於防止第一次Request請求的SLA 以往我們要在註冊的時候實例單例可能會這樣寫: //註冊: services.AddSingleton< ...
  • 最近公司的很多項目都要改單點登錄了,不過大部分都還沒敲定,目前立刻要做的就只有一個比較老的項目 先改一個試試手,主要目標就是最短最快實現功能 首先因為要保留原登錄方式,所以頁面上的改動就是在原來登錄頁面下加一個SSO登錄入口 用超鏈接寫的入口,頁面改造後如下圖: 其中超鏈接的 href="Staff ...
  • Like運算符很好用,特別是它所提供的其中*、?這兩種通配符,在Windows文件系統和各類項目中運用非常廣泛。 但Like運算符僅在VB中支持,在C#中,如何實現呢? 以下是關於LikeString的四種實現方式,其中第四種為Regex正則表達式實現,且在.NET Standard 2.0及以上平... ...
  • 一:背景 1. 講故事 前些天有位朋友找到我,說他們的程式記憶體會偶發性暴漲,自己分析了下是非托管記憶體問題,讓我幫忙看下怎麼回事?哈哈,看到這個dump我還是非常有興趣的,居然還有這種游戲幣自助機類型的程式,下次去大玩家看看他們出幣的機器後端是不是C#寫的?由於dump是linux上的程式,剛好win ...
  • 前言 大家好,我是老馬。很高興遇到你。 我們為 java 開發者實現了 java 版本的 nginx https://github.com/houbb/nginx4j 如果你想知道 servlet 如何處理的,可以參考我的另一個項目: 手寫從零實現簡易版 tomcat minicat 手寫 ngin ...
  • 上一次的介紹,主要圍繞如何統一去捕獲異常,以及為每一種異常添加自己的Mapper實現,並且我們知道,當在ExceptionMapper中返回非200的Response,不支持application/json的響應類型,而是寫死的text/plain類型。 Filter為二方包異常手動捕獲 參考:ht ...
  • 大家好,我是R哥。 今天分享一個爽飛了的面試輔導 case: 這個杭州兄弟空窗期 1 個月+,面試了 6 家公司 0 Offer,不知道問題出在哪,難道是杭州的 IT 崩盤了麽? 報名面試輔導後,經過一個多月的輔導打磨,現在成功入職某上市公司,漲薪 30%+,955 工作制,不咋加班,還不捲。 其他 ...
  • 引入依賴 <!--Freemarker wls--> <dependency> <groupId>org.freemarker</groupId> <artifactId>freemarker</artifactId> <version>2.3.30</version> </dependency> ...
  • 你應如何運行程式 互動式命令模式 開始一個互動式會話 一般是在操作系統命令行下輸入python,且不帶任何參數 系統路徑 如果沒有設置系統的PATH環境變數來包括Python的安裝路徑,可能需要機器上Python可執行文件的完整路徑來代替python 運行的位置:代碼位置 不要輸入的內容:提示符和註 ...