在EHCache中，如果設(shè)置了overflowToDisk屬性，當(dāng)Cache中的數(shù)據(jù)超過限制時，EHCache會根據(jù)配置的溢出算法（先進(jìn)先出（FIFO）、最近最少使用算法（LRU）等），選擇部分實(shí)例，將這些實(shí)例的數(shù)據(jù)寫入到磁盤文件中臨時存儲，已減少內(nèi)存的負(fù)擔(dān)，當(dāng)內(nèi)存中的實(shí)例數(shù)減少（因?yàn)槌瑫r或手工移除）或某些實(shí)例被使用到時，又可以將這些寫入磁盤的數(shù)據(jù)重新加載到內(nèi)存中。這個過程包含實(shí)例的序列化和反序列化，以及對磁盤文件不同區(qū)域的讀寫管理，這篇文章主要關(guān)注于磁盤文件不同區(qū)域的讀寫管理。

需求思考
當(dāng)Cache系統(tǒng)發(fā)現(xiàn)需要溢出某些實(shí)例到磁盤時，它需要把實(shí)例序列化后，將序列化后的二進(jìn)制數(shù)據(jù)寫入磁盤，并釋放內(nèi)存中的數(shù)據(jù)；當(dāng)用戶請求讀取已經(jīng)溢出到磁盤中的實(shí)例時，需要讀取磁盤中的二進(jìn)制數(shù)據(jù)，反序列化成內(nèi)存實(shí)例，返回給用戶，由于該實(shí)例最近一次被訪問，因而根據(jù)程序的局部性（或許這里是數(shù)據(jù)的局部性）原理，Cache會將新讀取的實(shí)例保存在內(nèi)存中，并釋放是磁盤中占用的空間；如果此時或者在將來的某個時候內(nèi)存依然或變的非常緊張，Cache系統(tǒng)會根據(jù)溢出算法溢出根據(jù)算法得到的實(shí)例到磁盤，因而這里磁盤的讀寫是一個動態(tài)的、周而復(fù)始的行為。在把序列化的實(shí)例寫入磁盤時，我們需要分配相同大小的磁盤空間，并紀(jì)錄該實(shí)例的key、在磁盤文件中的起始位置、數(shù)據(jù)大小用于在后來的讀回數(shù)據(jù)并反序列化成內(nèi)存實(shí)例；當(dāng)一個實(shí)例數(shù)據(jù)被讀回內(nèi)存時，需要釋放它在磁盤中占用的內(nèi)存，從而可以將它原本占用磁盤分配給其他溢出實(shí)例。這有點(diǎn)類似內(nèi)存管理的味道：對一臺機(jī)器來說，內(nèi)存大小是有限的，而進(jìn)程不斷的產(chǎn)生、銷毀，在啟動一個進(jìn)程時，需要為該進(jìn)程分配一定的初始空間，并且隨著進(jìn)程的運(yùn)行，需要不斷的為其分配運(yùn)行期間增長的內(nèi)存空間；當(dāng)一個進(jìn)程銷毀時，操作系統(tǒng)需要回收分配給它的空間，以實(shí)現(xiàn)循環(huán)利用。在操作系統(tǒng)中，內(nèi)存管理方式有：
1. 固定分區(qū)分配，操作系統(tǒng)把內(nèi)存分成固定大小的相等的或不等的內(nèi)存分區(qū)，每個進(jìn)程只能分配給這幾個固定大小的分區(qū)。這是一種最簡單的內(nèi)存管理算法，它需要提前直到一個進(jìn)程最大會使用的內(nèi)存大小，并且需要合理分配內(nèi)存分區(qū)的大小，以防止有些進(jìn)程因?yàn)槭褂脙?nèi)存過多而找不到對應(yīng)大小的空閑分區(qū)而無法載入，雖然此時可能內(nèi)存還有很多其他比較小的空閑分區(qū)，它也要防止內(nèi)存分區(qū)過大，從而在載入過小進(jìn)程時浪費(fèi)內(nèi)存。對這種內(nèi)存管理方式，只需要一張分區(qū)表即可，每個表項(xiàng)紀(jì)錄了分區(qū)號、起始位置、大小、分配狀態(tài)等。如果表項(xiàng)不多，可以直接用數(shù)組表示，實(shí)現(xiàn)簡單，查找效率影響也不大，如果表項(xiàng)很多，則可以考慮在其上層建立一顆空閑分區(qū)紅黑樹，已提升查找、插入、刪除效率。
2. 相對于固定分區(qū)分配，自然會存在動態(tài)內(nèi)存分配，已處理不同內(nèi)存需要不同大小的內(nèi)存的需求，即操作系統(tǒng)根據(jù)不同進(jìn)程所需的不同內(nèi)存大小分配內(nèi)存。可以使用三種數(shù)據(jù)結(jié)構(gòu)來管理分區(qū)：空閑分區(qū)表、空閑分區(qū)鏈以及空閑分區(qū)紅黑樹，對于空閑分區(qū)表和空閑分區(qū)紅黑樹，每一個節(jié)點(diǎn)都紀(jì)錄了空閑分區(qū)號、起始位置、大小等，不同的是分區(qū)表組成一個數(shù)組，而空閑分區(qū)紅黑樹組成一顆樹已提升查找、插入、刪除等性能，對空閑分區(qū)鏈，它不象空閑分區(qū)表和空閑分區(qū)紅黑樹，使用額外的內(nèi)存中間存儲信息，它直接使用在空閑內(nèi)存的頭和尾存儲額外的分區(qū)鏈信息。而對分區(qū)分配算法，可以使用：首次適應(yīng)算法、循環(huán)首次適應(yīng)算法、最佳適應(yīng)算法、最壞適應(yīng)算法等。在分配內(nèi)存時，首先根據(jù)一定的算法找到可以裝載該進(jìn)程的空閑分區(qū)，然后根據(jù)當(dāng)前分區(qū)的大小和進(jìn)程所需要的內(nèi)存大小以及最小可存在的內(nèi)存分區(qū)的大小（防止過多的過小的內(nèi)存碎片產(chǎn)生）選擇將當(dāng)前空閑分區(qū)的部分分區(qū)劃分給該新進(jìn)程或?qū)?dāng)前整個分區(qū)分配給新進(jìn)程，如果只是將當(dāng)前空閑分區(qū)的部分分區(qū)劃分給新進(jìn)程，只需調(diào)整當(dāng)前空閑分區(qū)項(xiàng)的基本信息即可，否則需要將該空閑進(jìn)程節(jié)點(diǎn)從空閑分區(qū)表、鏈、樹中移除。內(nèi)存回首時，根據(jù)不同的算法將該內(nèi)存區(qū)創(chuàng)建出一個空閑分區(qū)節(jié)點(diǎn)，將它插入到原有空閑分區(qū)表、鏈、樹中，在插入前，如果出現(xiàn)相鄰的空閑分區(qū)表，則需要將所有的相鄰空閑分區(qū)合并。
3. 伙伴系統(tǒng)。
4. 可重定位分區(qū)分配。
貌似有點(diǎn)離題了，作為Cache的溢出數(shù)據(jù)磁盤文件管理為了簡單和效率的考慮，不會也沒必要象內(nèi)存管理一樣實(shí)現(xiàn)的那么復(fù)雜，因而伙伴系統(tǒng)和可重定為分區(qū)分配不細(xì)講了，需要進(jìn)一步了解的可以參考任意一本的操作系統(tǒng)教材。其實(shí)Cache的溢出數(shù)據(jù)磁盤文件管理更類似于內(nèi)存溢出到磁盤的交換區(qū)管理，即操作系統(tǒng)會將暫時不用的進(jìn)程或數(shù)據(jù)調(diào)換到外存中，已騰出內(nèi)存供其他需要進(jìn)程使用，已提升內(nèi)存使用率。一般進(jìn)程或內(nèi)存交換出的數(shù)據(jù)在交換區(qū)中的停留時間比較段，而交換操作又比較頻繁，因而交換區(qū)中的空間管理主要為了提高進(jìn)程或數(shù)據(jù)換入和換出的速度，為此，一般采用的是連續(xù)分配方式，較少考慮外存碎片的問題，而對其管理的數(shù)據(jù)結(jié)構(gòu)和上述的數(shù)據(jù)結(jié)構(gòu)類似，不再贅述。

