柚子快報激活碼778899分享：分布式（6）

http://yzkb.51969.com/

目錄

26.雪花算法如何實現(xiàn)的？

27.雪花算法有什么問題？有哪些解決思路？

28.有哪些方案實現(xiàn)分布式鎖？

29.基于數(shù)據(jù)庫如何實現(xiàn)分布式鎖？有什么缺陷？

30.基于Redis如何實現(xiàn)分布式鎖？有什么缺陷？

26.雪花算法如何實現(xiàn)的？

Snowflake,雪花算法是由Twitter開源的分布式ID生成算法，以劃分命名空間的方式將64位分隔成多個部分，每個部分代表不同的涵義。而Java中64位的整數(shù)是Long類型，所以在Java中SnowFlake算法生成的ID就是Long來存儲的。

第1位占用1bit,其值始終是0，可看做事符號位不使用。

第2位開始的41位是時間戳，41bit位可表示2^41個數(shù)，每個數(shù)代表毫秒，那么雪花算法可用的時間年限是69年的時間。

中間的10bit位可以表示機器數(shù)，即2^10=1024臺機器，但是一般情況下我們不會部署這么多臺機器。如果我們對IDC（互聯(lián)網(wǎng)數(shù)據(jù)中心）有需求，還可以將10bit分5bit給IDC，分5bit給工作機器。這樣子就可以表示32個IDC，每個IDC下可以有32臺機器，具體的劃分可以根據(jù)自身需求定義。

最后12bit位是自增序列，可表示2^1=4096個數(shù)。

這樣的劃分之后相當(dāng)于在一毫秒一個數(shù)據(jù)中心的一臺機器上課產(chǎn)生4096個有序的不重復(fù)的ID。但是我們IDC和機器數(shù)肯定不止一個，所以毫秒內(nèi)能生成的有序ID數(shù)是翻倍的。

27.雪花算法有什么問題？有哪些解決思路？

有哪些問題？

時鐘回撥問題；

趨勢遞增，而不是絕對遞增；

不能在一臺服務(wù)器上部署多個分布式ID服務(wù)；

如何解決時鐘回撥？

以百度的UidGenerator為例，CachedUidGenerator方式主要采取如下一些措施和方案規(guī)避了時鐘回撥問題和增強唯一性：

自增列：UidGenerator的workerId在實例每次重啟時初始化，且就是數(shù)據(jù)庫的自增ID，從而完美的實現(xiàn)每個實例獲取到的workId不會有任何沖突。

RingBuffer：UidGenerator不再在每次取ID時都實時計算分布式ID,而是利用RingBuffer數(shù)據(jù)結(jié)構(gòu)預(yù)先生成若干個分布式ID并保存。

時間遞增：傳統(tǒng)的雪花算法實現(xiàn)都是通過System.currentTimeMills()來獲取時間并與上一次時間進行比較，這樣的實現(xiàn)嚴重依賴服務(wù)器的時間。而UidGenerator的時間類型是AtomicLong，且通過incrementAndGet()方法獲取下一次的時間，從而脫離了對服務(wù)器時間的依賴，也就不會有時鐘回撥問題

（這種做法也有一個小問題，即分布式ID中的時間信息可能并不是這個ID真正產(chǎn)生的時間點，例如：獲取的某分布式ID的值為3200169789968523265,他的反解析結(jié)果為{"timestamp":"2019 05 02 23:26:39";"workId":"21";"sequenece":"1"},但是這個ID可能并不是在“2019 05 02 23:26:39：這個時間產(chǎn)生的）。

28.有哪些方案實現(xiàn)分布式鎖？

使用場景

需要保證一個方法在同一時間內(nèi)只能被同一個線程執(zhí)行

實現(xiàn)方式：

加鎖和解鎖

方案，考慮因素（性能，穩(wěn)定，實現(xiàn)難度，死鎖）

基于數(shù)據(jù)庫做分布式鎖? ?樂觀鎖（基于版本號）和悲觀鎖（基于排他鎖）

