在EHCache中，如果設置了overflowToDisk屬性，當Cache中的數據超過限制時，EHCache會根據配置的溢出算法（先進先出（FIFO）、最近最少使用算法（LRU）等），選擇部分實例，將這些實例的數據寫入到磁盤文件中臨時存儲，已減少內存的負擔，當內存中的實例數減少（因為超時或手工移除）或某些實例被使用到時，又可以將這些寫入磁盤的數據重新加載到內存中。這個過程包含實例的序列化和反序列化，以及對磁盤文件不同區域的讀寫管理，這篇文章主要關注于磁盤文件不同區域的讀寫管理。
需求思考
當Cache系統發現需要溢出某些實例到磁盤時，它需要把實例序列化后，將序列化后的二進制數據寫入磁盤，并釋放內存中的數據；當用戶請求讀取已經溢出到磁盤中的實例時，需要讀取磁盤中的二進制數據，反序列化成內存實例，返回給用戶，由于該實例最近一次被訪問，因而根據程序的局部性（或許這里是數據的局部性）原理，Cache會將新讀取的實例保存在內存中，并釋放是磁盤中占用的空間；如果此時或者在將來的某個時候內存依然或變的非常緊張，Cache系統會根據溢出算法溢出根據算法得到的實例到磁盤，因而這里磁盤的讀寫是一個動態的、周而復始的行為。在把序列化的實例寫入磁盤時，我們需要分配相同大小的磁盤空間，并紀錄該實例的key、在磁盤文件中的起始位置、數據大小用于在后來的讀回數據并反序列化成內存實例；當一個實例數據被讀回內存時，需要釋放它在磁盤中占用的內存，從而可以將它原本占用磁盤分配給其他溢出實例。這有點類似內存管理的味道：對一臺機器來說，內存大小是有限的，而進程不斷的產生、銷毀，在啟動一個進程時，需要為該進程分配一定的初始空間，并且隨著進程的運行，需要不斷的為其分配運行期間增長的內存空間；當一個進程銷毀時，操作系統需要回收分配給它的空間，以實現循環利用。在操作系統中，內存管理方式有：
1. 固定分區分配，操作系統把內存分成固定大小的相等的或不等的內存分區，每個進程只能分配給這幾個固定大小的分區。這是一種最簡單的內存管理算法，它需要提前直到一個進程最大會使用的內存大小，并且需要合理分配內存分區的大小，以防止有些進程因為使用內存過多而找不到對應大小的空閑分區而無法載入，雖然此時可能內存還有很多其他比較小的空閑分區，它也要防止內存分區過大，從而在載入過小進程時浪費內存。對這種內存管理方式，只需要一張分區表即可，每個表項紀錄了分區號、起始位置、大小、分配狀態等。如果表項不多，可以直接用數組表示，實現簡單，查找效率影響也不大，如果表項很多，則可以考慮在其上層建立一顆空閑分區紅黑樹，已提升查找、插入、刪除效率。
2. 相對于固定分區分配，自然會存在動態內存分配，已處理不同內存需要不同大小的內存的需求，即操作系統根據不同進程所需的不同內存大小分配內存。可以使用三種數據結構來管理分區：空閑分區表、空閑分區鏈以及空閑分區紅黑樹，對于空閑分區表和空閑分區紅黑樹，每一個節點都紀錄了空閑分區號、起始位置、大小等，不同的是分區表組成一個數組，而空閑分區紅黑樹組成一顆樹已提升查找、插入、刪除等性能，對空閑分區鏈，它不象空閑分區表和空閑分區紅黑樹，使用額外的內存中間存儲信息，它直接使用在空閑內存的頭和尾存儲額外的分區鏈信息。而對分區分配算法，可以使用：首次適應算法、循環首次適應算法、最佳適應算法、最壞適應算法等。在分配內存時，首先根據一定的算法找到可以裝載該進程的空閑分區，然后根據當前分區的大小和進程所需要的內存大小以及最小可存在的內存分區的大?。ǚ乐惯^多的過小的內存碎片產生）選擇將當前空閑分區的部分分區劃分給該新進程或將當前整個分區分配給新進程，如果只是將當前空閑分區的部分分區劃分給新進程，只需調整當前空閑分區項的基本信息即可，否則需要將該空閑進程節點從空閑分區表、鏈、樹中移除。內存回首時，根據不同的算法將該內存區創建出一個空閑分區節點，將它插入到原有空閑分區表、鏈、樹中，在插入前，如果出現相鄰的空閑分區表，則需要將所有的相鄰空閑分區合并。
3. 伙伴系統。
4. 可重定位分區分配。
貌似有點離題了，作為Cache的溢出數據磁盤文件管理為了簡單和效率的考慮，不會也沒必要象內存管理一樣實現的那么復雜，因而伙伴系統和可重定為分區分配不細講了，需要進一步了解的可以參考任意一本的操作系統教材。其實Cache的溢出數據磁盤文件管理更類似于內存溢出到磁盤的交換區管理，即操作系統會將暫時不用的進程或數據調換到外存中，已騰出內存供其他需要進程使用，已提升內存使用率。一般進程或內存交換出的數據在交換區中的停留時間比較段，而交換操作又比較頻繁，因而交換區中的空間管理主要為了提高進程或數據換入和換出的速度，為此，一般采用的是連續分配方式，較少考慮外存碎片的問題，而對其管理的數據結構和上述的數據結構類似，不再贅述。
EHCache使用AA Tree數據結構來管理磁盤空間
在EHCache中，采用AA Tree數據結構來紀錄空閑磁盤塊，因而首先了解一下AA Tree的實現（AATreeSet類）。AA Tree出自Arne Andersson在1993年的論文“Balanced Search Trees Made Simple”中提出的對紅黑樹的改進，因而它是紅黑樹的變種，但是比紅黑樹實現要簡單。不同于紅黑樹采用顏色（紅色或黑色）來紀錄一個節點的狀態以調整節點的位置來保持其平衡性，AA Tree采用level值來紀錄當前節點的狀態以保持它的平衡性，level值相當于紅黑樹中的黑節點高度。AA Tree的定義如下：
1. AA Tree是紅黑樹的變種，因而它也是一顆二叉排序樹。
2. 每個葉子節點的level是1。
3. 每個左孩子的level是其父節點level值減1。
4. 每個右孩子的level和其父節點的level相等或是其父節點的level減1。
5. 每個右孫子的level一定比其祖父節點的level要小。
6. 每個level大于1的節點有兩個孩子。
類似紅黑樹，AA Tree通過對level值的判斷來調整節點位置以保證當前Tree維持以上定義。由于AA Tree采用level來紀錄每個節點的狀態，并且每個右孩子的level和其父節點的level值相等或是其父節點的level減1，因而一般AA Tree采用如下方式表達（圖片來自：http://blog.csdn.net/zhaojinjia/article/details/8121156）：
根據以上AA Tree的定義，AA Tree禁止以下兩種情況的出現：
1. 禁止出現連續兩個水平方向鏈（horizontal link），所謂horizontal link是指一個結點跟它的右孩子結點的level相同（左孩子結點永遠比它的父結點level小1）。這個規定其實相當于RB樹中不能出現兩個連續的紅色結點。即需要滿足定義5。
2. 禁止出現向左的水平方向鏈（left horizontal link），也就是說一個結點最多只能出現一次向右的水平方向鏈。在AA Tree中水平鏈相當于紅黑樹中的紅孩子，根據定義3，AA Tree不允許左孩子出現“紅節點”，即AA Tree的左孩子的level值總是要比父節點的level值小1。
對不允許的情況如下圖所示（圖片同樣來自：http://blog.csdn.net/zhaojinjia/article/details/8121156）：
AA Tree的節點調整
在AA Tree中，只需要當出現以上禁止的兩種情況下才需要調整，因而它比紅黑樹的邏輯要簡單的多。同紅黑樹，AA Tree也通過旋轉節點來調整節點以使當前樹始終保持AA Tree的特點，然而AA Tree創建了自己的術語：skew和split。skew用于處理出現向左的水平方向鏈的情況；split用于處理連續兩個水平方向鏈的情況。
skew相當于一個右旋操作：
private static <T> Node<T> skew(Node<T> top) {
if (top.getLeft().getLevel() == top.getLevel() && top.getLevel() != 0) {
Node<T> save = top.getLeft();
top.setLeft(save.getRight());
save.setRight(top);
top = save;
}
return top;
}
split相當于一個左旋操作，并且它還會使父節點的level加1：
private static <T> Node<T> split(Node<T> top) {
if (top.getRight().getRight().getLevel() == top.getLevel() && top.getLevel() != 0) {
Node<T> save = top.getRight();
top.setRight(save.getLeft());
save.setLeft(top);
top = save;
top.incrementLevel();
}
return top;
}
當skew之前已經有一個右孩子的level跟當前結點的level相同，skew 操作之后可能引起兩個連續水平方向鏈，這時需要配合使用split操作。split操作會新的子樹的根節點level增加1（原節點的右孩子），當原節點作為其父結點的右孩子而且其父結點跟祖父結點的level相同時，在split操作后會引起兩個連續水平方向鏈，此時需要進一步的split操作，而當原節點作為其父節點的左孩子時，在split操作后會引起向左方向的水平鏈，此時需要配合使用skew操作；因而AA Tree在做調整時，需要skew和split一起配合操作。
AA Tree節點定義
AA Tree節點定義和紅黑樹節點定義類似，只是它沒有了color字段，而使用level字段替代。在EHCache中采用Node接口表達，在該接口中它還定義了compare()方法以比較兩個節點之間的大小關系：
public static interface Node<E> {
public int compareTo(E data);
public void setLeft(Node<E> node);
public void setRight(Node<E> node);
public Node<E> getLeft();
public Node<E> getRight();
public int getLevel();
public void setLevel(int value);
public int decrementLevel();
public int incrementLevel();
public void swapPayload(Node<E> with);
public E getPayload();
}
對該接口的實現也比較簡單：
public abstract static class AbstractTreeNode<E> implements Node<E> {
private Node<E> left;
private Node<E> right;
private int level;
.....
}
private static final class TreeNode<E extends Comparable> extends AbstractTreeNode<E> {
private E payload;
public void swapPayload(Node<E> node) {
if (node instanceof TreeNode<?>) {
TreeNode<E> treeNode = (TreeNode<E>) node;
E temp = treeNode.payload;
treeNode.payload = this.payload;
this.payload = temp;
} else {
throw new IllegalArgumentException();
}
}
.....
}
AA Tree的插入操作
同紅黑樹，作為一顆二叉排序樹，AA Tree先以二叉排序樹的算法插入一個新節點，然后對插入的節點做skew和split調整，以維持AA Tree的定義，它是一個遞歸操作，因而可以保證在當前一次調整完成后還需要再調整時，在上一個遞歸棧中可以繼續調整（這里比較使用當前節點和傳入數據做比較，因而當direction大于0時表示當前節點要比傳入數據大，因而應該插入它的左子樹，我剛開始沒仔細看，還以為這是一顆倒序樹，囧。。。。）：
private Node<T> insert(Node<T> top, T data) {
if (top == terminal()) {
mutated = true;
return createNode(data);
} else {
int direction = top.compareTo(data);
if (direction > 0) {
top.setLeft(insert(top.getLeft(), data));
} else if (direction < 0) {
top.setRight(insert(top.getRight(), data));
} else {
return top;
}
top = skew(top);
top = split(top);
return top;
}
}
AA Tree的刪除操作AA Tree節點的刪除也只需考慮兩種情況：
1. 如果刪除節點的后繼節點不是葉子節點，將后繼節點的值賦給當前節點，后繼節點右孩子的值賦給后繼節點，刪除后繼節點。
如下圖，要刪除30，其后繼節點是35，刪除時，將30和35節點交換，將35和40節點交換，后刪除40節點（以下圖片都出自：http://blog.csdn.net/zhaojinjia/article/details/8121156）：
2. 如果刪除節點的后繼節點是葉子節點，后繼節點的值賦給當前節點，并將后繼節點的父節點level值減1，如果出現向左的水平鏈或向右的連續水平鏈，則做skew和split調整。
如下面兩圖分別為刪除50節點和刪除15節點的事例圖：
EHCache AATreeSet中刪除的代碼（這里的比較也是使用當前節點和傳入數據比較，因而當direction大于0時，應該向左走，要特別留意）：
private Node<T> remove(Node<T> top, T data) {
if (top != terminal()) {
int direction = top.compareTo(data);
heir = top;
if (direction > 0) {
top.setLeft(remove(top.getLeft(), data));
} else {
item = top;
top.setRight(remove(top.getRight(), data));
}
if (top == heir) {
if (item != terminal() && item.compareTo(data) == 0) {
mutated = true;
item.swapPayload(top);
removed = top.getPayload();
top = top.getRight();
}
} else {
if (top.getLeft().getLevel() < top.getLevel() - 1 || top.getRight().getLevel() < top.getLevel() - 1) {
if (top.getRight().getLevel() > top.decrementLevel()) {
top.getRight().setLevel(top.getLevel());
}
top = skew(top);
top.setRight(skew(top.getRight()));
top.getRight().setRight(skew(top.getRight().getRight()));
top = split(top);
top.setRight(split(top.getRight()));
}
}
}
return top;
}
參考文章：
http://blog.csdn.net/zhaojinjia/article/details/8121156
http://www.cnblogs.com/ljsspace/archive/2011/06/16/2082240.html
http://baike.baidu.com/view/10841337.htm
posted on 2013-10-27 19:13
DLevin 閱讀(4117)
評論(0) 編輯 收藏 所屬分類:
EHCache