cache源码分析一 存储机制分析

trafficserver的cache层包含两层，它在内存中维护了一个ram cache，缓存热点数据，该层的具体描述见这里，与此同时ts提供了磁盘一级的存储。

对比了一下trafficserver的cache存储系统与squid的coss文件系统，不难发现，它们的本质都是将cache看作是一个ring buffer，对这个buffer顺序写数据，当buffer满后回到首部继续顺序写入数据。在buffer满后，循环写入的机制不可避免会产生新写入的内容覆盖掉原来的内容而造成数据丢失。在web cache这种应用场景，这种实现方式是可行的，因为web cache的应用场景是在用户层与源服务器层之间加了一层存储做web加速之用，所以如果web cache上没有用户请求的数据，它会回源服务器请求数据，在取得源服务器的响应提供给用户端的同时，会把内容本地保存下来，下次用户请求相同的数据时，如果数据没有失效，也没有被覆盖，就可以直接从cache取出提供给用户服务，从而起到web加速的目的。

ts的存储系统支持任意大小的object读写，在ts安装好后，ts通过storage.config文件配置ts的存储路径，存储路径可以是一个文件，也可以直接是裸设备。

ts将用户配置的物理存储空间，逻辑上看作是一个个大文件，每个大文件视为一个ring buffer。通过向一个大文件写和读数据，从而避免了频繁调用open()与unlink()的系统开销。

当然，此ring buffer非内存中维护的ring buffer，它涉及到磁盘的写与读。当stop ts时候，缓存内容是持久化保存在磁盘上的，而当start ts时候，需要从磁盘上快速查找到用户查询的object。所以与传统文件系统如ext等一样，ts的cache系统需要对这个逻辑上视为一个大文件的disk空间进行格式化操作，以及索引的建立等操作。

Disk layout

如图所示，ts将整个disk逻辑上分为3个部分，前面两个Directory，维护的是整个disk的索引区，在ts启动后，会将Directory加载到内存中，以加快cache查找速度。同时CacheSync这个Continuation会定期将Directory信息flush到磁盘上去。ts使用数据结构Dir代表索引区中的每个索引。ts将剩余的disk空间看作一个ring buffer，用于读写数据。

ts是以理想模型来建立disk layout的。在理想状态下，ring buffer中存储的是相同大小的object。在此条件下，对ring buffer进行逻辑分段，并对每一段进一步分桶，每个桶只保存4个object，一个object的元信息保存在一个索引Dir中。基于此，只要知道一个disk空间的大小，就可以计算出一个disk需要多少索引。对于不同的应用场景，通过估算最坏情况下object的最小平均大小，就可以估算出一个应用场景最多需要多少索引。这个最小平均object大小是可以配置的，在records.config文件中，通过修改变量proxy.config.cache.min_average_object_size可以调整值的大小，默认为1M。

在实际实现上，ts存储一个segment中所有object的索引，维护了一个链表freelist。freelist将所有未使用的Dir构成一个双向链表，当向磁盘上写object时，从freelist中取出一个Dir，当删除一个object时，则回收对应的Dir至freelist上。由于一个segment包含很多bucket，以segment为单位对索引构造一个freelist，就避开了理想模型中一个bucket只能包含4个Dir的限制(但从源码上可以看到，ts规定一个bucket最多包含100个Dir)。

在web应用中，ts根据用户请求的url，计算出这个object对应的key值，该值是一个由2个64位整数构成的数组，也就是4个32位的整数。ts通过对第一个32位整数做hash映射查找到object对应的Dir所在的segment，再通过第二个32位的整数做hash找到对应的bucket，最后在这个bucket上找到第一个没有使用的Dir，由此就得到了该object对应的索引。如果计算object的key值的算法足够高效，且每一级映射也足够高效，则正如理想模型所示，每个bucket中object数目为4个，在桶中查找一个未被使用的索引速度就会很快。

索引的格式

Directory在物理上按顺序包含三部分内容，分别是header，索引区，footer。header与footer对应的内存数据结构为VolHeaderFooter，它包含了很多维护索引区以及读写操作的元信息。这里，最重要的数据结构就是每一个segment对应的freelist的首节点元素构成的数组，由此就把整个索引区串了起来。

每个索引对应的内存数据结构为Dir，这是一个由5个16位的整数构成的数组，共10个字节。这些字节维护了一个object保存在磁盘上的所有元信息。

iocore/cache/P_CacheDir.h中提供了很多宏用于操作Dir。比如，宏dir_set_offset用来将一个object在磁盘上的位置信息保存下来，它使用Dir的第一个，第五个的所有16位，以及第二个元素的低八位，共40位，存储一个object在disk上的位置。

object的存储格式

数据结构Doc对应的是一个object在磁盘上的格式。

作为一个web cache，它实际上保存的就是源服务器对一个http请求的http响应，它包含head和body两个部分，对应上图中的hdr与data。

ts以一个fragment为单位，如果一个http响应，也就是一个object的大小小于一个fragment，则视它为一个小文件，否则，ts认为它是一个大文件。这个fragment的大小是可配置的，在records.config文件中通过修改proxy.config.cache.target_fragment_size即可，默认为1M。

如果一个http响应作为一个object是一个小文件，ts是使用一个Doc完全保存该object的内容。这时，hdr保存响应头，data保存响应体。

如果一个http响应是一个大文件，这时ts首先单独使用一个Doc保存响应头的内容，而对于响应体，根据fragment的大小，会被切分为好几个fragment，每个fragment使用一个Doc保存。在响应头的head中，frags数组维护的是每个fragment在整个http响应内容中的位置信息。

对于小文件，该object生成的key值保存在first_key中。而对于一个大文件，整个http响应作为一个object生成的key值保存在first_key中，这个key值由响应头对应的Doc使用，由此在cache查找时，首先找到的就是一个http响应的头部。响应头的Doc的元素key保存的是第一个fragment的key值。而对于每个fragment，第一个fragment通过随机算法生成一个随机数作为一个key值保存在其对应的key中，后续的每个fragment的key值都是以前一个fragment的key值为种子随机生成的。

通过随机算法计算每个fragment使用的key值，这样做的好处是使得所获取的key值尽可能离散，从而映射到索引区的不同bucket中，避免了一个bucket不会维护太长的Dir链表。

下图描述各个fragment是如何通过随机数算法联系起来的：

第一个fragment的key值需要保证不和first_key冲突，否则重新随机生成一个，直到不冲突为止。