Cassandra源码阅读之本地数据存储/读取实现

作者: yangzhe1991 分类: 我是搞技术的 发布时间: 2014-08-11 19:44 ė 6没有评论

前文写了C*的轻量级事务的实现,侧重的是网络和逻辑的流程,因为整体的流程cas的操作包含了读写,所以没必要再研究C*如何完成一次完整的读取或者写入。不过对于流程的认识还局限在发了一条消息到对方节点异步等response,还不太清楚在节点本地如何读写数据,于是就研究下C*的数据存储以及相对应的读写逻辑。

C*的数据存在本地,不依赖第三方的分布式存储服务(相对于HBase需要hdfs),这样可以针对C*的特性来定制本地的存储逻辑,但因为也需要集群自己来实现存多份冗余,需要在数据库层面维护数据的强一致性。定制化的存储,一个很简单的例子是C*把SSTable按照data/keyspace/table的目录形式来存,而unix是支持按目录挂载不同的磁盘,因此理论上可以把一个ssd挂载到某个keyspace的目录,把机械硬盘挂载到/,这样那个keyspace的数据就总是会保存在ssd上,其他的表存机械磁盘,从而加速了特别需要降低响应时间的表,同时节约成本不需要全上ssd。

本地的数据除了放在本地磁盘的还有放在内存的。放内存的数据C*基本上都是用java的off heap memory实现,即不放在JVM的堆上,不通过JVM GC。坏处当然是需要自己释放自己管理,好处是尽量减轻GC的负担。

按照BigTable的数据模型,C*自然会有MemTable(放在内存)、CommitLog(放磁盘)和SSTable(放磁盘)。而为了提高性能,还构造了其他的辅助数据,这些数据有的放内存并备份到磁盘,有的放磁盘中。

缓存(Cache)

C*的缓存分三种,RowCache、KeyCache、CounterCache,都存储在off heap的内存中,分别缓存整行数据、key所在SSTable的位置、Counter数据。前两者是每个表二选一的一种配置,缓存整行数据还是只缓存key所在位置减少查找次数。CounterCache用来缓存counter类型的值。缓存值的RowKey每个表只会有一个key,对应一个value;而缓存数据所在位置的KeyCache,是存每个SSTable中某个key的位置,读一个key要读多个KeyCache。

因为内存的数据重启服务之后就没了,为了减少重新预热导致服务器延迟变高,缓存会定期备份到磁盘中。所有缓存都存在配置文件中指定的saved_cache目录,文件名按照{keyspace}-{table}-{RowCache/KeyCache/CounterCache}-{version(格式的版本,目前是b)}.db来保存。其中RowCache和CounterCache因为不能保证备份的时候的value和目前该key最新的值依然是一致的,因此在序列化到磁盘时只存了key的信息(具体来说就是一个数字n代表key的长度,然后接下来n个字节代表序列化成bytes的key),启动服务重新加载的时候会根据key重新去MemTable/SSTable读最新的值,而且是异步的读,读成就写进内存;而KeyCache因为是每个SSTable独立对key维护而SSTable是immutable的,缓存的位置也不会变,所以是可以把位置信息备份到磁盘的。

MemTable

MemTable理论上只要是个线程安全的哈希就行。但因为C*支持按where token(key)>123456这样的查询方式,也为了方便按token(row key)的形式序列化成SSTable,因此C*里的MemTable是个跳表SkipList,用的是jdk自带的ConcurrentSkipListMap。跳表的好处就不细说了。根据具体的配置和环境,MemTable中实际数据可能在heap里也可能off heap。然后因为C*的数据模型是二级map,每个row也是个map<column key,column>,而第二级在MemTable里是自己写了一个基于数组的b树,我猜这是因为同时读多个column的时候,基于数组比基于链表读出来要快很多。

在本地查询数据

当READ请求传到本节点,而对应查询的表又不是RowCache或RowCache不命中时,执行下面的逻辑。(如果是RowCache,查询完put进cache)

先区分要读的数据是普通数据还是counter。普通数据,在所有SSTable及MemTable中每个列取timestamp最新的value即可;而counter的数据因为是增量的写、求和的读,所以需要找到散布在每个地方的数据然后累加。一个是合并每个列的数据,一个是合并某个列的所有数据。合并的时候都需要特殊判断删除的情况,比删除操作timestamp小的所有数据相当于都要作废。因为具体查找SSTable/MemTable的逻辑相近,只考虑普通数据的情况。

C*针对每个表在heap中维护了一个区间树(Interval tree,可别和线段树segment tree搞混了),来方便查找哪些SSTable有可能涵盖对应的查询。算是一种剪枝。

因为内存性能比磁盘高、Memtable比所有SSTable生成的都晚、一旦Memtable里最近有删除可能SSTable完全可以忽略等等原因,会先读对应表的MemTable把数据拿出来,并记录最后一次删除操作的时间戳。然后把SSTable数据的最大时间戳排序然后逐个SSTable来分别查询对应key的数据。最后把每个Cell(列)的最新数据合并成一个ColumnFamily类型返回。

SSTable

终于到了最复杂的结构。

