###### tags: `database`

# Assignment 4 report 1

組員: 109062274, 109062314, 109062315

## 概述

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

優化的功能列序如下。

* File Package
* `featRWFileMgr`: 以 `StampedLock` 優化讀寫同步化
* `featBlockId`: 簡化計算固定 `hashCode` 與 `toString` 行為
* `featPage`: 以 `ReentrantLock` 優化讀寫同步化，並減少寫入次數
* Buffer Package
* `featBufMgrWaitQueue`: 優化 waiting queue 的行為
* `featBuffer`、`BufferPoolMgr`: 移除不必要的同步機制

以下針對各項進行說明；另外由於我們的 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`

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

## 實驗

### 實驗介紹與準備

將實驗略分為三組:

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|||
|High Pressure2|||
|High Pressure3|||

#### 低壓測試 (為了凸顯優化效果，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|||
|Low Pressure2|||
|Low Pressure3|||

#### 整體優化效果 (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


<!-- #### Buffer優化率高於100%的參數設定

|Condition|Buffer Pool Size|RW TX rate|Total Read Count|Local Hot Count|Write Ratio in RW TX|Hot Conflict Rate|
|:-:|:-:|:-:|:-:|:-:|:-:|:-:|
|1|50|0.5|10|10|0.5|0.01|
|2|500|0.5|10|10|0.5|0.001|
|3|5000|0.5|10|10|0.5|0.001|
|4|5000|1|20|2|0|0.001|

(buffer沒值代表優化率小於100%)
-->

#### 實驗分析解釋
* 高壓測試
可以看到 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%，可以看出此次的實作效果十分成功。

<!-- 我們把synchronized method 拿掉，這樣可以讓多個 thread 並行執行 object 的 method，而非取得object的monitor才能執行method。因此我們的方法比原始版本更能增加 throughput ，減少 latency。

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

而optFilePackage之所以可以提升這麼多，是因為我們可以同時多個讀、單一個寫，且進行讀時會採用 Optimistic read，並針對一些 `BlockID` 的內容提前進行計算等等，使得這部分的效能提升非常多。
-->