2025q1 Homework1 (ideas)

contributed by <Andrewtangtang>

並行程式設計

並行化的 Redis 實作

文章連結

名詞解釋

• 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實作

文章連結

名詞解釋

• 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 是否可作為 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 的延遲回收機制，可能導致較高的記憶體管理成本。