Succinct Data Structure

作者:唐刘

最近看了一篇论文 SuRF: Practical Range Query Filtering with Fast Succinct Tries,里面提到使用一种新的数据结构 Succinct Range Filter(SuRF) 替换掉了 RocksDB 默认的 Bloom filter, 在一些性能测试上面,尤其是 seek 上面,性能提升了不少,并且也降低了很多 I/O 开销,这一下子就引起了我的兴趣。

大家都知道,RocksDB 里面,为了加速 key 查询的速度,使用了 Bloom filter,但 Bloom filter 只适用于 point get,对于 seek 就无能为力了。虽然 RocksDB 后面引入了 prefix seek,但对于 key 的格式有要求,使用比较受限。为了提高 RocksDB range query 的速度,论文的作者引入了一种省空间的数据结构,也就是 SuRF。

在了解 SuRF 之前,首先要了解掌握的就是 Succinct data structure 相关的知识,这篇文章主要是讲 Succinct data structure 相关的东西,后面再讨论 SuRF 如何实现的。

Rank 和 Select

Succinct data structure 第一次提出,应该是 Guy Jacobson 的论文 "Succinct static data structures",但实话,我在网上找了半天,都没找到这篇 paper,只是找到了作者另一篇 Space-efficient static trees and graphs。它的主要思想就是使用非常少量的空间(接近信息编码的下界)来存储数据。你可以认为就是使用了一种非常高效的压缩算法,但不同于压缩,它同时来提供非常高效的查询。

对于 Succinct data structure 来说,我们会将数据按 0 和 1 来编码,所以可以用 bits,而不是 bytes。操作 succinct 数据,通常的就是几个操作函数:

  • rank1(x) - 返回在 range [0, x]里面 1 的个数
  • select1(y) - 返回第 y 个 1 所在的位置

上面我们只是列举了 rank1 和 select1,对应的也有 rank0 和 select0,这里就不需要解释了。这么说有点过于抽象,这里举一个简单的例子。假设我们有一个 bits 序列 11000001,那么 rank1 和 select1 可以映射如下:

image

另外,大家可以注意到,rank 和 select 其实是相反的,上面的例子,select1(3) = 7,然后我们也会发现,rank1(7) = 3

Level Order Unary Degree Sequence

上面简单介绍了下 Succinct data structure 的 rank 和 select。 在 SuRF 里面,它参考的基础编码方式,是 Level order unary degree sequence(LOUDS),在 LOUDS 里面,我们会将一颗树,分层依次进行编码。而规则也是非常的简单,如果这个树的节点有 N 个子节点,那么就用 N 个 1 来编码,然后最后加上 0。

假设我们有如下的 tree:

image

为了计算简单,LOUDS 会加入一个 pseudo root 节点,这里我们变成如下的 tree:

image

然后我们对这个 tree 进行编码,得到:

image

那么生成的 bits 序列为:

image

那么我们拿到了这一个序列到底有什么用呢?在 LOUDS 里面,我们可以非常方便的进行很多操作,假设我们的 node 就是按照上面的,0,1,2,这样的 number 来标记的,position 对应的就是 bits 里面的 position。我们通常会用两个计算公式来得到 node number 和 position 的对应关系:

  • node-num = rank1(i):在 position i 得到对应的 node number,譬如 rank1(2) = 2
  • i = select1(node-num),根据 node number,知道对应的 position,譬如 select1(2) = 2

有了上面的公式,我们就能对这个 tree 进行操作了:

  • first_child(i) = select0(rank1(i)) + 1 - 得到第 i 个位置所在节点的第一个子节点所在的 position
  • last_child(i) = select0(rank1(i) + 1) - 1 - 得到第 i 个位置所在节点的最后一个子节点所在的 position
  • parent(i) = select1(rank0(i)) - 得到第 i 个位置所在节点的父节点所在的 position
  • children(i) = last_child(i) - first_child(i) + 1 - 得到第 i 个位置所在节点的子节点的个数
  • child(i, num) = first_child(i) + num 得到第 i 个位置所在节点的第 num 个子节点所在的 position,num >= 0

