# 1 Introduction

增加叢集運算系統效能的方法最普遍的方法為增進 disk-locality。
在許多系統中， disk-locality 是最常用來度量效能的準則。

這篇論文表明了 disk-locality 在未來將不再那麼的重要。
追求 disk-locality 的兩大前提為：
1. disk 頻寬大於網路頻寬
2. disk I/O 占了 task 大多數的時間。

過去觀察顯示網路科技進度的速度比 disk 快得多。
從 local disk 讀取只比從同個機架(rack)上的另一個 node 的 disk 讀取快 8%。
至於機架間的通訊，目前趨向用 full-bisection topologies。這確保了機架間的頻寬跟機架內的頻寬一樣。

另一個支持本論文的趨勢為叢集運算對於資料節省的需求。
當前對於儲存空間的需求超過了可負擔的範圍，而這差距只會越來越大。這樣不只令 SSD 在經濟上不可行，同時也引出了資料壓縮的需求。
壓縮減少了需要從 disk 讀取的資料大小，也減少了 task 生命中的 I/O 時間。
我們從 Facebook 的 logs 分析出， disk-locality 只增進了極微幅的效能。

記憶體的速度雖然可以增進 task 執行效率，但是容量差了 disk 兩個數量級，所以以記憶體替代 disk 是不可行的，所以我們只剩一個選擇：用記憶體當作 cache。
跟 RAMCloud 不一樣的地方是，只會有一部份的資料存在記憶體當中。

記憶體 caching (in-memory caching)也面對了一些問題。
首先，記憶體不夠大到可以放進所有 jobs 的輸入(input)。
再來，有 75% 的 block 總共只會被存取一次，減少了 caching 的效果。
最後，為了確保效能，必須 cache 一個 job 所有的輸入。即使只有一個 task 從 disk 讀取資料也會變成拖油瓶，延長 job 的執行時間。

