本文是 Notion 工程师 Chet 通过一个警局内警察信息管理的案例,揭开数据库的由来与使用。文章中有说到一句话:大多数人并不具备数据库和信息架构的技术素养。这句话其实已经说明了为什么现在各种数据库表格类产品雷声大、雨点小,最终选择面向 B 端求生存。

缘由

终端用户数据库是最近最热门的产品 -- Notion、Airtable、Coda、Roam等。这些产品可以让人用一种更自然、更直观的方式对信息进行建模,这与我们日常生活中的体验方式是一样的。

我喜欢构建 Notion 这样的产品,但构建这类产品是很难的。原因有二:

  1. 大多数人并不具备数据库和信息架构的技术素养,以至于无法用这些工具来自动化和组织他们的生活。
  2. 我们今天的数据库并不适合用户生成的动态过滤器和分类。

第二个挑战更具技术性,我将把所有这些与程序员相关的细节隐藏在切换之后,这样您就不必阅读它们(如果您愿意)。

🤖 技术细节

我计划通过让你对什么是数据库有一个心理模型,并对数据库的工作原理有一个初步的了解来解决第一个原因。

我将把数据库作为一个抽象的概念来介绍,然后我们将通过一个真实世界的例子来探讨数据库如何利用排序和过滤器来快速查找信息。

到最后,我希望向你展示这些信息架构概念是如何无比强大,并且对于非技术人员来说完全可以接近。

最后,我想让你相信,基于这些概念的软件将远远优于我们今天用于终端用户数据库应用的任何东西。如果你对这些概念感兴趣,请联系我。我喜欢分享想法。😁

什么是数据库?

数据库是档案柜。

数据库不一定要那么复杂。如果你去掉所有花哨的语义,你最终会得到一些简单而熟悉的东西。

Notion 工程师带你从底层理解数据库-Linmi

字典、日历和文件柜特别有用,因为它们以排序的方式来表示信息,使得我们可以使用一种叫做二分查找的过程来快速有效地检索信息。数据库也不例外,它们也是分类信息的容器。

Notion 工程师带你从底层理解数据库-Linmi

什么是分类信息?

按字母、数字、复合、词法编码。

最简单的排序方式是按字母顺序排序(也就是按词法排序) ,这也是字典中单词的排序方式。但是,我们经常发现自己要按多个属性进行排序。例如,一个联系人列表通常是按姓,然后是名来排序的。这就是所谓的复合排序。

例如,请注意,当这样排序时,"Thomas Robins "应该排在 "Charlie Robinson "之前,复合排序与简单地将单词连接在一起然后排序有着本质的区别。

// Compound Sort: Last, First
Robins, Thomas
Robinson, Charlie

// Joining the words, then sorting: Last + First
RobinsonCharlie
RobinsThomas

我们到处都在做这种复式排序。尤其是日期,是按年、月、日复合排序的。

January 10, 2019
...
December 28, 2019
...
August 26, 2020
...

请注意,这种排序并不完全是按字母顺序排列的。一年中的月份绝对不是按字母排序的--每个月在一年中都有一个基本的顺序。即使是一个月中的几天也不是按字母排序的,而是按数字排序的。

数字排序与字母排序不同,因为字母排序是逐个字母进行比较的。例如,如果我们按字母顺序对数字进行排序,那么10会排在2之前,因为第一个数字 "1 "在 "2 "之前。

// Alphabetical Sort
1
10
11
2
3
...
9

// Numerical sort
1
2
3
...
9
10
11

用一种简单的方式来表示数字,可以按字母顺序排序,就是在数字的开头加上0。这对于有已知最大值的小数,如一年中的月份,效果很好。

// Zero-padded numbers representing months in a year. 零填充的数字代表一年中的月份。
01
02
03
...
09
10
11
12

而事实上,我们可以用ISO 8601日期格式来表示日期,可以按字母顺序排序。

2019-01-10
...
2019-12-28
...
2020-08-26
...

用这种方式来表示日期是很方便的,因为它不需要领域知识来理解如何排序。也有太多的东西可以被任意排序:一副牌,一个项目的状态,你收藏的石头 -- 它们只是不同类型的东西。

一般来说,词法编码是很重要的,因为它们允许数据库以正确的顺序存储任意信息,而不需要关于被排序的信息类型的额外知识。

🤖 技术细节

