# 2025q1 Homework1 (ideas)
contributed by <`Andrewtangtang`>

## 並行程式設計

### 並行化的 Redis 實作
[文章連結](https://hackmd.io/@sysprog/B1W2HKTER)

#### 名詞解釋
- redis:in-memory的資料庫
- RCU:高效同步機制，可以允許一個執行序write，多個執行序read(具體待查)
- userspace RCU:reader 與 writer 不直接進行同步，允許多個 reader 在 writer 運作時進行讀取。
- quiescent state(在選擇 flavor 時出現)
- neco:跨平台處理的 C 函式庫，在多種作業系統可使用，目標提供快速單執行序並行處理
- sco 排成器:排程器是 fair 的，使用在 neco coroutine中
- 巢狀 coroutine(待查):

#### 筆記
- 因為redis本質是單執行序執行的，希望可以提升併行表現
- why RCU:同步機制都會使用 lock ，而只要有lock都會造成效能瓶頸，因此需要尋求 lock free programming or RCU
- urcu 的五種 vlavor(細節待查)，各自有適合使用的場景，作者利用實驗
測試後最後選擇 `Signal-based RCU`，理論要使用 `QSBR` () why?
- Signal-based RCU using sys_membarrier() system call (liburcu)
- Memory-barrier-based RCU (liburcu-mb)
- Signal-based RCU (liburcu-signal)
- Bullet-proof RCU (liburcu-bp)
- QSBR (liburcu-qsbr)
- inter-Process Communication(待理解)
- redis 用socket 但 neco 使用 pipe or eventfd，會導致會發生socket 傳送的 buf 與 command_requests 佇列中數量不一致的情況
- 實驗結果: mt-redis 、加入 neco 之前的 mt-redis 與 bluebox 差不多
- 將thread 調到 4 效能會變好，經實驗測量 (4、5) threads 效能最好 cache miss context switch最少
- 實驗結論: redis 擴展性很差，多執行序效能不加
- 參考 nginx 設置 CPU affinity (具體設置原理待理解)，可以達到效能的提升
- 還未找到吞吐量上升但延遲增加的具體原因
#### TODO
- 還需要更多測試來證明多執行序處理沒問題
- 未經單元測試(Valkey)有
- 如何在設定 CPU affinity 下降低延遲
- 為何引入 neco 效能沒提升

### RCU實作
[文章連結](https://hackmd.io/@sysprog/HkkWZ20B0)
#### 名詞解釋
- RCU 的主要兩個元件
- RCU 讀側臨界區(RCU Read-Side Critical Section，以下縮寫 cs) : 由 `rcu_read_lock()` 和 `rcu_read_unlock()` 包圍的程式碼區域，該區域內部的 reader 可以安全的讀取 RCU 保護的共享資料
- RCU 寬限期 (RCU Grace Period):開始於 writer 開始修改 RCU 保護資料到 GP 開始前所有 reader 結束的時間。 RCU 保證所有在 GP 開始之前進入 cs 的 reader 都已完成。`synchronize_rcu()` 用於等待一個寬限期的結束。
- Slot-Pair:
- 每個 tsv（thread specific variable?）擁有兩個 slot：一個放當前一個放下一筆(使用r reference counter)
- Reader 讀取 tsv 版本號 (vp)來判斷當前 slot 是哪一個，讀取後保留 slot 值快照，
- Writer 將新資料寫入下一個 slot ，當 reader 都讀完後，writer 會切換當前 slot ，讓 Reader 讀取新數據，當舊 slot 沒有活躍的 Reader，才會被刪除或釋放
- Slot-List
- 透過鏈結串列維護讀取引用(reader subscription slots)，每個執行緒都有一個 slot ，第一次讀取時， reader 分配一個 slot 並將值串列的頭部複製到 slot 中(具體機制待理解)
- Reader 所有的操作都是無鎖的
- Writer 對引用值的鏈結串列執行回收，值在最後的一次寫入時被釋放

#### 筆記
- userspace RCU 已經有很多應用場景，但程式碼規模龐大，整合較困難，所以嘗試評估 [ctp:C Thread Primitives](https://github.com/nicowilliams/ctp) 是否可作為 userspace RCU 的替代選擇
- CTP
- 建構在 thread-safe variable (TSV待理解)，確保 reader 執行緒在無 lock 狀態下運行，writer 會等到最後引用的 reader 執行緒完成讀取後才會寫入
- 提供一種機制確保資料在多執行緒中保持一致性並且防止 race condition
- 每個 reader 執行緒可以有自己的 slot 能夠儲存目前的副本，類似 thread specific data(待詳細了解)，但透過安全機制更新和管理這些值
- CTP 和 userspace RCU 效能評估(7 reader 1 writer)
- 測試結果都會改變但 qsbr 和 memb 的在 reader 表現最好
- writer CTP 可以表現得比其他好很多
- 維持 writer 不同 reader 執行緒數量 qsbr 在多執行緒的表現最好
- 維持 writer 考量多執行緒 reader 對效能影響，多執行緒的 reader 情況下 writer 的效能增加
- 設定 CPU affinity 可以優化效能
- 作者優化的部分
- 修正 slot-list 中 `grow_slots()`
- CTP 優點
- Writer 邏輯簡單CTP 依賴引用計數，而不是管理多個資料版本與寬限期（Grace Period），讓 Writer 操作更簡單。
- 即時記憶體回收當最後一個引用被刪除時，記憶體立即釋放，減少不必要的記憶體使用。
- CTP 缺點
- Writer 可能會被 Reader 阻塞，而 userspace RCU 允許 writer 繼續執行，不需等待 Reader
- 記憶體頻繁分配與釋放成本高: CTP 需要頻繁分配與釋放記憶體，相比於 URCU 的延遲回收機制，可能導致較高的記憶體管理成本。