间% 67 8算法的速度源于简单% 在 67 8压缩算法
E+, C A +N 4 O 编码表 中#将一连串的 " 或者 ! 序列使用 =
示#而将相对较短的 " #! 混合序列按源序列编码#
67 8算法的高效性还在于它们是基于 D < = M, 3 C ) N +A M
的压缩数据% 确切来说#67 8压缩数据包含 . 种类 型的字!字面字和填充字% 字面字使用 ! Q) 存储类 4 型#其余比特存储逐位存储位图% 填充字也需要 ! 存储类型#使用另外 ! Q) 存储指示 " #! 序列的 4 Q) 4 指示位# 其 余 位 用 来 存 储 该 填 充 字 包 含 的 字 节 长 度% 通常填充字所包含长度是字面字的整数倍%
,+$ %& ' ( ) ' 结构
和传统数据库一样#以行和列组织数据% 2 3 * 4 5 ) 4 引入了分区可以将数据记录多的表存储在多 2 3 * 4 5 ) 4 个分区% 每个分区是一个目录# 分区内的元数据文
= 4 # 4 T 4 件 RS3 记录分区主要信息# 如分区名( 分区记
录数(分区列数目( 列名( 索引设置信息( 列的数据 类型(分区创建的时间戳以及创建该分区的描述信 息等% 数据分区内的主要文件是数据文件和索引 文件% 数据采用列式存储方式# 将每列数据存储为 一个文件# 数据文件名是该列的列名) 索引文件名 是对应列的数据文件名加上# ) MT后缀% 列名# U * F 文件用来指示该列数据文件中空值的位置% 使用 的数据文件必须转换为二进制文件才能使用% 数 据转换程序读取原始格式的源文件然后按列存储
-. -+位图索引 X H @ A ) C 位图索引由 W 在 !%-V 年提出 & / ' # 最简单
/+建立位图索引
2 3 * 4 5 ) 4 构造位图索引分为 $ 步!划分区间(编码
和压缩%
/. ,+划分区间
的位图索引是基本位图索引# 利用一个位向量表示 被索引属性的某个取值是否在被索引数据中存在% 位图索引由一系列代表索引属性的信息位序列组 成% 属性 的索引如图 ! 所示% 的可能值为 " #! #
3+测试与验证
为了验证该解决方案的性能#将系统部署在西南
J > #网络带宽 ! ] Q) 4 ' * % 系统将流量镜像在 ; ) +E, 某\ T W > "L A M8 3 4 ^ +4 A = S= ) * A; ) +ET 0_ $ &/Q) 4 # !& \ +4 A C "L $ ` A < +" L $ > W a^ 00." ._ .V 8 b #/ ] 5内存#. 块 97 G 7
&' 并#所以只需要进行额外的位逻辑运算&0, %
份目录#
. $ 交换当前工作目录与与备份目录# $ $ 用户对新生成的数据进行数据完整性测试#
选择回滚或者提交%
-. /+01 2 算法
-+$ %& ' ( ) ' 的特点
最主要的特点在于采用列式存储方式# 2 3 * 4 5 ) 4 能够构造丰富的位图索引# 采用独特的位图压缩算 法 67 8应对海量数据的查询# 尤其是范围查询具 有更短的查询响应时间%
/. -+编码
序列表示# 每个位序列被称为位图# 由位图和与位 图相关的信息共同组成位图索引%
编码是分配分区描述符并把分区描述符转换 为位图的过程% 平等编码( 范围编码和间隔编码是 的 $ 种基本编码方法% 2 由基本编码方 2 3 * 4 5 ) 4 3 * 4 5 ) 4 法演变出了多范围编码和多部分编码%
图 ,+位图索引
平等编码是最简单的编码方法#在平等编码中每 一个位图代表一个区间% 如果一个值在特定区间内 就把该区间对应的二进制位置为 !#其余的二进制位
位图索引在数据仓库和在线分析系统等密集查 询中特别有用% 位图索引响应查询速度快的重要原
* V/ *
! " # " $ % &' ( ))* + " ' % $ " ( +, . / 0 . -
* V$ *
工程应用
在以列名命名的文件下% 数据格式转换的过程分 $ 步完成!
! $ 将要转换的数据追加至当前工作目录的备
因是通过对位图进行逻辑位运算实现% 如图 ! 的例
., 的查询#就是通过对 !和 .进 子中如果进行+ Y
行逻辑或运算实现的% 位图索引查询速度快的另一 个原因是对于多个索引的查询结果合并速度快% 因 为每个位图索引的结果都是位图将这些结果进行合
. #$ % 对于每一个可能值都使用由 " 和 ! 组成的位
划分区间是扫描数据文件的值将它们划分到 若干个区间# 生成建立位图索引需要的描述符# 最 基本的划分区间策略是每个值一个区间% 划分区 间的一般策略是使用比列的基数更少的区间# 能够 减少需要使用位图表示的值的个数从而减少索引 大小#缺点在于值的精确度降低# 使用索引无法直 接完成所有查询#需要对边沿区间的值进行候选检 查#通常该 过 程 需 要 的 时 间 会 占 查 询 时 间 的 大 部 分% 从性能角度考虑#不划分区间是更好的策略%
%%% #可以按照十进制把每一个三位数分成 范围 " [ $ 个部分# 每一部分分别 进 行 平 等 编 码% 这 样# 个
由于位图索引自身的特点#位图索引中的每个位 图都含有大量的 "#这种规律使位图易于压缩% 为更 研究人员开发出了具有更快 有效地响应查询#2 3 * 4 5 ) 4
8 减少查询相应时 逻辑位运算能力的压缩方法 67
工程应用
! " # !!"# $%&% ' ( # ) * * +# !""!, $-./# ."!.# "!# "!-
在流量测量系统中的应用 $ %& ' ( ) 'பைடு நூலகம்
康书恒杨子江
" 重庆邮电大学 未来网络实验室#重庆 /"""&0 $
3 * 4 5 ) 4 摘1要通过对当前网络测量系统中数据存储方案的分析引入一种新的基于位图索引的列式数据库 2 的解 8算法减少了索引占用的存 决方案通过对不同查询类型引入不同索引编码方法可以提高查询的效率使用 67
工程应用
3 * 4 5 ) 4 置为 "#每一个位组只有一位置为 !% 在 2 中不
少的位图表解析较小的范围# 因此多级索引的底层 通常采用平等编码%
/. /+压缩
同的编码适用于不同的查询类型% 平等编码适于
Z 类型的等值查询%
范围编码的第一个位图是与该范围编码一致 的平等编码的第一个位图# 范围编码的第二个位图 是平等编码前 . 个位的或运算# 平等编码的第三个 位图是平等编码前三位的与运算# 以此类推范围编 码的第 位是平等编码的前 位的逻辑或运算% 由 于范围编码的最高位都是 ! # 因此范围编码时可以 省略最高位% 范围编码最适合用于单边范围查询% 间隔编码中每一位都是平等编码中的大约总 位数一半的位逻辑或运算% 假如平等编码中划分 了 !"" 个区间#则每一个值都需要 !"" 位的位图来 表示#而在间隔编码中只需要 0! 位位图表示% 间隔 编码的第一个位图是平等编码中的前 0" 个位图的 逻辑或)第二个位图是对应的平等编码中的第二个 位图开始的连续 0" 个位图的或运算% 以此类推#第 个位图是对应平等编码中的第 位开始的大概总 位图数目一半的位的或运算% 间隔编码# 是为双边 范围查询设计的# 然而间隔编码的位图不易压缩# 其使用并不广泛% 多部分编码是将分区分成多个部分然后对每 部分分别进行编码% 比如有! """ 个分区#数字持续
-. ,+列式存储
位图索引最主要缺点在于位图索引的大小随 着基数性的增大线性增长% 67 8 压缩方法通过压 缩每一个位图减少索引的大小# 同时使位图压缩的 处理更有效率% 一般来说# 索引存储在硬盘或者其 他辅助存储器上% 查询时# 在运算之前将索引的相 关部分读取到计算机的内存中% 传统观念认为# 查 询时将部分索引读入内存的时间大于将数据载入 中由于采用了 内存进行运算的时间#然而在 2 3 * 4 5 ) 4 压缩技术#查询时使用压缩位图索引计算位图的时 间多于将位图载入内存消耗的时间% 67 8 算法的 出现不仅提高了压缩位图的计算效率# 而且有效减 少了索引大小%
列式存储方式更适合于数据的存储与查询# 主 要体现在 . 点!第一#同一列的数据类型一致且具有 更高的相似性#采用按列存储的组织形式可以有效 降低数据的基数性# 从而降低位图索引的大小# 节 省存储空间) 第二# 由于在大量数据查询时数据量 非常大#数据按列存储可以避免不相关列数据的读 取#有效提高计算机资源的利用率和加快查询速度%
储空间位图索引可以在查询时快速生成 不需要时删除 通过在网络环境下的测试 证明了该解决方案比基于
9: ;数据库的方案有更高的效率更适合高速网络的测量 3 * 4 5 ) 4 关键词2 位图索引列式数据库按字编码网络测量
*+引+言
流量测量系统通常需要采集每个数据包的信息# 而随着互联网带宽的不断增加由此产生的采集数据 会非常庞大#对这些数据进行快速存储和分析变得越 来越有挑战性% 传统的数据存储方案有. 种!文件系 统存储和关系数据库存储% 文件存储方式架构简 单#数据紧凑# 容易实现# 并能提供较高的压缩比# 适用 于 小 型 监 测 系 统 中# 典 型 的 如 9+< 系 统 & !' % = 4 不过文件存储方式分析效率很低# 数据管理不便# 难以满足大规模( 高速网络的监测要求% 关系数据 库存储方式可以利用数据库提供的 9: ;和丰富的 函数提供灵活的查询和聚合# 在报表创建和数据聚 合方面很有优势# 广泛应用于商业流采集系统# 如 等 & .' # > ) * ? <@ A 4 B C < D? < C C A ? 4 < = #2 C EFA@ A 4 B C < DG = 3 ? FA = 然而关系数据库为了加快查询速度通常会引入索 引#在数据录入时需要更新索引# 这样就会降低了 插入速度并且索引会占用较大的存储空间% 关系数据库由于自身的存储结构和特点#在对海 量数据进行快速分析时存在一些不足#通过不断分析 和探索#我们试图使用非关系数据库解决该问题% 使 用位图索引的 2 是一款追随 @ 3 * 4 5 ) 4 H 9: ;运动的开 类似以列的形式存 源数据库#与 I < +A 4 J 5和 K A = 4 ) ? 3 储用户数据#由美国加州大学伯克利分校劳伦斯伯克