当你查看文件系统中的文件时,你可能经历过这样的挫折。自然排序通过同时表示字母和数字排序,优雅地解决了这个问题。

将数字表示为可词法排序是另一个有趣的挑战,特别是非常大和非常小的数字。Elen 是一种有趣的编码浮动精度数的方法。

通过用null-byte分隔每项(并在每项内转义null-byte) ,可以将图元组表示为可复合排序。

分数排序也是一个非常相关且有趣的话题。

管理警察局

你可以用思考系统文件柜的方式来思考数据库。为了进一步探讨这个类比,让我们想象一下,你负责管理一个警察部门,在那里你要跟踪你所在地区的每个警察的各种信息--姓名、警徽号码、地址和辖区,以及其他细节。

作为这些信息的管理员,你负责确保所有信息都是最新的,并且容易访问。

为了使事情简单化,你首先要把所有的官员信息放在一个文件柜里,按警徽号码分类。这样就可以根据警徽号码很容易地检索到任何官员的信息,例如当一个官员晋升或搬到新的地址时。

Notion 工程师带你从底层理解数据库-Linmi

读写权衡

我们如何将信息复制到其他柜子里。

有一天,警察局长要求你提供第60分局每个警官的地址。

所有这些信息都在一个档案柜里,按警徽号码分类,这是一个痛苦的要求,因为你必须扫描每一个文件,检查每个警官是否在第60分局。

也许这只是一个一次性的要求,所以你可以劳而无功,但警察局长说,每个月他都要给辖区内逮捕人数最多的每个警员邮寄一张奖金支票。如果你每个月都要这样做,也许值得让这项工作更快一点。

为了解决这个问题,你再建立一个文件柜,把所有的警员按辖区分类。为了简单起见,你把徽章号柜里的所有信息都复印到分局柜里。现在,当局长要求你获取一个辖区内每个官员的地址时,你可以使用这个新的文件柜来快速检索信息。

这个新的档案柜让你更容易获得信息,但每次你要更新信息时,你又产生了一个新的问题。如果一个新的官员加入一个辖区,或者一个办公室从一个辖区搬到另一个辖区,你现在必须确保信息的正确性,并在两个不同的地方更新。

Notion 工程师带你从底层理解数据库-Linmi

更糟糕的是,我们最终会浪费时间来更新不必要的信息。例如,也许我们不需要出生日期,也不需要我们制作的新分局档案柜里的官员照片,但我们还是会把它复制过来,这样信息就不会不同步。

Notion 工程师带你从底层理解数据库-Linmi

另一方面,也许我们决定在辖区柜中存储的唯一信息是徽章号。这样一来,更改和管理警员信息所需的工作就少多了--我们只需要在原来的警徽号柜中进行更新。这也意味着,辖区柜的体积要小得多,因为我们没有那么多的信息塞在里面。

但是有一个问题。现在,如果你需要得到一个辖区内每个官员的地址,你就必须先用你做的新档案柜来获取该辖区内官员的名单,然后你就必须用原来的徽章号档案柜来获取每个官员的地址。这样做还是比没有辖区柜快,但没有之前扫描每个警官档案的方法快。

Notion 工程师带你从底层理解数据库-Linmi

从根本上说,没有 "最好 "的方法--这都是你在读取和写入信息时想做多少工作之间的权衡。

在这两种方法之间有一个中间地带,我们把地址和徽章号码都记录在我们创建的新的分局档案柜中。这就达到了一个很好的平衡,我们不必更新我们不关心的信息在Precinct柜中。

Notion 工程师带你从底层理解数据库-Linmi

然而,这确实带来了一些后勤方面的开销--现在我们有了一份更新徽章号柜时必须遵循的程序清单。

Notion 工程师带你从底层理解数据库-Linmi

🤖 技术细节

这里有一个直接与SQL的类比。Badge # cabinet是以徽章号为主键的官员表。Precinct cabinet是官员表上的索引。

而过程列表只是数据库模式定义的官员表上的SQL索引列表,每当有官员更新时,内部需要更新。

这个过程列表还将包括官员表上的SQL触发器。虽然SQL不能让你在跨表连接的信息上创建索引,但你可以通过触发器有效地实现这一点。

查询规划

确定如何用现有的档案柜来回答一个问题。

现在我们假设,每当有人对某位警官提出投诉时,我们都要在该警官的档案中记下投诉的内容。通常情况下,当有人提出投诉时,他们没有该警员的警徽号码,但他们有该警员的名字。

