数据库的时光之梦#

你做了个网站。用户在你的网站上唯一能做的事情就是记录自己的心情。你看,老王昨天心情是“期待”,今天变成了“空虚”。这个网站的后端是用 Cozo 数据库这么实现的:

:create status {uid: String => mood: String}

翻译成 Postgres 的 SQL 的话,是这样:

create table status (
    uid text primary key,
    mood text not null
)

网站的主页也特简单:就是所有人心情的一个大列表。你这么生成这个列表:

?[uid, mood] := *status{uid, mood}
select uid, mood from status

用户记录心情时,后端执行:

?[uid, mood] <- $input
:put status {uid => mood}
update status 
set mood = $1 
where uid = $2

简单,对吧。有一天,一群自称搞研究研究的人找你,想买你的数据做疫情期间的人群焦虑分析。机智如你,当然知道他们没安好心,所以你直接把他们轰走了。然后你就开始扇自己嘴巴子:“怎么就把网站最值钱的东西丢了呢?怎么就没记录历史呢?怎么想的呢?”

单是懊悔也没用,所以你找未来的你借了个时光机,回去给过去的你提个醒。“简单!”,过去的你不以为然:

:create status {uid: String, ts default now() => mood: String}
create table status (
    uid text not null,
    ts timestamptz not null default now(),
    mood text not null,
    primary key (uid, ts)
)

这么一来,用户也没法删除他们的账号了,他们只能不停地更新心情。“真好”,你说。

修改后主页大列表这么生成:

?[uid, mood] := *status{uid, mood, ts}, ts == now()
select uid, mood from status
where ts = now()

完了,网站崩了,主页永远都是空的!

问题在于,查询条件 ts == now() 永远都不可能为真,因为“当下”是虚幻的,所有的心情都只存在于“过去”。

折腾了半天之后,你终于写出了以下查询:

candidates[uid, max(ts)] := *status{uid, ts}
?[uid, mood] := candidates[uid, ts], *status{uid, ts, mood}
with candidates(uid, ts) as (
    select uid, max(ts) from status
    group by uid
)
select status.uid, status.mood from status
inner join candidates on status.uid = candidates.uid and status.ts = candidates.ts

先找出每个用户最后心情的时间戳,再根据时间戳把他们最后的心情取出来。绕了个圈子。

有了这些改动,“时光穿梭”的查询也就很自然了:

candidates[uid, max(ts)] := *status{uid, ts}, ts < $date_ts
?[uid, mood] := candidates[uid, ts], *status{uid, ts, mood}
with candidates(uid, ts) as (
    select uid, max(ts) from status
    where ts < $1
    group by uid
)
select status.uid, status.mood from status
inner join candidates on status.uid = candidates.uid and status.ts = candidates.ts

沉重的历史#

网站成了爆款,“研究人员”们也很满意。但是随着日子一天天过去,网站也越发慢了起来,逐渐让人无法忍受。

不应该啊?目前你的网站仅限于某校内网访问,而学校里连流浪猫都算上也不过一万个用户而已。你仔细看了看数据,发现大多数用户更新心情起来都废寝忘食,有些简直可以说是颇具奥林匹克精神:三个月不到的时间转换过万次以上心情的大有人在。而生成主页的查询

candidates[uid, max(ts)] := *status{uid, ts}
?[uid, mood] := candidates[uid, ts], *status{uid, ts, mood}
with candidates(uid, ts) as (
    select uid, max(ts) from status
    group by uid
)
select status.uid, status.mood from status
inner join candidates on status.uid = candidates.uid and status.ts = candidates.ts

必须扫描所有数据才能生成列表。一万个用户,按照平均每个用户一千次心情来算,那就每次访问主页都要扫描一千万条数据。而你正在做将网站推广到整个互联网的计划。这样下去,生成主页过不了多久就会变成每次扫描成百上千亿条数据。

索引梦#

