Redis 實戰 —— 08. 實現自動補全、分佈式鎖和計數信號量

2021 年 1 月 27 日
筆記
Redis, Redis 實戰

自動補全 `P109`

自動補全在日常業務中隨處可見，應該算一種最常見最通用的功能。實際業務場景肯定要包括包含子串的情況，其實這在一定程度上轉換成了搜索功能，即包含某個子串的串，且優先展示前綴匹配的串。如果僅包含前綴，那麼可以使用 Trie 樹，但在包含其他的情況下，使用數據庫/ ES 本身自帶查詢就足夠了。可以按照四種情況（精確匹配、前綴、後綴、包含（也可將後兩種融合成包含）），分別查詢結果，直至達到數據條數上限或者全部查詢完畢。但這種使用方法有缺點：查詢次數多、難以分頁。不過實際場景中需要補全的情況都只要第一頁的數據即可。

自動補全最近聯繫人 `P110`

需求： 記錄最近聯繫過的 100 個人名，並支持對輸入的串進行自動補全。 P110

數據量很小，所以可以在 Redis 中用列表維護最近聯繫人，然後在內存中進行過濾可自動補全的串。

步驟： P111

維護長度為 100 的最近聯繫人列表
1. 如果指定的聯繫人已在列表中，則從列表中移除 (LREM)
2. 將指定的聯繫人添加到列表最前面 (LPUSH)
3. 如果添加完成後，列表長度超過 100 ，則對列表進行修剪，僅保留列表前面的 100 個聯繫人 (LTRIM)
獲取整個最近聯繫人列表，在內存中根據四種情況進行過濾即可

通訊錄自動補全 `P112`

需求： 有很多通訊錄，每個通訊錄中有幾千個人（僅包含小寫英文字母），盡量減少 Redis 傳輸給客戶端的數據量，實現前綴自動補全。 P112