为了更方便地按姓名查找警员,我们建立了另一个档案柜,将所有警员按姓名分类。现在我们的档案系统是这样的。

Notion 工程师带你从底层理解数据库-Linmi

现在,让我们想象一下,这个警察局从1万名警察发展到1千万名警察。你收到一个投诉,投诉人是121分局的史密斯警官,棕色头发,蓝眼睛。

你正在考虑用两种不同的方式来查找这位警官--你可以扫描121分局的每一位警官寻找史密斯警官,也可以扫描121分局的每一位姓史密斯的警官寻找这位警官。

你做了一个假设,同名同姓的人可能比同一分局的人少,所以你决定先按名字查找这位警官。

在数据库中,这个过程被称为查询规划:你有一个问题(你想检索的一些信息) 和一个现有的档案柜设置,你需要确定收集所有这些信息的最快方法。

🤖 技术细节

我们刚才凭直觉考虑的权衡,正是SQL数据库的查询规划器的工作。查询规划器使用了关于数据在不同列中的分布情况的启发式方法,以选择扫描哪个索引的结果量最小。

也就是说,启发式的方法并不完美,完全有可能姓Smith的警官比任何一个辖区的警官人数还要多。


所以你查看了你创建的姓名内阁,最后发现121分局里其实有上百个叫史密斯的警官。再一次,你决定值得想出一个更快的方法来解决这个问题。

你想要的是像你创建的 "分局柜 "那样的东西,并按警官姓名进行二级排序。但是,"辖区柜 "不包括官员姓名,所以你必须创建一个新的文件柜来包括他们。您决定将官员姓名复制到现有的 Precinct 柜中,然后按姓名排序以节省空间,这样可能更有效。

正如我们前面所讨论的,这是一个复合排序,因为我们要对多个属性进行排序:辖区,然后是姓名。

Notion 工程师带你从底层理解数据库-Linmi

程序内阁

内部机制自动化。

为了回应公众对警员投诉暴涨的不满,警察局已经聘请了当地的审计公司对每个辖区进行审计。现在每当增加或修改一名警员的信息时,我们都需要通知分配到该警员所在辖区的审计小组,告知他们这些变化。

我们开始把这些程序写在和以前一样的清单上,但我们开始意识到,这将是一个非常长的程序清单。
W65zvFom9hS2yrD

每当我们对 Badge# 柜进行更改时,我们现在都需要扫描这个庞大的程序列表,这需要花费太多时间。所以我们要做的很简单,我们把所有的审计师地址移到一个新的档案柜里,然后在我们的程序列表中增加一个步骤,告诉职员在哪里查找审计师的地址。

Notion 工程师带你从底层理解数据库-Linmi

这就容易管理多了,但你可以想象,随着组织复杂性的发展,程序清单会不断增加;人力资源部门每当地址发生变化或有人投诉时,都想知道;财务部每当某位官员晋升时,都需要知道,这样他们就可以适当调整工资单--程序清单还在继续。

Notion 工程师带你从底层理解数据库-Linmi

希望不难看出,这个程序列表本身可以变成一个按属性分类的文件柜。这样一来,当我们只是更新一个地址的时候,就不需要把每一个属性的过程都读一遍。因此,每当我们对Badge #柜进行更改时,我们就会在这个程序柜中查找每一个更改的属性,看看我们需要做什么。

Notion 工程师带你从底层理解数据库-Linmi

🤖 技术细节

这种抽象是SQL和大多数数据库系统的基本限制。在SQL中,每个触发器都会进入一个程序列表,甚至是条件触发器。这意味着每一个额外的触发器都会线性地减慢每次写入的速度。

你可以做一些事情,比如将审计师地址列表保存在一个单独的表中,而不是创建一堆触发器,但在SQL中不能做的是拥有一个动态的存储过程列表,并进行有效的查找。

我想这也有一个很实用的原因:如果没有静态的程序列表,那么如果不实际尝试去做,查找程序,看看要做多少工作,就很难预测写的性能。有了静态的程序列表,你至少可以看看列表的长度,了解有多少工作量。


到目前为止,我们只为Badge #机柜维护了一个程序列表,但没有理由我们不能为其他机柜建立同样类型的程序列表。而事实上,这样做真的很有用,因为它可以让我们将我们的过程列表划分为更有效的过程排序方式。

