原文地址 ASPLOS 12
解决的问题
从标题就可以看出文章是针对低局部性、密集型更新操作负载的优化存储系统。旨在解决这类应用负载在现今读写接口存储系统中性能差的问题。
具体问题要点
具体到实际处理中有两方面问题：① 更新操作的异步是可以接受的，而如今磁盘则设计为尽量保持同步，减少每个请求的等待时间。② 理想的情况是聚合全部对块的更新操作，再读到内存中集中处理，但问题在于多个应用程序同时发起请求，简单的read/write 接口不能完成这样的聚合，需要依靠应用程序执行更新。
解决方法
BOSC 独立于应用，批处理请求，串行交付。
更新磁盘块过程
一次磁盘更新过程包括对目标磁盘块的一次读出，和在内存更新完后由内存到磁盘的一次写入。
A disk update involves a disk read of the target disk blocks and then a disk write of the same block after the block is brought into memory and modified.
BOSC 结构
- BOSC 对外提供Modify() 和read() 接口
- BOSC 对到达的更新以日志记录的方法连续地记录到Logging Disk Blocks 中
- Logging Disk（日志磁盘）是一个logging structured file system 的记录磁盘
- 每一条logging record 都包含了：
- 需要更改的数据结构
- 当前磁盘更新请求的一个全局序列号
- 指向前一条日志记录的向后指针
- 全局前沿，对应着所有要写入请求中最年轻请求的全局序列号
- 局部前沿，对应着所有要写入同一目标块中最年轻请求的全局序列号
- BOSC 在内存中为每一个磁盘块维持了一个更新请求队列
- Data Disk 用于保存数据
当有一条块更新请求到达时，BOSC 首先看所更新的块是否在内存中，如果是则立即更新响应的块。否则将该请求添加到块请求队列，并日志方式写入logging disk。
BOSC 在后台有一个线程不断地从Data Disk 中读取数据块到内存，这些数据块对应着其在内存中请求队列不为空的块。至于读取怎样的块到内存取决于内存中请求队列的长度，通过阈值设定。
恢复过程
如果处理过程中发生宕机了，就需要进行重演提交更新请求。BOSC 在恢复过程中并不重演所有的更新过程，而只关注那些内存中更新请求队列中的更新请求。恢复步骤如下
-
log 中寻找具有最大全局序列号的log record，可使用二分查找加速
-
决定重放窗口大小，并重建更新请求队列
-
解析重放窗口中log record，重建每个块请求
基于BOSC 的B+ 树
基于BOSC 的B+ 树假设所有的内部树节点和少部分的叶子节点是驻留在内存的。我的理解B+ 树的出现是为了组织好内存的数据块请求队列。
当有一个更改（插入、删除、更新）请求到达时，遍历树的内部节点，确定包含请求的叶子节点，然后创建一个更新记录，最后调用BOSC 磁盘更新API 进行磁盘块修改，将目标叶子节点的磁盘块地址、相关联的更新请求记录和响应的提交函数（哪个函数发起的这个请求）作为输入参数。（这个有点糊，主要是前面的Extension 没搞清楚）
为保证更新的原子性，基于BOSC 的B+ 树为每一个叶子节点配锁，修改前上锁，log record 写入和请求排到队列之后释放锁。
（这部分还有没看清楚的就不忽悠大家了）
还有一点不清楚的是，如果处理logging disk 的garbage collection。如果知道哪些更新请求被处理了，哪些没有被处理！
