Try   HackMD
tags: database

Assignment 4 report 1

組員: 109062274, 109062314, 109062315

概述

本次我們實作非常多優化,主要以並行上的優化為主。我們為每一項完整的優化設定一個 branch (以 feat 開頭),使實驗可以透過 merge 各個 branch 完成。

優化的功能列序如下。

  • File Package
    • featRWFileMgr: 以 StampedLock 優化讀寫同步化
    • featBlockId: 簡化計算固定 hashCodetoString 行為
    • featPage: 以 ReentrantLock 優化讀寫同步化,並減少寫入次數
  • Buffer Package
    • featBufMgrWaitQueue: 優化 waiting queue 的行為
    • featBufferBufferPoolMgr: 移除不必要的同步機制

以下針對各項進行說明;另外由於我們的 commit 說明都頗清楚,所以其實可以直接閱讀得知實作細節。

Buffer Package

BufferPoolMgr

BufferPoolMgr 的優化主要是把其 method 拿掉 synchronized。並在其 data member 加上 lock,或把 data member 改成 Atomic

Buffer::pin(BlockId blk)

  • 優化 : 把 synchronized 拿掉,希望多個 thread 可以 pin bufferPool,但沒有過testcase所以維持synchronized。
  • 想法 : 我們不希望當一個 thread 在 swap out block 的時候,另一個 thread 想要 pin 同一個 Buffer (或是也想 swap out 同一個 Buffer)。因此,我們的做法是根據每一個不同的 Buffer 上一個 lock (用 Buffer::isSwapLock() 取得該lock)。首先找尋 bufferPool 有沒有 hit 同一個 block , 如果沒有再找尋哪一個 Buffer 沒被 pin 過,我們也加 buffer.isSwapLock().tryLock() 條件來判斷是否這個buffer 正在 swapping,沒有的話才能取得 Buffer 的 lock 並做 swapping。如果有 hit 同一個 block,我們還是要取得此 Buffer 的 lock,因為有可能同時另一個 thread 想要做 swapping,這樣會造成 Buffer 中的 blockId 造成不一致。

BufferMgr

  • Implement loose FIFO algorithm

    not just wake up the fist element in waiting queue, but with WAKE_RATIO parameter, 0 means strict FIFO mode, to decide the ratio in queue to wake up from head

    即我們不希望嚴格的 FIFO,改實作為允許當喚醒由 WAKE_RATIO 外部參數決定之區間大小時皆可繼續執行的邏輯。

  • Reduce critical section

    the synchronized keyword only contain the operaions of bufferPool

Buffer

  • Use atomic integer to get rid of monitor method
    • transform variable pins into AtomicInteger
  • Remove unneeded monitors
    • getVal/setVal is based on thread-safe page
    • flush is based on given lock
    • others are just returning member reference

File Package

Page

  • Remove monitor of read/write/append
    • since FileMgr is thread-safe
  • Restrict CS of getVal/setVal using lock
    • Create lock member to protect content-related section
    • Use ByteBuffer to reduce time of write content in setVal

FileMgr

  • Replace plain IoChannel with self-defined data structure LockableFile

    file: original IoChannel object
    sl: StampedLock as lock with read optimization
    deleted: atomic boolean mark to check whether a file is deleted

  • Optimize readonly attribute

    No synchronization/lock needed for isNew attribute, make it readonly

  • Use Java Stampedlock
    • Read method: use pessimistic read
    • Size method: use very-optimistic read
    • Write & delete method: use write lock

BlockId

調整使 hashCodetoString 方法可以直接取出恆定的計算結果: 將該恆定的計算結果於建構時計算並保留於成員。

實驗

實驗介紹與準備

將實驗略分為三組:

  1. branch optFilePackage: 包含所有與 File package 有關的優化。
  2. branch optBufferPackage: 包含所有與 Buffer package 相關的優化。
  3. branch release: 整合所有優化。

對照組為 dev,其只包含與環境設定相關的調整 (Makefile 等)。