你的投资人急了,逼你做“大厂”式的优化:不再实时计算主页,而是提前批量算好,隔一段时间更新一次。作为一个(前)黑客,你最烦的词就是“大厂”,抵触情绪强烈。你搞金融的哥们儿建议你试试时序数据库:“那么多股指的实时更新都能搞定,你这点儿数据毛毛雨啦!”但是你试了一下还是不行:股指是一起以固定间隔更新并存储的,人的心情可不是。要不,任何人更新情绪时,就强行给所有人的情绪再存一次?云服务商听了这个主意特别兴奋,立刻就给你发了他们时序数据库产品的折扣报价单。投资人觉得也不错,因为这样一来你公司立刻就真的有“大数据”了,但是担心融资速度可能赶不上账单的速度。你掐指算了算账单大概会有多少,遂放弃了这个念头。

投资人还是纠缠不休,凌晨三点了还要跟你视频会议。你心中燃起邪火,拔了网线,恍恍惚惚地睡去了。

梦中你悠悠荡荡,到了一处。但见朱栏玉砌,绿树清溪,真是人迹不逢,飞尘罕到。你在梦中欢喜,想道:“这个地方儿有趣!我若能在这里过一生,强如天天被投资人入肉呢。”正在胡思乱想,却猛地发现你原来是个木头人,躯体不受意识控制,嘎吱嘎吱驶入一处。但见此处布满大橱,架子上齐齐整整司存着簿册:原来数据库中的树在梦中幻象成形了!你意识到你的任务是生成几天前的心情表,只见你腐朽的躯体机械地将簿册一一拿下,展开,记录,再放回原处:

“林〇〇,壬寅年腊月初九午时三刻,太早。”

“林〇〇,壬寅年腊月初九戌时整,太早。”

“林〇〇,壬寅年腊月初九亥时一刻,仍太早。”

……

“林〇〇,壬寅年腊月初九亥时五刻,仍太早。”

“林〇〇,壬寅年腊月初十子时六刻。过了需要的时间了,那么上一条就是需要的心情记录。”(记录的是“爆竹”。)

“林〇〇,壬寅年腊月初十子时七刻。不用看这条了。”

“林〇〇,壬寅年腊月初十丑时一刻。不用看这条了。”

……

“林〇〇,壬寅年腊月十一午时。干嘛还在看这人的……”

……

“薛〇〇,壬寅年九月初六卯时……”

你发现这木头身子着实蠢。首先,应当倒着查:这样就不需要在过了需要的时间去返回去看前一本(特别是前一本还不一定是同一个人的,操作起来很乱)。然后,如果这真是存储树的幻象,就不能直接跳到想要的地方吗?非要一本一本看吗?

正想着,忽然狂风乱作,大橱尽倒,簿册遍地。顷刻风停,本子又像有了魂似的,自己飞回重新立好的大橱架内。你发现躯体不知道什么时候也变了,不再是木头,成了硅胶,也灵敏得多了:现在你想去架子哪个位置,立刻就能蹦着过去了,而架子上面每个人的簿册,也按照时间倒着放了。

虽然活儿需要重头干,但是这回快多了:

“林〇〇,壬寅年腊月十一午时。太晚。直接快进到壬寅年腊月初十子时。”

“林〇〇,壬寅年腊月初九亥时五刻。就是这条,记下来。然后快进到林〇〇盘古开天时候的记录。”

“薛〇〇,壬寅年腊月初九亥时一刻。这条也该记下来。想起来,薛〇〇之后就没记录过心情了?”

……

你从梦中惊坐起,汗下如雨。随后赶紧摸到电脑边,将梦中所见以代码形式记录了下来。

回到正事#

多年后,你那个小破站的铁蹄踏平了寰宇,人们也再无从知晓网站出现前的生活是如何的。所有这些,靠得仅仅是下面这个存储表:

:create status {uid: String, ts: Validity default 'ASSERT' => mood: String}

查询目前心情:

?[uid, mood] := *status{uid, mood @ 'NOW'}

以及查询过往心情的代码:

?[uid, mood] := *status{uid, mood @ '2019-12-31T23:59:59Z'}

当然,这些查询不能靠 Postgres 了,所以也没有 SQL 的翻译。

你的故事,或者说 Cozo 0.4 版本中添加的 历史穿梭查询 功能的故事,到此结束。在入门教程中也有一些新的内容,用来熟悉此功能的基本使用。

