徒手用 Go 寫個 Redis 伺服器
作者:HDT3213
今天給大家帶來的開源專案是 Godis:一個用 Go 語言實現的 Redis 伺服器。支援:
5 種資料結構(string、list、hash、set、sortedset)
自動過期(TTL)
釋出訂閱、地理位置、持久化等功能
你或許不需要自己實現 Redis 服務,但你是否厭煩了每天都是寫增刪改查的業務程式碼,想提高程式設計水平試圖從零寫個專案開啟 IDE 卻發現無從下手?
動手造輪子一定是提高程式設計能力的好辦法,下面就帶大家用 Go 從零開始寫一個 Redis 伺服器(Godis),從中你將學到:
如何編寫 Go 語言 TCP 伺服器
設計並實現安全可靠的通訊協議(redis 協議)
如何使用 Go 語言開發高併發程式
設計和實現分散式叢集以及分散式事務
熟悉連結串列、雜湊表、跳錶以及時間輪等常用資料結構
千萬不要擔心內容太難,學不會或者沒有 Go 語言基礎!!雖然示例程式碼是 Go 但不會影響你理解 Redis 的原理和底層協議以及高效能的秘密。而且作者為了照顧到廣大讀者,對技術的講解做了最佳化。示例程式碼在原專案基礎上做了簡化,並逐行地加了註釋。
下面讓我們一起撥開 Redis 的迷霧。
一、寫個 TCP 伺服器
眾所周知 Redis 是 C/S 模型,使用 TCP 協議進行通訊。接下來就從實現 TCP 服務端開始。作為廣泛用於服務端的程式語言 Golang 提供了非常簡潔的 TCP 介面,所以實現起來十分方便。示例程式碼:
至此只用了 40 行程式碼就搞定服務端啦!啟動上面的 TCP 服務後,在終端中輸入
telnet 127。0。0。1 8000
就可以連線到剛寫好的伺服器,它會將你傳送的訊息原樣返回給你(所以請不要罵它):
這個 TCP 伺服器的非常簡單,主協程呼叫 accept 函式來監聽埠,接受新連線後開啟一個 Goroutine 來處理它。這種簡單的阻塞 IO 模型有些類似於早期的 Tomcat/Apache 伺服器。
阻塞 IO 模型是使用
一個執行緒處理一個連線
,在沒有收到新資料時監聽執行緒處於阻塞狀態,直到資料就緒後執行緒被喚醒進行處理。因為阻塞 IO 模型需要開啟大量執行緒並且頻繁地進行上下文切換,所以它的效率很低。而 Redis 使用的 epoll 技術(IO 多路複用)用
一個執行緒處理大量連線
,極大地提高了吞吐量。那麼我們的 TCP 伺服器會比 Redis 慢很多嗎?
當然不會,Golang 利用 Goroutine 排程開銷遠遠小於執行緒排程開銷的優勢封裝出
goroutine-per-connection
風格的極簡介面,而且 net/tcp 庫將 epoll 封裝成了阻塞 IO 的樣子,在享受 epoll 高效能的同時避免了原生 epoll 介面所需的複雜非同步程式碼。
在作者的電腦上 Redis 每秒可以響應 10。6k 個 PING 命令,而 Godis(完整程式碼) 的吞吐量為 9。2 kqps 相差並不大。想了解更多 Golang 高效能的㊙️密,可以搜尋
go netpoller
或者
go 語言 網路輪詢器
關鍵字
另外,合格的 TCP 的伺服器在關閉的時候不應該一停了之,而需要完成響應已接收的請求、釋放 TCP 連線等必要的清理工作。這個功能我們一般稱為
優雅關閉
或者
graceful shutdown
,優雅關閉步驟:
首先,關閉 listener 停止接受新連線
然後,遍歷所有存活連線逐個關閉
優雅關閉的程式碼比較多,這裡就不完整貼出了。
二、透視 Redis 協議
在解決完通訊後,下一步就是搞清楚 Redis 的協議,其實就是一套序列化協議類似 JSON、Protocol Buffers,你看底層其實也就是一些基礎的知識。
自 Redis 2。0 以後的通訊統一為 RESP 協議(REdis Serialization Protocol),該協議易於實現不僅可以高效的被程式解析,還能夠被人類讀懂容易除錯。
RESP 是一個二進位制安全的文字協議,工作於 TCP 協議上。RESP 以行作為單位,客戶端和伺服器傳送的命令或資料一律以
\r\n
(CRLF)作為換行符。
二進位制安全是指允許協議中出現任意字元而不會導致故障。比如 C 語言的字串以
\0
作為結尾不允許字串中間出現
\0
,而 Go 語言的 string 則允許出現
\0
,我們說 Go 語言的 string 是二進位制安全的,而 C 語言字串不是二進位制安全的。
RESP 的二進位制安全性允許我們在 key 或者 value 中包含
\r
或者
\n
這樣的特殊字元。在使用 Redis 儲存 protobuf、msgpack 等二進位制資料時,二進位制安全性尤為重要。
RESP 定義了 5 種格式:
簡單字串(Simple String):伺服器用來返回簡單的結果,比如 “OK” 非二進位制安全,且不允許換行
錯誤資訊(Error):伺服器用來返回簡單的錯誤資訊,比如 “ERR Invalid Synatx” 非二進位制安全,且不允許換行
整數(Integer):llen、scard 等命令的返回值,64 位有符號整數
字串(Bulk String):二進位制安全字串,比如 get 等命令的返回值
陣列(Array,又稱 Multi Bulk Strings):Bulk String 陣列,客戶端傳送指令以及 lrange 等命令響應的格式
RESP 透過第一個字元來表示格式:
簡單字串:以“+” 開始, 如:“+OK\r\n”
錯誤:以“-” 開始,如:“-ERR Invalid Synatx\r\n”
整數:以“:”開始,如:“:1\r\n”
字串:以
$
開始
陣列:以
*
開始
下面讓我們透過一些實際例子來理解協議。
2。1 字串
字串(Bulk String)有兩行,第一行為
$
+正文長度,第二行為實際內容。如:
$3\r\nSET\r\n
字串(Bulk String)是二進位制安全的,就是說可以在 Bulk String 內部包含 “\r\n” 字元(行尾的 CRLF 被隱藏):
$4a\r\nb
2。2 空
$-1
表示 nil,比如使用 get 命令查詢一個不存在的 key 時,響應即為
$-1
。
2。3 陣列
陣列(Array)格式第一行為 “*”+陣列長度,其後是相應數量的 字串(Bulk String)。比如
[“foo”, “bar”]
的報文(傳輸時的內容):
*2$3foo$3bar
客戶端也使用 陣列(Array)格式向服務端傳送指令。命令本身將作為第一個引數,比如
SET key value
指令的 RESP 報文:
*3$3SET$3key$5value
將換行符打印出來:
*3\r\n$3\r\nSET\r\n$3\r\nkey\r\n$5\r\nvalue\r\n
2。4 解析預備
知道常用的 RESP 報文內容後,就可以開始著手解析了。但需要注意的是 RESP 是
二進位制安全
的協議,它允許在正文中使用
\r\n
字元。舉例來說 Redis 可以正確接收並執行
SET “a\r\nb” hellogithub
指令,這條指令的正確報文是這樣的:
*3 $3SET$4a\r\nb $11hellogithub
當
ReadBytes
讀取到第五行 “a\r\nb\r\n” 時會將其誤認為兩行:
*3 $3SET$4a // 錯誤的分行b // 錯誤的分行$11hellogithub
因此當讀取到第四行
$4
後,不應該繼續使用
ReadBytes(‘\n’)
讀取下一行,應使用
io。ReadFull(reader, msg)
方法來讀取指定長度的內容。
msg = make([]byte, 4 + 2) // 正文長度4 + 換行符長度2
_, err = io。ReadFull(reader, msg)
2。5 編寫 RESP 協議解析器
解決完上面內容包含 “\r\n” 的問題,我們就可以開始放手編寫 Redis 協議解析器啦!
由於解析器的程式碼比較多,這裡只簡單地介紹一下核心流程。
三、實現記憶體資料庫
至此我們已經搞定資料接收和解析的部分了,剩下就是我們應該把資料存在哪裡了?
拋開持久化部分,作為基於記憶體的 KV 資料庫 Redis 的所有資料需要都儲存在記憶體中的雜湊表,而這個雜湊表就是我們今天需要編寫的最後一個元件。
與單執行緒的 Redis 不同我們實現的 Redis(godis)是並行工作的,所以我們必須考慮各種併發安全問題。常見的併發安全雜湊表設計有幾種:
sync。map
:Golang 官方提供的併發雜湊表,適合讀多寫少的場景。但是在
m。dirty
剛被提升後會將
m。read
複製到新的
m。dirty
中,在資料量較大的情況下複製操作會阻塞所有協程,存在較大的隱患。
juc。ConcurrentHashMap
:Java 的併發雜湊表採用分段鎖實現。在進行擴容時訪問雜湊表執行緒都將協助進行 rehash 操作,在 rehash 結束前所有的讀寫操作都會阻塞。因為快取資料庫中鍵值對數量巨大且對讀寫操作響應時間要求較高,使用 juc 的策略是不合適的。
memcached hashtable
:在後臺執行緒進行 rehash 操作時,主執行緒會判斷要訪問的雜湊槽是否已被 rehash 從而決定操作 old_hashtable 還是操作 new_hashtable。這種設計被稱為
漸進式 rehash
它的優點是 rehash 操作基本不會阻塞主執行緒的讀寫,是最理想的的方案。
但漸進式 rehash 的實現非常複雜,所以 godis 採用 Golang 社群廣泛使用的分段鎖策略(非上面的三種),就是將 key 分散到固定數量的 shard 中避免進行整體 rehash 操作。shard 是有鎖保護的 map,當 shard 進行 rehash 時會阻塞 shard 內的讀寫,但不會對其他 shard 造成影響。
程式碼如下:
ConcurrentDict
可以保證對單個 key 操作的併發安全性,但是仍然無法滿足併發安全的需求,舉例來說:
Incr 命令需要完成:
讀取 -> 做加法 -> 寫入
三步操作,讀取和寫入兩步操作不是原子性的
MSETNX 命令當且僅當所有給定鍵都不存在時所有給定鍵設定值,我們需要保證「檢查多個key是否存在」以及「寫入多個key」這兩個操作的原子性
因此我們需要實現
db。Locker
用於鎖定一個或一組 key 直到我們完成所有操作後再釋放。
實現
db。Locker
最直接的想法是使用一個
map[string]*sync。RWMutex
加鎖過程分為兩步:初始化 mutex -> 加鎖
解鎖過程也分為兩步: 解鎖 -> 釋放mutex
那麼存在一個無法解決的併發問題:
由於 t3 時協程 B 釋放了鎖,t4 時協程 A 試圖加鎖會失敗。若協程B在解鎖時不執行
delete(locker[“a”])
就可以避免該異常的發生,但是這樣會造成嚴重的記憶體洩露。
我們注意到雜湊槽的數量遠少於 key 的數量,反過來說多個鍵可以共用一個雜湊槽。所以我們不再直接對 key 進行加鎖而是鎖定 key 所在的雜湊槽也可以保證安全,另一方面雜湊槽數量較少即使不釋放也不會消耗太多記憶體。
在鎖定多個 key 時需要注意,若 協程A 持有 鍵a 的鎖試圖獲得 鍵b 的鎖,此時 協程B 持有 鍵b 的鎖試圖獲得 鍵a 的鎖則會形成死鎖。
解決方法是所有協程都按照相同順序加鎖,若兩個協程都想獲得 鍵a 和 鍵b 的鎖,那麼必須先獲取 鍵a 的鎖後獲取 鍵b 的鎖,這樣就可以避免迴圈等待。
到目前為止構建 Redis 伺服器所需的基本元件已經備齊,只需要將 TCP 伺服器、協議解析器與雜湊表組裝起來我們的 Redis 伺服器就可以開始工作啦。
最後,以上程式碼均簡化自我寫的 Godis:一個開源僅用 Go 語言實現的 Redis 伺服器。期待您的關注和 Star
四、結束
很多朋友的日常工作主要是編寫業務程式碼,對於框架、資料庫、中介軟體這些“架構”、“底層程式碼” 有一些恐懼感。
但本文我們只寫了 3 個元件,共計幾百行程式碼就實現了一個基本的 Redis 伺服器。所以底層的技術並不難,只要你對技術感興趣由淺入深、從簡到繁,“底層程式碼”也並不神秘。
- END -
興趣是最好的老師,
HelloGitHub
發現程式設計的樂趣
相關文章
- 2021-09-18詳細步驟!WiFi轉串列埠模組搭配MQTT使用例項
- 2021-09-11談談理論修煉之Redis,分散式快取的中流砥柱
- 2021-07-27魔獸懷舊服:TBC上線近倆月,玩家心態改變,開始湧入60級伺服器
- 2021-07-16B站領銜主演的大型懸疑推理劇《崩了》,7月13日正式上線
- 2021-05-24【創投行聚焦】物聯網雲平臺:一個可以讓你的物聯網架構降低成本的