2009年10月7日星期三

Bitmap 的数据库持久化实现

以下是基于数据覆盖的一个初步讨论,实用中,位映射有广泛的应用领域,也有大量的算法实现需求。在经过初步的推演后,我发现这不是可以一蹴而就的。所以先给出一个简单的实现和应用算法讨论。

Bitmap 的数据库持久化实现

Bitmap 是一个常见的数据类型,常用于优化大量数值的存储和查询。这个概念对于数据 库程序员应该不陌生,Oracle 等数据库通过这种技术优化查询。通常程序员会在一些算法 或数据结构书籍上读到以 C 语言 char* 实现的 bitmap 。这里,我们考虑一个在数据库中 存储的 bitmap 实现。

PG 上的数据结构实现

bitmap 的实现不难,PostgreSQL 中提供了 bitstring 类型,可以直接存储位串。但是单行 bitstring 能提供的数据长度终归有限。为了存储和性能的需要,我们将其设计为一个表。 通过索引值将 bitmap 分片为 bitstring 集。

create table bitmap(idx bigint, segment bit(32));

分析

计算时我们将一个bitmap表视为一个完整的bitmap数据集,设 segment 的宽度为 w ,索引 值为 i 。将第行的 idx 置为0,则第 i 个索引行上的第 b 位对应整个 bitmap 的第 b+i*w 位。逆推之,bitmap 第 x 位为 x div w 行,第 x%w 位。

因为数据分行存储,位计算操作也需要重新定义,要考虑跨界定位问题。Postgres 的 bit 本身支持左移右移操作。这点并不复杂。可以利用掩码技巧将计算参数分解为区片。具体算 法几乎与 C 语言版本一致。当然针对一些有规则操作时,可以充分的利用 SQL 和 PLSQL 的语法特色进行简化。

实例

覆盖统计

详细内容介绍见下一段中的链接。这里简单介绍一下:每个数据样本是一个由大量一维区间 值组成的文本。每一行是一个(起点,终点)区间。要计算二到N个样本件的覆盖率。而数 据本身是未经整理的,可能有重复。

事实上,这个例子是我最初着手实现 bitmap 的起因。可以说 bitmap 可以直接优化此类问 题,首先bitmap以至少8倍以上的比例节省存储空间(以 c 语言 char* 每字节存储位置状 态来计)。而空间缩减后对查询性能也有直接提升。

这个应用的操作非常好实现,将收集来的数据区间段(s, e)转换为二进制数 2^s+2^(s+1)+...+2^e ,即从 s 到 e 之间都为1的二进制位串。然后与整个 bitmap 做或 运算。示例代码如下:

create or replace function segment_over(s bigint, e bigint) returns void as $$
declare
sidx bigint;
eidx bigint;
d_data bit(32) := 4294967295::bit(32); -- pow(2, 32) -1
begin
if currval('bitmap_idx_seq') < (e/32)+1 then
for i in currval('bitmap_idx_seq')..e/32+1 loop
insert into bitmap(segment) select 0::bit(32);
end loop;
end if;
sidx := s/32;
eidx := e/32;
if sidx = eidx then
update bitmap set segment = (d_data << cast((32-e%32) as int))&(d_data >> cast((s%32) as int)) where idx = sidx;
else
update bitmap set segment = segment | (d_data >> cast((s%32) as int)) where idx = sidx;
update bitmap set segment = d_data where sidx < idx and idx < eidx;
update bitmap set segment = segment | (d_data << cast((e%32) AS INT)) where idx = eidx;
end if;
end;
$$ language plpgsql;
优化分析

此示例中,segment_over 操作并未做任何深度优化,仅仅是将前述的思路直接实现出来而 已。实际上根据业务,我们还可以进一步的提高操作效率。

例如,由于覆盖度操作是在数据区迭加或操作,单向的填充动作,可以将已覆盖区间直接压 缩掉(这需要将 idx 字段扩展为起点和终点一对数据,或者通过触发器机制同步一个查询 表)。

再例如,前例中我们的 segment 长度为32,idx 是一个 bigint 类型。这对于海量数据比 较有效,不过如果总样本量较小,完全可以用 integer ,这样可以减少很多转型操作。

在 segment_over 中,我写了一个防出错的探测代码,如果索引值超出了初始化范围,会扩 展 bitmap 表。但是实际上很多应用,其总数据量是有明确上界的。此时可以去掉这部分代 码,使用一个一次性的初始化代码,例如下面这样:

create or replace function init(len bigint) returns void as $$
declare
i bigint;
begin
truncate table bitmap restart identity;
insert into bitmap(idx, segment) select 0, 0::bit(32);
if len/32 < 1 then
return;
end if;
for i in 1..len/32 loop
insert into bitmap(segment) select 0::bit(32);
end loop;
if len%32 > 0 then
insert into bitmap(segment) select 0::bit(32);
end if;
end;
$$ language plpgsql;

将 segment 的宽度调整为略大于覆盖区间长度期望值的数值,可以减少对中间区间的覆盖 操作,也有优化读写效率的可能。

数据库实现的动机

使用数据库存储 bitmap ,可以避免海量长度 bitmap 超出内存容量的情况,是一个比较经 济的实现方式,特别是在机器不够强劲,或者没有条件部署云或网格集群的场景。只要熟练 数据库层开发即可。

由于 Postgres 中已经实现了完备的并发访问、数据备份和查询等功能,可以避免自己开发 文件型 bitmap 所需要考虑以上问题,带来的开发成本。轻松可以满足 OLAP 的需求,在线 随时查询覆盖情况。

合理的使用数据库功能,可以有效的降低使用和开发成本,这种组件式的开发和集成方式, 对于当下追求灵活、高性价比和可持续性的 IT 产业理念,是契合的。


……

劉鑫
March.Liu