思路： 使用有序集合存儲人名，利用有序集合的特性：當成員的分值相同時，將根據成員字符串的二進制順序進行排序。如果要查找 abc 前綴的字符串，那麼實際上就是查找介於 abbz... 之後和 abd 之前的字符串。所以問題轉化為：如何找到第一個排在 abc 之前的元素的排名和第一個排在 abd 之前的元素的排名。我們可以構造兩個不在有序集合中的字符串 (abb{, abc{) 輔助定位，因為 { 是排在 z 後第一個不適用的字符，這樣可以保證這兩個字符串不存在與有序集合中，且滿足轉化後的問題的限制。 P113

綜上： 通過將給定前綴的最後一個字符替換為第一個排在該字符前的字符，再再在末尾拼接上左花括號，可以得到前綴的前驅 (predecessor) ，通過給前綴的末尾拼接上左花括號，可以得到前綴的後繼 (successor) 。

字符集：當處理的字符不僅僅限於 a~z 範圍，那麼要處理好以下三個問題： P113
- 將所有字符轉換為位元組：使用 UTF-8 、 UTF-16 或者 UTF-32 字符編碼（注意： UTF-16 和 UTF-32只有大端版本可用於上述方法）
- 找出需要支持的字符範圍，確保所選範圍的前面和後面至少留有一個字符
- 使用位於範圍前後的字符分別代替反引號 ` 和左花括號 {

步驟： P114

運用思路中的方法找到前綴的前驅和後繼（為了防止同時查詢相同的前綴出現錯誤，可以在前驅和後繼之後添加上 UUID）
將前驅和後繼插入到有序集合里
查看前驅和後繼的排名
取出他們之間的元素
從有序集合中刪除前驅和後繼

通過向有序集合添加元素來創建查找範圍，並在取得範圍內的元素之後移除之前添加的元素，這種技術還可以應用在任何已排序索引 (sorted index) 上，並且能通過改善（第七章介紹）應用於幾種不同類型的範圍查詢，且不需要通過添加元素來創建範圍。 P115

分佈式鎖 `P115`

分佈式鎖在業務中也非常常見，能夠避免在分佈式環境中同時對同一個數據進行操作，進而可以避免並發問題。

導致鎖出現不正確行為，以及鎖在不正確運行時的癥狀 `P119`

持有鎖對進程因為操作時間過長而導致鎖被自動釋放，但進程本身並不知曉這一點，甚至還可能會錯誤地釋放掉了其他進程持有但鎖
一個持有鎖並打算執行長時間操作但進行已經崩潰，但其他想要獲取鎖但進程不知道哪個進程持有鎖，也無法檢測出持有鎖但進程已經崩潰，只能白白地浪費時間等待鎖自動釋放
在一個進程持有但鎖過期之後，其他多個進程同時嘗試去獲取鎖，並且都獲取了鎖
第一種情況和第三種情況同時出現，導致有多個進程獲取了鎖，而每個進程都以為自己是唯一一個獲得鎖但進程

簡單示例

// 在 conn 上獲取 key 的鎖，鎖超時時間為 expiryTime 毫秒，等待時間最長為 timeout 毫秒
func acquireLock(conn redis.Conn, key string, expiryTime int, timeout int) (token *int) {
	// 為了簡化，用 納秒時間戳 當 token ，實際應該用 UUID
	value := int(time.Now().UnixNano())

	for ; timeout >= 0; {
		// 嘗試加鎖
		_, err := redis.String(conn.Do("SET", key, value, "PX", expiryTime, "NX"))
		// 如果獲取鎖成功，則直接返回 token 指針
		if err == nil {
			return &value
		}
		// 睡 1ms
		time.Sleep(time.Millisecond)
		timeout --
	}

	// timeout 內仍未成功獲取鎖，則獲取失敗，返回 nil
	return nil
}

// 在 conn 上釋放 key 的鎖，且鎖與 token 對應
func releaseLock(conn redis.Conn, key string, token int) error {
	// 用 lua 腳本保證原子性，只有 token 和值相等是才釋放
	releaseLua := "if redis.call('get', KEYS[1]) == ARGV[1] then return redis.call('del', KEYS[1]) else return 0 end"
	script := redis.NewScript(1, releaseLua)
	result, err := redis.Int(script.Do(conn, key, token))
	if err != nil {
		return err
	}
	if result == 0 {
		return errors.New("release failure")
	}
	return nil
}

計數信號量 `P126`

計數信號量是一種鎖，它可以讓用戶限制一項資源最多能同時被多少個進程訪問，通常用於限定能夠同時使用的資源數量。 P126

基本的計數信號量 `P126`

將多個信號量的持有者的信息存儲到同一個有序集合中，即為每個嘗試獲取的請求生成一個 UUID ，並將這個 UUID 作為有序集合的成員，而成員對應的分值則是嘗試獲取時的時間戳。 P127

獲取信號量步驟： P127

清理有序集合中所有已過期的 UUID （時間戳 <= 當時時間戳 – 過期時間）
生成 UUID ，使用當時時間戳作為分值，將 UUID 添加到有序集合裏面
檢查剛剛的 UUID 的排名
- 若排名低於可獲取的信號量總數（成員排名從 0 開始計算），那麼表示成功獲取了信號量
- 若排名等於或高於可獲取的信號量總數，那麼未獲取成功，需要將剛剛的 UUID 移除

釋放信號量時直接從有序集合中刪除 UUID 即可。若返回值為 1 ，則表明成功手動釋放；若返回值為 0 ，則表明已經由於過期而自動釋放。 P128

缺點：

所有信號量的過期時間都需要一樣：為了方便刪除過期的 UUID
不公平，依賴系統時間：
- 當多機環境下， A 的系統時間比 B 的系統時間快 10ms ，那麼當 A 取得了最後一個信號量的時候， B 只要在 10ms 內嘗試獲取信號量，那麼就會造成 B 獲取了不存在的信號量，導致獲取的信號量超過了信號量的總數。 P128
- 還可能造成信號量提早被其他系統的獲取請求釋放

公平的計數信號量 `P128`

為了實現公平的計數信號量，即先發出獲取請求的客戶端能夠獲取到信號量。我們需要在 Redis 中維護一個自增的計數器，每次發出獲取請求前先對其自增，並使用自增後的值作為分值將對應的 UUID 插入到另一個有序集合中。即原本的有序集合僅用來查找並刪除過期的 UUID ，新的有序集合用來獲取排名判斷請求是否成功獲取到信號量。同時為了保持新的有序集合及時刪過期的 UUID ，在原本的有序集合執行完刪除操作後，還要使用 ZINTERSTORE 命令，保留僅在原本有序集合中出現的 UUID (ZINTERSTORE count_set 2 count_set time_set WEIGHTS 1 0)。注意： 若信號量獲取失敗，則需要及時刪除本次插入的無用數據。

上述方法能在一定程度上解決信號量獲取數超過信號量總數的問題，但刪除過期 UUID 的地方還是依賴本地時間，所以盡量保證各個主機的系統時間差距要足夠小。 P131

自我思考：做到與系統時間無關

去除原本的有序集合，僅留下計數器和計數值作為分值的有序集合，並對於每個 UUID 都設置一個有過期時間的鍵，每次移除前，遍歷有序集合，並查詢其是否過期，並從有序集合中刪除所有已過期的 UUID 。

這樣做不僅能完全達到與系統時間無關，還不會存在信號量獲取數超過信號量總數的問題，且能夠實現單個獲取的信號量能有不同的過期時間，也一定程度上降低了時間複雜度，不過會增加客戶端與 Redis 服務器之間的交互次數。

刷新信號量 `P131`

信號量使用者可能在過期時間內無法處理完請求，此時就需要續約，延長過期時間。由於公平的計數信號量已將時間有序集合和計數有序集合分開，所以只需要在時間有序集合中對 UUID 執行 ZADD 即可，若執行失敗，則已過期自動釋放。 P131

對於我剛剛提出的那種方法，有兩種方法可以續約：

使用 lua 腳本保證原子性
先讀取過期時間
- 未過期：再使用帶 XX 選項的 SET 命令設置新的過期時間（需要加上原有的過期時間），返回成功則續約成功，否則續約失敗
- 已過期：續約失敗

消除競爭條件 `P132`

兩個進程 A 和 B 都在嘗試獲取剩餘的一個信號量時，即使 A 首先對計數器執行了自增操作，但只要 B 能夠搶先將自己的 UUID 添加到計數有序集合中，並檢查 UUID 的排名，那麼 B 就可以成功獲取信號量。之後 A 再將自己的 UUID 添加到有序集合里，並檢查 UUID 排名，那麼 A 也可以成功獲取信號量，最終導致獲取的信號量多餘信號量總數。 P132

為了消除獲取信號量時所有可能出現的競爭條件，構建一個正確的計數信號量，我們需要用到前面完成的帶有超時功能的分佈式鎖。在想要獲取信號量時，首先嘗試獲取分佈式鎖，若獲取鎖成功，則繼續執行獲取信號量的操作；若獲取鎖失敗，那麼獲取信號量也失敗。 P132

不同計數信號量的使用場景 `P133`

基本的計數信號量：對於多機系統時間的差異不關心，也不需要對信號量進行刷新，並且能夠接收信號量的數量偶爾超過限制
公平的計數信號量：對於多機系統時間的差異不是非常敏感，但仍然能夠接收信號量但數量偶爾超過限制
正確的計數信號量：希望信號量一致具有正確的行為

本文首發於公眾號：滿賦諸機（點擊查看原文）開源在 GitHub ：reading-notes/redis-in-action

Tags: Redis Redis 實戰