空閑磁盤管理資料結構和算法
最壞适應算法（worst fit），在《計算機作業系統（湯子瀛版）》中對該算法描述如下：最壞适應配置設定算法要掃瞄整個空閑分區表或連結清單，總是挑選一個最大的空閑分區分分割給作業使用，其優點是可使剩下的空閑區不至于太小，産生碎片的幾率最小，對中小作業有利，同時最壞适應算法查找效率很高。該算法要求将所有的空閑分區按其容量以從大到小的順序形成一空閑分區鍊，查找時隻要看第一個分區能否滿足作業要求。但該算法的缺點也時明顯的，它會使存儲器中缺乏大的空閑分區。最壞适應算法與前面所述的首次适應算法、循環首次适應算法、最佳适應算法一起被成為順序搜尋算法。
首次适應算法在《計算機作業系統（湯子瀛版）》描述如下：我們以空閑分區鍊為例來說明采用ff算法時的配置設定情況。ff算法要求空閑分區鍊以位址遞增次序連結。在配置設定記憶體時，從鍊首開始順序查找，直到找到一個大小能滿足要求的空閑分區為止；然後再按照作業的大小，從該分區中劃出一塊記憶體空間配置設定給請求者，餘下的空閑分區仍留在空閑鍊中。若從鍊首直至鍊尾都不能找到一個滿足要求的分區，則此次記憶體配置設定失敗，傳回。該算法傾向于有限利用記憶體中低位址部分的空閑分區，進而保留了高位址部分的大空閑區。這給尾以後到達的大作業配置設定大的記憶體空間創造了條件。其缺點時低位址部分不斷被劃分，會留下許多難以利用的、很小的空閑分區，而每次查找右都時從低位址部分開始，這無疑會增加查找可用空閑分區時的開銷。
作為cache的溢出資料檔案作為cache的交換區，顯然我們希望資料檔案越小越好，此時一般的選擇是使用首次适應算法（first fit）。然而雖然ff算法能盡可能多的利用資料檔案低位址部分的磁盤空間以減少磁盤檔案的大小，但是它的缺點也是明顯的，而wf算法雖然效率很高，但是它很容易使資料檔案膨脹導緻磁盤使用率很低。因而ehcache的空閑磁盤去管理時采用了兩種結合的方法：即空閑鍊（aa tree鍊）的以磁盤位址順序排列，樹的每個節點包含一個字段用于紀錄目前節點以及其所有子節點中的最大size，在查找時，以層級順序周遊，并且優先選擇左子樹（磁盤位址低的region）。
ehcache将一個空閑磁盤區抽象成一個region類，它包含start、end字段，用于紀錄在目前該區域在磁盤檔案中的其實位置；并且每個region執行個體是aa tree中的一個節點，因而它繼承自aatreeset.abstracttreenode類，即繼承了該類的left、right、level字段；根據region的比較算法，它大緻上以region所在磁盤檔案的位置排序（而不是以region的大小來排序），因而為了提升查找性能，它還包含了一個long類型的contiguous字段，該單詞字面意思是“臨近的、連續的”，用于表示該目前region臨近節點的區域的最大region大小，即該字段表示目前region以及其所有子節點的最大region的大小，進而當在查找時，隻有如果要查找的size比目前region的contiguous字段要大的話，就可以不用繼續查找其子節點了，并且通過該字段也實作了最壞适應算法。在每次更新左子節點和右子節點時都會調整contiguous的大小，在新建立一個region節點時也會更新contiguous字段大小，進而保證目前region中的contiguous始終是其所有子節點的最大size，對于葉子節點，其contiguous的值是目前region的size。在計算size時，start，end值是閉合的。
public abstract static class abstracttreenode<e> implements node<e> {
private node<e> left;
private node<e> right;
private int level;
.....
}
public class region extends aatreeset.abstracttreenode<comparable> implements comparable<comparable> {
private long start;
private long end;
private long contiguous;
public region(long start, long end) {
super();
this.start = start;
this.end = end;
updatecontiguous();
}
public long contiguous() {
if (getleft().getpayload() == null && getright().getpayload() == null) {
return size();
} else {
return contiguous;
}
private void updatecontiguous() {
region left = (region) getleft().getpayload();
region right = (region) getright().getpayload();
long leftcontiguous = left == null ? 0 : left.contiguous();
long rightcontiguous = right == null ? 0 : right.contiguous();
contiguous = math.max(size(), math.max(leftcontiguous, rightcontiguous));
public void setleft(aatreeset.node<comparable> l) {
super.setleft(l);
public void setright(aatreeset.node<comparable> r) {
super.setright(r);
public long size() {
// since it is all inclusive
return (isnull() ? 0 : this.end - this.start + 1);
//region的比較算法，使region在這棵aa tree中大緻保持其在資料檔案中的排序順序
public int compareto(comparable other) {
if (other instanceof region) {
return compareto((region) other);
} else if (other instanceof long) {
return compareto((long) other);
throw new assertionerror("unusual type " + other.getclass());
private int compareto(region r) {
if (this.start > r.start || this.end > r.end) {
return 1;
} else if (this.start < r.start || this.end < r.end) {
return -1;
return 0;
private int compareto(long l) {
if (l.longvalue() > end) {
} else if (l.longvalue() < start) {
ehcache中對空閑磁盤的配置設定與回收
在c語言中使用malloc和free來對記憶體的配置設定與回收，在c＋＋中使用new和delete，在java中隻有new，在ehcache中則将磁盤空間的配置設定與回收抽象成fileallocationtree類，它提供alloc、free、mark等接口用于管理磁盤區的配置設定與回收。另外ehcache還增加了regionset類，它繼承子aatreeset類，用于表達它專門用于存儲region節點。這裡吐槽一下，fileallocationtree竟然設計成繼承自regionset而不是組合。。。。。所有這些類的結構圖如下：
磁盤的配置設定
磁盤的配置設定分成一下幾個步驟（邏輯比較簡單，就不貼代碼了）：
根據傳入的size，在aa tree中查找到一個可以容納傳入size大小的region節點，并将找到的region的前size部分配置設定出一個新的region并傳回。
查找邏輯在regionset類中實作(find方法)，它從root節點向下查找，因為root節點的contiguous字段儲存了整棵樹的最大size，因而先檢查root節點的contiguous，如果size比root的contiguous要大，則抛異常，因為整棵樹中已經沒有比傳入的size要大的region。然後層級周遊aa樹，如果目前節點的size要比傳入的size大或相等，則找到足以容納傳入size大小的region節點，以目前節點的size大小的前部分新建立一個region傳回；否則如果它的左子樹的contiguous字段要比傳入size大，則向左子樹查找；否則如果它的右子樹的contiguous字段要比傳入的size大，則向右子樹查找；否則，抛出異常，因為左右子樹都找不到可以容納size大小的region。
将新建立的region執行個體mark成已經使用（這個新建立的region的start和aa樹中某個region節點的start值一樣，而end大小則不一定一樣）。
因為這個新建立的region執行個體是要從aa樹中的某個節點分出部分空間，因而首先要将aa樹中的那個節點從樹中移除，然後如果樹中移除的節點的end值和新建立的region的end值一樣，則直接移除就可以了，否則，要将樹種移除的節點剩餘部分的重新建立一個region插回樹中。從代碼的角度，首先以新建立的region的start值找到樹中對應的region（region中接收long作為參數的compare方法的存在以實作這種方式的查找），将其移除并傳回移除後的region（removeandreturn方法，在regionset中重新拷貝一個region執行個體是為了防止通過r傳回的region改變樹内部的狀态，因為region即作為一個node也作為payload存在，同時也可以給接下來的插入提供新的region節點），然後把将新建立的region從原樹中的region中移除，這裡的移除邏輯假設新建立的region可以是原樹中的region的前部分、中間部分以及末位部分，作為前部分和末位部分，因為region是新建立的節點，因而直接更新目前節點即可，而如果是中間部分，則前部分作為目前節點，而後部分作為新節點傳回。最後，如果原樹中節點還剩餘部分資料作為新的空閑磁盤區添回到空閑磁盤樹中。最後，檢查是否需要增加檔案大小，這裡隻需要更新檔案大小的字段即可而不需要實際增加檔案的大小，因為檔案在寫入時會自動增加大小。region中移除其中的部分region代碼如下：
protected region remove(region r) throws illegalargumentexception {
if (r.start < this.start || r.end > this.end) {
throw new illegalargumentexception("ranges : illegal value passed to remove : " + this + " remove called for : " + r);
if (this.start == r.start) {
this.start = r.end + 1;
updatecontiguous();
return null;
} else if (this.end == r.end) {
this.end = r.start - 1;
region newregion = new region(r.end + 1, this.end);
return newregion;
最後将配置設定出來的region執行個體傳回，并紀錄在diskmarker中，在以後需要将磁盤中的資料重新讀取到記憶體中時用于定位該資料在磁盤中的位置，并可以将該regin回收。
磁盤的回收
磁盤的回收也分幾個步驟來完成：
對要回收的region，查找在目前樹中是否有一個region節點其start和要回收的region的(end - 1)值相等，如果有，則删除樹中的原節點并傳回，合并這兩個節點，将合并後的節點重新插入到樹中。region中合并的代碼邏輯如下：
protected void merge(region r) throws illegalargumentexception {
if (this.start == r.end + 1) {
this.start = r.start;
} else if (this.end == r.start - 1) {
this.end = r.end;
throw new illegalargumentexception("ranges : merge called on non contiguous values : [this]:" + this + " and " + r);
對要回收的region（或合并後的region），繼續查找目前樹是否有一個region節點，其end和要回收的（或已合并的）region的(start - 1)的值相等，如果有，則删除樹中的原節點并傳回，合并這兩個節點，将合并後的節點繼續插入樹中。
如果在樹中找不到可以和回收的region合并的region節點，則隻是将要合并的region添加到樹中。
最後如果回收後資料檔案可以減小，更新資料檔案大小的字段，并将資料檔案的縮小，進而保持資料檔案處于盡量小的狀态。
最後我寫了一個簡單的測試程式，對磁盤配置設定與釋放做了一些随機的模拟，以增加一些直覺的感受(類似diskstoragefactory，在建立fileallocationtree時，給了long.max_value的初始值，我這也給這個值作為初始值，進而保證基本上在所有情況下，都能找到一個合适的region節點，也就是說fileallocationtree不用來控制資料檔案的大小，資料檔案的大小由其他邏輯來控制，這在後面會詳細講解)：
public class fileallocationtreetest {
public static void main(string[] args) {
final int count = 5;
random random = new random();
fileallocationtree alloc = new fileallocationtree(long.max_value, null);
list<region> allocated = lists.newarraylist();
for(int i = 0; i < count; i++) {
int size = random.nextint(1000);
region region = alloc.alloc(size);
system.out.println("new size: " + size + ", " + tostring(region) + ", filesize: " + alloc.getfilesize() + ", allocator: " + tostring(alloc));
allocated.add(region);
region = allocated.get(random.nextint(allocated.size()));
alloc.free(region);
allocated.remove(region);
system.out.println("freed region: " + tostring(region) + ", after file size: " + alloc.getfilesize() + ", allocator: " + tostring(alloc));
private static string tostring(fileallocationtree alloc) {
stringbuilder builder = new stringbuilder("[");
for(region region : alloc) {
builder.append(tostring(region)).append(", ");
builder.replace(builder.length() - 2, builder.length() - 1, "]");
return builder.tostring();
private static string tostring(region region) {
return "regin(" + region.start() + ", " + region.end() + ")";
輸出的随機結果如下：
new size: 397, regin(0, 396), filesize: 397, allocator: [regin(397, 9223372036854775806)]
new size: 175, regin(397, 571), filesize: 572, allocator: [regin(572, 9223372036854775806)]
new size: 210, regin(572, 781), filesize: 782, allocator: [regin(782, 9223372036854775806)]
new size: 11, regin(782, 792), filesize: 793, allocator: [regin(793, 9223372036854775806)]
new size: 432, regin(793, 1224), filesize: 1225, allocator: [regin(1225, 9223372036854775806)]
new size: 226, regin(1225, 1450), filesize: 1451, allocator: [regin(1451, 9223372036854775806)]
freed region: regin(572, 781), after file size: 1451, allocator: [regin(572, 781), regin(1451, 9223372036854775806)]
new size: 500, regin(1451, 1950), filesize: 1951, allocator: [regin(572, 781), regin(1951, 9223372036854775806)]
freed region: regin(793, 1224), after file size: 1951, allocator: [regin(572, 781), regin(793, 1224), regin(1951, 9223372036854775806)]
new size: 681, regin(1951, 2631), filesize: 2632, allocator: [regin(572, 781), regin(793, 1224), regin(2632, 9223372036854775806)]
freed region: regin(1951, 2631), after file size: 1951, allocator: [regin(572, 781), regin(793, 1224), regin(1951, 9223372036854775806)]
new size: 23, regin(793, 815), filesize: 1951, allocator: [regin(572, 781), regin(816, 1224), regin(1951, 9223372036854775806)]
freed region: regin(0, 396), after file size: 1951, allocator: [regin(0, 396), regin(572, 781), regin(816, 1224), regin(1951, 9223372036854775806)]
new size: 109, regin(816, 924), filesize: 1951, allocator: [regin(0, 396), regin(572, 781), regin(925, 1224), regin(1951, 9223372036854775806)]
freed region: regin(1225, 1450), after file size: 1951, allocator: [regin(0, 396), regin(572, 781), regin(925, 1450), regin(1951, 9223372036854775806)]