# Anti-Caching -- A New Approach to Database Management System Architecture

## Anti-Caching: A New Approach to Database Management System Architecture

### 引言

We implemented a prototype of our anti-caching proposal in a high-performance, main memory OLTP DBMS and performed a series of experiments across a range of database sizes, workload skews, and read/write mixes. We compared its performance with an open-source, disk-based DBMS optionally fronted by a distributed main memory cache. Our results show that for higher skewed workloads the anti-caching architecture has a performance advantage over either of the other architectures tested of up to 9x for a data size 8x larger than memory.


### 系统模型

#### 存储架构

2. 一个在内存中的Evicted Table，保存着元组到数据块的映射信息，它存在的目的就是需要将数据取回的时候知道去哪一个数据块读取数据；

#### Block Eviction

• 从哪一个表里面驱逐数据；
• 从选定的表里面驱逐多少数据；

这里解决第一个问题的方式就是根据表的使用频率。当然这里不让一味的驱逐使用最不频繁表的数据，而是根据比例来驱逐。访问越不频繁的表越可能被驱逐更加多的数据。

对于第二个问题，在决定了从哪一个表驱逐数据之后，运行一个特殊的事务来选择被驱逐的元组，然后将其写入磁盘。这个驱逐事务会阻塞这个分区上面执行的启动的事务。每一个被驱逐的元组被使用 evicted flag标示。

This eviction process continues until the block is full, at which point the transaction will create the next block. The process stops once the transaction has evicted the req- uisite amount of data from each table. Groups of blocks are written out in a single sequential write. For example, if the table is asked to evict a set of n blocks, it will create each of the n blocks independently, and only when all n blocks have been created will it write the result to disk in one sequential write.


#### Transaction Execution & Block Retrieval

##### Pre-pass Phase

For some transactions, it is not possible for the DBMS to discover all of the data that it needs in a single pre-pass. This can occur if the non-indexed values of an evicted tuple are needed to retrieve additional tuples in the same transaction. In this case, the initial pre-pass phase will determine all evicted data that is not dependent on currently evicted data.


##### Block Retrieval

• Tuple-Merging，这种方式为了解决前面取回很多无用数据的问题，它只取回需要访问的数据，这样，由于磁盘上面的块还存在需要保存的数据，这样就不能将其简单地删除，这样导致的问题就是在内存和磁盘上存在两个版本的数据，这样就需要将之前的数据标记为无效，只使用现在的在内存中的最新的数据。之后处理磁盘上面的数据块的时候，也要将这个块里面的过期的数据忽略。这样的做法还有另外的一个问题需要处理，就是随着时间的推移，一个磁盘上面的数据块里面存活的数据是越来越少的，这里就需要将这些数据块里面的数据合并，同时更新相关的结构。

We employ a lazy block compaction algorithm during the merge process. This compaction works by tracking the number of holes in each of the blocks in the Block Table. When the DBMS retrieves a block from disk, it checks whether the number of holes in a block is above a threshold. If it is, then the DBMS will merge the entire block back into the memory, just as with the block-merge strategy.


#### Distributed Transactions & Snapshots & Recovery

• Distributed Transactions，Paper中使用H-Store数据还支持分布式事务，这里的方式和在单一分区的方法没有很大的区别。另外一个要注意的问题就是H-Store会确保在处理取回数据的时候它要访问的元组不会被驱逐出去,

The transaction is aborted and not requeued until it receives a notification that all of the blocks that it needs have been retrieved from the nodes in the cluster. The system ensures that any in-memory tuples that the transaction also accessed at any partition are not evicted during the time that it takes for each node to retrieve the blocks from disk.

• Snapshots & Recovery，snapshot的处理和一般的数据库没有什么区别，要做的额外的时间就是在antiaching中添加的几个结构也需要做对应的处理就行了。在一个snapshot执行的过程中是不允许驱逐出去的，因为这样可能导致出现错误。未来优化性能，还是用了增量snapshot的方式，

Instead of making copies for each checkpoint, the DBMS takes delta snapshots. Because the data within a block in the Block Table is not updated, the DBMS just checks to see which blocks were added or removed from the Block Table since the last snapshot. This technique greatly reduces the amount of data copied with each snapshot invocation.


## 参考

1. Anti-Caching: A New Approach to Database Management System Architecture, VLDB’13.