基于Redis做分布式鎖：setnx(key,當(dāng)前時間+過期時間）和redlock機制；

基于zookeeper做分布式鎖：臨時有序節(jié)點來實現(xiàn)的分布式鎖，Curator

基于Consul做分布式鎖

29.基于數(shù)據(jù)庫如何實現(xiàn)分布式鎖？有什么缺陷？

基于數(shù)據(jù)庫表（鎖表，很少使用）

最簡單的方式可能就是直接創(chuàng)建一張鎖表，然后通過操作該表中的數(shù)據(jù)來實現(xiàn)了。當(dāng)我們想要獲得鎖的時候，就可以在該表中增加一條記錄，想要釋放鎖的時候就刪除這條記錄。為了更好的延時，我們先創(chuàng)建一張數(shù)據(jù)庫表，參考如下：

當(dāng)我們想要獲得鎖時，可以插入一條數(shù)據(jù)：

當(dāng)需要釋放鎖時，可以刪除這條數(shù)據(jù)：

基于悲觀鎖

悲觀鎖實現(xiàn)思路？

在對任意記錄進行修改前，先嘗試為該記錄加上排他鎖（exclusive? locking)。

如果加鎖失敗，說明該記錄正在被修改，那么當(dāng)前查詢可能等待或者拋出異常。具體響應(yīng)方式由開發(fā)者根據(jù)實際需要決定。

如果成功加鎖，那么就可以對記錄做修改，事務(wù)完成后就會解鎖了。

其間如果有其他對該記錄做修改或者加排他鎖的操作，就會等待我們解鎖或者直接拋出異常。

以MySQL? InnoDB中使用悲觀鎖為例？

要使用悲觀鎖，我們必須關(guān)閉mysql數(shù)據(jù)庫的自動提交屬性，因為MySQL默認使用autocommit模式，也就是說，當(dāng)你執(zhí)行一個更新操作后，MySQL會立刻將結(jié)果進行提交，set? ?autocommit=0；

上面的查詢語句中，我們使用了select? ...? for? update的方式，這樣就通過開啟排他鎖的方式實現(xiàn)了悲觀鎖。此時在t? goods表中，id為1的那條數(shù)據(jù)被我們鎖定了，其他的事務(wù)必須等本次事務(wù)提交后才能執(zhí)行。這樣我們就可以保證當(dāng)前的數(shù)據(jù)不會被其他事務(wù)修改。

上面我們提到，使用select ... for? update會把數(shù)據(jù)給鎖住，不過我們需要注意一些鎖的級別，MySQL? Innodb默認行級鎖。行級鎖是基于索引的，如果一條SQL語句用不到索引是不會使用行級鎖的，會使用表級鎖把整張表鎖住，這點需要注意。

基于樂觀鎖

樂觀并發(fā)控制（又名：樂觀鎖，縮寫OCC）是一種并發(fā)控制的方法。他假設(shè)多用戶并發(fā)的事務(wù)在處理時不會彼此互相影響，各事務(wù)能夠在不產(chǎn)生鎖的情況下處理各自影響的那部分數(shù)據(jù)。在提交數(shù)據(jù)更新之前，每個事務(wù)輝縣檢查在該事務(wù)讀取數(shù)據(jù)后，有沒有其他事務(wù)又修改了該數(shù)據(jù)。如果其他事務(wù)有更新的話，正在提交的事務(wù)會進行回滾。

以使用版本號實現(xiàn)樂觀鎖為例？

使用版本號時，可以在數(shù)據(jù)初始化時指定一個版本號，每次對數(shù)據(jù)的更新操作都對版本號執(zhí)行+1操作。并判斷當(dāng)前版本號是不是該數(shù)據(jù)的最新的版本號。

需要注意的是，樂觀鎖機制往往基于系統(tǒng)中數(shù)據(jù)存儲邏輯，因此也具備一定的局限性。由于樂觀鎖機制是在我們的系統(tǒng)中實現(xiàn)的，對于來自外部系統(tǒng)的用戶數(shù)據(jù)更新操作不受我們系統(tǒng)控制，因此可能會造成臟數(shù)據(jù)被更新到數(shù)據(jù)庫中。在系統(tǒng)設(shè)計階段，我們應(yīng)該寵妃考慮到這些情況，并進行相應(yīng)的調(diào)整（如將樂觀鎖策略在數(shù)據(jù)庫存儲過程中實現(xiàn)，對外只開放基于此存儲過程的數(shù)據(jù)更新途徑，而不是將數(shù)據(jù)庫表直接對外公開）。

缺陷

對數(shù)據(jù)庫依賴，開銷問題，行鎖變表鎖問題，無法解決數(shù)據(jù)庫單點和可重入的問題。

30.基于Redis如何實現(xiàn)分布式鎖？有什么缺陷？

最基本的Jedis方案

加鎖：? set? NX PX+重試+重試間隔