令人意外的是，當使用 LFU 置換機制時，仍有 64% 的 job 其底下所有 task 都有達成 memory locality。
這歸功於大部分的 job 只存取一小部分的 block。
更意外的是，大部分(96%)的 job 可以塞得進叢集總記憶體的一部份(a fraction of the cluster's total memory)。

我們從 Facebook 的 Hadoop logs 裡面分析表明了大部分的資料只被存取一次，這需求了採用預先擷取(pre-fetching)資料的技術。
即使 LFU 可以提供好的 memory-locality，但是還有機會可以有更好的技術。
激烈的 file block churn* 將構成挑戰，所以需要一個可拓展的架構。

> \*churn 這邊我覺得意思應該是指放進去 cache 裡面但還沒被讀過一次就被置換掉的資料。

# 2 Disk-Locality Considered Irrelevant

## 2.1 Fast Network

由於網路的進步， 40Gbps 與 100Gbps 量級的網路交換器在市場上越發常見。
所以，從 local disk 讀取跟從 local network 讀取已經可以相提並論了。

### Deployment Validation
我們用$\large \frac{(data\_read + data\_written)}{duration}$ 來度量 task 的 *progress rate*
我們比較了 node-local 跟 rack-local 的 task 的 progress rate，對於每個 job ，我們取其 progress rate 中位數的比率。
85% 的 job 落在 1.0 的 ratio 附近，意即博取 node-locality 並沒有顯著成效。
此現象呼應了上述"從 local disk 讀取跟從 local network 讀取已經可以相提並論"。

## 2.2 Storage Crunch

一個悠久的假設提到在資料量繁重的計算裡面，讀取佔據了 task 大部分的時間。
資料中心已經開始採取了壓縮(compression)以及去重複(de-replication)資料的方法。

### Compression

由於 datacenter jobs 主要的推手都為大量有結構的文字資料，所以它們可以被高度的壓縮。
高度壓縮的資料意味著更少的讀取，排除了 disk-locality 的需求。

從圖 2 中，讓一個 task 在 off-rack 情況下執行僅會慢 1.2 到 1.4 倍，我們把這視為壓縮的直接功效。

### De-replication

相比於其他資料，老邁的資料有更少的重複(最低只有一個)，即使在中度叢集使用率，找到 disk-local slot 的機率微乎其微。
從 Facebook 的 Hadoop logs 裡面分析表明了達到 disk-local 很困難，只有 34% 的 task 有跑在有輸入資料的 node 上。

==因此我們總結了 storage crunch 的技術，會使 data-locality 在 datacenter 計算中顯得不重要。==

## 2.3 Why SSDs will not help

即使 SSD 有更高的頻寬還有更低的反應時間，但現今仍不是非常吸引人。
因為未來對於資料量的需求，會使得 SSD 的每 byte 的價格必須下降 3 個量級，才能被納入考量。

隨著網路速度匹敵或甚至超越 disk 頻寬，更可能發生的會是**要**讓 disk-locality 越顯不重要。

# 3 Memory Locality

我們相信議題應該從 disk-locality 轉向 memory-locality。
根據上圖 1，從記憶體讀取資料是從 disk/network 讀取的兩個數量級以上的速度。
我們相信 memory-locality 有可能會提供顯著的效益，基於以下幾個觀察。
在 Facebook 的 Hadoop workload 中，96% 的 jobs 可以把整個資料塞進記憶體中。(假設 32GB 記憶體)
這是由於大多數的 job 只會存取一小部分的 block。如圖 3(a)

我們接著模擬測試各種置換策略 memory-locality 的表現。
> 在此省略

首先預估最佳的 memory-locality 表現。其他資料顯示 75% 的 block 只會被存取一次，那些 block 是被 42% 的 task 所使用。
因為 cache 只會在第一次被存取的時候放入，所以最好的 memory-locality 只能是 58%。
> 因為那 42% 都沒有貢獻 memory-locality

==可以看到 LFU 比 LRU 好上 15%。==

最後我們來看 memory-locality 如何影響 jobs 的完成時間。
我們保守假設 jobs 可以被加速的條件是所有 task 都是從記憶體讀取資料(而非硬碟)。
我們的結果顯示 64% 的 job 的所有 task 都有 memory-local。
這仍然還有很大的進步可能，我們只需要研究新的置換機制與預先擷取(pre-fetching)機制。
我們以以下三點總結：
### 1. Cache Eviction

目前置換機制都注重 cache-hit ratio ，但是如先前所述，增進 job 的 hit ratio 也許不會增進完成時間。
LFU 置換策略改進了 96% 中的 64%。所以，仍然還有空間量身訂製一個更適合 datacenter 的置換機制。
==置換機制應該更傾向增加 cache 中完整的 file 的數量==

### 2. Pre-fetching Blocks

那些有用到只會存取一次的 block 的 task 無法達成 memory-locality。這 42% 的 task 分布於 11% 的 job 之中。
==增進這些 job 效能需要一個帶外(out-of-band)機制來預測並預先擷取那些 block 進 memory。==
一個可能性是載入最近才剛被建立的資料，例如某些 job 的輸出(output)。

### 3. Scalable Cache Management

記憶體 cache (in-memory cache)被預期會在 block 的位置(location of blocks)有更高的 churn。
所以，==有十足可擴充性的架構對 caching 跟服務 data block 是需要的==

# 4 Related Work

## Disk-Locality

某些情況仍然會需要 disk-locality。
一些情況如 slot contention ，會發生在當一個有所需資料卻沒有空位執行的機器時。
在機器間複製常用的 block 能夠避免以上情況。

## Global Memory

從遠端節點的記憶體讀取資料不太可能可以跟從本地的 disk 循序讀取比得上。

## Memory Storage

有些系統設想將所有資料存在記憶體中。
然而，記憶體跟 disk 那兩個數量級的差距意味著我們只會用記憶體來當 cache。