database
組員: 109062274, 109062314, 109062315
本次我們實作非常多優化,主要以並行上的優化為主。我們為每一項完整的優化設定一個 branch (以 feat
開頭),使實驗可以透過 merge 各個 branch 完成。
優化的功能列序如下。
featRWFileMgr
: 以 StampedLock
優化讀寫同步化featBlockId
: 簡化計算固定 hashCode
與 toString
行為featPage
: 以 ReentrantLock
優化讀寫同步化,並減少寫入次數featBufMgrWaitQueue
: 優化 waiting queue 的行為featBuffer
、BufferPoolMgr
: 移除不必要的同步機制以下針對各項進行說明;另外由於我們的 commit 說明都頗清楚,所以其實可以直接閱讀得知實作細節。
BufferPoolMgr
對 BufferPoolMgr
的優化主要是把其 method 拿掉 synchronized
。並在其 data member 加上 lock,或把 data member 改成 Atomic
。
Buffer::pin(BlockId blk)
synchronized
拿掉,希望多個 thread 可以 pin bufferPool
,但沒有過testcase所以維持synchronized。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
- transform variable
pins
intoAtomicInteger
getVal/setVal
is based on thread-safepage
flush
is based on given lock- others are just returning member reference
Page
read/write/append
- since
FileMgr
is thread-safe
getVal/setVal
using lock
- Create lock member to protect
content-related
section- Use
ByteBuffer
to reduce time of writecontent
insetVal
FileMgr
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
No synchronization/lock needed for isNew attribute, make it readonly
- Read method: use pessimistic read
- Size method: use very-optimistic read
- Write & delete method: use write lock
BlockId
調整使 hashCode
和 toString
方法可以直接取出恆定的計算結果: 將該恆定的計算結果於建構時計算並保留於成員。
將實驗略分為三組:
optFilePackage
: 包含所有與 File
package 有關的優化。optBufferPackage
: 包含所有與 Buffer
package 相關的優化。release
: 整合所有優化。對照組為 dev
,其只包含與環境設定相關的調整 (Makefile 等)。
我們使用 Micro Bench
進行實驗,針對本次作業的六個可調參數分別進行遍歷:
BUFFER_POOL_SIZE
: 50, 500, 5000RW_TX_RATE
: 0.0, 0.5, 1TOTAL_READ_COUNT
: 10, 20LOCAL_HOT_COUNT
: 2, 10WRITE_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 | ||
High Pressure2 | ||
High Pressure3 |
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 | ||
Low Pressure2 | ||
Low Pressure3 |
我們寫一個 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 |
高壓測試
可以看到 optFilePackage 和 release 有明顯提升,但 optBufferPackage 跟 dev 沒相差多少,這是因為在 BufferPoolMgr
中跟 pin()
和 unpin()
相關的 method 沒有把 synchronized 拿掉,而造成 bottleneck,多個 thread 不能併行執行 pin
unpin
。在高壓測試中,這個 bottleneck 會更加明顯,我們較看不到 optBufferPackage 的優化。
低壓測試
前兩個參數設定以沒有 write 操作為原則去調整其他參數,可以發現 Buffer package
的優化有差不多 20% 的提升,而 File package
的優化有差不多 30% 的提升,而兩種優化合起來可以有多達 40% 的提升。而第三種參數設定多了些 write 操作,相比 dev
和 Buffer package
有了 70% 的提升,代表我們在 File package
對讀寫操作的優化十分成功。
整體優化效果
這裡將 216 種參數設定得出的優化效果取平均值,可以發現我們File package
的優化效果竟然高達 50%,而之所以可以提升這麼多,是因為我們特別針對同時多個讀、單一個寫、進行讀時會採用 Optimistic read 去進行優化,並對一些 BlockID
的內容提前進行計算等等,使得這部分的效能提升非常多。而 Buffer package
僅只有 10% 的提升,原因大致上就是我們對BufferPoolMgr
中跟 pin()
和 unpin()
的優化沒有處理恰當,如同高壓測試中所提到的描述。而整體看下來,最後合併版本 release
的 throughput 提升率多達快 60%,且 latency 也減少了快 30%,可以看出此次的實作效果十分成功。