向Redis發(fā)起如下命令：SET? ?productid:lock? 0xx9p03001? NX? PX? 30000其中，”productId"由自己定義，可以是與本次業(yè)務(wù)有關(guān)的Id,"0xx9p03001"是一串隨機值，必須保證全局唯一（原因在后文中會提到），“NX“指的是當(dāng)且僅當(dāng)key（也就是案例中的”productid:lock")在Redis中不存在時，返回執(zhí)行成功，否則執(zhí)行失敗?！癙X 30000”指的是在30秒后，key被自動刪除。執(zhí)行命令后返回成功，表名服務(wù)成功的獲得了鎖。

解鎖：采用lua腳本：在刪除Key之前，一定要判斷服務(wù)A持有的Value與Redis內(nèi)存儲的Value是否一致。如果貿(mào)然使用服務(wù)A持有的key來刪除鎖，則會誤將服務(wù)B的鎖釋放掉。

基于RedLock實現(xiàn)分布式鎖

假設(shè)有兩個服務(wù)A，B都希望獲得鎖，有一個包含了5個Redis Master的Redis Cluster，執(zhí)行過程大致如下：

客戶端獲取當(dāng)前時間戳，單位：毫秒

服務(wù)A輪詢每個Master節(jié)點，嘗試創(chuàng)建鎖。（這里鎖的過期時間比較短，一般就幾十毫秒）RedLock算法會嘗試在大多數(shù)節(jié)點上分別創(chuàng)建鎖，假如節(jié)點總數(shù)為n,那么大多數(shù)節(jié)點指的是n/2+1。

客戶端計算陳工建立完鎖的時間，如果建鎖時間小于超時時間，就可以判定鎖創(chuàng)建成功。如果鎖創(chuàng)建失敗，則依次（遍歷master節(jié)點）刪除鎖。

只要有其他服務(wù)創(chuàng)建過分布式鎖，那么當(dāng)前服務(wù)就必須輪詢嘗試獲取鎖。

基于Redisson實現(xiàn)分布式鎖？

過程？

線程去獲取鎖，獲得成功：執(zhí)行l(wèi)ua腳本,保存數(shù)據(jù)到redis數(shù)據(jù)庫。

線程去獲取鎖，獲取失?。河嗛喠私怄i消息，然后再嘗試獲取鎖，獲取成功后，執(zhí)行Lua腳本，保存數(shù)據(jù)到redis數(shù)據(jù)庫。

互斥?

如果這個時候客戶端B來嘗試加鎖，執(zhí)行了同樣的一段Lua腳本。第一個if判斷會執(zhí)行“exists? ?myLock”，發(fā)現(xiàn)myLock這個鎖key已經(jīng)存在。接著第二個If判斷，判斷myLock鎖key的hash數(shù)據(jù)結(jié)構(gòu)中，是否包含客戶端B的ID，但明顯沒有，那么客戶端B會獲取到pttl? myLock返回的一個數(shù)字，代表MyLock這個鎖key的剩余生存時間。此時客戶端B會進入一個while循環(huán)，不聽的嘗試加鎖。

watch? dog 自動延時機制？

客戶端A加鎖的鎖key默認生存時間只有30秒，如果超過了30秒，客戶端A還想一直持有這把鎖，怎么辦？其實只要客戶端A一旦加鎖成功，就會啟動一個watch dog看門狗，他是一個后臺線程，會每隔10秒檢查一下，如果客戶端A還持有鎖Key，那么就會不斷的延長鎖key的生存時間。

可重入？

每次lock會調(diào)用incrby，每次unlock會減一。

方案比較

1.借助Redis實現(xiàn)分布式鎖時，有一個共同的缺陷：當(dāng)獲取鎖被拒絕后，需要不斷地循環(huán)，重新發(fā)送獲取鎖（創(chuàng)建key）的請求，直到請求成功。這就造成空轉(zhuǎn)，良妃寶貴的CPU資源。

2.RedLock算法本身有爭議，并不能保證健壯性。

3.Redisson實現(xiàn)分布式鎖時，除了將key新增到某個指定的Master節(jié)點外，還需要由master自動異步的將key和Value等數(shù)據(jù)同步至綁定的slave節(jié)點上。那么問題來了，如果master沒來得及同步數(shù)據(jù)，突然發(fā)生宕機，那么通過故障轉(zhuǎn)移和主備切換，slave節(jié)點被迅速升級為Master節(jié)點，新的客戶端加鎖成功，舊的客戶端的watch dog發(fā)現(xiàn)key存在，誤以為舊客戶端仍然持有這把鎖，這就導(dǎo)致同時存在多個客戶端持有同名鎖的問題了。

柚子快報激活碼778899分享：分布式（6）

http://yzkb.51969.com/

參考閱讀