EHCache使用AA Tree數(shù)據(jù)結(jié)構(gòu)來管理磁盤空間
在EHCache中，采用AA Tree數(shù)據(jù)結(jié)構(gòu)來紀(jì)錄空閑磁盤塊，因而首先了解一下AA Tree的實(shí)現(xiàn)（AATreeSet類）。AA Tree出自Arne Andersson在1993年的論文“Balanced Search Trees Made Simple”中提出的對紅黑樹的改進(jìn)，因而它是紅黑樹的變種，但是比紅黑樹實(shí)現(xiàn)要簡單。不同于紅黑樹采用顏色（紅色或黑色）來紀(jì)錄一個節(jié)點(diǎn)的狀態(tài)以調(diào)整節(jié)點(diǎn)的位置來保持其平衡性，AA Tree采用level值來紀(jì)錄當(dāng)前節(jié)點(diǎn)的狀態(tài)以保持它的平衡性，level值相當(dāng)于紅黑樹中的黑節(jié)點(diǎn)高度。AA Tree的定義如下：
1. AA Tree是紅黑樹的變種，因而它也是一顆二叉排序樹。
2. 每個葉子節(jié)點(diǎn)的level是1。
3. 每個左孩子的level是其父節(jié)點(diǎn)level值減1。
4. 每個右孩子的level和其父節(jié)點(diǎn)的level相等或是其父節(jié)點(diǎn)的level減1。
5. 每個右孫子的level一定比其祖父節(jié)點(diǎn)的level要小。
6. 每個level大于1的節(jié)點(diǎn)有兩個孩子。
類似紅黑樹，AA Tree通過對level值的判斷來調(diào)整節(jié)點(diǎn)位置以保證當(dāng)前Tree維持以上定義。由于AA Tree采用level來紀(jì)錄每個節(jié)點(diǎn)的狀態(tài)，并且每個右孩子的level和其父節(jié)點(diǎn)的level值相等或是其父節(jié)點(diǎn)的level減1，因而一般AA Tree采用如下方式表達(dá)（圖片來自：http://blog.csdn.net/zhaojinjia/article/details/8121156）：