附册:正事是索引的性能#

正经的数据库需要注重性能,而 Cozo 是正经的数据库。下面我们来做一些性能测试:就用 之前 的 Mac Mini:操作系统是 MacOS 13.0.1,用的苹果 M1 处理器,有 4 个性能核与 4 个功效核,16GB 内存,以及挺快的 NVMe SSD 存储。为了测试不过于繁复,我们只测 RocksDB 存储引擎。

首先,生成一堆存储表,每个表中都有一万个用户的数据。第一种表叫“无历史”表:只存储当前的数据。第二种表叫做“扫历史”表:存储方式就是幻境中刮风前的方式,而这个表有多个版本,分别对应每个用户不同的历史心情数量的情况。第三种表叫做“跳历史”表,用的是幻境中刮风后的存储方式。

测试时我们查询的时间戳是随机生成的,以下结果是多次测试的平均值。

首先我们来看历史存储对性能的影响:对于点查询,以下是对各表查询时每秒能完成的查询次数(QPS):

种类

单用户心情数量

QPS

性能比

无历史

1

143956

100.00%

扫历史

1

106182

73.76%

扫历史

10

92335

64.14%

扫历史

100

42665

29.64%

扫历史

1000

7154

4.97%

跳历史

1

125913

87.47%

跳历史

10

124959

86.80%

跳历史

100

100947

70.12%

跳历史

1000

102193

70.99%

当单用户心情数达到一千时,扫历史的性能就比无历史差了 20 倍。而跳历史则一直能保持无历史 70% 的性能。

实际上,如果点查询足够简单(比如只需要查一条信息,也同时知道所有需要的键的时候),可以将查询改写成较为巧妙的形式,以使扫历史和跳历史在这种情况下性能类似。在上面测试中我们特地没有这么做,因为这种优化不是什么情况下都做得到的。

接下啦我们看看聚合计算的性能:在聚合计算中,我们必须遍历所有的用户。在这个测试中我们关注的是延迟:

种类

单用户心情数量

延迟(毫秒)

减速比

无历史

1

2.38

1.00

扫历史

1

8.90

3.74

扫历史

10

55.52

23.35

扫历史

100

541.01

227.52

扫历史

1000

5391.75

2267.53

跳历史

1

9.60

4.04

跳历史

10

9.99

4.20

跳历史

100

39.34

16.55

跳历史

1000

31.41

13.21

随着数据不断增多,扫历史的性能越来越糟糕:无历史表只需要 2 毫秒,而扫历史单用户仅仅存了 1000 条历史数据就需要整整 5 秒。跳历史就没这个问题,多得多的历史数据也能很好支持。注意上表中显示跳历史存 1000 条数据时性能比存了 100 条数据还好一些。这并不是测量的误差:我们多种方式测了很多次,结果都一样。这可能是因为当数据到达一定量后 RocksDB 存储使用的逻辑不一样,不过我们也没深究。

当然,无论怎么存历史,比起不存来,在所有情况下都要慢至少三倍。这是时光穿梭的最小开销。这也是为什么在 Cozo 中,不是什么样的存储表都自动支持历史穿梭查询。Cozo 的理念是“零成本、零脑力开销的抽象”:当你不需要一个功能的时候,第一你不必为不用的功能损失性能,第二你也不用费劲去理解与此功能相关的任何知识就也能使用其他所有功能。

有些人宣称数据从根本上来说是不可变的,因此最好的数据存储形式也应该是不可变的。我们不这么理解。“不可变性”与“历史穿梭”都仅仅是工具,在适合的时候才应该使用。进一步来说,我们都仅仅是簿册中早已写好的谶语的展开吗?希望不是,而现代物理理论,不管是从波函数的塌陷方面来理解,还是从混沌边缘的生命方面来理解,对此问题都已经给出了明确的否定的答案。因此,所谓“不可变性”本身才是虚幻的,或者说是一种柏拉图式的梦,我们依托这种梦来理解世界。这本身并没问题,因为人只有将自己创造出来的模型映射到现实,才能理解这个世界,即使模型本身是虚幻的。我们应该坚持的,是不要成为虚幻的奴隶,不要被其束缚。