# 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
- [ ] SET Average Latency
- [ ] SET p50 Latency
- [ ] SET p99 Latency
- [ ] SET p99.9 Latency
- [ ] GET Ops/sec
- [ ] GET Average Latency
- [ ] GET p50 Latency
- [ ] GET p99 Latency
- [ ] GET p99.9 Latency
#### 讀寫比例 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
- [ ] SET Average Latency
- [ ] SET p50 Latency
- [ ] SET p99 Latency
- [ ] SET p99.9 Latency
- [ ] GET Ops/sec
- [ ] GET Average Latency
- [ ] GET p50 Latency
- [ ] GET p99 Latency
- [ ] GET p99.9 Latency
#### 讀寫比例 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
- [ ] SET Average Latency
- [ ] SET p50 Latency
- [ ] SET p99 Latency
- [ ] SET p99.9 Latency
- [ ] GET Ops/sec
- [ ] GET Average Latency
- [ ] GET p50 Latency
- [ ] GET p99 Latency
- [ ] GET p99.9 Latency
根據測試結果，我會使用 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
- [ ] Total Average Latency
- [ ] Total p50 Latency
- [ ] Total p99 Latency
- [ ] Total p99.9 Latency
從測試結果可以觀察到， 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
- [ ] Total Average Latency
- [ ] Total p50 Latency
- [ ] Total p99 Latency
- [ ] Total p99.9 Latency
在進行測試時，發現引入 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
使用 `perf` 測量 context switch 的數量與 cache miss rate ，這兩個因素是影響多執行緒效能的關鍵，命令如下。
```shell
sudo perf stat -d ./src/redis-server ./mt-redis.conf --appendonly no --save ""
```
- [ ] Cache Miss
- [ ] Context Switch
參考 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
- [ ] Cache Miss
- [ ] Context Switch
由測試結果可以發現，在沒有加入 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
- [ ] Total Average Latency
- [ ] Total p50 Latency
- [ ] Total p99 Latency
- [ ] Total p99.9 Latency
可以發現，當 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
Sign in with Wallet
Connect another wallet