例如,假设有一个正在进行的调查,FBI想知道第50分局中姓Colombo的官员是否有任何变化。

我们可以为Badge #柜创建一个程序,每当一个名字或一个分局发生变化时,就会检查,然后检查是否是第50分局和姓Colombo的人。

Notion 工程师带你从底层理解数据库-Linmi

但是,每次更换辖区时,检查这个程序会浪费很多精力。例如,假设史密斯警官从60号辖区调到61号辖区--当你查找程序时,你会看到这个程序,需要检查50号辖区的科伦坡。

有一个更好的解决方案--我们可以为辖区内阁创建一个程序。回想一下,Precinct cabinet是一个复合型的排序,先按辖区,再按名称。因此,我们可以通过对程序使用复合排序来使我们的程序柜变得非常精细。

Notion 工程师带你从底层理解数据库-Linmi

现在,当我把史密斯警官从60号辖区移到61号辖区时(下图中的第一个柜子) ,我会看到一个程序告诉我更新辖区柜子,更新辖区柜子后,我会查找辖区柜子的程序,看看是否有61号辖区和名字史密斯的程序。注意,我们能够跳过检查50号选区和名字Colombo的程序。这真是太有效率了!

Notion 工程师带你从底层理解数据库-Linmi

🤖 技术细节

从SQL的角度来看,这类似于在索引上创建一个触发器(你不能这样做,但如果你自己用单独的表生成索引的话,你算是可以的) ,创建一个更新的层次结构,从而消除一些浪费的努力。此外,我们还创建了可以有效查询的条件过程。
有可能我们想要监听整个辖区的变化,而不是仅仅监听一个辖区内的特定人员,如果我们把这个工作方式泛化,我们可以使用这个同样的Precinct和Precinct程序柜来实现。
假设我们想要一个程序来运行51号选区的任何名字的更新。我们可以添加一个按元组[51]排序的程序,它在[51,A]之前。而当我们查找程序时,对于[51,Colombo],我们只需要确保我们查找的不仅仅是[51,Colombo],而是所有的前缀a好--在这种情况下,[]和[51]。请注意,[]的意思是 "这个文件柜的任何变化"。


程序列表,在更新柜子的时候,能够有效地查询到需要做哪些程序,这对于信息系统的自动化来说,是一个非常强大的抽象。甚至于,这种抽象超越了现有数据库系统的能力。

审计日志

收据、表格、更改信息的请求。

有一段时间,当有这么多的人和这么多的信息改变,它变得重要的是要跟踪所有的细节,围绕着谁改变什么,什么时候。

例如,也许你打开琼斯警官的档案,上面写着他是一名侦探。而也许你以为他只是一个副手,所以你可能会倾向于问一些问题,比如 "他什么时候晋升的?"、"谁晋升的?"、"今年有多少人晋升?"。

这些问题在我们目前的设置下是不可能回答的,你可以想象,如果你管理的是一家银行,你会经常问这类关于账户之间资金流动的问题。

在银行里,每一笔账户之间的转账都会被记录下来,并附上某种收据,永远保存下来。而在我们的警察局,改变任何信息都可能用某种表格来记录。例如,当警察局长想把琼斯警官提升为警探时,他就会填写一份 "提升表",然后把它交给行政办公室的档案员。

档案员可能会把这张表格放在一个档案柜里,用来存放晋升表格,按级别和日期分类。然后我们查到一套这次晋升的程序,其中一个程序就是简单地更新警徽号柜里的警员等级。

Notion 工程师带你从底层理解数据库-Linmi

这个过程肯定比简单地更新徽章编号柜中的官员等级需要更多的工作,但它允许我们审计变化,并回答一系列更广泛的问题,即事情如何随着时间的推移而变化。例如,我们可以从 "晋升表格 "柜中查看一段时间内所有按级别晋升的情况。而如果我们想确定一个官员何时晋升,我们可以创建一个单独的柜子,将这些晋升表格按徽章编号,然后按日期进行分类。

在保存历史变化列表以备审计时,建立机制以确保信息不被篡改往往很重要。

例如,假设一个不良行为者想秘密添加一条记录,显示Jones警官在12月11日被降级,而在12月12日被提升(也许是为了在选举前制造一个欺诈性的丑闻,他们可以在新闻中写出来诋毁警察局长) 。

