Motivation | 动机
终端用户数据库是最近最热门的产品 —— Notion、Airtable、Coda、Roam等。这些产品使得人们可以用一种感觉更自然、更直观的方式来对信息进行建模,以适应我们日常生活中的体验。
我喜欢打造像Notion这样的产品,但打造这类产品很难。原因有二。
- 大多数人不具备数据库和信息架构的技术素养,无法真正用这些工具来自动化和组织自己的生活。
- 我们今天的数据库并不适合用户生成的动态过滤器和排序。
第二个挑战比较有技术含量,我会把这些与程序员有关的细节都隐藏在下面的 block后面,如果你没兴趣,就不用看了。
Underneath any end-user database is another database and so much complexity arises from the challenge of building a database inside a database. Solutions to this problem vary widely and make some sort of trade-off between scalability (performance) and complexity.
Some applications load the entire end-user database in-memory. This creates long initial load times, but really performant interactions once the application loads. There are obvious scalability issues with this approach, but it is fairly simple to implement.
Other applications resort to O(n) scans on the server to fetch data and filter/sort records in memory with a few caching and indexing optimizations when convenient. The problem here is that users can create their own columns and filters dynamically. If your cloud application is backed by a SQL database, for example, it’s worrisome to allow users to edit the database schema and create an unbounded number of tables and indexes. Thus, you must resort to filtering records in-memory.
If you’re dedicated to O(log n) queries, you’ll need to build indexes yourself (unless there’s some amazing database I am unaware of). On every write, you can compute what indexes need to be updated and you write to a NoSQL database to incrementally update a cached query result. This can lead to a good solution, but it comes at the cost of consistency. Now that you’re building your own indexes outside of the database, writes are no longer transactional and you lose the guarantee of being able to read your own write.
Another solution is to have a separate database for every user and allow users to edit the schema of their own isolated database. This allows writes to be transactional, but creates other kinds of collision problems (i.e. dealing with merge conflict) when you want users to be able to collaborate. With separate databases for each user, you’re also doing a lot more computing labor, especially if the same records are shared amongst many people.
Long story short, existing databases are not great for building end-user databases.
我计划通过简单的讲解,让你对什么是数据库有一个基础模型,并对数据库的工作原理有一个初步的了解来解决第一个原因。
我将把数据库作为一个抽象的概念来介绍,然后我们将通过一个真实世界的例子来探讨数据库如何利用排序和过滤器来快速查找信息。
到最后,我希望向你展示这些信息架构概念是如何无比强大,并且对于非技术人员来说完全可以接近。
最后,我想让你相信,基于这些概念的软件将远远优于我们今天用于终端用户数据库应用的任何东西。如果你对这些概念感兴趣,请联系! 我喜欢分享想法。😁
What is a database? | 什么是数据库
数据库是文件柜
数据库不一定要那么复杂。如果你去掉所有花哨的语义,你最终会得到一些简单而熟悉的东西。
字典、日历和文件柜特别有用,因为它们以排序的方式来表示信息,使得我们可以使用一种叫做二进制搜索(二分搜索)的过程来快速有效地检索信息。数据库也不例外,它们也是分类存放信息的容器。
What is sorted information? | 什么是排序信息?
字母、数字、复合、词法编码。
最简单的排序方式是按字母顺序排序(也就是按词法排序),这就是字典中单词的排序方式。但是,我们经常发现自己要按多个属性进行排序。例如,一个联系人列表通常是按姓,然后是名来排序的。这就是所谓的复合排序。
例如,注意到这样排序时,"托马斯-罗宾斯 "应该排在 "查理-罗宾逊 "之前,复合排序与简单地将单词连接在一起再排序有着本质的区别。
// 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
...
用这种方式表示日期是很方便的,因为它不需要领域知识来理解如何排序。有无限多的东西可以任意排序:一副扑克牌,一个项目的状态,你的各种收藏 —— 它们都只是不同类型的东西。
一般来说,词法编码很重要,因为它们允许数据库以正确的顺序存储任意信息,而不需要额外的关于被排序信息类型的知识。
You’ve probably experienced frustration with this when looking at files in your filesystem. Natural sort solves this problem elegantly by representing both alphabetical and numerical sort at the same time.
Representing numbers as lexicographically sortable is another interesting challenge, particularly very large and very small numbers. Elen is an interesting approach for encoding floating precision numbers.
Tuples can be represented as compound sortable by separating each item with null-byte (and escaping null-bytes inside each item).
Fractional sorting is a very related and interesting topic as well.
Administering a Police Department | 管理一个警察部门(案例)
你可以用思考系统文件柜的方式来思考数据库。为了进一步探讨这个类比,让我们想象一下,你负责管理一个警察部门,你要跟踪你所在地区的每一个警察的各种信息 —— 姓名、警徽号、地址和辖区等细节。
作为这些信息的管理员,你有责任确保所有信息都是最新的,并且易于访问。
为了使事情简单化,你首先要把所有警察的信息放在一个文件柜里,按警徽号码分类。这样就可以很容易地根据警徽号码检索到任何官员的信息,例如,当一个警察晋升或搬到新的地址时。
读/写平衡
我们如何将信息复制到其他柜子里。
有一天,局长要求你提供第60分局中,每个警官的地址。
所有这些信息都在一个档案柜里,按警徽号码分类,这是个很痛苦的要求,因为你必须扫描每一个档案,检查每个警官是否在第60分局。
也许这只是一个一次性的要求,所以你可以劳而无功,但警察局长说,每个月他都要给辖区内逮捕人数最多的每个警员邮寄一张奖金支票。如果你每个月都要这样做,也许值得让这项工作快一点。
为了解决这个问题,你建立了另一个档案柜,在那里你按辖区对所有人员进行分类。为了简单起见,你把 "警徽#"柜里的所有信息都复印到 "辖区"柜里。现在,当局长要求你获取一个辖区内每一位警员的地址时,你可以使用这个新的文件柜来快速检索信息。
这个新的档案柜让你更容易获得信息,但是每次你要更新信息的时候都会产生一个新的问题。如果一个新的官员加入一个辖区,或者从一个辖区搬到另一个辖区,你现在必须确保信息的正确性,并在两个不同的地方更新。
更糟糕的是,我们最终会浪费时间来更新不必要的信息。例如,也许我们不需要出生日期,也不需要我们制作的新分局档案柜里的官员照片,但我们还是会把它复制过来,这样信息就不会不同步。
另一方面,也许我们决定在辖区柜中存储的唯一信息就是警徽号。这样一来,更改和管理官员的信息所需的工作就少了很多 —— 我们只需要在原来的警徽号柜中进行更新。这也意味着,辖区柜的体积要小得多,因为我们没有那么多信息挤在里面。
但是有一个问题。现在如果你需要得到一个辖区内每个官员的地址,你就得先用你做的新档案柜来得到辖区内的官员名单,然后你就得用原来的警徽#档案柜来得到每个官员的地址。这样做还是比没有辖区柜要快,但没有之前扫描每个警察档案的方法快。
从根本上说,没有 "最好 "的方法 —— 这都是你在读取与写入信息时要做多少工作之间的权衡。
在这两种方法之间有一个中间地带,我们将地址和徽章号码都记录在我们创建的新辖区文件柜中。这就达到了一个很好的平衡,我们不必在辖区柜中更新我们不关心的信息。
然而,这确实带来了一些后勤方面的开销 —— 现在我们有了一份更新徽章号柜时必须遵循的程序清单。
There is a direct analogy here with SQL. The Badge # cabinet is the officers table with the badge number as a primary key. The Precinct cabinet is an index on the officers table.
And the procedures list is just the list of SQL indexes on the officers table defined by the database schema that internally needs to be updated whenever an officer is updated.
This procedures list will also include SQL triggers on the officers table. While SQL does not let you create indexes on information joined across tables, you can effectively achieve this with triggers.
Query Planning | 查询规划
确定如何用现有的文件柜回答问题。
现在我们假设,每当有人对某位警官提出投诉时,我们都想在该警官的档案中记录下这一投诉。通常情况下,当有人提出投诉时,他们没有该官员的警徽号码,但他们有该官员的名字。
为了更方便地按姓名查找警员,我们建立了另一个档案柜,将所有警员按姓名分类。现在我们的档案系统是这样的。
现在,让我们想象一下,这个警察局从1万名警察发展到1千万名警察。你收到一个投诉,投诉人是121分局的史密斯警官,棕色头发,蓝眼睛。
你正在考虑用两种不同的方式来查找这位警官 —— 你可以扫描121分局的每一位警官寻找史密斯警官,也可以扫描121分局的每一位姓史密斯的警官寻找这位警官。
你做了一个假设,同名同姓的人可能比同一分局的人少,所以你决定先按名字查找警官。
在数据库中,这个过程被称为查询规划:你有一个问题(一些你想检索的信息)和一个现有的档案柜设置,你需要确定收集所有这些信息的最快方法。
The trade-off we just considered by intuition is exactly what a SQL database’s query planner does. The query planner uses heuristics about how distributed the data is in different columns in order to choose which index to scan that will have the smallest amount of results.
That said, heuristics aren’t perfect and it’s totally possible that there are more officers with last name Smith than the number of officers in any given precinct.
所以你查看了你创建姓名的数据库,结果发现121分局里居然有上百名叫史密斯的警官。再次,你决定值得想出一个更快的方法来做这件事。
你想要的是类似于你创建的辖区柜的东西,并按警官姓名进行二级排序。但辖区柜不包括官员姓名,所以你必须在其中创建一个新的文件柜来包括他们。您决定将官员姓名复制到现有的辖区柜中,然后按姓名排序以节省空间,这样可能更有效率。
正如我们前面所讨论的那样,这是一个复合排序,因为我们要对多个属性进行排序:辖区,然后是姓名。
Procedure Cabinet | 文件柜的流程
使内部机制自动化;
为了回应公众对警员投诉飙升的强烈抗议,警察局已经聘请了当地的审计公司对每个辖区进行审计。现在,每当增加或修改一名警员的信息时,我们都需要通知分配到该警员所在辖区的审计小组,告知他们这些变化。
我们开始把这些程序写在和以前一样的清单上,但我们开始意识到,这将是一个非常长的程序清单。
每当我们对警徽号码柜进行更改时,我们现在都需要扫描这个庞大的程序列表,这需要花费太多时间。所以我们要做的很简单,我们把所有的审计师地址移到一个新的档案柜里,然后在我们的程序列表中增加一个步骤,告诉职员在哪里查找审计师的地址。
这就容易管理多了,但你可以想象,随着组织复杂性的发展,程序清单会不断增加;人力资源部门每当地址发生变化或有人投诉时,都想知道;财务部每当某位官员晋升时,都需要知道,这样他们就可以适当调整工资单 —— 程序清单还在继续。
不难看出,这个程序列表本身可以变成一个按属性分类的文件柜。这样一来,当我们只是更新一个地址的时候,就不需要把每一个属性的过程都读一遍。因此,每当我们对警徽号码柜进行更改时,我们就会在这个程序柜中查找每一个更改的属性,看看我们需要做什么。
This abstraction is a fundamental limitation of SQL and most database systems. In SQL, every trigger goes into a procedural list, even conditional triggers. This means that every additional trigger is going to linearly slow down every write.
You can do things like keep the list of auditor addresses in a separate table rather than create a bunch of triggers, but what you cannot do in SQL is have a dynamic list of stored procedures with efficient lookups.
I think there’s a very pragmatic reason for this as well: without a static list of procedures then it’s difficult to predict the performance of a write without actually trying to do it, looking up the procedures, and seeing how much work it’s going to be. With a static list of procedures, you can at least look at the length of the list to understand how much work is involved.
到目前为止,我们只为警徽号码柜维护了一个程序列表,但其他机构的文件柜也需要同样的程序列表。而事实上,这样做真的很有用,因为它可以让我们将程序列表划分为更有效的程序排序方式。
例如,假设有一个正在进行的调查,FBI想知道第50分局中姓科伦坡的官员是否有任何变化。
我们可以为警徽号码柜创建一个程序,每当一个名字或一个辖区发生变化时,就会检查,然后检查是否是第50辖区和姓科伦坡。
但是,每次更换辖区时,检查这个程序会浪费很多精力。例如,假设史密斯警官从60号分局调到61号分局 —— 当你查找程序时,你会看到这个程序,需要检查50号分局的科伦坡。
有一个更好的解决方案 —— 我们可以为辖区柜创建一个程序。回想一下,辖区柜是一个复合排序,先按辖区,再按姓名。因此,我们可以通过对程序使用复合排序来使我们的程序柜变得非常精细。
现在,当我把史密斯警官从60号辖区移到61号辖区时(下图中的第一个柜子),我会看到一个程序告诉我更新辖区柜子,更新辖区柜子后,我会查找辖区柜子的程序,看看是否有61号辖区和名字史密斯的程序。注意,我们能够跳过检查50号选区和名字Colombo的程序。这真是太有效率了!
From a SQL perspective, this is similar to creating a trigger on an index (you can’t do this, but you kind of can if you generate indexes yourself with separate tables), creating a hierarchy of updates and thus eliminating some wasted effort. Furthermore, we’re creating conditional procedures that can be efficiently queried.
It’s possible that we want to listen to changes for an entire precinct, not just a specific person in a precinct, and we can use this same Precinct and Precinct Procedures cabinets to do this if we generalize how this works.
Suppose we want a procedure to run for updates to precinct 51 for any name. We can add a procedure sorted by the tuple [51] which comes before [51, A]. And when we lookup procedures, for [51, Colombo], we just need to make sure that we lookup not just [51, Colombo] but for all prefixes a well — in this case, [] and [51]. Note that [] means “any change to this filing cabinet”.
程序列表,在更新柜子的时候,能够有效地查询到需要做哪些程序,这对于信息系统的自动化来说,是一个非常强大的抽象。甚至于,这种抽象超越了现有数据库系统的能力。
Audit Log | 审计日志
收据、表格、信息变更申请。
当经过一段时间后,有这么多的人和这么多的信息变化,它变得重要的是要跟踪所有的细节,围绕着谁改变了什么,什么时候。
例如,也许你打开琼斯警官的档案,上面写着他是一名侦探。而也许你以为他只是一个副手,所以你可能会倾向于问一些问题,比如 "他什么时候晋升的?"、"谁晋升的?"、"今年有多少人晋升?"。
这些问题在我们目前的设置下是不可能回答的,你可以想象,如果你管理的是一家银行,你会经常问这类关于账户之间资金流动的问题。
在银行里,每一笔账户之间的转账都会被记录下来,并附上某种收据,永远保存下来。而在我们的警察局,改变任何信息都可能用某种表格来记录。例如,当警察局长想把琼斯警官提升为警探时,他就会填写一份 "提升表",然后把它交给行政办公室的档案员。
档案员可能会把这张表格放在一个档案柜里,用来存放晋升表格,按级别和日期分类。然后我们查到一套这次晋升的程序,其中有一条就是简单地更新警徽号码柜里的警员等级。
这个过程肯定比简单地更新警徽号码柜中的官员等级需要更多的工作,但它允许我们审计变化,并回答一系列更广泛的问题,即事情如何随着时间的推移而变化。例如,我们可以从 "晋升表格 "柜中查看一段时间内所有级别的晋升情况。如果我们想确定一个官员何时晋升,我们可以创建一个单独的柜子,将这些晋升表格按徽章号,然后按日期分类。
当为了审计目的而保存历史变化列表时,通常必须建立机制以确保信息不被篡改。
例如,假设一个不良行为人想秘密添加一个记录,显示琼斯警官在12月11日被降职,而在12月12日被提升(也许是为了制造一个欺诈性的丑闻,他们可以在新闻中写出来,在选举前诋毁警察局长)。
签名是这里的第一道防线。如果签名很难复制,那么就很难制造出一份欺诈性的降级表(注:我们在降级时也使用同样的晋升表)。另外,我们可以做的是在晋升表格中备注之前的级别。也就是说,如果不良行为人想要创建这个欺诈性的降级表格,他们还需要欺诈性地更新12月12日的晋升表格,以参考之前的降级等级。
在物理世界中,防范这种欺诈是相当困难的,不可避免地需要对系统的某种信任。但在现代世界,通过加密和单向哈希,我们可以为记录创建无法篡改的签名。这正是区块链防止比特币欺诈性交易的工作方式。
Beyond Filing Cabinets | 超越文件柜
权限、异步通信、一致性、冲突。
到此为止,我们已经几乎涵盖了关于文件柜的所有有趣的东西,以及我们如何利用它们来管理大量的信息与操作程序。但对于任何一个现实的行政管理部门来说,还需要几个重要的系统。
第一个是管理权限。谁有权限提拔一个警员?谁有权限读取某个警员的投诉?谁又有权限更改某位警员的地址?
有很多方法来管理这个问题,大多数组织使用某种权限等级制度来保持简单。我将把回答这些问题作为读者的练习,但如果你有技术上的倾向,我会推荐你阅读Google如何用他们的桑给巴尔数据库解决这个问题
系统中另一个需要仔细管理的部分,是如何将信息邮寄给不同部门。邮寄东西需要时间,这在一个复杂的组织中会引起各种问题。
例如,也许一个官员在12月12日获得晋升,而当财务部门在12月13日发送工资支票时,他们仍然没有收到邮件中的晋升信息,因此他们根据他们之前的级别发送了一份工资支票。
如果涉及到协调问题,事情就更有难度了。例如,也许人力资源部门认定某位官员有太多的投诉,必须降级。人力资源部门将降级的邮件发给行政部门以及财务部门。同时,主管认为该官员应该得到晋升,于是将晋升邮件寄给行政部门和财务部门。
现在会发生什么呢?不管结果如何,最重要的是行政部门、人力资源部门和财务部门最终的结果是一致的(也就是所谓的最终一致性)。例如,如果财务部门决定处理晋升,而行政部门决定处理降级,那么他们的记录就会有所不同,该官员将获得比行政部门预期更大的薪水。
这些都是很难解决的问题,我会让读者去思考如何管理这类协调问题。但如果你有技术上的能力,我建议你阅读一下【Automerge如何处理点对点软件的这些问题】
Conclusion | 小结
数据库看起来相当复杂,但每个数据库的基本工作原理就像一个文件柜和存储程序的系统。当我们需要在许多地方保持信息的更新,并且我们希望对数据库的所有变化进行审计跟踪时,事情就开始变得更加复杂。但这种复杂性对于解决我们所解决的问题是必要的。
当谈到未来的计算机知识时,我知道并不是每个人都会成为程序员,但了解如何构建文件柜系统的细节,将使普通人能够从计算机中获得最大的好处。
From a technical perspective, there are a few important things we should consider from this analogy.
For one, there are no database systems I am aware of that efficiently query and evaluate user-generated procedures. This kind of flexibility is essential to build a scalable end-user database application.
Another thing to consider is how information is sharded. In this analogy “sending something in the mail” is effectively saying that there is a boundary between shards. That is, the HR department and the Finance department are in different physical locations.
When we’re building applications for our users, where do all these filing cabinets live? One way to do it is if everyone has their own filing cabinets at home (and some people do). Another way to do it is every service you use keeps records of your information and you have to ask them for it whenever you want to see it. This is currently how most things work in the world: your health records live at your doctor’s office, the blueprints for your house live at the building department, and your emails live in a virtual filing cabinet in a Google data center.
This way of doing things is actually quite convenient for many people — they don’t need to keep track of their own records at all! On the other hand, it means people are less empowered to build their own filing cabinet systems to manage and automate their life. It also means that their information is less private.
If you are inspired by these ideas, want to build an embedded database, or just want to toss around some related ideas, please don’t hesitate to reach out. Thanks for reading 🙏
Published January 12, 2020 by Chet Corcos
Thanks to Haris Butt and Max Einhorn for reading drafts of this. https://ccorcos.github.io/filing-cabinets/
Name | 分享者 | 分类 | 所属邮件组 | 推荐到索引 | 最后更新 | 来源 |
---|---|---|---|---|---|---|
Plidezus | Aug 6, 2023 8:28 AM | |||||
Plidezus | Aug 6, 2023 8:27 AM | |||||
Plidezus | Aug 6, 2023 8:27 AM | |||||
Plidezus | Dec 5, 2021 6:17 PM | |||||
Plidezus | Aug 6, 2023 8:27 AM | |||||
Plidezus | Aug 6, 2023 8:58 AM | |||||
Plidezus | Aug 6, 2023 8:27 AM | |||||
Plidezus | Aug 6, 2023 8:26 AM | |||||
Plidezus | Aug 6, 2023 8:26 AM | |||||
Plidezus | Feb 14, 2022 2:49 AM | |||||
Plidezus | Aug 6, 2023 8:26 AM | |||||
Plidezus | Feb 18, 2022 11:32 AM | |||||
Plidezus | Aug 6, 2023 8:21 AM | |||||
Plidezus | Aug 27, 2023 12:32 AM | |||||
Plidezus | Aug 6, 2023 8:21 AM | |||||
Plidezus | Sep 14, 2023 2:14 PM |