我們使用 Micro Bench 進行實驗,針對本次作業的六個可調參數分別進行遍歷:

  • BUFFER_POOL_SIZE: 50, 500, 5000
  • RW_TX_RATE: 0.0, 0.5, 1
  • TOTAL_READ_COUNT: 10, 20
  • LOCAL_HOT_COUNT: 2, 10
  • WRITE_RATIO_IN_RW_TX: 0., 0.5, 1.
  • HOT_CONFLICT_RATE: 0.001, 0.01

使用 Python + Makefile 撰寫腳本進行實驗與數據搜集,共實驗了216種實驗結果。

實驗環境

CPU RAM Disk OS
Intel Core i3-12100 3.3GHz 16GB 512GB SSD Ubuntu 22.04

實驗分析

我們以高壓以及低壓測試進行分析,各個測試採3種參數來分析及佐證我們的優化效果,對照組為dev。最後再根據216種實驗結果,找出整體優化效果平均與最好的數值及該參數之設定

高壓測試

Parameter Name Buffer Pool Size RW TX rate Total Read Count Local Hot Count Write Ratio in RW TX Hot Conflict Rate
High Pressure1 50 1 20 2 1 0.01
High Pressure2 50 1 20 10 1 0.01
High Pressure3 500 1 20 10 1 0.01

高壓測試結果

Type Throughput (Higher Better) Latency (Lower Better)
High Pressure1
Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →
Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →
High Pressure2
Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →
Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →
High Pressure3
Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →
Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

低壓測試 (為了凸顯優化效果,BufferPool size 固定為 50)

Parameter Name Buffer Pool Size RW TX rate Total Read Count Local Hot Count Write Ratio in RW TX Hot Conflict Rate
Low Pressure1 50 0 10 10 0 0.001
Low Pressure2 50 0 20 2 0 0.001
Low Pressure3 50 0.5 10 10 0.5 0.001

低壓測試結果

Type Throughput (Higher Better) Latency (Lower Better)
Low Pressure1
Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →
Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →
Low Pressure2
Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →
Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →
Low Pressure3
Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →
Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

整體優化效果 (Average perfomance)

我們寫一個 python script 來分析 optFilePackage、optBufferPackage 以及 release 對比對照組 dev 實驗結果,總共 216 種參數設定。

Optimizaton Level Committed提升(%) Avg Latency減少(%)
optBufferPackage 10.23 8.26
optFilePackage 50.16 29.13
release 57.26 29.81

Image Not Showing Possible Reasons
  • The image was uploaded to a note which you don't have access to
  • The note which the image was originally uploaded to has been deleted
Learn More →

實驗分析解釋

  • 高壓測試
    可以看到 optFilePackage 和 release 有明顯提升,但 optBufferPackage 跟 dev 沒相差多少,這是因為在 BufferPoolMgr 中跟 pin()unpin() 相關的 method 沒有把 synchronized 拿掉,而造成 bottleneck,多個 thread 不能併行執行 pin unpin。在高壓測試中,這個 bottleneck 會更加明顯,我們較看不到 optBufferPackage 的優化。

  • 低壓測試
    前兩個參數設定以沒有 write 操作為原則去調整其他參數,可以發現 Buffer package 的優化有差不多 20% 的提升,而 File package 的優化有差不多 30% 的提升,而兩種優化合起來可以有多達 40% 的提升。而第三種參數設定多了些 write 操作,相比 devBuffer package 有了 70% 的提升,代表我們在 File package 對讀寫操作的優化十分成功。

  • 整體優化效果
    這裡將 216 種參數設定得出的優化效果取平均值,可以發現我們File package 的優化效果竟然高達 50%,而之所以可以提升這麼多,是因為我們特別針對同時多個讀、單一個寫、進行讀時會採用 Optimistic read 去進行優化,並對一些 BlockID 的內容提前進行計算等等,使得這部分的效能提升非常多。而 Buffer package 僅只有 10% 的提升,原因大致上就是我們對BufferPoolMgr 中跟 pin()unpin() 的優化沒有處理恰當,如同高壓測試中所提到的描述。而整體看下來,最後合併版本 release 的 throughput 提升率多達快 60%,且 latency 也減少了快 30%,可以看出此次的實作效果十分成功。