SSTable作为一种只读不改的结构,其设计只需要考虑如何快速的读取。C*定义了多种数据格式作为基础SSTable的辅助,帮助更快的查找数据。SStable存在配置文件中设置的路径中,按照keyspace/table/filename的形式命名,其中filename的命名格式为{keyspace}-{table}-{version}-{generation}-{type}.db。

version是数据格式的版本,两个字母,第一个是大版本,貌似从h开始;第二个是小版本,在每个大版本中都从a开始,最近的一次版本升级,2.0.0是ja,2.0.1是jb,2.1.0是ka。

generation是本地文件的版本号,每个table每生成一个SSTable,这个数字就+1,用来在本地唯一标识同一个table的不同SSTable。

type是具体的文件种类(代码中定义文件的类型的类是Component),包括真正的SSTable数据和辅助的数据。目前最新的稳定版本2.0.x中一共有7种——Data、Index、Filter、CompressionInfo、Statistics、Summary、TOC。也就是说生成一个SSTable就会有这7个文件。其中,Data是真正的SSTable数据;Index是索引文件,存储一个key在SSTable里的位置;Filter是把内存中的bloom filter进行序列化备份,bloom filter可以高效的判断一个key一定不在这个SSTable里还是有非常大概率在这里;CompressionInfo用来存压缩数据相关的信息;Statistics存统计数据;Summary是下采样的索引,放在内存中并序列化备份到磁盘上,后面会细说;TOC后缀名是txt而非db,用来保存这个SSTable都有哪几个文件,table of contents。

SSTableReader类load到一个SSTable的所有文件之后就可以读数据了。从SSTable读数据总体分两步:找到key所在的位置(或不存在),这个位置信息封装的类叫RowIndexEntry;再再对应位置从Data中拿数据。

找key的位置,首先过bloom filter,如果一定不存在就直接退出;然后走KeyCache,如果找到就直接获取到了位置。

接下来去查询内存中的index summary,即会被序列化到Summary文件中的采样索引。在2.0.x的版本中,默认SSTable中每128个key在这个索引中出现一个,所有key有序排列,查找一个key的时候只需要二分即可找到对应的长度是128的区间。这样就把SSTable的搜索范围从几万几十万甚至更多个key减少到128个。这个128是可配置的。2.1开始,index summary支持动态调整下采样比例,对不热门的SSTable最大变成每2048取1(也是可配置的),减少内存占用。index summary的value是对应key在Index文件中的位置,sampledPosition。Index在硬盘中。

Index和Data文件读取的时候都会被分成若干个segment,每个segment分别是一个FileDataInput类。因为这俩文件的读取为了加速,会尽量使用mmap,而mmap把文件映射到内存里肯定会有大小的限制,所以把一个大文件拆成若干个segment就降低了内存的使用。拿到Index文件的从sampledPosition开始的文件输入流之后就按顺序读Index文件中的key,跟查询的key比较。

在Index文件中存储的是序列化的RowIndexEntry类型的数据,这个类型也是KeyCache的value。首先是一个short类型的16bit数字表示长度,然后bytes表示key;接下来是一个64bit的long数字表示SSTable中的position;一个int表示是否有后续信息(但好像这个具体的数只判断了是否大于0,不知道为啥不是bool,可能是兼容性吧);如果有后续信息,先是这行数据的删除标记,具体说是一个int+一个long分别表示墓碑tombstone的本地创建时间(涉及到何时彻底删除此数据,默认是10天后)和数据删除操作发生时的毫秒时间戳用来屏蔽掉小于这个时间戳的数据,俩数据搞成正无穷就说明这个row没被删;接下来是column index,一个int表示被index的column个数,然后n个column index分别被序列化。

C*属于WideRow类型的数据库,前面提到的所有的key都是物理层面一行数据的key,即partition key。而Column实际上也是CQL模型中table中的一行。所以找到Data中一个key对应的位置不够,还需要根据其他主键的查询条件定位到对应的Column中。cassandra.yaml里可以配置column_index_size_in_kb这个项,默认是64,即当一个WideRow的数据量超过64K之后,会建立一个column index,每64K建立一个column index。column index相当于一个区间,被封装成IndexInfo类,里面存这个区间第一个Column、最后一个Column、相比于这个Row所对应的Data文件起始position的偏移量,区间总长度。因为Column中的主键(封装成CellName)是按定义顺序来限制查询条件的不能跳过,所以逐个CellName的定位column index即可最终找到需要的第一个Column。

读到了最接近需要的result的精确position,可以去Data文件拿最终的数据了。把clomun index中可能满足条件的所有区间按顺序逐个扫描,满足条件就加到最终的读取结果里,因为是按顺序的,所以输出的结果直接就是有序的了。

终于等所有SSTable都执行了这样的读操作之后,再全局过一遍删除信息保证被删掉的数据都被拿掉,就可以把结果返回了。整个读数据的流程结束。

此外,如果最终发现拿到了数据的SSTable数>=设置的最小compaction文件数,就自动执行compaction。

 

本文出自 杨肉的演讲台,转载时请注明出处及相应链接。

本文永久链接: https://yangzhe1991.org/blog/2014/08/cassandra-code-reading-local-dada/

发表回复

您的电子邮箱地址不会被公开。

 

Ɣ回顶部