空闲磁盘管理数据结构和算法
最坏适应算法（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)]