# Linux 核心專題: 並行化的 Redis 實作
> 執行人: yeh-sudo
> [專題錄影解說](https://youtu.be/ovMkMNbM1xc)
### Reviewed by `Petakuo`
看起來引入 neco 至 mt-redis 沒有使效能提升,請問當初選擇 neco 的原因是什麼?或是 neco 有可以改進的地方嗎?
> 選擇 neco 的原因是他可以在 userspace 達成快速的 context switch ,以達成 coroutine ,讓多個任務並行進行,但可能是引入的方式有問題,所以效能沒有很大的提升。
### Reviewed by `stevendd543`
想請問使用 QSBR 效能會較好的的原因是什麼,所有 thread 都進入 quiescent states 這項是否會影響效能,也就是說會需要額外的開銷去紀錄嗎?
> QSBR 效能較好是因為在讀取端幾乎沒有成本,所以讀取的效能會最好,但是寫入端要看讀取端是怎麼進出 quiescent state ,假如所以執行緒都進入 quiescent state 而不退出,寫入端就沒有辦法更新資料,讀取端就會一直讀取到舊的資料,對寫入端效能影響很大。
### Reviewed by `ssheep773`
結果中的圖表是單次結果圖嗎,若不是可以多執行幾次取平均,避免數據點波動劇烈的情況。
為什麼在執行緒超過 16 時 mt-redis 加入 CPU affinity 的 context switch 個數會較多?
> 我剛開始做測試的時候是沒有取平均的,因為測試一種 Redis 版本重複 200 次很花時間,後面實驗不用跑這麼多次測試時才加入多執行幾次這個項目,但是因為 `memtier_benchmark` 有 Bug ,在取平均時輸出的數據都會是 0 ,可見 [`memtier_benchmark` 的 pipeline 參數](https://hackmd.io/WcW-q-n4QwSOfPK4YRT8Mw?view#memtier_benchmark-%E7%9A%84-pipeline-%E5%8F%83%E6%95%B8)。
> 執行緒超過 16 時 mt-redis 加入 CPU affinity 的 context switch 個數會較多,在當時測試時, `memtier_benchmark` 沒有加入 `taskset` 命令,所以測試程式和 mt-redis 競爭 CPU 資源有可能是主因,會再測試一次。
> 已更新實驗結果。
### Reviewed by `william linn`
為什麼 cpu affinity 不要一個 thread 一個 cpu 而是要兩個 thread 一個 cpu?
> 因為我測試過每個 CPU 一個執行緒,但是效能不如一個 CPU 兩個執行緒,這樣也能透過 context switch 讓要進行 I/O 的執行緒休息,將 CPU 資源讓給另外一個執行緒。
### Reviewed by `Shiang1212`
> Linux 核心中存在許多種 lock , spinlock 與 semaphore ,最大的問題是可擴展性太差,一次只允許一個執行緒或是處理程序進入 critical section ,當一個執行緒進入 critical section 時,其他的執行緒就只能透過 busy wait 等待一個執行緒退出 critical section ,這樣對系統的效能衝擊非常大
當 semaphore 的 count 大於 1,就能允許多個執行續進入 critical section。請問這裡的 semaphore 是指 binary semaphore 嗎?
> 這裡的 semaphore 不單只是指 binary semaphore ,這樣的用法是沒有問題的,這樣就和 read-write lock 很像,這種鎖有一個問題,就是當有 writer 在 critical section 中,其他的 reader 就必須要等待這個 writer 退出之後才能進行讀取,就算 counter 還剩下 9999 , reader 也不能進入 critical section ,反過來, writer 必須等待所有 reader 退出之後才能進行更動,對 writer 非常不公平,而且在 semaphore 中,還是必須要執行緒去取鎖 (acquire lock) ,這個操作本身就必須要犧牲額外的效能去做。
>
> 可以參考 [Linux 核心設計: 淺談同步機制](https://hackmd.io/@sysprog/linux-sync#read-write-lock-rwlock) 。
### Reviewed by `youjiaw`
1. 我想請問 mt-redis 在設定 CPU affinity 後,在 thread 數量小於 4 的測試中 cache miss rate 變高的原因是什麼?
2. 你的圖表有測試 threads number 到 20,所以下方的句子是否應修改為 1 ~ 20?
> 從 1 ~ 16 ,測試每一個執行緒數量對 mt-redis 效能的影響
3. 在我問題 2 提到的圖表中,mt-redis-no-affinity 是使用紫色表示,但是到下一個比較環節卻變成綠色,而紫色變用來表示 mt-redis-affinity,我建議顏色統一會增進易讀性和一致性。
## 任務簡介
儘管 Redis 6 開始引入多執行緒來處理 I/O 操作,但其本質仍為單一執行緒的設計,本任務嘗試藉由 [userspace RCU](https://liburcu.org/) 讓 Redis (及後繼真正開放原始碼的 [Valkey](https://valkey.io/) 專案) 得以有更好的並行表現,並確保相容於 Redis 原本的功能。
延伸閱讀:
* [Make redis 7 multi-threaded](https://github.com/redis/redis/issues/8340)
* [Redis 的眾多 fork](https://blog.gslin.org/archives/2024/03/30/11722/redis-%E7%9A%84%E7%9C%BE%E5%A4%9A-fork/)
## 開發環境
```shell
$ uname -a
Linux andyyeh-ubuntu 6.5.0-21-generic #21~22.04.1-Ubuntu SMP PREEMPT_DYNAMIC Fri Feb 9 13:32:52 UTC 2 x86_64 x86_64 x86_64 GNU/Linux
$ gcc --version
gcc (Ubuntu 11.4.0-1ubuntu1~22.04) 11.4.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
$ lscpu
Architecture: x86_64
CPU op-mode(s): 32-bit, 64-bit
Address sizes: 44 bits physical, 48 bits virtual
Byte Order: Little Endian
CPU(s): 16
On-line CPU(s) list: 0-15
Vendor ID: AuthenticAMD
Model name: AMD Ryzen 7 4800HS with Radeon Graphics
CPU family: 23
Model: 96
Thread(s) per core: 2
Core(s) per socket: 8
Socket(s): 1
Stepping: 1
Frequency boost: enabled
CPU max MHz: 2900.0000
CPU min MHz: 1400.0000
BogoMIPS: 5788.79
Virtualization features:
Virtualization: AMD-V
Caches (sum of all):
L1d: 256 KiB (8 instances)
L1i: 256 KiB (8 instances)
L2: 4 MiB (8 instances)
L3: 8 MiB (2 instances)
```
## 事前準備
理解 mt-redis 是如何儲存資料以及運作: [mt-redis 運作原理](https://hackmd.io/@yehsudo/mt-redis-work)
## TODO: 理解 Userspace RCU 設計及其考量
> 研讀 [RCU 研究](https://hackmd.io/@sysprog/ry_6RHgS3),理解 Userspace RCU (以下簡稱 urcu) 各個 flavor 的應用場景,並針對 Redis 的並行化,提出適用性的規劃和探討。
### 什麼是 RCU?
RCU 全名 read-copy update ,是一種在 2002 年 10 月加入到 Linux 核心的同步機制,與普通的上鎖機制不同, RCU 允許多個 reader 讀取資料,同時一個 writer 更新資料。
> In contrast with conventional locking primitives that ensure mutual exclusion among concurrent threads regardless of whether they be readers or updaters, or with reader-writer locks that allow concurrent reads but not in the presence of updates, RCU supports concurrency between a single updater and multiple readers.
#### Why RCU?
Linux 核心中存在許多種 lock,其中 spinlock 與 semaphore 最大的問題是可擴展性太差,一次只允許一個執行緒或是處理程序進入 critical section ,當一個執行緒進入 critical section 時,其他的執行緒就只能透過 busy wait 等待一個執行緒退出 critical section ,這樣對系統的效能衝擊非常大,儘管增加系統資源還是會對性能有很大的影響,接著出現 read-write lock,允許多個 reader 進入 critical section ,但 reader 和 writer 不能同時進入 critical section ,對讀多寫少的使用情境比較友善,後來出現 ticket spinlock ,但是因為需要去檢查 ticket,更新 ticket 之後需要進行廣播,更新每個 CPU 的 ticket,但是廣播這個操作,會需要很高的成本,可能會有數百至幾千個 cycle,導致 ticket spinlock 的成本過高,即使後來出現解決 cache coherence 問題的 MCS spinlock , 根據 [Linux 核心設計: 淺談同步機制](https://hackmd.io/@sysprog/linux-sync#lock-%E5%B0%8D-scalability-%E8%A1%9D%E6%93%8A%E6%A5%B5%E5%A4%A7)中的描述,只要有 lock ,就會對系統效能造成影響,所以要尋找新的解決方式,也就是 lock-free programming 與 RCU(Read-Copy-Update) 。
### 什麼是 User-space RCU?
urcu 於 2009 年 2 月建立, urcu 與 Linux 核心中的 RCU 類似,提供 read-write lock 的替代方案, reader 不直接與 writer 進行同步,允許多個 reader 在 writer 運作時進行讀取。
### Flavor 應用場景
urcu 共有 5 種 flavor 。
- [ ] Signal-based RCU using sys_membarrier() system call (`liburcu`)
當作業系統有支援 `sys_membarrier` 系統呼叫時就可以使用,在讀寫兩端都使用 memory barrier ,有了這個系統呼叫,這個模式的 writer 效能會比 Signal-based RCU 要好,因為不用發送信號通知全部的 reader ,透過系統呼叫就可以執行,在使用 urcu 時,引入 `#include <urcu.h>` ,預設的模式就會是這個,但若系統不支援 `sys_membarrier` ,就會使用 Memory-barrier-based RCU ,連接時要使用 `-lurcu` 參數。
- [ ] Memory-barrier-based RCU (`liburcu-mb`)
與使用 `sys_membarrier` 系統呼叫的 urcu 一樣,在讀寫兩端都使用 memory barrier ,可以更快測寬限期,但會導致讀取速度變慢。使用時,要加上 `-DRCU_MB` 編譯參數,連接時要加上 `-lurcu-mb` 參數。
- [ ] Signal-based RCU (`liburcu-signal`)
Signal-based RCU 效能較 QSBR 差,但是是最接近 QSBR 的機制,但 writer 需要發送信號給 reader ,所以 writer 效能最差,在使用時要使用 `-DRCU_SIGNAL` 參數進行編譯,依照[官方網站](https://liburcu.org/)的敘述,如果加上 `-lurcu-signal` 會導致錯誤。
- [ ] Bullet-proof RCU (`liburcu-bp`)
這個模式不需要在執行緒開始與結束使用 `rcu_register_thread` 與 `rcu_unregister_thread` ,對於 Bullet-proof RCU 來說,這兩個操作都是無效的,在進入 critical section 前自動進行 register ,離開 critical section 時自動進行 unregister ,但代價是讀寫操作性能都降低。
- [ ] QSBR (`liburcu-qsbr`)
與其他 flavor 不同的是, QSBR flavor 必須要定期進入 quiescent states,後者是當執行緒沒有在 critical section 時,就處於 quiescent states ,所以在執行緒離開 critical section 時,就必須要手動進入 quiescent states ,否則寬限期不會結束。在使用上必須引入 `#include <urcu-qsbr.h>` 且進行連接時要使用 `-lurcu-qsbr` 參數。在 reader 進行讀取時,必須時常使用 `rcu_quiescent_state` 退出 critical section ,讓 writer 可以更新資料,在 urcu 的 [`test_urcu_qsbr.c`](https://github.com/urcu/userspace-rcu/blob/master/tests/benchmark/test_urcu_qsbr.c#L132) 中有說明每 1024 個讀取操作之後進入 quiescent states ,而 `rcu_read_lock` 和 `rcu_read_unlock` 對 reader 來說是沒有作用的。
在 [User-space RCU](https://lwn.net/Articles/573424/#URCU%20Overview) 清楚描述每種 flavor 的應用場景。如果使用者最在意效能,那首選就會是 QSBR ,如果使用者沒辦法掌控執行緒的建立與銷毀,則使用 Bullet-proof RCU ,若能掌控執行緒的建立與銷毀,且執行的 Linux 系統支援 `sys_membarrier` ,則使用 `RCU_MEMBARRIER` ,反之則使用 `RCU_MB` ,若能預定一個信號給 urcu ,則使用 `RCU_SIGNAL` 。在建立並行化的 Redis 雛形中,會針對五種 flavor 進行測試,探討哪一種 flavor 最適合應用在並行化的 Redis 。
### 參考資料
* [Linux 核心設計: RCU 同步機制](https://hackmd.io/@sysprog/linux-rcu)
* [What is RCU, Fundamentally?](https://lwn.net/Articles/262464/)
* [What is RCU? Part 2: Usage](https://lwn.net/Articles/263130/)
* [User-space RCU](https://lwn.net/Articles/573424/)
* [liburcu.org](https://liburcu.org/)
* [Linux 核心專題: RCU 研究](https://hackmd.io/@sysprog/ry_6RHgS3)
## TODO: 建立並行化的 Redis 雛形
> [mt-redis](https://github.com/jserv/mt-redis) 在 [Redis 3.2.13](https://download.redis.io/releases/) 的基礎之上,進行一系列調整,並運用 urcu 落實並行處理。
從 [mt-redis](https://github.com/jserv/mt-redis) 萃取出修改 (參見 `changes.diff`),施加到 [v3.2 分支](https://github.com/redis/redis/tree/3.2)上,確保所有修改都有效且相容於 Redis 原本的功能。對此進行必要的效能評估,尤其是 Userspace RCU 的 flavor 選擇及考量。
考慮引入〈[並行程式設計: 排程器原理](https://hackmd.io/@sysprog/concurrency-sched)〉提到的 [bluebox](https://github.com/tidwall/bluebox) 專案,展示 [neco](https://github.com/tidwall/neco) 的功能,支持 SET、GET、DEL 和 PING 操作。較單執行緒的 Redis 有更高的資料吞吐量和更低的延遲。評估 M:N threading model 對於 Redis 並行化的助益。
### Userspace RCU 的 flavor 選擇
#### Redis 在現實中的應用
- [ ] Cache
Redis 可以作為 cache ,儲存用戶經常需要存取的資料,藉此減少用戶向資料庫發送請求的數量,降低應用程式的延遲,使用這項技術的公司有 Twitter ,使用 Redis 儲存用戶資料、推文、時間線和趨勢,透過減少發送到資料庫的請求數量,提高平台的性能和可擴展性。當 Redis 作為 cache 時,讀寫比例大約為 10:1 至 100:1 。
- [ ] Session Store
應用程式通常使用 session store 來追蹤用戶身份、登入憑證、個人化資訊、最近的操作等,使用 Redis 以降低延遲以及提高應用程式的效能,在這個使用情境中,讀寫比例大約為 1:1 。
根據上述情境,我打算使用三種測試方式,分別為讀寫比例 100:1 、 10:1 、 1:1 ,來測試哪一種 flavor 最適合並行化的 Redis 。
#### 讀寫比例 10:1
`memtier_benchmark` 預設的讀寫比例就是 10:1 ,測試時將執行緒數量為 4 個,每一個執行緒有 50 個用戶對 mt-redis 進行連線,每個用戶會發送 20000 個請求,並且使用隨機資料,完整的命令如下,同樣的命令執行 100 次,觀察 mt-redis 的延遲以及每秒操作次數。
```shell
memtier_benchmark --hide-histogram -p 6379 --random-data --requests=20000 --json-out-file=FILE_NAME
```
在 10:1 測試中, QSBR 的表現較不穩定,不管是 SET 或是 GET 操作,延遲在剛開始都很高,而且寫入效率在測試剛開始時效率很低,至於其他種 flavor 表現則差不多,但是 Signal-based RCU 雖然在每秒操作次數沒有很突出,但在延遲方面,不管是 SET 還是 GET ,比 Memory-barrier-based RCU 、使用 `sys_membarrier()` 的 RCU 以及 Bullet-proof RCU 都還要低一些。
- [ ] SET Ops/sec
![image](https://hackmd.io/_uploads/HkalkpIBC.png)
- [ ] SET Average Latency
![image](https://hackmd.io/_uploads/ByTbyTLSA.png)
- [ ] SET p50 Latency
![image](https://hackmd.io/_uploads/S1LzJTIBC.png)
- [ ] SET p99 Latency
![image](https://hackmd.io/_uploads/HkyQ1T8BA.png)
- [ ] SET p99.9 Latency
![image](https://hackmd.io/_uploads/H18mya8HR.png)
- [ ] GET Ops/sec
![image](https://hackmd.io/_uploads/Hk75y6ISR.png)
- [ ] GET Average Latency
![image](https://hackmd.io/_uploads/HkA916IHC.png)
- [ ] GET p50 Latency
![image](https://hackmd.io/_uploads/rk8iyTIBR.png)
- [ ] GET p99 Latency
![image](https://hackmd.io/_uploads/ryNnk6LrR.png)
- [ ] GET p99.9 Latency
![image](https://hackmd.io/_uploads/S1cnJ6LSC.png)
#### 讀寫比例 100:1
測試的命令與 10:1 的相同,只是比例改為 100:1 ,完整的命令如下。
```shell
memtier_benchmark --hide-histogram -p 6379 --random-data --ratio=1:100 --requests=20000 --json-out-file=FILE_NAME
```
在 1:100 測試中,在 SET 操作方面,每秒操作次數,每一種 flavor 表現差不多,但在延遲方面, Signal-based RCU 在平均延遲與 p50 的延遲還有 p99 的延遲都贏過其他 flavor ,分佈的位置要低,而在 GET 方面,每一種 flavor 的每秒操作次數也差不多,但在延遲的結果上, Signal-based RCU 的表現全部都較其他種 flavor 要好,而理論上效能最好的 QSBR 略遜於 Signal-based RCU ,但也優於另外三種。
- [ ] SET Ops/sec
![image](https://hackmd.io/_uploads/H19MLTIBA.png)
- [ ] SET Average Latency
![image](https://hackmd.io/_uploads/SkQV86UHR.png)
- [ ] SET p50 Latency
![image](https://hackmd.io/_uploads/BJY4LTIS0.png)
- [ ] SET p99 Latency
![image](https://hackmd.io/_uploads/B11HLTUHC.png)
- [ ] SET p99.9 Latency
![image](https://hackmd.io/_uploads/ByFHI68H0.png)
- [ ] GET Ops/sec
![image](https://hackmd.io/_uploads/SJ1U8aUrC.png)
- [ ] GET Average Latency
![image](https://hackmd.io/_uploads/S1rLUaLrR.png)
- [ ] GET p50 Latency
![image](https://hackmd.io/_uploads/SJiU8p8r0.png)
- [ ] GET p99 Latency
![image](https://hackmd.io/_uploads/S1fw8aLBC.png)
- [ ] GET p99.9 Latency
![image](https://hackmd.io/_uploads/BkvDI6IHA.png)
#### 讀寫比例 1:1
測試的命令與 10:1 的相同,只是比例改為 1:1 ,且將請求數量降回預設數量,因為在測試的時候會因為我電腦的記憶體不足,讓測試的程式自動停止,完整的命令如下。
```shell
memtier_benchmark --hide-histogram -p 6379 --random-data --ratio=1:1 --json-out-file=FILE_NAME
```
在 1:1 的測試中, Signal-based RCU 在 SET 操作方面的每秒操作次數就比其他 flavor 要低,因為 SET 操作次數變多,根據先前對 Signal-based RCU 的敘述, Signal-based RCU 的 writer 效能較差也在這裡得到驗證,造成 SET 的延遲也提高,不像 1:10 和 1:100 的測試可以贏過其他 flavor ,在 GET 的操作中, 反而是 Bullet-proof RCU 與 Memory-barrier-based RCU 每秒操作次數較多。
- [ ] SET Ops/sec
![image](https://hackmd.io/_uploads/HyDZPTIHR.png)
- [ ] SET Average Latency
![image](https://hackmd.io/_uploads/B16-vaUr0.png)
- [ ] SET p50 Latency
![image](https://hackmd.io/_uploads/BkGGPpUSA.png)
- [ ] SET p99 Latency
![image](https://hackmd.io/_uploads/HyOfvT8BA.png)
- [ ] SET p99.9 Latency
![image](https://hackmd.io/_uploads/ByTfPpUH0.png)
- [ ] GET Ops/sec
![image](https://hackmd.io/_uploads/SyNXDTIBA.png)
- [ ] GET Average Latency
![image](https://hackmd.io/_uploads/SyqXDa8H0.png)
- [ ] GET p50 Latency
![image](https://hackmd.io/_uploads/SkN4DpUH0.png)
- [ ] GET p99 Latency
![image](https://hackmd.io/_uploads/B1t4Dp8HA.png)
- [ ] GET p99.9 Latency
![image](https://hackmd.io/_uploads/HyJSvpLHR.png)
根據測試結果,我會使用 Signal-based RCU 作為 mt-redis 的 flavor ,在讀取大於寫入的測試中,他的表現是最好的,理論上來說應該是 QSBR 效能要最好,但是使用 QSBR 時,要很精確的讓執行緒進入 quiescent state ,讓 writer 不要被 block 太久,在 urcu 的 [`test_urcu_qsbr.c`](https://github.com/urcu/userspace-rcu/blob/5eb8d947c57e092129443aa38efffc9fb6ab6816/tests/benchmark/test_urcu_qsbr.c) 中是讓 reader 進行 1024 個讀取操作後再進入 quiescent state ,我在 mt-redis 中採用一樣的方法,但是效能不如 Signal-based RCU ,且一開始的 SET 延遲會很高,所以,我覺得在 mt-redis 這種應用在讀取大於寫入的資料庫,使用 Signal-based RCU 較合適,一開始的 SET 延遲不會很高,且幾乎在所有情況下的延遲都較低。
### 引入 [neco](https://github.com/tidwall/neco)
#### 什麼是 neco?
neco 是一個以 coroutines 提供並行處理的跨平台 C 函式庫,可以在多種作業系統上使用,目標是提供快速的單執行緒並行處理,且提供 API 給網路與 I/O 。
#### 引入 neco 至 mt-redis
- [ ] Coroutine
neco 提供了 coroutine 的功能,包含啟動、休眠、暫停等功能,在執行 coroutine 時,會使用到 [sco](https://github.com/tidwall/sco) 這個 coroutine 排程器,這個排程器是 fair 的,代表每一個 coroutine 的優先順序都一樣,不會有搶佔的情況,一個執行緒只能有一個 coroutine 排程器,第一次執行 `neco_start` 開始一個 coroutine 時,會先初始化 neco 的排程器,引入 coroutine ,我將事件循環放入 coroutine 中,在 `aeMain` 執行的 coroutine 是執行緒第一個執行的 coroutine ,所以會初始化排程器。
```diff
-void aeMain(aeEventLoop *eventLoop)
+void main_coroutine(int argc __attribute__((unused)), void *argv[])
{
+ aeEventLoop *eventLoop = argv[0];
eventLoop->stop = 0;
while (!eventLoop->stop) {
if (eventLoop->beforesleep != NULL)
@@ -526,6 +547,13 @@ void aeMain(aeEventLoop *eventLoop)
}
}
+void aeMain(aeEventLoop *eventLoop)
+{
+ aeEventLoop *ev = eventLoop;
+
+ neco_start(main_coroutine, 1, ev);
+}
```
因為 neco 允許巢狀的 coroutine ,所以無論是寫入或是讀取,每一個事件的處理函式都會開始一個新的 coroutine 。
```diff
+void rwfileProc(int argc __attribute__((unused)), void *argv[])
+{
+ int op = *(int *)argv[0];
+ aeFileEvent *fe = argv[1];
+ aeEventLoop *eventLoop = argv[2];
+ int fd = *(int *)argv[3];
+ int mask = *(int *)argv[4];
+ if (op == AE_READABLE)
+ fe->rfileProc(eventLoop, fd, fe->clientData, mask);
+ else if (op == AE_WRITABLE)
+ fe->wfileProc(eventLoop, fd, fe->clientData, mask);
+ else
+ return;
+}
+
/* Process every pending time event, then every pending file event
* (that may be registered by time event callbacks just processed).
* Without special flags the function sleeps until some file event
@@ -455,15 +471,18 @@ int aeProcessEvents(aeEventLoop *eventLoop, int flags)
*
* Fire the readable event if the call sequence is not
* inverted. */
+ aeEventLoop *ev = eventLoop;
if (!invert && fe->mask & mask & AE_READABLE) {
- fe->rfileProc(eventLoop, fd, fe->clientData, mask);
+ int op = AE_READABLE;
+ neco_start(rwfileProc, 5, &op, fe, ev, &fd, &mask);
fired++;
}
/* Fire the writable event. */
if (fe->mask & mask & AE_WRITABLE) {
if (!fired || fe->wfileProc != fe->rfileProc) {
- fe->wfileProc(eventLoop, fd, fe->clientData, mask);
+ int op = AE_WRITABLE;
+ neco_start(rwfileProc, 5, &op, fe, ev, &fd, &mask);
fired++;
}
}
@@ -472,7 +491,8 @@ int aeProcessEvents(aeEventLoop *eventLoop, int flags)
* after the writable one. */
if (invert && fe->mask & mask & AE_READABLE) {
if (!fired || fe->wfileProc != fe->rfileProc) {
- fe->rfileProc(eventLoop, fd, fe->clientData, mask);
+ int op = AE_READABLE;
+ neco_start(rwfileProc, 5, &op, fe, ev, &fd, &mask);
fired++;
}
}
@@ -516,8 +536,9 @@ int aeWait(int fd, int mask, long long milliseconds)
}
}
```
- [ ] Inter-Process Communication
:::warning
TODO: 將 mt-redis 執行緒 IPC 的方式改為 pipe 或是 eventfd 以使用 `neco_read` 與 `neco_write` 來獲取更好的 I/O 效能。
目前使用 pipe 的方法會導致寫入事件錯誤,根據 `server.c` 程式碼中 `server_event_process` 函式敘述,會發生 socket 傳送的 `buf` 與 command_requests 佇列中數量不一致的情況。
```c
// Number of request in command_requests NOT 1:1 with num of bytes inside
// socketpairs
qnode = __cds_wfcq_dequeue_blocking(&server.command_requests_head,
&server.command_requests_tail);
// ToDo: need fine control of number of commands to be executed.
// the sockerpair buf can be overflowed when num of connections increase, so
// Num of requests in command_requests list is NOT 1:1 with num of bytes in
// socketpair buf, the code has to deal with this mismatch.
```
:::
#### 效能測試
效能測試最主要以 cache server 的應用場景來做效能測試,所以採用讀寫比例 100:1 的命令,完整命令如下,比較的項目有加入 neco 的 mt-redis 、沒有加入 neco 的 mt-redis 、使用 neco 的 [bluebox](https://github.com/tidwall/bluebox/tree/main) 與 Valkey 。
```shell
memtier_benchmark --hide-histogram -p 6379 --random-data --ratio=1:100 --json-out-file=FILE_NAME
```
- [ ] Total Ops/sec
![ops](https://hackmd.io/_uploads/B13fQbxUR.png)
- [ ] Total Average Latency
![latency](https://hackmd.io/_uploads/S1-mQWxUA.png)
- [ ] Total p50 Latency
![p50](https://hackmd.io/_uploads/BJHXQWgIA.png)
- [ ] Total p99 Latency
![p99](https://hackmd.io/_uploads/Hk97Q-lL0.png)
- [ ] Total p99.9 Latency
![p999](https://hackmd.io/_uploads/rkam7WxUA.png)
從測試結果可以觀察到, mt-redis 的效能是可以勝過 bluebox 這個迷你 Redis 實作的,但是對比有沒有加入 neco ,加入 neco 後與加入 neco 之前效能並沒有差太多,在延遲部份,平均延遲 mt-redis 、加入 neco 之前的 mt-redis 與 bluebox 三者是差不多的,但在 tail latency 延遲上, bluebox 表現最好,而 mt-redis 在加入 neco 前後依然沒有太大的區別。
### 執行緒數量對 mt-redis 的影響
在測試時,原本效能都差不多的,將執行緒數量調整到 4 個以後,調整過後,效能提高了不少。
```diff
getRandomHexChars(server.runid, CONFIG_RUN_ID_SIZE);
server.configfile = NULL;
server.executable = NULL;
- server.threads_num = 8;
+ server.threads_num = 4;
server.hz = CONFIG_DEFAULT_HZ;
server.runid[CONFIG_RUN_ID_SIZE] = '\0';
server.arch_bits = (sizeof(long) == 8) ? 64 : 32;
```
調整之後再進行測試,使用的命令與測試引入 neco 是一樣的。
- [ ] Total Ops/sec
![ops](https://hackmd.io/_uploads/r1W9Gse8C.png)
- [ ] Total Average Latency
![latency](https://hackmd.io/_uploads/r1BcMieUA.png)
- [ ] Total p50 Latency
![p50](https://hackmd.io/_uploads/HkFcfsgIC.png)
- [ ] Total p99 Latency
![p99](https://hackmd.io/_uploads/BJ2cfixUC.png)
- [ ] Total p99.9 Latency
![p999](https://hackmd.io/_uploads/BJxifsl8R.png)
在進行測試時,發現引入 neco 之後,效能依然沒有提升太多,所以提高了執行緒數量,效能依然沒有提升,所以改變想法,將執行緒數量降到 4 個,結果發現得到巨大的提升,甚至超越 bluebox 這個迷你的 Redis ,所以我又做了以下測試,從 1 ~ 16 ,測試每一個執行緒數量對 mt-redis 效能的影響,測試命令如下。
```shell
taskset -c 11-15 memtier_benchmark --hide-histogram -p 6379 --random-data --ratio=1:100
```
- [ ] Total Ops/sec
![ops](https://hackmd.io/_uploads/HkGq4JQwC.png)
使用 `perf` 測量 context switch 的數量與 cache miss rate ,這兩個因素是影響多執行緒效能的關鍵,命令如下。
```shell
sudo perf stat -d ./src/redis-server ./mt-redis.conf --appendonly no --save ""
```
- [ ] Cache Miss
![cache_miss](https://hackmd.io/_uploads/SyriVkXvA.png)
- [ ] Context Switch
![context_switch](https://hackmd.io/_uploads/Syk2Vy7DA.png)
參考 NGINX ,對 worker 設定 CPU affinity 並再次測量 context switch 次數與執行緒數量對 mt-redis 效能的影響,同時也紀錄 context switch 數量與 cache miss rate 。
```diff
static void *q_thread_run(void *data)
{
q_thread *thread = data;
+ int cpu_id = thread->cpu_id;
srand(ustime() ^ (int) pthread_self());
+ cpu_set_t cpuset;
+ CPU_ZERO(&cpuset);
+ CPU_SET(cpu_id, &cpuset);
+ pthread_setaffinity_np(pthread_self(), sizeof(cpuset), &cpuset);
+ printf("thread sched_getcpu = %d\n", sched_getcpu());
+
return thread->fun_run(thread->data);
}
```
設定 server 執行緒的 affinity 與 master 執行緒的 affinity ,我讓這兩個執行緒都執行在 CPU 0 上。
```diff
q_workers_run();
q_master_run();
+
+ // Set server thread's affinity
+ cpu_set_t cpuset;
+ CPU_ZERO(&cpuset);
+ CPU_SET(0, &cpuset);
+ pthread_setaffinity_np(pthread_self(), sizeof(cpuset), &cpuset);
+
aeSetBeforeSleepProc(server.el, beforeSleep, NULL);
aeMain(server.el);
aeDeleteEventLoop(server.el);
```
```diff
int q_master_run(void)
{
- q_thread_start(&master.qel.thread);
+ q_thread_start(&master.qel.thread, 0);
return C_OK;
}
```
另外, worker 的 CPU affinity ,我使用 `cpu_count` 函式取得目前電腦的 CPU 數量,接著讓兩個執行緒執行在同一個 CPU ,因為 server 執行緒與 master 執行緒共用 CPU 0 ,所以跳過 CPU 0 從 CPU 1 開始計算。
```diff
+int cpu_count()
+{
+ cpu_set_t cpuset;
+ sched_getaffinity(0, sizeof(cpuset), &cpuset);
+ return CPU_COUNT(&cpuset);
+}
+
int q_workers_run(void)
{
uint32_t i, thread_count;
q_worker *worker;
+ int cpu_num = cpu_count();
thread_count = (uint32_t) num_worker_threads;
serverLog(LL_NOTICE, "fn: q_workers_run, start %d worker thread",
@@ -439,7 +449,7 @@ int q_workers_run(void)
for (i = 0; i < thread_count; i++) {
worker = darray_get(&workers, i);
- q_thread_start(&worker->qel.thread);
+ q_thread_start(&worker->qel.thread, ((i + 2) / 2) % cpu_num);
}
return C_OK;
```
- [ ] Total Ops/sec
![ops_aff](https://hackmd.io/_uploads/Bkma4kXPR.png)
- [ ] Cache Miss
![cache_miss_aff](https://hackmd.io/_uploads/SkyA4y7P0.png)
- [ ] Context Switch
![context_switch_aff](https://hackmd.io/_uploads/rkVC4JXDA.png)
由測試結果可以發現,在沒有加入 CPU affinity 時, mt-redis 效能最好的時候是在 4 個執行緒,恰好這個時候的 context switch 數量與 cache miss rate 都很少,因此效能會最好,但觀察吞吐量的曲線就發現, mt-redis 的擴展性很差,給予越多的執行緒,效能並沒有得到相對應的提升,反而還降低不少,在大於 4 個執行緒時, context switch 與 cache miss 都快速增長,造成效能顯著的下降,在加入 CPU affinity 後,效能有明顯的提升, cache miss rate 相對於沒有 CPU affinity 時都要低,另外, context switch 數量有很明顯的改善,雖然擴展性與性能不只與 context switch 數量與 cache miss rate 有關,因為測試時用到的 `memtier_benchmark` 會用到 4 個執行緒,所以 mt-redis 執行緒數量增加時,就要與測試工具共用一個 CPU ,造成 context switch 與 cache miss rate 增加,但是在執行緒數量較少時,可以看出效能有很明顯的提升,所以加入 CPU affinity 是有助於提升整體 mt-redis 的性能的。
:::info
根據[測試結果](https://github.com/yeh-sudo/mt-redis?tab=readme-ov-file#performance) ,吞吐量雖然上升,但是延遲也顯著增加,不知道延遲跟什麼因素有關係?
```
============================================================================================================================
Type Ops/sec Hits/sec Misses/sec Avg. Latency p50 Latency p99 Latency p99.9 Latency KB/sec
----------------------------------------------------------------------------------------------------------------------------
Sets 38465.04 --- --- 4.11819 2.28700 23.80700 30.71900 2962.48
Gets 384227.73 0.00 384227.73 0.52990 0.27900 16.31900 24.31900 14967.33
Waits 0.00 --- --- --- --- --- --- ---
Totals 422692.77 0.00 384227.73 0.85643 0.28700 18.04700 26.36700 17929.81
```
:::
### `memtier_benchmark` 的 pipeline 參數
`memtier_benchmark` 測試中有一個 pipeline 參數,允許在不等待每個單獨響應的情況下發送多個請求,預設值是 1 ,代表每發送 1 個請求, `memtier_benchmark` 就會等待 redis 回傳這個請求的結果,才會發送下一個請求,但在現在的後端開發或是應用程式開發中,都是使用[非同步的技巧](https://developer.mozilla.org/zh-TW/docs/Learn/JavaScript/Asynchronous/Introducing#%E9%9D%9E%E5%90%8C%E6%AD%A5_javascript),代表發送請求後,不等待回傳結果就去執行其他事情,避免了阻塞的問題,而 pipeline 參數就有點像是 JavaScript 的非同步處理,當 pipeline 設置為 `n` 時,就會同時發送 `n` 個請求,並且過程中不等待 redis 回應。
為了測試這個參數對 mr-redis 與 ValKey 的影響,設計以下實驗,依次提高 pipeline 的值,並紀錄過程中的吞吐量與延遲等數據,來模擬更真實的使用情境,測試參數如下,測試時加入了 `--random-data` ,因為真實的應用上,資料不會都是同樣的值,且每次執行都用 `-x` 參數測試 10 次並取最好的結果,最後,執行命令時使用 [`taskset`](https://man7.org/linux/man-pages/man1/taskset.1.html) 目的是為了不要讓 `memtier_benchmark` 的程式影響到 mt-redis 或是 ValKey 。
```shell
taskset -c 11-15 memtier_benchmark --hide-histogram -p 6379 --pipeline=n --random-data -x 10
```
:::info
這邊取 10 次中最好的結果,而不是 10 次中的平均,是因為 `memtier_benchmark` 有 bug ,將測試結果輸出到 JSON 檔案時,平均數據的延遲都是 0 ,不知道是哪一部分出了問題,之後研究一下,然後發一個 PR 解決這個錯誤。以下為 10 次測試跑完之後輸出的平均數據。
```
AGGREGATED AVERAGE RESULTS (10 runs)
============================================================================================================================
Type Ops/sec Hits/sec Misses/sec Avg. Latency p50 Latency p99 Latency p99.9 Latency KB/sec
----------------------------------------------------------------------------------------------------------------------------
Sets 84032.73 --- --- 5.05352 2.83100 20.09500 30.46300 6471.99
Gets 839403.88 0.00 839403.88 4.66573 2.78300 19.19900 29.82300 32698.40
Waits 0.00 --- --- --- --- --- --- ---
Totals 923436.62 0.00 839403.88 4.70102 2.78300 19.19900 29.82300 39170.40
```
但在 JSON 檔案中為 0 。
```json
"Percentile Latencies": {
"p50.00": 0.000,
"p99.00": 0.000,
"p99.90": 0.000,
"Histogram log format": {
"Compressed Histogram": "HISTFAAAACB4nJNpmSzMwMDAyAABTFCaC0zyOznYf4AIMAIAQ0gDFQ=="
}
}
```
:::
- [ ] Total Ops/sec
![ops](https://hackmd.io/_uploads/ry0VeW6LA.png)
- [ ] Total Average Latency
![latency](https://hackmd.io/_uploads/B1NBlWpUC.png)
- [ ] Total p50 Latency
![p50](https://hackmd.io/_uploads/HkOBxZT8C.png)
- [ ] Total p99 Latency
![p99](https://hackmd.io/_uploads/rkaHxZaUR.png)
- [ ] Total p99.9 Latency
![p999](https://hackmd.io/_uploads/S1x8lW6UA.png)
可以發現,當 pipeline 變大時, 8 個執行緒與 16 個執行緒的吞吐量最後都可以到達百萬等級,但是 ValKey 的成長幅度就很小,在延遲方面, mt-redis 在平均延遲與 p50 延遲都是贏過 ValKey ,但在 tail latency 的部份,在 pipeline 數量拉高之後, mt-redis 的 tail latency 可以超越 ValKey ,前面有提到,根據[測試結果](https://github.com/yeh-sudo/mt-redis?tab=readme-ov-file#performance) ,吞吐量雖然上升,但是延遲也顯著增加,這時 pipeline 為 1 , mt-redis 的 tail latency 是不如 ValKey 的,代表 ValKey 對大量並行的請求處理能力不如 mt-redis 。
## TODO: 使 Valkey 具備並行處理能力
針對近期的 [Valkey](https://valkey.io/),移植上述 urcu 在內的修改,使其運作符合預期。
> 專題所有的成果應以開放原始碼的形式發布,因此該針對 [Valkey](https://valkey.io/)
目前 mt-redis 的成熟度還不足以將成果整合到 ValKey 中,原因是還沒有找到如何提升性能的同時,有效的降低延遲,當測試沒有使用 pipeline 參數時,雖然吞吐量是勝過 ValKey 的,但同時 mt-redis 的 tail latency 也變得很高,比 ValKey 多出不少,並且, mt-redis 也沒有確認過 thread safety 等議題,也沒有進行單元測試,之後可以考慮整合 ValKey 的[單元測試](https://github.com/valkey-io/valkey/tree/unstable/tests) ,確保在 mt-redis 上的改動是相容於 ValKey 的。
## 延伸問題
* 如何在設定 CPU affinity 的情況下有效降低延遲?
* 為何引入 neco 後對效能沒有太大的提升?
* 引入單元測試到 mt-redis 以確保改動都相容於 ValKey 。
## 參考資訊
[valkeyri](https://github.com/wqld/valkeyri): Provide an in-kernel cache for valkey or redis