上面这些公式感觉好绕,那么我们来一个简单的例子,以节点 4 为例。从上面的 tree 可以知道,4 的 parent node 是 1,它的第一个子节点是 7,最后一个是 8,总共有两个子节点。

首先我们需要计算节点 4 的位置,根据上面的公式 select1(4) 我们得到 position 是 4。那么第一个子节点位置就是 first_child(4) = select0(rank1(4)) + 1 = select0(4) + 1 = 9 + 1 = 10,那么第一个子节点就是 rank1(10) = 7

我们再来计算最后一个子节点,根据公式,最后一个就是 last_child(4) = select0(rank1(4) + 1) - 1 = select0(4 + 1) - 1 = 12 - 1 = 11,那么最后一个子节点就是 rank1(11) = 8

再来看看父节点,就是 parent(4) = select1(rank0(4)) = select1(1) = 0,那么父节点就是 rank1(0) = 1

Epilogue

使用 LODUS,我们可以用 bits 方便的编码一棵树,然后用 rank 和 select 操作,就能方便的对 tree 进行遍历,业内已经有很多 paper,能将 rank 和 select 做到 O(1) 的开销,所以速度还是很快的。

但在实际中,如果光用 LODUS,性能还是没法保证的,所以这也是为啥会有 SuRF 的原因,关于 SuRF,后面会在说明。

在数据库领域,Succinct 是一个比较有趣的研究方向,也有很多数据库采用了 succinct 来保存数据,毕竟如果能用更少的空间存放数据,memory 能装的更多,cache 更友好,性能就更好。但现在 succinct 还没有大规模的落地,可以看看后续的发展。如果你对构建新的存储引擎有兴趣,欢迎联系我 tl@pingcap.com。

原文链接

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏一个会写诗的程序员的博客

Spring Reactor 项目核心库Reactor Core

Non-Blocking Reactive Streams Foundation for the JVM both implementing a Reactiv...

2142
来自专栏张善友的专栏

LINQ via C# 系列文章

LINQ via C# Recently I am giving a series of talk on LINQ. the name “LINQ via C...

2635
来自专栏陈仁松博客

ASP.NET Core 'Microsoft.Win32.Registry' 错误修复

今天在发布Asp.net Core应用到Azure的时候出现错误InvalidOperationException: Cannot find compilati...

4838
来自专栏杨龙飞前端

scrollto 到指定位置

2494
来自专栏我和未来有约会

Silverlight第三方控件专题

这里我收集整理了目前网上silverlight第三方控件的专题,若果有所遗漏请告知我一下。 名称 简介 截图 telerik 商 RadC...

4005
来自专栏飞扬的花生

jsencrypt参数前端加密c#解密

      写程序时一般是通过form表单或者ajax方式将参数提交到服务器进行验证,如何防止提交的请求不被抓包后串改,虽然无法说绝对安全却给非法提交提高了难度...

3859
来自专栏张善友的专栏

Mix 10 上的asp.net mvc 2的相关Session

Beyond File | New Company: From Cheesy Sample to Social Platform Scott Hansel...

2547
来自专栏我和未来有约会

Kit 3D 更新

Kit3D is a 3D graphics engine written for Microsoft Silverlight. Kit3D was inita...

2526
来自专栏pangguoming

Spring Boot集成JasperReports生成PDF文档

由于工作需要,要实现后端根据模板动态填充数据生成PDF文档,通过技术选型,使用Ireport5.6来设计模板,结合JasperReports5.6工具库来调用渲...

1.2K7
来自专栏一个爱瞎折腾的程序猿

sqlserver使用存储过程跟踪SQL

USE [master] GO /****** Object: StoredProcedure [dbo].[sp_perfworkload_trace_s...

2050

扫码关注云+社区