根據(jù)以上AA Tree的定義，AA Tree禁止以下兩種情況的出現(xiàn)：
1. 禁止出現(xiàn)連續(xù)兩個水平方向鏈（horizontal link），所謂horizontal link是指一個結(jié)點(diǎn)跟它的右孩子結(jié)點(diǎn)的level相同（左孩子結(jié)點(diǎn)永遠(yuǎn)比它的父結(jié)點(diǎn)level小1）。這個規(guī)定其實(shí)相當(dāng)于RB樹中不能出現(xiàn)兩個連續(xù)的紅色結(jié)點(diǎn)。即需要滿足定義5。
2. 禁止出現(xiàn)向左的水平方向鏈（left horizontal link），也就是說一個結(jié)點(diǎn)最多只能出現(xiàn)一次向右的水平方向鏈。在AA Tree中水平鏈相當(dāng)于紅黑樹中的紅孩子，根據(jù)定義3，AA Tree不允許左孩子出現(xiàn)“紅節(jié)點(diǎn)”，即AA Tree的左孩子的level值總是要比父節(jié)點(diǎn)的level值小1。
對不允許的情況如下圖所示（圖片同樣來自：http://blog.csdn.net/zhaojinjia/article/details/8121156）：


AA Tree的節(jié)點(diǎn)調(diào)整
在AA Tree中，只需要當(dāng)出現(xiàn)以上禁止的兩種情況下才需要調(diào)整，因而它比紅黑樹的邏輯要簡單的多。同紅黑樹，AA Tree也通過旋轉(zhuǎn)節(jié)點(diǎn)來調(diào)整節(jié)點(diǎn)以使當(dāng)前樹始終保持AA Tree的特點(diǎn)，然而AA Tree創(chuàng)建了自己的術(shù)語：skew和split。skew用于處理出現(xiàn)向左的水平方向鏈的情況；split用于處理連續(xù)兩個水平方向鏈的情況。
skew相當(dāng)于一個右旋操作：