签名是这里的第一道防线。如果签名很难复制,那么就很难制造出一份欺诈性的降级表(注:我们在降级时也使用同样的晋升表) 。另外,我们可以做的是在晋升表格中备注之前的级别。也就是说,如果不良行为人想要创建这个欺诈性的降级表格,他们还需要欺诈性地更新12月12日的晋升表格,以参考之前的降级等级。

Notion 工程师带你从底层理解数据库-Linmi

在物理世界中,防范这种欺诈是相当困难的,不可避免地需要对系统的某种信任。但在现代世界,通过加密和单向哈希,我们可以为记录创建无法篡改的签名。这正是区块链防止比特币欺诈性交易的工作方式。

超越文件柜

权限、异步通信、一致性、冲突。

在这一点上,我们已经几乎涵盖了关于文件柜的一切有趣的东西,以及我们如何利用它们来管理大量的信息与操作程序。但是,对于任何一个现实的行政部门来说,还需要几个重要的系统。

第一个是管理权限。谁有权限提拔一个官员?谁有权限读取某个官员的投诉?谁又有权限更改某位官员的地址?

有很多方法来管理这个问题,大多数组织使用某种权限等级制度来保持简单。我将把回答这些问题作为一项练习留给读者,但如果你有技术上的倾向,我会推荐阅读关于Google如何用他们的桑给巴尔数据库解决这个问题。

系统中另一个需要仔细管理的部分是如何将信息邮寄给不同部门。在邮件中发送一些东西需要时间,这在一个复杂的组织中可能会引起各种问题。

例如,也许一个官员在12月12日获得晋升,而当财务部门在12月13日发送工资支票时,他们仍然没有收到邮件中的晋升信息,因此他们根据他们之前的级别发送了一份工资支票。

当涉及到协调时,事情就更有挑战性了。例如,也许人力资源部门认定某位官员有太多的投诉,必须降级。人力资源部门将降级的邮件发给行政部门以及财务部门。同时,主管认为该官员应该得到晋升,于是将晋升邮件寄给行政部门和财务部门。

现在会发生什么呢?不管结果如何,最重要的是行政部门、人力资源部门和财务部门最终的结果是一致的(也就是所谓的最终一致性) 。例如,如果财务部门决定处理晋升,而行政部门决定处理降级,那么他们的记录就会有所不同,该官员将获得比行政部门预期更大的薪水。

这些都是很难解决的问题,我会让读者去思考如何管理这类协调问题。但如果你有技术上的倾向,我会推荐你阅读Automerge如何处理这些问题的点对点软件。

结论

数据库可能看起来相当复杂,但每个数据库的基本工作原理就像一个文件柜和存储程序的系统。当我们需要在许多地方保持信息的更新,并且我们希望对数据库的所有变化有一个审计跟踪时,事情就开始变得更加复杂。但这种复杂性对于解决我们所解决的问题是必不可少的。

当谈到未来的计算机知识时,我知道并不是每个人都会成为忍者程序员,但了解如何构建文件柜系统的细节,将使普通人能够从计算机中获得最大的好处。

技术细节

从技术角度来看,从这个类比中我们应该考虑一些重要的事情。

其一,据我所知,没有任何数据库系统可以高效地查询和评估用户生成的程序。这种灵活性对于构建一个可扩展的终端用户数据库应用是必不可少的。

另一个需要考虑的是信息如何被分片。在这个类比中,"在邮件中发送东西 "实际上是说,碎片之间有一个边界。也就是说,人力资源部门和财务部门在不同的物理位置。

当我们在为用户构建应用时,这些文件柜都住在哪里?一种方式是如果每个人家里都有自己的文件柜(有些人有) 。另一种方式是你使用的每一个服务都会保存你的信息记录,你想看的时候就得向他们要。这就是目前世界上大多数事情的运作方式:你的健康记录住在医生的办公室,你房子的蓝图住在建筑部门,你的电子邮件住在谷歌数据中心的虚拟文件柜里。

这种方式对很多人来说其实是相当方便的--他们根本不需要跟踪自己的记录! 另一方面,这意味着人们不太有能力去建立自己的文件柜系统来管理和自动化生活。这也意味着他们的信息不那么私密。

如果你受到这些想法的启发,想建立一个嵌入式数据库,或者只是想抛出一些相关的想法,请不要犹豫,联系我们

感谢您的阅读🙏