Page 87 - 《软件学报》2021年第5期

尤勇 等:一种监控系统的链路跟踪型日志数据的存储设计 1311

blockArray.append(logData)
end function
在反过来进行查询操作时,能够通过 headAddress 和 blockSize 读取指定大小的块到内存中,然后根据块内偏
移量 offset 定位到内存块从哪里开始是表示指定 LogView 的数据.偏移量的后 4 个字节表示 LogView 占据的字
节量大小 logSize,从而可以读取到对应 LogView 被压缩后的所有字节数据,再经过解压缩即可获得 LogView 的
原始日志数据.
3.2.2 压缩算法性能比较
表 1 展示了多种主流的快速压缩算法的各项指标的数据,机器配置为 Core i9-9900K CPU@5.0GHz [23] .从表
格可以看出:lz4 的压缩与解压缩的速度都是最快的,而压缩率比较小.CAT 使用的压缩算法是 Snappy,虽然该算
法的压缩与解压缩速度不如 lz4,但是 lz4 的压缩效率受数据块的大小影响较大,而 Snappy 受此影响较小.事实
上,每条日志的数据量大小也是不定的,所以后者更加合适.Snappy 是目前很成熟的压缩与解压缩算法,它具有
更加稳定的性能,所以同样选择性能稳定均衡的 Snappy 更合适.

Table 1 Performance comparison of compression algorithm
表 1 压缩算法的性能对比
Compressor name Ratio Compression (MB/s) Decompress (MB/s)
zstd 1.4.5 -1 2.884 500 1 660
quicklz 1.5.0 -1 2.238 560 710
lzo1x 2.10 -1 2.106 690 820
lz4 1.9.2 2.101 740 4 530
snappy 1.1.8 2.073 560 1 790

3.3 两级索引的结构设计
在创建数据文件之后,需要创建对应的索引文件,且当内存块写入数据文件后,同样需要更新对应的索引
文件.
存储方案设计了两级索引,每级索引中的索引条目(entry)空间大小为 8byte.如图 6 所示:正常情况下,存在一
个一级索引和 4K−1(4×1024−1)个二级索引,且一级索引中存在 4K 个 Entry,每个二级索引中也同样存在 4K 个
Entry,所以所有一二级索引总计占用 4K×4K×8bytes(即 128MB)的空间.如果当前一级索引中所有 Entry 都被使
用了,会在索引文件后继续创建一个新的一级索引和 4K−1 个二级索引;而索引文件中是否存在多个一级索引,
可以通过文件中的大小进行判断:如果索引文件的大小超过了 128MB,则会存在多个一级索引.

Fig.6 Structure of two-level indexing
图 6 两级索引结构
• 一级索引(header)
如图 7 所示,一级 Header 索引中存在 4K−1 个有效 Entry 与 4K−1 个二级 Segment 索引一一对应.每个 Entry
占据 8byte 的空间,且 8byte 共 64 位分别用于存储 ip 地址与{index}的哈希值,高 32 位存储 ip-v4 地址,低 32 位
存储 index 模 4K 的哈希值.
• 二级索引(segment)
如图 7 所示,共计 4K−1 个 Segment 索引,且每个 Segment 下对应存在 4K 个 Entry,每个 Entry 同样占据 8byte