split相當(dāng)于一個左旋操作，并且它還會使父節(jié)點(diǎn)的level加1：

當(dāng)skew之前已經(jīng)有一個右孩子的level跟當(dāng)前結(jié)點(diǎn)的level相同，skew 操作之后可能引起兩個連續(xù)水平方向鏈，這時需要配合使用split操作。split操作會新的子樹的根節(jié)點(diǎn)level增加1（原節(jié)點(diǎn)的右孩子），當(dāng)原節(jié)點(diǎn)作為其父結(jié)點(diǎn)的右孩子而且其父結(jié)點(diǎn)跟祖父結(jié)點(diǎn)的level相同時，在split操作后會引起兩個連續(xù)水平方向鏈，此時需要進(jìn)一步的split操作，而當(dāng)原節(jié)點(diǎn)作為其父節(jié)點(diǎn)的左孩子時，在split操作后會引起向左方向的水平鏈，此時需要配合使用skew操作；因而AA Tree在做調(diào)整時，需要skew和split一起配合操作。

AA Tree節(jié)點(diǎn)定義
AA Tree節(jié)點(diǎn)定義和紅黑樹節(jié)點(diǎn)定義類似，只是它沒有了color字段，而使用level字段替代。在EHCache中采用Node接口表達(dá)，在該接口中它還定義了compare()方法以比較兩個節(jié)點(diǎn)之間的大小關(guān)系：
對該接口的實(shí)現(xiàn)也比較簡單：

AA Tree的插入操作
同紅黑樹，作為一顆二叉排序樹，AA Tree先以二叉排序樹的算法插入一個新節(jié)點(diǎn)，然后對插入的節(jié)點(diǎn)做skew和split調(diào)整，以維持AA Tree的定義，它是一個遞歸操作，因而可以保證在當(dāng)前一次調(diào)整完成后還需要再調(diào)整時，在上一個遞歸棧中可以繼續(xù)調(diào)整（這里比較使用當(dāng)前節(jié)點(diǎn)和傳入數(shù)據(jù)做比較，因而當(dāng)direction大于0時表示當(dāng)前節(jié)點(diǎn)要比傳入數(shù)據(jù)大，因而應(yīng)該插入它的左子樹，我剛開始沒仔細(xì)看，還以為這是一顆倒序樹，囧。。。。）：

AA Tree的刪除操作
AA Tree節(jié)點(diǎn)的刪除也只需考慮兩種情況：
1. 如果刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)不是葉子節(jié)點(diǎn)，將后繼節(jié)點(diǎn)的值賦給當(dāng)前節(jié)點(diǎn)，后繼節(jié)點(diǎn)右孩子的值賦給后繼節(jié)點(diǎn)，刪除后繼節(jié)點(diǎn)。
如下圖，要刪除30，其后繼節(jié)點(diǎn)是35，刪除時，將30和35節(jié)點(diǎn)交換，將35和40節(jié)點(diǎn)交換，后刪除40節(jié)點(diǎn)（以下圖片都出自：http://blog.csdn.net/zhaojinjia/article/details/8121156）：

2. 如果刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)是葉子節(jié)點(diǎn)，后繼節(jié)點(diǎn)的值賦給當(dāng)前節(jié)點(diǎn)，并將后繼節(jié)點(diǎn)的父節(jié)點(diǎn)level值減1，如果出現(xiàn)向左的水平鏈或向右的連續(xù)水平鏈，則做skew和split調(diào)整。
如下面兩圖分別為刪除50節(jié)點(diǎn)和刪除15節(jié)點(diǎn)的事例圖：


EHCache AATreeSet中刪除的代碼（這里的比較也是使用當(dāng)前節(jié)點(diǎn)和傳入數(shù)據(jù)比較，因而當(dāng)direction大于0時，應(yīng)該向左走，要特別留意）：

參考文章：