「计算机百年史」系列 · 第 7 篇 / 共 10 篇
按《从铜线到智能——计算机两百年》原书卷次连载。本篇:数据与规模(1970—2015),共 10 章,约 9.1 万字符。
卷七 · 数据与规模(1970—2015)卷首语
当数据体量突破单机内存的一万倍,程序员再也无法靠指针追溯世界。本卷记录数据如何从笨拙的层次网状指针,跃迁为优雅的关系代数,又在互联网洪峰逼迫下重写一致性理论:科德用一阶谓词逻辑终结了 IMS 的指针地狱,System R 与 Ingres 把数学变成生意,B 树家族与优化器把磁盘的物理现实翻译成数学结构,格雷用 ACID 把"算对账"从人品变成数学,列存革命向介质低头,CAP 定理逼所有人认账,三架马车用堆料战胜精工,Dynamo 用一致性换可用性,Spanner 用原子钟买时间——每一步都是规模逼的,每一步都付了代价。
必须预先声明:本卷没有"正确"的一方,只有"相配"的一方。关系模型赢了声明式的优雅,却在分析负载前撞墙;NoSQL 赢了扩展的自由,却把一致性的账单留给应用层;Spanner 赢了全球强一致,买单的是原子钟与毫秒延迟。银行必须换 ACID,微博可以不换——银行讲绝对,微博讲大概。架构师的第一课不是选最好的,是选最配的;配错了,神仙难救。
本卷的主导物理约束有三条:外存持久化随机 I/O 的物理延迟(寻道与擦除是改不掉的税)、网络分区故障的不可避免性(分区不是会不会来,是什么时候来)、跨国合规的制度边界(数据出境的关口站着穿制服的人)。三条约束在本卷末尾汇成一句话:国境成了新的分区键,分区键写在宪法里,不写在配置里。
阅读指引。 本卷讲数据如何从单机走向全球:后端工程师、数据工程师与架构师应当全卷精读——从 Codd 的关系模型到 Spanner 的原子钟,每一章都是当下面试与架构评审的高频考点。非技术读者建议读 074(Codd 的关系模型)、075(SQL 的垄断)、079(CAP 定理)、082(Spanner 与原子钟)——这四章的叙事完整,技术门槛已被压到"知道数据库是什么"即可。081(Dynamo)是亚马逊购物车的故事,也可独立读。
第 074 章 1970:埃德加·科德与关系代数的破晓
1969 年的深夜,某银行的机房里,一个程序员在重写上周刚写完的查询。业务提了个小要求:报表上加一列,顺带按新口径汇总。要求很小,代价很大——数据躺在层层嵌套的记录里,找一笔账要从根节点一层层钻下去,钻的路径写死在代码里;加一列,路径全变,遍历的代码全重写。重写完编译,编译完测试,测试完上线,上线发现另一个报表又坏了——它共用了同一条路径。救火的 DBA 半夜被叫起来,回滚、补丁、重跑批处理;批处理跑完天亮了,业务的第一单卡在门口等数据。等数据的队伍越排越长,柜台的抱怨越积越多;抱怨传到管理层,管理层问为什么加一列要一夜,技术答不上来——答不上来不是因为笨,是因为路太绕,绕到没人说得清。说不清的系统最可怕:改不敢改,动不敢动,需求堆成山,山下压着一群不敢动手的人。人的恐惧传导成组织的保守:新业务不敢上,旧系统不敢碰;不敢的代价是机会,机会的流失没有账单。没有账单的损失最贵:看不见,就不心疼;不心疼,就一直拖;拖到竞争对手用新系统抢走客户,账单才一次结清。结清的那一天,埋掉的不只是旧系统,还有守着旧系统的整个部门。陪葬的逻辑是连带的:系统死了,懂系统的人没用了;人没用了,新人更不敢碰——越没人懂,越不敢动;越不敢动,烂得越快。烂与怕的循环,转一圈深一层;转到最后,连重写的勇气都没了,只剩维持。维持的成本逐年涨,涨到比天还高;高到离谱的那一天,就是下一场革命的产房。产房的门外排着队:供应商带着新产品,学者带着新论文,年轻人不怕死;三拨人凑齐,旧时代就该办葬礼。葬礼的主角每年都换,葬礼本身年年都有;有的年份葬的是机器,有的年份葬的是思想。这样的深夜在当年的机房里是日常:数据的形状一动,程序就得跟着动;动的是结构,疼的是人。本章从这个深夜开始:人类是怎么被迫亲手记住每一块数据的地址的;又是谁,用一页数学把所有人从记地址的苦役里解放出来的。
指针地狱
六十年代的主流答案有两套。第一套叫层次:数据组织成一棵倒置的树,有且仅有一个根,每个节点有且仅有一个父节点;找数据从根出发,沿着唯一的路径往下走。订单查明细是树的拿手好戏:订单是父,明细是子,一对多顺藤而下,又快又稳;快的前提是关系恰好长成树形。银行的账务天生是树的形状:分行下面是账户,账户下面是交易流水,一层套一层,天然分明;电信的计费也一样:账单下面是话单,话单下面是详单,层层下钻。IBM 的信息管理系统就是这套思想的产品,银行的账务、电信的计费跑在上面,一跑几十年。天然的树遇上天然的查询,层次模型跑得飞起;飞起的另一面是路径依赖:一旦业务问了树外的问题,飞起来的翅膀就成了枷锁。枷锁的形状是改写的账单:昨天还快的查询,今天加个条件就慢十倍;慢的原因是路绕远了,远的路要穿过整棵树。穿树的代价写在响应时间里,用户等得起的叫系统,等不起的叫事故。事故的根子不在机器,在模型:模型的假设与业务的现实错位了,错位的每一分,都由重写买单。买单的频率写在需求变更单上:业务一变,模型先问能不能装;装不下就两种下场,改模型,或者改业务;改模型的代价是重写,改业务的代价是机会。但两种代价都不便宜,便宜的只有当初选对模型;选对的红利,吃一辈子。红利的形状是安稳:业务怎么变,模型都装得下;装得下的底气,来自模型的抽象层次;层次越高,装的东西越多。装得多的另一面是学得难:抽象层次越高,上手越费劲;费劲的前三个月,换的是后三十年的安稳。这笔账,算得过的人都成了架构师。树的好处是查询路径唯一:根到叶子的路只有一条,顺着走,准没错;树的坏处是路只有一条:想跨分支关联两个节点,没有直达的路,只能爬回公共祖先再下去,或者忍受冗余——同一个信息在多个分支各存一份。多对多是树的死穴:学生选课,学生是一边,课程是另一边,树只能装下一边,另一边要么复制,要么绕远;绕远的路径写进代码,代码的复杂度随关系数膨胀。插入删除也被树形卡住:没招到学生的新系,因为缺了主键的一部分,信息录不进去;退光课的学生,记录一删,连人带系一起消失。
第二套叫网状:节点可以有多个父节点,记录之间用指针物理地连成网。网状的表达力更强,多对多的关系直接落地;落地的代价是导航:程序员必须知道数据存哪,沿着指针一条条走,路径写进代码,走错一步满盘皆错。标准的制定者试图给导航立法:数据任务组定接口规范,set 类型、成员关系、遍历语句,一一标准化;标准化的钥匙,开的是同一把乱锁——路还是那些路,只是路牌统一了。遗留的系统至今还在跑:银行早期的账务、电信的计费核心,不少仍是层次与网状的身子;身子老了,动不了大手术,只能外面包一层又一层。包的每一层都是税,税的名字叫适配;适配的尽头,是重写还是退休的二选一。选重写的要算总账:迁移的风险、停机的窗口、数据的校验,加起来未必比维持便宜;选退休的要熬:熬到业务下线,熬到没人用,熬本身就是成本。迁移是绞肉机:旧模型的每一条指针,都要翻译成新模型的关联;翻译的规则写一本,例外写三本;例外的存在,说明世界从不按模型长。长歪的世界,迁一次脱一层皮;皮脱多了,新系统也成了旧系统。脱皮的疼,疼在映射表上:旧字段对新字段,一条条对;对不上的,写规则转;转不过去的,人工扛。人工扛的部分最贵:贵在人天,贵在出错;错一个,查三天。查的每一遍,都是对旧世界的考古;考古的每一铲,都可能挖出新的例外。熬与写的权衡没有公式,只有勇气;勇气的来源,是新系统的诱惑够不够大。指针的维护是隐形的税:增一条记录,要把相关的指针链全接上;删一条记录,要把指过来的指针全摘掉;漏摘一条,悬链就成了地雷——踩上的时候才知道。1973 年的图灵奖颁给了网状模型的奠基人,获奖演讲的题目就叫《程序员即领航员》——领航是荣耀,也是判决:程序员的时间花在认路上,而不是想业务上。认路的本事越强,离业务越远;离业务越远,写的程序越难被业务理解。两套的共同点是把物理结构暴露给程序:存的地方变了,取的程序就得改;改的成本,就是数据独立性的缺失。用今天的话说:没有独立性,数据的每一次搬家都是全城大修。
导航式取数(伪代码)
open 员工文件 → 定位根记录
循环 取出下属指针 → 跟随指针读部门记录
若 部门名 == 目标: 收集员工行
指针断一条,全程重写;结构一变,导航作废
导航的代码写出来全是路:打开谁,先找谁,顺着什么指针,走到哪停下。路的每一步都依赖物理现实:记录怎么摆,指针往哪指,索引有没有。现实一变,路就断了;断了的路要人去修,修路的人读着几个月前自己写的寻址逻辑,骂着几个月前的自己。地狱的形状就是这样:不是火,是路;走不完的路,修不完的路。最惨的是接手的人:前任的路只有前任认识,后任读代码如考古,注释没有,文档失传;考古的每一铲,都可能挖断另一条正在用的路。路与路之间互相牵连,牵一发而动全身;全身的每一处,都是前人埋的指针。
一篇论文
1970 年 6 月,《美国计算机学会通讯》登出一篇标题拗口的论文:《大型共享数据库数据的关系模型》。作者是 IBM 圣何塞实验室的埃德加·科德(Edgar F. Codd),三年前刚从东海岸调到西海岸,研究方向与公司的主流技术格格不入。格格不入是有来历的:数学出身的人看数据库,看到的不是记录与指针,是集合与逻辑;同行看到的是机器怎么存,他看到的是数学怎么说。论文的动作只有一个:把数据看成数学里的关系——一张表是元组的集合,一行是一个元组,一列是一个属性;关系的严格定义是域的笛卡尔积的子集,表里的每一行,都是若干值域里各取一个拼成的;键的概念随之落地:能唯一标识一行的属性组叫超键,最小的那个叫候选键,被选中的叫主键,别家表的主键拿过来叫外键——名分一定,约束就有了抓手。两年后,作者补上了另一半:关系完备性——一种查询语言只要能表达代数的全部能力,就算合格;合格线一划,语言的设计有了判据,不再各说各话。完备的另一半是演算:代数讲怎么做,一步步算;演算讲是什么,描述要什么;两条路通向同一个终点,殊途同归的证明写在论文里。殊途的意义是自由:喜欢过程的用代数,喜欢描述的用演算;自由的另一面是统一——殊途,但必须同归;归不到一处的语言,出局。出局的名单很长:长得好看但表达力不够的,走;表达力够但没人实现的,也走。走与留的裁判是时间:十年后还活着的,才算数;算数的标准,就是完备的那条线。判据的另一面是门槛:达不到完备的语言,注定只能做配角;配角的命运,从判据写下的那一刻就定了。定标准的权力从来不小:谁定义合格,谁就定义了方向;方向一定,跟风的、投资的、教书的,全往一个方向涌。涌的方向对了是生态,错了是泡沫;对错的验证,要等十年。查询的基础是一套代数:选择挑行,投影挑列,并、差、交做集合运算,笛卡尔积做拼接,连接做关联。代数的妙处是封闭:输入的是关系,输出的还是关系;输出的可以接着当输入,无限组合下去,永远是合法的查询。封闭的含义是组合自由:小查询拼成大查询,大查询拆成小查询,拼与拆都不需要知道数据存在哪。
数学的另一面是独立。物理独立性:程序不用知道数据存在哪个磁盘块、用没用索引、压没压缩;存的地方随便搬,搬了程序照跑。搬家的自由是 DBA 的解放:加索引不用改程序,换存储不用停机,分区调整业务无感;以前要停机割接的活,现在在线就能干。逻辑独立性:加个列、拆张表,不用重写查询;结构的演化被隔离在程序之外。不隔离的代价前文已经算过:加一列重写一片;隔离之后,加列只是定义的事,用到才读,用不到当没看见。两层独立加起来,等于宣布导航作废:从此没有开文件、没有跟指针、没有记路径;要什么,直说。直说的底气是代数:关系运算的每一步都有数学定义,定义的组合保证结果正确;正确的保证写在数学里,不写在程序员的记忆里。论文发表时,IBM 内部并非全员叫好——自家的主流产品正是被革命的对象,革谁的命,谁就不鼓掌。冷遇的另一面是时间:新思想进大公司,先被无视,再被嘲笑,最后被收编;收编花了十年,十年的学费由先行者垫付。掌声迟到了十一年:1981 年,图灵奖颁给了这位格格不入的研究员;落地的第一家,是后来叫甲骨文的公司——那是下一章的故事。
关系代数流水线(封闭组合)
员工表 ──选择(入职>某年)──▶ 子集 ──投影(姓名,部门)──▶ 瘦表
│
部门表 ──────────────────────────────自然连接(部门)──▶ 结果表
每一步输入输出都是关系;组合任意长,结果恒为关系
封闭的威力在优化:既然每一步都是关系,机器就可以自由重排步骤——先过滤再连接,还是先连接再过滤,结果一样,代价天差地别;选哪条路,交给优化器,不劳程序员费心。自由的另一面是信任:把“怎么做”交给机器,人只说“要什么”;信任的建立需要时间,时间的起点就是这篇论文。
大宽表的四种死法
关系模型落地的第一课是拆表。把所有东西塞进一张大宽表的诱惑人人都有:一张选课表,装着学号、姓名、系名、系主任、课号、成绩,一眼看全,多省事。省事的另一面是偷懒:设计的时候图省事,运行的时候天天还;还的方式是补丁,补丁摞补丁,表越补越烂。烂到一定程度,只能推倒重拆;重拆的学费,比一开始就拆贵十倍。省事的代价分四期兑现:冗余,一个学生选十门课,姓名系名系主任存十遍,硬盘替懒惰买单;更新异常,系里换了主任,全系学生的记录逐条改,漏一条就不一致;插入异常,新开的系没招生,没有学号课号撑门面,系的信息录不进去;删除异常,学生退光了课,记录一删,人带系一起消失。四种死法的病根是依赖混乱:谁决定谁,没写清楚。
范式的显微镜照的就是依赖。第一范式:列不可再分,原子是底线;地址拆成省市区,电话拆成区号加号码,含糊的一列必须拆开。拆的依据是查询:按省统计人数,地址就不能是一整坨;查什么拆什么,不查不拆。第二范式:非主键字段必须完全依赖主键,不能只依赖一半——姓名跟学号走,跟课号没关系,硬塞进同一张表就是部分依赖;部分的另一半是浪费:课号变了,姓名跟着存一遍,存的都是重复。第三范式:字段之间不许传话,系主任由系名决定,系名由学号决定,主任与学号之间隔着一层,就该拆成两张表。传话的链条越长,更新的噩梦越深:改一个主任,要找到所有传过话的记录;漏一条,数据就分叉。分叉的数据没有真相,只有版本;版本一多,业务就没法做了。拆的规矩有两条:拆完拼回去不能丢信息,拆之前成立的依赖拆之后还得成立;规矩守住了,拆就是安全的。还有更严的一档:每个决定因素都必须是候选键,一点含糊不留。严的代价是拆得更碎:碎到每一张表都只剩骨头,查一次要连七八张;碎的查询靠视图拼回去,拼的视图又成了新的维护对象。严与用的权衡没有标准答案,答案写在查询的形状里:查得多的地方少拆,写得多的地方多拆。拆的终点是一组干净的表:学生归学生,课程归课程,选课归选课,系归系;每张表只讲一件事,一件事只讲一遍。讲一遍的含义是单一事实来源:改,只改一处;查,处处一致。一致的代价是联表,联表的代价写在响应时间里;愿意付的付,不愿意的走反范式。完整性的三条铁律守在门口:主键非空唯一,外键必须对得上,业务规则自定义;铁律的含义是数学的形状不许走样,走样的数据进不了门。门的三道各有分工:实体管身份,参照管关联,自定义管业务;分的越清,错的越少。门的另一面是约束的代价:每一条铁律都是写入时的检查,检查越多,写入越慢;慢与对的权衡,写在业务的容忍度里。容忍度低的业务宁可慢,不可错;容忍度高的业务宁可快,错了再补。补的方式是事后对账,对账的批量作业,成了另一门手艺。手艺的精髓是对得平:两边的账轧差为零;轧不平的差异,逐笔追到源头。追源头的活又苦又关键,干的人叫对账员,对账员的眼睛就是最后的完整性。门内有规矩管着,门外只能靠对账兜底。对账的最高境界是自动:规则写进程序,天天跑,差异报警;报了警有人跟,跟了有人改,改了再对账。自动的另一面是信任:信程序,就得先信规则;规则的正确,需要人来担保。担保的人叫业务,业务说对,才是真的对;机器说的对,只是候选答案。
反范式是落地的另一面:范式拆出的表越多,查询要连的表越多,联表是性能的税;税重的场景允许适度冗余,用空间换时间。反的不是数学,是教条:需求第一,性能第二,表结构第三;教条的信徒把范式当宗教,工程师把范式当工具。工具的用法写在场景里:读多写少,冗余划算;写多读少,规范划算;算账的人是 DBA,账本是压测报告。
反对者
导航派的辩护首先值得听。巴克曼的追随者指出:指针是最快的路,沿着指针走,一步都不多走;关系的集合操作听着优雅,底层还不是循环与比较,中间商赚了差价。差价的学名叫抽象开销:通用引擎为了应付所有查询,准备了全套家伙;专用的路只走一种查询,一套家伙就够。家伙越少越快,这是物理;物理的账在特定场景下压倒一切。辩护的另一半是控制:导航把寻址攥在手里,性能调优有抓手;声明式把寻址交出去,慢了都不知道慢在哪。抓手的含义是可解释:慢了能看执行路径,路径的每一步都对应代码的一行;对应的关系越直接,调优越有方向。辩护在特定场景下全对:路径固定的查询,导航就是比通用引擎快;已知的路比现算的路短,这是常识。常识的边界是变化:路不变,导航赢;路一变,导航输;现实世界的路,天天在变。IBM 内部的路线派算的是另一笔账:自家产品线全押在层次上,革命等于自废武功;武功的存废不是技术问题,是季度财报问题。财报的压力下,正确的新思想也要排队;排了十几年,队才排到。排队的另一面是护城河:存量客户、存量代码、存量人才,全是革命的成本;成本越高,队伍排得越长。实用派的账算得更细:跑得好好的老系统,凭什么为了优雅重写?重写的风险看得见,优雅的收益看不见;看得见的账,压倒看不见的账。压倒的逻辑没错:业务的命是第一位的,模型的纯洁排不上号。排不上号的纯洁,只能等下一次大修;大修的窗口,几年才开一次。窗口一开,新思想排队进场;进场的顺序,按痛的程度排,痛得最狠的先进。先进的吃肉,后进的喝汤;汤的味道,取决于锅里还剩什么。剩的越少,抢得越凶;抢的本质,是对旧痛的投票。投票的结果写在迁移史上:痛得最狠的行业,换得最坚决;银行的核心系统,电信的计费系统,都是第一批倒戈的。倒戈的顺序,就是疼痛的排名;排名的榜首,永远是被旧模型折磨得最惨的。折磨的刻度是加班:越折磨,加班越多;加班越多,换的意愿越强。意愿的另一面是预算:再想换,没钱也白搭;预算的松紧,看老板被折磨到什么程度。折磨传导链的终点,永远是签字的人;签了字,革命才算开张。
数学即界面
回到卷七的主导约束:外存持久化随机 I/O 的物理延迟、网络分区故障不可避免性,与跨国合规制度边界。本章的仗打在第一条上。指针导航的本质是一次次随机追逐,追一次等一次;集合操作的本质是批量——优化器把查询翻译成扫描、排序、哈希,一次读一批,随机变顺序。代数的封闭给了优化器自由调度的权力,重排、剪枝、选算法,每一步都在省随机 I/O。省的学问叫访问路径:全表扫描一行行看,索引先查目录再定位;目录维护本身要成本,写一次更新一回。扫描与索引的抉择,优化器按统计信息下注;数据分布变了注就错,错注的代价是慢查询,救法是更新统计。DBA 的日常功课就是给统计保鲜——十次慢查询,九次是计划错了,九成是统计过期。明知要更新,业务高峰期不敢动;怕更新拖慢业务,怕新计划更差,解法是灰度,先备库试再主库推,每一步留退路,退路的名字叫备份。备了没练过等于没备,演练多了半夜被叫醒也知道先干什么。独立性管的是变化的隔离,不管天花板的位置:不依赖物理位置了,开始依赖优化器的聪明;介质换代的红利自动兑现,程序不用改,瓶颈却搬到别处——CPU 跟不上了换向量化,单机跟不上了换分布,分布的账单留给下一卷去结。慢了是谁的锅?DBA 说查询烂,开发说索引差;但比起从前,这已是幸福的烦恼——从前的锅只有一个:重写。
本章的断言是:关系模型证明,数据的正确组织方式是数学而不是直觉——一阶谓词逻辑描述关联,代数操作保证封闭,独立性隔离变化;直觉擅长走捷径,数学擅长立长久。长久的另一面是门槛:数学的东西学起来费劲,用起来省心;费劲在前,省心在后,先苦后甜是数学一贯的脾气。这个断言可以被反驳:如果未来主流数据系统抛弃声明式关系模型,回到显式导航却取得更大规模的成功且维护成本更低,那么数学论就是错的,直觉另有更便宜的组织形式,指针只是暂时输了,长久属于下一代直觉。
第 075 章 1974—1979:System R、Ingres 与 SQL 的事实垄断
1972 年,美国的东西两岸,两拨人同时动手,把同一篇论文变成能跑的系统。论文是 1970 年的,系统是 1972 年动手的,语言是 1974 年成形的——从纸到码,隔着两年;从码到能用,又隔两年。时间的刻度说明一件事:理论到工程没有直达车,中间站站停靠;每一站都要有人下车干活,干完再上车。停靠的每一站都有名字:验证、原型、打磨、商用;站名不同,干的活一样——把对的东西,变成能用的东西。对的东西不一定能用,能用的不一定对;对与用的鸿沟,填了整整一个十年。东岸是 IBM 的圣何塞实验室:大公司的正规军,经费充足,目标明确——证明关系模型不是纸上谈兵,造一个真能用的关系数据库出来。西岸是伯克利的一间办公室:助理教授带着几个学生,五年考核期悬在头顶,成了拿终身教职,不成走人——赌注是职业生涯,赌的是同一个理论。两拨人互相知道对方的存在,论文的引用里有彼此的名字,学术会议的走廊里打过照面;知道归知道,动手各干各的,干出来的东西,一个叫 System R,一个叫 Ingres。互不知深浅的另一面是暗自较劲:东岸看不上西岸的学生代码,西岸看不上东岸的大公司流程;较劲的赌注是谁先跑起来,跑起来的定义权在用户手里。定义权的另一面是傲慢:都觉得对方走不通,都觉得自己才是正统;正统的认证机构还没出生,认证靠的是跑分与用户。用户用脚投票之前,两边都是自封的正统。两种实现,一种语言胜出;胜出的不是技术最好的那个。本章是这场双城记:好东西是怎么赢的,赢的又为什么不一定是最好的。
蓝巨人的赌局
IBM 的赌局从 1972 年开盘。赌注押在 System R,一个实验型关系数据库管理系统;赌局的庄家是公司本身——自家的主流产品正是关系模型要革命的对象,自己革自己的命,需要的不只是勇气,还有预算。预算的另一面是耐心:实验项目按年拨款,每年都要证明还值得投;证明的方式是里程碑,里程碑的背后是加班。配套的查询语言先叫 SQUARE,满纸数学符号,工程师看着亲切,用户看着头晕;符号的门槛挡住了推广,推广的压力催生了第二版。符号的另一种代价是排他:看得懂的人自动结成圈子,圈外的人连问题都问不出来;圈子的存在,语言就长不大。长不大的语言没有未来,不管它多优雅。第二版的思路反过来:不考数学,考英语;会说话就会查,门槛降到识字为止。识字的门槛意味着市场:会识字的人比会数学的人多几个数量级;多出来的,全是潜在用户。1974 年,唐纳德·钱伯林(Donald Chamberlin)与雷蒙德·博伊斯(Raymond Boyce)发表论文,语言的名字叫 SEQUEL,念作“续集”:续的是 SQUARE 的命,讲的是英语的故事。一个名字,两种读法;读法的背后是定位的转移:从数学家的工具,变成所有人的工具。用英语写查询,是刻意的设计——SELECT 要什么,FROM 从哪拿,WHERE 挑哪个;读起来像人话,写起来像填空。填空的每一格都有讲究:格子的顺序固定,格子的含义唯一;填错格,机器立刻报错。报错的及时是英语化的红利:错的不是逻辑,是语法;语法的错,当场就能改。后来改名 SQL,是商标的避让,语言还是那个语言;名字的更替没换来任何不兼容,老查询照跑不误。
两位作者的合作是实验室友谊的样本:1972 年一起搬到圣何塞,一起买房,一起拼车上班;午休时玩“查询游戏”,一人编题,一人用新语法解,看谁先把刁钻的需求说清楚。游戏的副产品是语言的打磨:难表达的查询逼出新句式,新句式反过来降低表达的门槛。游戏的规则很简单:出的题必须刁钻,解的人必须用新语法;解不出来的,回去改语法。出题与解题的循环转起来,语言越转越顺;顺的另一面是默契,默契的两个人,一个眼神就知道对方卡在哪。博伊斯没能看到语言的胜利:二十多岁突发脑动脉瘤离世,女儿当时只有一岁;钱伯林此后每年夏天都与老友的女儿去露营,露营的话题一半是故人,一半是查询。出题的人走了,题目留下来了;语言的每一句里,都有没写完的那一半。没写完的那一半,由后来者续写;续写的人换了一茬又一茬,查询游戏的规则没变:出的题越来越难,解的人越来越多。
System R 要证明的只有一件事:关系数据库不是玩具。玩具论的底气是性能:解释执行逐条跑,导航的指针直来直去;一个数量级的差距,摆在基准测试里,谁看谁摇头。证明的方式是跑起来:优化器自动选执行计划,用哪个索引、哪种连接、先过滤后连接还是先连接后过滤,机器自己定;应用的代码只管说什么要,不管怎么做。证明的另一面是编译:查询先编译成执行计划,计划再跑;编一次,多次用,分摊的成本越摊越薄。薄到一定程度,差距就从数量级变成几成;几成的差距,生产力的十倍轻松覆盖。覆盖的账本写给管理层看:关系模型从论文变成了产品,产品的下一步是商品。商品的门槛是可支持性:能装,能跑,能调,有人接电话;电话的另一头,是商业公司的雏形。雏形的另一面是跑分:基准测试一跑,数字说话;数字不好看,管理层不批预算。批预算的每一轮,都要新的数字;数字的背后,是工程师的头发。雏形的另一面是文档:安装手册、管理员指南、故障排查,一样不能少;少的每一份,都是未来的投诉。投诉的积累倒逼成熟:每一次深夜被叫醒,都长一分记性;记性攒多了,产品就稳了。稳的代价是慢:实验的锐气被流程磨平,磨平之后才能卖;卖的东西,要的不是锐,是稳。
SELECT 系名, AVG(成绩) AS 均分
FROM 选课 JOIN 学生 ON 选课.学号 = 学生.学号
WHERE 入学年份 > 2020
GROUP BY 系名
HAVING AVG(成绩) > 80
ORDER BY 均分 DESC;
十行,干的是几十行导航代码的活:连表、过滤、分组、排序、二次过滤,一气呵成;怎么写不管,写什么才管。读这十行不需要知道执行顺序:先连后滤还是先滤后连,机器定;用哪个索引,走哪种连接,机器定。定的依据是统计信息:表多大,区分度多高,内存够不够;依据越准,定的越好。定的不好会慢,慢了可以看计划、调索引、改写法;调的学问,就是数据库性能优化的全部。声明式的另一面是把权力交给优化器:同样的查询,数据量不同、索引不同,最优的路就不同;路让机器选,人只负责把意图说对。说对的门槛比写对低得多:意图是业务语言,路径是机器语言;前者人人会说,后者只有少数人懂。门槛的降低,是 SQL 日后席卷一切的伏笔。伏笔的另一面是黑箱:路怎么选的,看不懂;看不懂的优化,调起来靠猜。猜的依据是经验,经验的积累靠踩坑;坑踩得多了,人就成了专家。专家的诞生需要土壤:慢查询的日志、执行计划的可视化、统计信息的透明;土壤越肥,专家越多。伏笔埋的是普及,收获的是生态;生态的厚重,反过来抬高替换的门槛。门槛的另一面是黑箱的学问:看执行计划,认全表扫描,调索引顺序;学问的入门靠踩坑,坑的学费叫停机。停机的教训最深刻:一次全表扫描拖垮生产,周报里多一行事故;事故的复盘会上,新人学会了第一课——意图要对,路径也要对。
伯克利的平行宇宙
西岸的赌局赌注更大。1971 年,导师尤金·王(Gene Wong)把刚入职的助理教授迈克尔·斯通布雷克(Michael Stonebraker)叫到跟前:别做博士论文那个方向了,没前途;数据库这块地不错,一起干吧。那是科德论文发表的第二年。1972 年,Ingres 在伯克利启动,名字是交互式图形检索系统的缩写,动因之一是要管地理信息——点线面的空间数据,标准类型装不下,于是先拿通用活命,再做专用扬名。他的赌注是终身教职:助理教授聘期五年,五年内拿不出东西就走人,Ingres 就是那张门票,1976 年兑现。倒计时逼出一套朴素的节奏:第一年搭架子,第二年出雏形,第三年能演示,第四年有人用,第五年数论文。做出能跑的雏形只花九成力气,把它打磨到别人也能用还得再花九成——文档写全,测试覆盖,移植容易,缺一件,"能用"就打折。Unix 正在大学里铺开,Ingres 是上面唯一免费的关系数据库,几年内上百所大学装上它;学生时代用过的东西,工作了还想用,呼声传到企业,采购单上就有了名字。免费的种子,结的是商业的果。熟之前先有尴尬:访客总问最大的生产应用是哪个,回答是没有——学术圈子很热闹,工业的单子一张没有。
尴尬在亚利桑那州立大学的项目里爆了雷:四万学生的学籍管理,校方能接受非官方的操作系统,能接受非官方的数据库,唯独接受不了没有 COBOL——全校业务都写在这种语言上,换语言等于重写一切。项目黄了,原因与技术无关:生态的锁链拴住了一切。最时髦的 Unix,栽在最传统的 COBOL 手里,新潮输给守旧,不是因为技术,是因为存量。新系统的出路只剩一条:开公司,搬到"真正的"操作系统上,提供商业支持。1980 年,公司成立,系统移植到 DEC 的小型机上;学术项目从此有了销售部,免费时代结束。商业的 ABC 是支持合同:宕机有人接电话,升级有人上门做,出事有人背锅——买的不是软件,是安心。DEC 的机器占领着机房,VMS 是彼时的企业标准,站上这条船,生意自然来;来的都是大客户,单子大,要求也高。但转身的代价是初心:免费的旗帜收起来,合同与报价单摆出来,Ingres 从运动变成了生意。生意有生意的节奏:季度要数字,年底要增长,压力传导到研发,周期被压缩,代价记在质量账上——白天写功能,晚上修缺陷,修的永远赶不上欠的。
Ingres 的查询语言叫 Quel。技术派的口碑一边倒:Quel 更接近科德的演算传统,设计更干净,组合更自然;SQL 是工程师赶工的产物,重性能轻设计,连基本的组合都不顺。干净的含义是正交:概念之间不重叠,规则没有例外;学一个规则,能推一串用法。推的快感是智识的:举一反三,触类旁通;快感的另一面是门槛,看懂门道需要功底。举例是最好的证明:嵌套的查询一层套一层,内层的结果喂给外层,层层相扣;扣得越紧,组合的威力越大。正交的设计让组合自然发生:拼什么都对,怎么拼都不错。赶工的反面是凑合:能跑就行,好不好看另说;凑合的债,子孙后代来还,还的利息叫兼容。1985 年,数据库学者 Date 专门写文论证 Quel 更优:一个精心设计的语言,对一个赶工出来的接口,纸面胜负分明。判词的依据是血统:Quel 离 Codd 的演算传统更近,近到几乎是换了层皮;SQL 离得远,远到亲爹都快认不出。血统论的另一面是迂腐:血统纯不代表好用,好用才是硬道理;硬道理的裁判是用户,不是族谱。纸面的法官是同行:同行点头,才算数;点头的人越多,判的越准。准的判词没能换成订单:法庭赢了,市场输了。输的账本要细看:输的不是技术,是时机、渠道与话语权;三样加起来,技术只占一份。话语权的本质是谁定义好坏:定义权在手,输的也能说成赢;定义权旁落,赢的也被说成输。
卖未来的商人
甲骨文的创始人拉里·埃里森(Larry Ellison)是 Ingres 最难缠的对手。以下关于他的打法,主要来自竞争对手 Stonebraker 在访谈中的说法,引用时须注明这是单方视角:他把“现在能用的”与“将来会有的”说得毫无区别——还没实现的功能先卖出去,让第一批客户帮忙调通;手册里花两页讲清参照完整性的定义,页脚一行小字注明“尚未实现”。定义的共识有了,实现的货没到;货没到,钱先收。收钱的逻辑是速度优先:市场不等人,先占坑再填坑;填坑的活外包给客户,客户既是买家又是测试员。测试员的工资是折扣:早买便宜,用着难受;难受的另一面是锁定:数据进去容易,出来难。难的本质是迁移成本:换系统要倒数据、改程序、训新人;成本一算,不如将就。将就的客户越多,坑填得越快;填坑的免费劳动力,是对手花钱也买不到的。以下关于商业手段的全部叙述,均引自 Stonebraker 的单方说法,甲骨文自有另一套叙事;本章取之作为理解竞争烈度的一个视角,而非定案。
胜负的天平不在技术室。1983 年底,IBM 推出商业关系数据库 Db2,旗舰产品加大型机基本盘,等于官方宣布关系模型是正统。基本盘的含义是存量:全世界的大机房跑着 IBM 的机器,换供应商等于换全家,成本写在 CFO 的噩梦里;不换就不用重来,重来的风险比守旧的代价更吓人。正统的查询语言是 SQL,Quel 再优美也是方言——方言的命运写在招聘广告里,招 SQL 的职位遍地,招 Quel 的论个。紧接着,美国国家标准学会在 IBM 与甲骨文的推动下把 SQL 立为标准;投票桌上,Ingres 的主帅甚至没有到场——他意识形态上反对设标准,战术上等于弃权。缺席的代价写在此后十年:标准会的每一次投票,都是对手在场、自己缺席,缺席的次数攒多了,标准就长成了别人的形状。1984 年的账本写着结局:甲骨文销售额翻倍到一千二百七十万美元,Ingres 翻三倍到九百万美元——增速更快,绝对值落后;落后的一方缺的不只是钱,还有 SQL:没有它,跨平台移植处处碰壁,读一致性也差一截。Ellison 的名言为这场战争收了尾:"也许 Quel 比 SQL 好,就像法语也许比英语好——没关系,英语和 SQL 必胜。"语言的胜负从来不由语言学家决定,由使用者用脚投票;赢的从来不是最美的,是最多的。
为什么是 SQL
标准的战争从来不在技术室里打。SQL 的胜利是四张桌子同时开席的结果:IBM 的基本盘最大,大型机上跑什么,标准就是什么;ANSI 的章盖下来,政府采购只认章不认理;甲骨文的销售满世界跑,把没实现的功能卖成已实现,市场份额先占住再说;伯克利的免费流行培养了整整一代会写 SQL 的学生,毕业进企业,点名就要 SQL。技术、标准、销售、人才四张桌子朝同一方向使劲,Quel 只占了第一张,还没坐热。网络效应的算法很简单:用的人越多,学的人越多;学的人越多,招的人越好招;循环转三圈,雪球就停不下来。1986 年 ANSI 标准落定,1987 年国际标准跟进;标准一定,战争结束。落定的另一面是冻结:标准写死之后,演进要走数年的修订流程,等不及的厂商各自加料,加的料叫扩展;扩展多了,标准就只剩封面。后来的挑战者都要先回答同一个问题:兼不兼容 SQL?兼容是入场券,不兼容是墓志铭。
垄断的另一面是停滞。一种语言管了四十年,优点是人人会写,缺点是人人忍着:组合的别扭、空值的暧昧、优化器的黑箱,一代代新人骂,一代代新人接着用。骂的清单越积越厚:空值到底算什么,三值逻辑绕晕几代人;组合的别扭逼出层层嵌套,嵌套的括号数都数不清;黑箱的优化器偶尔犯浑,犯浑的查询慢到天荒地老。骂与用的并存,恰恰说明垄断的本质:换的成本高于忍的成本。换的成本是生态:存量代码、存量人才、存量工具,全是沉没成本;沉没的越多,换的越难。难到最后,新语言干脆宣布兼容:语法照抄,语义照搬,只换引擎不换舌头。舌头保住了,江山就保住了。保住的另一面是创新被招安:再好的想法,也要先套上 SQL 的皮;皮一披,新意打三折,革命变改良。改良的队伍越排越长:对象关系映射、文档模型、图查询,个个宣称超越,个个兼容 SQL;兼容的声明写在首页,不兼容的埋在脚注。脚注越读越心凉:凉的不是技术,是生态的重量。重量压得新人不敢另起炉灶,炉灶一起,第一个问题就是兼不兼容。兼容的另一面是方言的繁荣:各家在标准上加私货,私货多的成了事实标准;事实的版本一多,标准就只剩封面。封面与里子的差距,就是下一轮战争的火药。火药的引信,攥在挑战者手里;挑战者的名单,每年都在变。
方言的代价与标准的红利
回到卷七的主导约束:外存持久化随机 I/O 延迟、网络分区故障不可避免性,与跨国合规制度边界。本章的仗打在标准这一层——标准是跨组织的协作界面。SQL 一旦成为标准,人才可以在公司间流动,工具可以跨厂商通用,代码可以在系统间迁移,每一笔流动都在摊薄协作的摩擦。稳定的共识从供需两头加固:新人只学一套语言,到哪都能上手;教材、认证、考试、培训班随之而起,链条上的每个人都希望标准别变——变了教材要重写,题库要更新,证书要重考。稳的另一面是路径依赖与锁定:学了一辈子 SQL 的人对新语言第一反应是排斥,排斥的不是技术,是沉没成本;标准定死的那一天,创新的天花板也封了顶,好处是安稳,坏处是四十年不变的老面孔。会 SQL 的永远有饭吃,发明新语言的九死一生,于是用人单位要现成人才,人才要现成岗位,岗位要现成生态——三个"现成"锁死了未来,开锁的人此刻可能还在学校里读书。声明式本身也在减负:把"怎么做"交给优化器,人脑的认知预算全花在"要什么"上。本章的断言就钉在这里。
本章的断言是:SQL 的胜利证明,标准的战争从来不在技术室里打,而在市场、委员会与销售现场的三张桌子上同时开席——技术更好的 Quel 输了,技术够用的 SQL 赢了;赢的不是语言,是生态位。这个断言可以被反驳:如果未来出现一种技术明显更优的查询语言,仅凭技术优势就替换了 SQL 的存量生态而不靠商业与标准运作,那么标准无用论就是错的,好东西自己会赢,桌子只是摆设。
第 076 章 1980s:B树家族、缓冲池与查询优化器的心脏
磁盘在转,CPU 在等
1970 年代初的机房里,最贵的声音是磁盘的寻道声。一条查询下来,磁头在盘面上来回摆动,每摆一次都要等,CPU 在旁边干等——处理器算得飞快,磁盘摆得极慢,两者差好几个数量级。IMS 时代的程序员活在指针里(见第 074 章):记录与记录用物理指针串着,查一条记录,要顺着指针把一串磁盘块全读进来;数据挪个地方,指针全断。指针是手工的网,网眼里漏的全是 I/O:开发时埋指针,加班;运维时断指针,半夜被叫醒。关系模型的“数据独立性”,治的就是这个病——而 B 树,是药方里的第一味。所有数据库问题的根子,在 1970 年代是同一个:磁盘太慢,慢到必须把每一次 I/O 都当成钱来花。
1970 年,两个工程师给出了花钱的方案。鲁道夫·拜尔(Rudolf Bayer)与爱德华·麦克雷特(Edward McCreight)发明了 B 树,1972 年发表。当时的磁盘又贵又小:一个柜子装今天一个文件的零头,租机时按分钟计费——I/O 不只是慢,是贵。贵的东西要省着用,省的办法就是一次多拿:一个节点塞满一整个磁盘块,一次 I/O 的钱,买几百个键。主意一句话:让树的每个节点刚好装满一整个磁盘块,一个节点一次 I/O 读进来,里面塞几百个键、指几百个孩子——扇出一大,树就变矮;树一矮,查到底只要几次 I/O。二叉树查十亿条记录要三十层,B 树只要三四层。更妙的是自平衡:插入填满就分裂,删除掏空就合并,所有叶子永远等深——树不会长歪,查询时间没有最坏情况的惊吓。分裂是局部手术:满节点一分为二,中间键上提,父节点多一个孩子——手术只动一条路径,整棵树纹丝不动。合并是逆手术:空节点并入邻居,父节点少一个孩子。最坏的情况是分裂一路顶到根,树长高一层——全树高度加一,所有叶子同步加深,依然等深。平衡的代价是写放大:一次插入可能引发一串分裂,写一个键,动好几个节点。读的便宜,是用写的贵换的——读写比,决定了 B 树的账本。磁盘还是那个磁盘,算法把寻道次数从三十砍到三。这就是整章的起点:一块旋转的铁盘子,逼出半个世纪最长寿的数据结构。
B 树的发明有个谜:B 到底代表什么,没人说得清——拜尔、波音、平衡,众说纷纭,官方从未认证。一个字母的悬案,半个世纪没人破;破不了也不耽误用,全世界的关系数据库,从甲骨文到开源小库,索引的默认选项都是它的后代。名字是谜,疗效确凿——这是工程史的常态:先好用,再考据,考据永远排队。排队的还有 B 树的年龄:1970 年发明,1972 年发表——发明与发表之间隔了两年,审稿、修改、排版,学术生产线的标准耗时。标准耗时背后是同行评审:匿名审稿人逐行挑刺,作者逐条反驳——B 树的每一处细节,都经过陌生人的毒打。毒打是质量的保证:没挨过打的论文,不敢上生产线。
为磁盘块量身定做的树
B 树的形状,是磁盘形状的翻版。磁盘读写的单位是块,一次几 KB;内存读写的单位是字节,相差千倍。B 树把一个节点做成跟磁盘块一样大:读一次,读一整个节点,节点里的几百个键一次到位。扇出(一个节点能指多少个孩子)越大,树越矮;树越矮,寻道越少。设计公式就一句:节点大小对齐块大小,扇出顶到块容量。十亿条记录,扇出一千,三层到顶——根下一层索引,索引下一层叶子,三次 I/O,必达。算一笔直观的账:扇出一百时,十亿记录要五层;扇出一千,只要三层——扇出翻十倍,高度砍两层,I/O 省两次。这就是为什么内点不存记录:省出来的每一个字节,都变成扇出;扇出的每一个增量,都砍在寻道上。三层是什么概念?根常驻内存,实际 I/O 只有两次——十亿条记录,两次磁盘寻道。人类眨眼的功夫,数据已经到手。B+ 树的两处改动,本质是一处:把字节从记录搬到扇出。磁盘的物理现实(块大、寻道贵)被翻译成树的设计参数,这是本章“机械骨架”的第一块:硬件长什么样,数据结构就长什么样。
1979 年,道格拉斯·科默(Douglas Comer)发表综述《无处不在的 B 树》(The Ubiquitous B-Tree),给 B 树家族最成功的一支定了名:B+ 树。综述的写法值得学:不发明新东西,把散落的实践收拢、命名、比较——B 树、B+ 树、B* 树,各写优劣,各配场景。1979 年的数据库圈,正缺这样一张地图:论文里百花齐放,工程师无所适从。科默的地图一出,选型有了共识:点查加范围扫,闭眼 B+ 树。综述的权力,有时大于发明:发明给一种可能,综述给全行业一个默认选项。默认选项的价值,十年后才看出来——满世界的 B+ 树,全是这篇综述的选民。改动只有两处,却招招致命:第一,内点只存键不存记录,记录全沉到叶子——内点更苗条,扇出更大,树更矮;第二,叶子用链表串起来,范围扫描一路向右,不用回头。查一个值,走树;查一片值,走链表。关系数据库最常见的两种操作(点查与范围扫),被一棵树同时伺候了。从此 B+ 树成了默认索引:建表不建索引是裸奔,建索引就是建 B+ 树。科默的综述标题成了预言:“无处不在”——发表时还是愿景,五十年后是现状。B+ 树的代价在写操作:插入填满节点就分裂,一分二,二分四,分裂向上传播;删除掏空节点就合并,合并向上传播——读是三四次 I/O,写可能是一串。删除的另一面是震荡:频繁增删会让页在分裂合并间来回横跳——刚分就合,合完又分,I/O 全花在折腾上。治震荡的方子是留余量:分裂不满,合并留存——空间换稳定,亘古不变的交易。读多写少的负载下,这笔账划算;写密集的负载下,分裂合并的抖动能把延迟曲线戳出毛刺。这笔账,第 078 章有人来算——LSM 树的反叛,起点就在这里。B+ 树是图书馆卡片目录的自动化:卡片按首字母排,找书先翻卡片,再按索书号取书——内点是卡片柜,叶子是书架,链表是相邻书架的走道。几百年的图书馆学,一夜之间被压缩进三次 I/O。卡片目录的精髓从来不是卡片,是顺序——按序排列的东西,才能二分、才能范围扫、才能“从这开始往后翻”。B+ 树把“顺序”从管理学变成数据结构,把图书管理员的直觉变成指针。直觉的自动化,是所有数据结构的共同剧本。
二叉树(内存的形状) B+ 树(磁盘的形状)
● ┌───┬───┬───┐
/ \ │键 │键 │键 │ 一节点 = 一磁盘块
● ● └──┬──┬──┴──┬──┘
/ \ / \ ▼ ▼ ▼
● ● ● ● 查十亿条:约30次I/O [叶子]→[叶子]→[叶子]
链表串起,范围扫描一路向右
B 树家族还有亲戚:B* 树(分裂时先找邻居借空间,填得更满)、R 树(空间索引的变体)——本章不展开,提一句证明家族兴旺。B* 树的思路值得多看一眼:标准 B 树半满就分裂,空间利用率有天花板;B* 树满了先问邻居有没有空位,有就匀过去,实在没地方才分裂——同样的数据,占更少的页。为了省出来的页,代码复杂度翻几番,值不值?磁盘贵的年代值,磁盘便宜的年代不值——B* 树始终是备选,不是主流。主流永远属于“够用且简单”的那个:B+ 树赢在刚刚好。但主角永远是 B+ 树:它赢,不是因为数学最美,是因为最懂磁盘。数据结构没有抽象的美丑,只有与硬件的合拍程度——合拍的活半个世纪,不合拍的进论文集。这是卷七主导约束的第一条:外存随机 I/O 的延迟,是一切设计的起点。
内存里的候车室
树再矮,I/O 还是 I/O——能不读盘,就别读盘。缓冲池就是干这个的:从主存里划出一片地,缓存刚读过的磁盘页;下次再要,直接从内存拿,零寻道。缓冲管理器是候车室的检票员:页进来,登记;要踢人,看谁最久没被用过——LRU(最近最少使用):踢最久没人理的那页。LRU 的直觉是时间局部性:刚用过的,大概率马上还用;好久不用的,大概率继续不用。直觉大多时候对,错起来也好看:顺序扫描大表时,每页只用一次,LRU 把热页全踢了,留一堆刚读过、再也不会读的——缓存污染。数据库老手治污染有偏方:顺序扫描用完即弃,不进缓冲池,或者单独划区——大象走专用通道,别踩花园。直觉的反例,逼出工程的补丁;补丁摞补丁,就是成熟系统。补丁是 CLOCK:给每页一个引用位,被访问就置一,时钟指针转圈清零,遇到零就踢——LRU 的穷人版,效果八九不离十,代价小得多。CLOCK 的妙处在“差不多”:完美 LRU 要维护链表、加锁、调顺序,并发一高,锁本身就成瓶颈;CLOCK 一位一指针,原子操作搞定,并发友好。从 LRU 到 CLOCK,是工程史的缩影:完美的算法让位给够用的算法,够用的赢。赢的逻辑很直白:缓存置换的差距是几个百分点,并发的差距是几倍吞吐——为几个点丢几倍,没人干。
缓冲池的命中率,是数据库性能的晴雨表:命中率高,磁盘基本歇着;命中率掉下来,磁头转得冒烟。调优 DBA 的一半工作,就是看缓冲池:谁在蹭热页,谁在污染,谁该绑专用池。看板的另一面是取舍:内存就那么多,给 A 多了,B 就少了——缓冲池的分配,是 DBA 的预算政治。预算政治没有公式,靠经验:热表多给,冷表少给,临时排序单独划区。大系统里,缓冲池调优是门手艺,手艺人的眼睛就是监控图表。图表会撒谎:命中率高,可能是真热,也可能是污染——热页与垃圾都占着内存,命中率照样好看。看板的艺术,在于分清谁是客,谁是贼。专用池是大型系统的标配:索引页一池,数据页一池,排序的临时页另起一池——不让顺序扫描的大象踩死随机点查的花园。池子之外还有两手:预读与延迟写。预读赌的是顺序:顺序扫描时,提前把后面几页读进来,磁头不用等——赌赢了,流水不断;赌输了,读了白读。延迟写赌的是合并:改了页先不落盘,攒一批一起写——随机写变顺序写,寻道省大半。延迟写的另一面是脏页:内存里改过、盘上还没落的页,叫脏页;脏页攒多了,崩溃时丢的就多——恢复要重放,停机要等人。脏页与检查点(定期刷盘的同步点)是一对冤家:刷得勤,恢复快,平时慢;刷得懒,平时快,恢复时哭。调这对冤家,是 DBA 的日常:在线交易系统刷勤一点,分析系统刷懒一点——业务不同,账不同。这对冤家的官司,下一章接着打——WAL 与 ARIES,就是为脏页擦的屁股。缓冲池管得再好,也管不了断电——断电之后的事,归下一章。两个赌局,一个赌读,一个赌写;读赌顺序,写赌批量。缓冲池的三件套(缓存、预读、延迟写),本质是同一句话:磁盘慢,就别让它等、别让它乱跑、别让它白跑。但缓冲池有个天花板:内存再大,也装不下整个库;装得下的那天,磁盘就退休了——那一天四十年没来,内存涨得快,数据涨得更快。缓冲是买时间的,不是买断的:买到命中,买不到认命。这是机械骨架的第二块:B 树管“怎么找”,缓冲池管“怎么少找”。两块合起来,就是存储引擎的一大半:找得快,找得少,剩下的交给优化器去操心“找的顺序”。
但找得再快,也架不住问得蠢。一条 join 写错了顺序,B 树再快也救不回来——省 I/O 的下一站,是省计划。1979 年,答案来了。
最便宜的,只是预测
1979 年,IBM 的帕特里夏·赛林格(Patricia Selinger)带着 System R 团队发表《关系数据库管理系统中的访问路径选择》,业界第一个关系查询优化器。System R 是 IBM 圣何塞实验室的赌局:赌关系模型能跑、SQL 能用、优化器能算赢——三赌全中,赌出一个产业。第 075 章讲过 System R 的诞生,这里只讲它的心脏:没有优化器,SQL 的“非过程化”就是空头支票——用户不说怎么查,机器必须自己会查。优化器是声明式语言的兑现人:没有它,SQL 只是漂亮话;有了它,漂亮话能跑出结果。赛林格们兑现的,是科德开的支票。赛林格 1975 年加入 IBM 研究院,带着优化器一路做到 IBM Fellow(1994 年)、美国国家工程院院士(1999 年),2018 年退休——一辈子押在一件事上。但 1979 年的论文从不写成个人传记:领衔之外,联署着莫顿·阿斯特拉罕(Morton Astrahan)、唐纳德·张伯伦(Donald Chamberlin)、雷蒙德·洛里(Raymond Lorie)、托马斯·普莱斯(Thomas Price)——访问路径、SQL、编译器,各路人马凑一桌。张伯伦后来在口述史里说,赛林格组织了优化工作与这篇突破性论文,同时点名洛里等人的贡献。领导力在这里不是独自发明每一环,是把问题组织成可实现的合同:统计给输入,模型给标尺,动态规划给边界——合同一签,声明式语言才能经济地跑起来。SQL 的承诺是非过程化:用户说要什么,不说怎么拿——怎么拿,优化器定。定之前,先列出所有走法:全表扫描还是走索引,先连 A 再连 B 还是反过来,嵌套循环还是归并;再给每种走法估个价:读多少页、调多少次接口,加权求和——COST = 页面读取 + W×接口调用。W 是权重:I/O 与 CPU 的汇率。今天看来,汇率是拍的——CPU 与 I/O 的相对速度,机器不同,汇率不同;但 1979 年把 CPU 写进公式,本身就是进步:此前的模型只看磁盘,CPU 当免费的。免费的东西最贵——CPU 瓶颈的查询,用纯 I/O 模型会错得离谱。W 的存在,是诚实:承认算力也要钱。至于汇率准不准,那是下一轮的事——先有名目,再谈精度。最便宜的上场。这就是代价优化器的全部:枚举、估价、选最低。
估价的输入是统计,不是现实:表多少行(NCARD)、占多少页(TCARD)、索引多少不同值(ICARD)——目录里的压缩快照。快照会旧:统计靠定期更新,更新之间,数据早变了。统计的维护本身就是买卖:每次修改都同步更新,锁与目录开销受不了;太久不更新,优化器拿着旧地图打新仗。System R 的选择是定期刷新——UPDATE STATISTICS 负责收税,税率(频率)由 DBA 定。税率定的全是权衡:勤了,维护贵;懒了,计划瞎。目录统计的本质,是用昨天的现实赌明天的查询——赌注不大不小,刚好是一个全表扫描与一个索引查找的差价。选择率靠拍:无索引等值条件猜十分之一,单边范围猜三分之一,闭合区间猜四分之一——论文作者自己承认,这些数“没有更深意义,只用于排序”。拍脑袋的数,居然管用——因为优化器要的不是精确,是排序正确:A 比 B 便宜,这个判断对就行,至于便宜多少,无所谓。这是工程数学的精髓:精度不够,序关系来凑。十分之一准不准?不准。但“有索引比没索引强”这个序,对了就够。优化器是排序机器,不是预言家——排对名次,不猜具体分数。多个条件相乘,隐含独立性假设:城市与邮编、产品线与价格,默认互不相干——现实里高度相关,误差就此埋下。一个经典翻车:性别与职业各自看都均匀,合起来“女矿工”万里挑一、“男护士”凤毛麟角——按独立相乘,基数差出几个数量级。2015 年的研究证实:与成本公式的小错相比,基数估计的错误更能搞砸计划——错的不是算术,是输入。
优化器最妙的一招叫“有趣顺序”:眼前贵的路径,如果自带后续要的排序,可能全局最便宜。物理计划不只选路径,还定形状:访问路径、物理算子、连接顺序,三件套缺一不可。访问路径管“从哪拿”:全表扫还是走索引;物理算子管“怎么拼”:嵌套循环(一行行对)、归并(拉链式对接)、哈希(建表一次定位)——算子没有银弹,小表配嵌套,有序配归并,大表无序配哈希;挑错一个,慢一个数量级。算子的家谱很长:排序归并、哈希连接、嵌套循环是三大姓,往下还有位图、跳跃、分区版——姓是原理,名是实现。选哪个姓,看数据的面相:有序的脸配归并,散列的脸配哈希,什么都没有的脸,只能嵌套循环硬扛。看面相的本事,叫基数估计——估计错了,配错亲,慢是轻的,跑不完是重的。配亲的红娘,就是优化器;红娘也有看走眼的时候,看走眼的代价,全场买单。三件套互相咬合:索引给了顺序,归并就便宜;顺序没了,哈希才划算;顺序错了,全盘皆错。优化器是三维棋手,下一步,看三步。看三步还不够,要看对手——对手是数据分布,分布天天变,昨天的最优是今天的陷阱。自适应优化应运而生:跑着看,不对就换计划——认赌,允许反悔,反悔趁早。举个现实例子:查询要按客户分组汇总,A 方案全表扫描快但无序,最后还得大排序;B 方案走客户索引慢一点,出来的数据天然按客户排好,分组直接算——B 眼前贵,全局便宜。为了这个可能,优化器给每个子计划多留几个候选:最便宜的无序版,各排序下最便宜的有序版。局部贪心会杀死全局最优,有趣顺序专治贪心。连接顺序用动态规划压住组合爆炸:八个表两两组合,顺序一排就是天文数字——n 个表的连接顺序接近 n 的阶乘,十个表就数百万种,二十个表直接天文数字。穷举是死路,贪心是赌命,动态规划是中间道路:先算小子集的最优,再往大了拼,笛卡尔积尽量往后推——IBM 370 上八表连接数秒出计划。1979 年的机器,几秒钟规划八个表的连接,是工程奇迹。奇迹的另一面是剪枝:搜不完,只能剪;剪掉的候选里,可能藏着真最优——优化器找的是“搜得到里的最优”,不是“宇宙里的最优”。承认搜不完,本身就是诚实。连接树的形状也有讲究:单机优化器只认左深树——A 连 B 的结果再连 C,一路向左深潜;右深树(先连好右边再整体拼)省内存但难流水,并行时代才翻红。树形即策略:形状定了,内存与流水的账就定了。
但这套制度有个诚实的注记,论文自己写的:预测成本作为绝对值常常不准;它在多数测试里选中了真实最优,但“仍需验证”。1986 年,麦克特与洛曼对分布式 R* 优化器做了验证:把估算资源与实际消耗并列——I/O 模型大体有效,CPU 细节要补,缓冲假设一变结果就变。这次验证的制度意义,比特务工作还大:成本模型从此是可以被审计的——误差集中在哪类连接、哪组参数,就补哪里的统计与公式。预测的价值来自可证伪,不是数学外观。2015 年的研究补上后半句:与成本公式的小错相比,基数估计的错误更能搞砸计划——错的从来不是算术,是输入;2025 年的回顾仍把基数误差列为未竟之业。四十年过去,敌人还是同一个:不知道未来有多少行。不知道,就只能猜;猜,就要认。认,是优化器的出厂设置。最便宜的,只是预测——预测与现实之间,隔着缓存状态、并发、参数、数据分布。PostgreSQL 把这句注记做成了命令:EXPLAIN 只给预测,EXPLAIN ANALYZE 才真正跑一遍报实测。一个看广告,一个验货。DBA 的日常就是对账:预测说走索引很快,实测走了很久——差在哪?行数估错几个数量级,嵌套循环把小表扫成了大海。对账单越积越厚的地方,就是优化器最瞎的地方; DBA 修统计、建索引、改写法,一单单一结。结不完的单,攒成技术债;技术债的利息,是每一次慢查询。看懂执行计划,是 DBA 的成人礼:顺序扫描、索引扫描、嵌套、哈希,每个节点一行行对——计划是优化器的自白书,读懂它,才知道机器在想什么。自白书也会撒谎:撒谎的不是计划,是过期的统计——读计划先看统计日期,日期太老,计划先打三折。优化器的约束决斗对手,不是别人,是未来本身:计划定在执行前,证据到在执行后——用过去的统计,赌未来的负载。赌赢是常态,赌输是新闻;新闻多了,就有了自适应优化、运行时重规划——认赌,但允许反悔。这是约束决斗的硬性对价:对手(不确定性)占据技术道德高地——它说的全对,优化器只能认,然后想办法少输。少输的办法,PostgreSQL 早写好了:先看广告,再验货;广告与货对不上,调统计、建索引、改写法——优化器不是神,是参谋;参谋的图旧了,前线自己更新。参谋与前线的关系,就是优化器与 DBA 的关系:一个出主意,一个负全责。出主意的可以错,负全责的不行——权责不对等的经典结构,古今同理。
回看卷七的三项主导约束,本章正面回答第一项:外存随机 I/O 的延迟——B 树压寻道,缓冲池省 I/O,优化器选最少的路;三招全是为延迟买的单。后两项(网络分区、合规边界)是后面的章节的事,但伏笔已经埋下:R* 的分布式验证,是分区的预演;统计与目录的集中管理,是合规的前身。一章写磁盘,章章写约束——主线从不缺席,只是有时隐身。
所以,本章的判断是:B 树家族与优化器的胜利,是把磁盘的物理现实翻译成数学结构的两次成功——拜尔们用扇出把寻道压到几次,赛林格用代价模型把“怎么查”外包给机器;前者让人少等磁盘,后者让人少操心。少操心是有代价的:操心外包给机器,人就看不懂机器在干什么——执行计划越聪明,DBA 越像巫医,对着看不懂的节点猜来猜去。外包的终点是黑箱,黑箱的终点是信仰。信优化器,得永生;疑优化器,自己写提示。提示是后门,也是认输——认赌的人,连骰子都想自己掷。掷骰子的人多了,优化器就老了:人人手写提示,等于人人投票不信任;不信任攒多了,优化器名存实亡。信任的悖论在于:优化器用得越多越准,越准越没人看,错了也没人发现——直到一次大慢查询翻出三年的烂账。打破这种黑箱循环的只有事故:一次全站慢查询,逼所有人重读执行计划;一次统计过期引发的雪崩,逼全行业重写采集策略。事故是最好的老师,学费最贵,记得最牢。优化器的进化史,就是一部事故驱动史——每一次大改进的背后,都躺着一次生产事故。太平无事时,没人改优化器;改优化器的,都是被事故逼的。两次翻译隔了十年:1970 年代解决“存得下、找得到”,1979 年解决“找得巧”——前者是空间的胜利:把二维的盘面压成三层的树;后者是时间的胜利:把运行时的选择提前到编译时。空间换时间的老把戏,在这里玩到极致:B 树用空间(宽节点)换时间(少寻道),优化器用时间(提前规划)换时间(执行更快)。存、找、巧,三步上篮,缺一步都不行。而两次翻译之间,还隔着一次分布式远征:R* 把优化器搬到多地机房,验证了代价模型在广域网依然有效——1986 年的验证报告,是单机理论走向分布式的出生证。这张出生证的有效期很长:从集中式到分布式,从磁盘到闪存,代价模型的骨架一直没换,换的只是统计的精度与权重的标尺。而骨架之外的血肉——缓冲池的置换、预读的火候、统计的税率——全是 DBA 的手艺:手艺传三代,徒弟出师,机器还没换代。手艺与骨架,一个管今天,一个管十年。管十年的东西最难写:写早了没人懂,写晚了没人用。1979 年的论文,写得刚刚好——早一年,机器撑不住;晚一年,别人先写了。时机是论文的隐藏作者,硬件是论文的出版商。出版商换了,书要重印:磁盘时代的优化器,到了闪存时代要重调权重;权重一调,江湖重排——每一代存储介质,都逼优化器重写一遍假设。但翻译都有税:B 树的税是写放大与分裂合并(越更新越忙,详见第 078 章 LSM 的反叛),优化器的税是“预测冒充事实”——统计会旧,假设会错,基数一偏,全盘皆错。有人可以反驳:如果统计实时、算力无限,预测能否逼近现实?回答藏在 1986 年的验证里:误差最大的从来不是公式,是输入——现实拒绝被压缩成目录;只要观察有成本,预测就永远是预测。B 树赌的是局部性,优化器赌的是未来——两个赌局都赢了半个世纪,赌注是同一个:人脑算不过来,交给机器算;机器算不准,认。认,是工程的成年礼。成年礼之后是中年危机:第 078 章,闪存来了,B 树的税单到期;第 079 章,网络分区来了,优化器的赌局换桌。但那是后话——本章的任务,是给磁盘时代立碑。碑上只有两行:扇出压高度,代价选计划。碑文简短,因为真理不长;碑文长寿,因为磁盘不死——磁盘还没死,碑就不会倒。等哪天存储介质换了天,碑文自会更新;更新的那天,就是下一章的故事。
第 077 章 1986:事务处理、ACID 与两阶段提交的绝对确定性
断电的那一秒
1980 年代的银行机房里,最可怕的不是黑客,是停电。想象一笔转账: A 账户扣 100,B 账户加 100,两条写入之间隔着几毫秒——如果断电恰好劈在这几毫秒里,A 扣了,B 没加上,100 块钱凭空消失;或者反过来,B 加了,A 没扣,100 块钱凭空出现。银行的账本不允许凭空:多一分是事故,少一分也是事故。更日常的是并发:柜台在扣款,ATM 在取款,网银在转账——同一账户三面开战,余额到底听谁的?柜台的单子先到,ATM 的请求后到,网银的卡在半路——三个“同时”撞在一起,没有事务的年代,靠的是运维的胆量与深夜对账:白天硬着头皮跑,晚上拿着报表逐笔勾。勾不平的,人工调账;调不平的,认赔。事务出现之前,银行的正确性是拿人肉换的。人肉换正确,换到深夜对账单堆成山——山越高,越说明机器该接手了。格雷们的全部工作,就是把这座山搬进机器:账不错,人不熬夜。对账单的山平了,另一种山起来了:锁等待的报表、死锁的日志、慢查询的清单——山还是那座山,从纸上搬进了屏幕里。操作系统的世界里,断电是常态:插头、雷击、机房跳闸,平均每年总有几次。数据库的全部尊严,系于一个问题:断电可以发生,账不能乱。
吉姆·格雷(Jim Gray)1944 年生于旧金山,一辈子研究怎么让账不乱。1998 年,他凭“对事务概念及其实现的开创性贡献”获得图灵奖——颁奖词把“事务”与“实现”并列:概念重要,实现同等重要。1985 年,他写下事务处理能力的度量——怎么比谁的数据库快,得有个跑分;这个跑分后来长成 TPC 基准组织,至今仍是数据库跑分的尺子。尺子一立,厂商就开始刷分;刷分带动优化,优化反哺用户——基准的政治经济学,从 1985 年玩到今天。2007 年 1 月,他独自出海后失踪,2012 年被宣告死亡;搜救动用了卫星图像众包,成为互联网时代第一次大规模网络搜救——志愿者在卫星图上找船;找他的人,和他做的系统一样分布式。分布式找人,没找到人;但找的过程,成了众包的成人礼。后来的搜救、寻物、灾害响应,全是这个模式的续集。格雷的告别,意外成了一次分布式协作的演示。演示的代价是生命,课免费。免费的课,最贵。最贵的那一课,是缺席:系统设计得再好,设计师会缺席;缺席之后,系统还得转。格雷的系统转了下去——事务照跑,账照算,人不在了,机制还在。这是对工程师最高的奖赏:人走,茶不凉,因为茶本来就不是人烧的,是机制烧的。机制,才是不朽的真正形态。最贵的课,往往最简单:人会消失,系统要活下去——格雷用一生回答“系统怎么不丢数”,用告别回答“人没了怎么办”。两个答案,一个比一个重。他生前定的度量,至今仍是数据库跑分的尺子。事务二字,经他之手,从工程黑话变成学科基石。
事务的定义一句话:要么全做,要么全不做——中间状态不许被看见。但“一句话”背后,是四个互相打架的承诺。
四个互相打架的承诺
1983 年,哈尔德与罗伊特(Haerder & Reuter)发表《面向事务的数据库恢复原理》,给事务的四个性质定了名:ACID。原子性(Atomicity):事务是原子,要么全生效,要么全没发生——断电劈在中间,恢复后世界要么是旧的,要么是新的,不能是半个。转行李的比喻:要么整箱托运,要么整箱留下,不许开箱抽走一件——一半的事务比没有更糟。原子的实现靠 undo:没干完就崩,照着日志把干过的全擦掉——擦得干干净净,像没来过。擦除本身也要记账:擦到一半又崩,下次接着擦——undo 的 undo,还是 undo。原子性的背后,是“可撤销”的承诺:干过的都能抹掉,抹的动作本身也可重入。承诺听起来简单,做起来是 ARIES 一整套 redo/undo 机器——机械的复杂,换语义的干净。一致性(Consistency):事务把数据库从一个合法状态带到另一个合法状态——约束不被打破,账永远平。注意:一致性不保证业务对,只保证约数守恒——转错了账,只要借贷相等,数据库照样说“一致”;对错是应用的事,平账是数据库的事。外键、非空、唯一、检查约束——数据库替你盯着的,全是“形状”;形状对了,内容错了,数据库不背锅。背锅的是写应用的人。这就是一致性的诚实与无情:它只保格式,不管对错。隔离性(Isolation):并发的事务互相看不见中间态——你转你的账,我查我的余额,看到的都是完整快照。最难的是“看不见”:几十个事务同时跑,每个人眼里的世界都得是自洽的——自洽的假象,靠锁与版本维持。看得见中间态的病,叫脏读:读到别人没提交的数,对方一回滚,你手里的就是幻觉;读两次不一样,叫不可重复读;查着查着多出几行,叫幻读——三种病,病因都是“看见了不该看的”。隔离的等级,就是捂眼睛的严实程度:捂得越严,并发越低;捂得越松,病越多。医生(DBA)开药,看的是业务的体质:银行捂严实,计数器松一松——病与药,得对症。持久性(Durability):提交了就是提交了,断电、宕机、天塌下来,数据不丢。持久是承诺,不是现状——承诺的兑现,靠 WAL 落盘的那一下;没落盘的提交,只是口头支票。支票与现金之间,差一次刷盘;刷盘之前断电,支票作废。于是有了组提交:一批事务的日志攒一起刷,均摊一次 I/O——延迟换吞吐,个体的快换整体的省。持久性的账本,记的都是 I/O:刷得勤,丢得少,慢得多;刷得懒,跑得快,赌得大。赌桌的名字叫“断电概率”:赌赢了省 I/O,赌输了丢提交。银行不赌,社交敢赌——账本不同,赌法不同。
四个性质互相打架,是本章的约束内核。原子性要求“全有或全无”,碰上断电就得回滚——回滚要记录,记录要写盘,写盘要时间;隔离性要求“互不干扰”,碰上并发就得加锁——锁多了死锁,锁少了串味;持久性要求“落袋为安”,碰上速度就得等刷盘——等刷盘就慢,不等就可能丢。一致性最微妙:它是目的,另外三个是手段——手段打架,目的遭殃。ACID 不是四个并列的愿望,是一个不可能三角形的四角宣言:又要快,又要并发,又要不断电丢数——全都要,怎么办?答案是分层:每一层解决一个,用机制换确定性。第一层叫 WAL,第二层叫 ARIES,第三层叫锁,第四层叫提交协议。四层叠起来,就是现代数据库的信任栈——和第 070 章的信任栈异曲同工:每一层都假设下层坚固,每一层都在为上层兜底。
先写日志,再碰数据
一切恐惧有个名字:页断裂(torn page)。磁盘读写的单位是页,一页几 KB;断电可能劈在写一半的时候——半页新、半页旧,拼出一页谁也没见过的脏数据。断电后要么旧状态、要么新状态,不能是半个——这条规矩,是恢复系统的宪法第一条。torn page 的阴险在于静默:读到半页脏数据,校验和可能还对得上——错得悄无声息,比报错可怕十倍。WAL 的第一要务,就是让 torn page 不可能发生:数据页可以半写,日志是顺序追加,一条写完算一条——日志没有“半条”,只有“有”或“无”。把原子单位从“页”换成“日志记录”,torn page 就从物理定律降级成历史名词。两条路线从这条宪法出发,走向相反的哲学:影子分页(shadow paging)玩“写时复制”——改数据先写影子页,提交瞬间切换指针,原子切换天然成立;WAL(预写式日志)玩“记账在先”——改数据之前,先把“要改什么”顺序记到日志里并刷盘,数据页随后慢慢写,崩溃了按账本重放。WAL 的铁律有两条:第一,改页之前,日志先行——账本不到盘,数据不动笔;第二,提交之前,日志落盘——不落盘的承诺不算数。两条铁律一立,崩溃恢复就有了抓手:盘上的日志是唯一的真相,内存里的全是草稿。草稿丢了不心疼,照着账本重抄一遍。规矩的代价是延迟:每次提交都要等一次刷盘,再快的盘也有延迟——延迟攒起来,就是事务的吞吐天花板。天花板之下,各家显神通:组提交攒批刷,异步提交赌不断电,不落盘的内存表干脆不要持久——铁律是死的,人是活的;活人为了快,发明了一百种打折的持久。打折的尽头,是把“D”从 ACID 里划掉——那是另一个故事的开头。开头已经写好:日志即真相,真相即恢复——WAL 的哲学,一句话:先记账,后干活;账在,活就在。影子页优雅但碎片化,WAL 笨拙但通用——历史选了 WAL:PostgreSQL 到 SQLite 到 Kafka,人人先写日志。日志还是复制的事实来源:主库的账本,备库照抄——同一条日志,又当恢复用,又当同步用,一鱼两吃。
ARIES 是 WAL 的集大成者:1992 年,IBM Almaden 的莫汉(Mohan)等人发表《ARIES》,全称“利用语义的恢复与隔离算法”。三阶段:分析一遍日志(谁赢了谁输了)——从最后一个检查点开始扫,列出活跃事务与脏页清单;重做一遍赢的(redo)——按日志序列号重放,不管三七二十一,先把盘面推到崩溃前的样子,多做的也不怕;撤销一遍输的(undo)——没提交的全倒回去,倒回去的操作本身也记日志(补偿日志),倒一半再崩,照样能续。三阶段的顺序不能反:先向前滚到顶,再向后退到位——历史先重演,再修正。配套两条纪律:偷(steal,没提交的页也允许先落盘)与不强制(no-force,提交了也不必立刻落盘)——自由的代价是恢复时全靠日志,日志成了唯一的真相。偷的逻辑是内存不够:缓冲池满了,没提交的页也得腾地方——腾出去,靠日志兜底;不强制的逻辑是攒批:提交了不急着刷,攒一波一起写——省的是随机 I/O。一偷一懒,把“落盘时机”彻底交给缓冲管理器;恢复时,ARIES 按 LSN 对账,该重做的重做,该撤销的撤销。自由与纪律的交换:运行时越自由,恢复时越依赖账本。账本,是自由的抵押物。日志序列号(LSN)给每条记录编号,页头也盖戳——重放时对号入座,跳过已落盘的,只补没写完的。LSN 是时间的化身:单调递增,永不回头——谁先谁后,看号说话。页头的戳是页的简历:写着“我已重放到哪条”,重放时一对,发现已做就跳过。跳过是性能的关键:几十 GB 的日志,重放只补没落盘的那几页,其余的全是“已搞定”。对号入座的背后,是幂等:同一条日志重放十遍,和放一遍结果一样——重放不怕重复,就怕漏放。ARIES 的每一行设计,都在回答同一个问题:崩了之后,怎么不多不少正好恢复?答案是:编号、盖戳、对号、幂等——四个词,半本书。ARIES 之后,崩溃恢复从玄学变成工程:断电、重启、重放、上线,一套流程走完,账一分不差。银行敢把钱存在会断电的机器里,底气全在这套流程上。把一次真实的恢复按秒走一遍:凌晨三点机房掉电,三分钟后电力恢复,数据库进程重启。第一步装日志:检查点之前的账目确认已落盘,直接跳过——检查点就像定期存档的游戏进度,恢复永远从最近的存档开始。第二步扫描:从检查点读到日志末尾,列出崩溃时还在跑的事务名单。第三步重做:按 LSN 把所有已提交事务的改动重新施加,哪怕这笔事务的页早已落盘——先无条件重放到崩溃瞬间,宁可重复不可遗漏。第四步撤销:名单上没来得及提交的事务,按补偿日志逐条倒带。四步走完,磁盘上的状态与断电前一毫秒完全一致,一个比特都不多、一个比特都不少——整个过程无人值守,这也是它被称为算法而不是流程的原因。
这套流程里藏着一个环形的代价:第三步的重放要从检查点扫到崩溃点,检查点打得太勤,正常运行时刷盘的额外开销就大——每打一次,缓冲池里的脏页都要强制落一轮盘,前台事务跟着卡一拍;打得太懒,崩溃后要重放的日志就越堆越长,恢复时间没有上界。检查点的频率,就是“平时多疼一点”与“疼一次疼个够”之间的旋钮,DBA 按恢复时间的服务承诺来定它的刻度——承诺五分钟上线,检查点的间隔就按五分钟内的可重放量反推。一笔看不见的账,记在每一次看似无关的例行卡顿里。
WAL 要防的头号事故叫页断裂(torn page):一个数据库页在磁盘上占多个扇区,断电劈在写入中途,恢复出来的页一半是新值一半是旧值——日志说这页改过了,页上的数据却是残缺的,重放无从下手。工程上配了两套对策:给每个页存校验和,恢复时发现断裂就用日志把整页重放一遍(既然残缺,索性全量重做);或者更老派的一条路——影子分页(shadow paging),写前先克隆整页,改完把指针原子地切到新页,旧页原封不动。影子页的思路干净,但它每改一页都要复制一页、提交时要一次性切换整棵页表,随机写与地址碎片让它在大负载上败给了 WAL 的就地更新加日志重放。两条路线的分野也是一章的缩影:断电恢复没有优雅解,只有付得起与付不起的解。
锁与投票的双重困境
恢复管的是“断电不丢”,并发管的是“同时不乱”。两个事务同时读写同一行:一个要加钱,一个要读数——读到一半的值,算谁的?2PL 锁行,2PC 锁库——锁的粒度越大,僵住的代价越大。两阶段加锁(2PL)的规矩值得细看:膨胀期只加不放,收缩期只放不加——一把锁一旦放了,就不能再拿新的。这条规矩保证了可串行化:并发执行的效果,等价于某个串行顺序——乱中有序,序在事后可找。规矩的另一半解释了性能的形状:事务前半段只加不放,锁的持有量随执行单调上升,直到最后一个写操作才开始放——并发度在整个事务的生命周期里先被压缩到最低点。为什么不能提前放?提前释放的锁会让别的事务插进自己的中间态,可串行化的保证当场作废;这条纪律的严格程度,正是隔离级别可调的边界所在。代价是死锁:A 锁了甲等乙,B 锁了乙等甲,互相等到天荒地老。死锁的解法两派:预防派(按序加锁,天下太平但不灵活),检测派(画等待图,成环就杀一个)。生产系统多用检测:杀谁看代价,年轻的、改得少的先杀——被杀的事务回滚重来,用户只感到卡了一下。卡一下的背后,是一次谋杀:系统挑了最便宜的受害者,悄无声息地毙掉,重跑一遍。用户无感,系统有数——死锁检测的日志里,躺着每一次谋杀的记录。锁的哲学是悲观的:假设冲突一定发生,先锁为敬。
跨机器的事务更麻烦:A 地扣款,B 地入账,两边都得成——一半成的事,比全不成更糟。两阶段提交(2PC)回答:先问大家“能不能干”(准备),都说能,再喊“干”(提交);有一家说不能,全员撤销。准备阶段,各参与者把 undo/redo 日志刷盘,锁死资源,回一个“准备好了”——注意刷盘的对象:参与者在“同意”之前必须先把 undo 日志写到盘上,这一笔是整个协议的信用抵押;协调者若在收集完选票后崩溃,这些抵押品就是恢复时裁决的凭据;提交阶段,协调者一声令下,各家放行——准备是立军令状,提交是开闸。军令状的代价是资源冻结:从“准备好”到“收到令”,这段时间资源被锁死,谁也别想动——窗口越长,冻结越久。冻结的资源是沉默成本:业务停着,锁占着,钱不转。窗口的长短,看协调者的脸色:协调者快,全网快;协调者一卡,全网陪卡。阻塞最深的场景是协调者在第二阶段前宕机:所有参与者已经锁好资源、刷好日志,卡在“准备好了”的状态进退两难——放行没有指令,回滚没有授权,锁一直握到协调者复活。这段冻结窗口的长度不由任何参与者决定,只由那台宕机的机器多久被修好决定;跨库事务把几台机器的命运焊在同一个协调者身上,可用性随之取整队的最小值。工程上的缓解是超时与互询(参与者之间交换状态推断决议),但缓解不等于消除——2PC 的阻塞是协议结构自带的,想根治只能换协议,而换协议就是下一节 MVCC 与最终一致要讲的故事。拍板的人,成了全网的心跳——心跳一停,全网装死。投票加执行,两阶段缺一不可。但 2PC 有个死穴:协调者。准备完了、提交之前,协调者宕机——参与者们锁着资源,不敢提交,不敢回滚,集体僵住,叫阻塞。等协调者复活,或者等超时人工介入,锁一直占着,业务一直停着。人工介入是最后的手段:DBA 上线,查日志,问各方,手动提交或回滚——机器解决不了的问题,回归人肉。人肉解决有个前提:人得到场;半夜三点,电话打不通,业务就多停几小时。2PC 的账本上,最大的一笔不是性能,是半夜的电话费。超时的艺术在于阈值:太短,网络抖一下就误杀——好好的事务被判死刑;太长,僵住的时间全是停机——业务等到天荒地老。阈值没有公式,只有血泪:每家生产系统的值,都是被事故调出来的。调参的尽头是认命:2PC 的阻塞窗口关不掉,只能缩——缩到比故障恢复快,阻塞就约等于没有。约等于不是等于:约等于的另一边,躺着小概率。一年一遇的阻塞,遇上就是 P0 事故。粒度的学问:行锁精细,并发高,开销大——锁本身也要内存,一行一锁,锁表先爆;表锁粗放,并发低,开销小——一锁了之,别人全等。精细与粗放之间,是意向锁的折中:先声明“我要动这片”,再细化到行——粗锁探路,细锁干活。锁的粒度没有银弹,只有账本:并发度、内存、死锁率,三本账一起算。算来算去,大多数系统停在行锁——贵,但值。贵在哪?贵在锁表本身也是热点:加锁要原子操作,原子操作要缓存一致性,并发一高,锁管理器先成瓶颈。锁的悖论:为并发加的锁,成了并发的天花板。天花板之下,各家显神通:分区锁、无锁结构、MVCC 绕行——条条大路通罗马,罗马是“少锁”。少锁的终点是不加锁:乐观并发先干再验,验不过重来——赌冲突少,赌赢了飞起,赌输了重跑。
悲观锁之外的第三条路,是多版本并发控制(MVCC):写操作不覆盖旧值,而是为新数据另起一个版本,每个版本带着各自的时间戳;读操作按事务的快照时点取“当时最新”的版本——读的人读旧版本,写的人生成新版本,两条路互不挡道。读不阻塞写,写不阻塞读,这句口号是它对两阶段锁最直接的造反:锁的账本上,读写互斥原本是最大的一笔开销。代价同样明码标价:旧版本不能无限堆,需要后台回收;写与写之间照样冲突,两个事务同时改同一行,还是要有一个等一个。MVCC 换走的不是全部锁,是读写之间那把最挤的锁——对读多写少的负载,这一换就把并发度抬了一个量级。新版本堆多了,旧版本就得有人收:后台的清理线程沿着版本链挑出没有快照再引用的旧值,物理抹掉。回收有一条绕不开的暗礁——长事务。只要存在一个跑了几个小时仍未提交的事务举着旧快照,它快照点之后的所有版本都不能回收;一个忘了提交的长报表查询,能让整张表的版本链膨胀几倍。回收的速度与长事务的寿命,构成 MVCC 自己的一对内耗:版本留得长,快照读得稳;清得勤,磁盘才不胀。这条内耗没有消停解,只有监控——版本链长度是 MVCC 系统的体温计,烧起来就得去找那个忘了提交的长事务。
赌字当头,赢字在后。赌输的代价是重跑的成本:重跑便宜的业务随便赌,重跑昂贵的业务不敢赌——赌之前,先看赌注。赌注太大,就老实加锁;锁虽慢,稳。稳字当头,慢字靠边——银行选稳,微博选快;稳与快之间,隔着整整一个隔离级别。级别是刻度,刻度是妥协:最严最慢,最松最险——中间档,各取所需。取所需的本事,叫调优;调优的本事,叫经验;经验的学费,叫事故。这些讨论最终都要落到同一个门口:故障复盘室。每一次生产事故的复盘报告,都在重写下一版的锁策略、日志策略与隔离级别——数据库行业的工程纪律,一半是从事故报告里长出来的。学费已经交了,课程表也已经写完;剩下的,是把这一章的账目合上。
这门手艺的掌门人也有自己的账。吉姆·格雷 1998 年的图灵奖致辞把毕生工作概括为一句话——让交易处理成为一门可以计算的科学;他在 1985 年参与奠立的 TPC 基准,把各家数据库的交易性能放到同一张公开成绩单上比试,采购第一次有了中立的标尺。2007 年 1 月 28 日,格雷独自驾船出海撒母亲的骨灰,从此失联;2012 年被宣告死亡。数据库行业对他的纪念方式,是把他定义的 ACID 与他参与创立的基准,写进了此后每一笔全球交易的底层——一个人的名字消失在海上,他立的规矩替他继续上班。
所以,本章的判断是:事务处理的胜利,是把“算对账”从人品问题变成数学问题——格雷用机制把“不断电丢数、并发不串味、跨机不半吊”变成可验证的工程;ACID 四个字母,是人类对不确定世界开出的一张绝对支票,WAL、ARIES、2PL、2PC 是兑现支票的四台印钞机。而印钞机烧的是真金白银:锁的等待、日志的 I/O、投票的轮次、阻塞的风险——确定性没有免费的午餐,每一分确定性都是拿性能与可用性换的。换得值,因为银行的账本错一分就是事故;换不换得来,看的是业务——银行必须换,微博可以不换;银行讲绝对,微博讲大概——绝对与大概之间,隔着整整一个 ACID。这是工程最诚实的一课:没有最好的保证,只有最配的代价。最配的反面是最不配:给微博上 ACID,给银行上最终一致——错配比没有更糟。架构师的第一课不是选最好的,是选最配的;配错了,神仙难救。神仙难救的事,人间天天上演:为了 KPI 上强一致,为了省钱砍 WAL,为了省事关掉校验——省下的都是小钱,赔出去的都是大事。账,迟早要还。还账的时候,别嫌利息高——借的时候,可没人嫌钱多。利息的算法,写在每一次深夜告警里:省掉的 WAL,变成恢复时的眼泪;省掉的锁,变成脏数据的官司;省掉的投票,变成跨库的烂账。省与赔,迟早两清。两清的那天,账本是平的,人是累的——累,说明账算对了;不累,说明有人在替你熬夜。熬夜的人叫 DBA,他的终极梦想是失业——系统永不宕机,优化器永远选对。梦很美,现实很忙。对账的人换了一茬又一茬,账本越记越厚,厚到最后成了文明本身——美索不达米亚的泥板,威尼斯的复式账簿,关系模型的表,区块链的链——记账的介质换了又换,执念没变过。人类文明史,半部是记账史;数据库史,是记账史的电子版。电子版的账本,比泥板快,比纸账准,但记账的人心,和五千年前刻泥板的人心,是同一颗:怕错,怕丢,怕对不上。怕,就对了——怕,才有 ACID。ACID 是怕的形状,事务是怕的学名。学名很拗口,怕很实在。有人可以反驳:如果业务不在乎绝对正确(点赞数差几个谁在乎),凭什么付这税?回答藏在分层里:银行付全款,社交付零头,中间地带按需付款——ACID 不是宗教,是菜单;菜单的价值,在于点菜的人知道每道菜的价格。怕,就点全套;不怕,就点白开水。最怕的是不知道自己怕不怕——稀里糊涂点了全套,白花钱;稀里糊涂点了白开水,丢了账。点菜的学问,就是架构的学问。
第 078 章 1990s:数据仓库、OLAP 与闪存介质驱动的列存革命
凌晨三点,分析师的查询还在跑,DBA 的电话已经被打爆。一张上百列的宽表,他只要其中两列:销售额,和日期。白天的交易库不敢动,晚上的抽数窗口越来越短,数据装进仓库之前,要清洗、要转换、要对账,装完天都快亮了。装数的队伍,和查数的队伍,抢的是同一台机器,抢的是同一段深夜。数据库却把整行读进内存——一百多列,读两列,扔九十八列,磁盘灯狂闪,查询跑了一夜。浪费的账可以细算:每行几 KB,一扫几亿行,几 TB 的 I/O 里,九成九是扔掉的列;扔掉的列,占着带宽,占着内存,占着时间。行式存储的世界里,这是日常:为在线交易设计的布局,一行躺在一起,取一行飞快;取一列,必须把整行扛回来再拆。这种浪费在交易系统里不存在——交易一次取一整行,天经地义;分析的世界反过来,一次查几列,扫几亿行。1990 年代,两个世界分家了:OLTP 归行存,OLAP 另起炉灶。分家的导火索,是一张越来越宽的表,和越来越等的分析师。等的极限,是耐心;耐心的极限,是换数据库。
星型与列
先解决“怎么摆”:分析师的查询有固定形状——按时间、按地区、按品类,把销售额加总。拉尔夫·金博尔(Ralph Kimball)给出的答案叫维度建模:把世界切成两类,事实与维度。事实是度量事件(卖了多少),维度是上下文(谁、何时、何地、何物、为何、如何)。星型模型的图纸画出来是这样:
时间维度
│
地区维度 ── 事实表(销售额/数量)── 品类维度
│
顾客维度
中心一张事实表(全是数字与外键),
外围一圈维度表(全是描述),
外键连线,形如星星。
星型的聪明在于,它把分析师最常用的动作——过滤加分组求和——翻译成最便宜的连接:事实表只存数字与键,维度表存描述,查“华东区三季度手机销售额”,先在维度表里圈定范围,再回事实表加总。圈定的范围越小,扫的事实越少;维度设计得好,查询天然带过滤。过滤之后,还可以预聚合:常用的组合提前算好存起来,查询直接读结果,毫秒返回。预聚合是空间换时间的终极形态:算一次,读一万次。圈定的艺术在于维度之纯:时间维度只管时间,地区维度只管地区,职责单一,索引好建;事实表只管数字,数字好压缩,好求和。维度建模牺牲存储效率换查询简单:维度冗余存放,事实保持苗条,空间换时间。换的账算得过来:磁盘便宜,人等不起;空间多花一点,时间省下一大截。金博尔的方法成了数据仓库建设的标准姿势,事实表与维度表,从此是分析型 schema 的普通话。普通话的另一面是,过度设计的精巧让位给星型的糙快;糙快的胜利,和每一场技术战争的胜利一样,靠的不是优雅,是够用。
再解决“怎么存”。行式存储把一行的所有列存在一起,读整行最快;分析查询通常只读一小部分列,却要扫几亿行——读一列,扛整行,I/O 全浪费在扔掉的列上。浪费的账可以量化:宽表一百列,查两列,有效 I/O 不到 2%,剩下全是垃圾搬运;数据量越大,垃圾越多,查询越慢。OLAP 负载的画像与 OLTP 恰好相反:多为读请求,写入是大批量(一次上千行),旧数据不修改,每次查询读海量数据。读多写少、不改旧账,是分析的基本盘;盘口既定,存储可以大胆取舍:写路径让位给读路径。列式存储反其道:同一列存一起,只读要的列。同列的数据长得像:地区列翻来覆去就那几个省,日期列天然有序,长得像就好压缩,一压再压,存得少,读得快。压缩是列存的意外之喜:行存里五花八门挤一团,压不出花;列存里整齐划一,压缩率翻几倍。省下的不只是磁盘,更是每次查询要扛的 I/O。2005 年的 C-Store 把列存做成读优化的关系架构:列式存储打底,内存打包处理,执行层层重叠,为读优化到极致。极致的另一面是偏科:读得越快,写得越要排队;排队的写,攒成大批量,半夜统一入库。入库的窗口,就是分析师睡觉的时间;分析师睡觉,机器干活,人机两不误。作息的默契,是 OLAP 的潜规则:白天查,晚上装,井水不犯河水。河水一犯,DBA 的电话就响。打包的意思是,内存里按列压缩存放,一次读一批;重叠的意思是,读、解压、过滤、聚合流水线并行,谁也不等谁。为读优化到极致的另一面是,为写还债:读得越快,写得越慢,债迟早要还。还债的方式,就是 LSM 那一套——读优化的列存,加上写优化的追加,两笔账,两种还法。谱系往上,有 1970 年代的列存讨论,1985 年 Copeland 与 Khoshafian 的 DSM 分解存储模型(按属性存、每行配代理键,列存的学院鼻祖);谱系往下,2016 年 Yandex 开源 ClickHouse——名字直白到像招牌:点击流加数据仓库,单进程多线程,C++ 压阵,专吃 OLAP,被字节、腾讯、快手、Uber 们奉为座上宾。座上宾的含义是,省下来的机器钱,够买好几年的授权费——开源的列存,性能是免费的午餐。列存对行存的裁决,可以借论文标题说:分析场景,列胜行。胜的代价是写入:列存追加容易、原地修改难,旧数据不动正好是 OLAP 的形状;OLTP 的频繁单点更新,在列存里是灾难。两种形状,两种引擎,井水不犯河水——犯了,就撞墙。
行存阵营的反对在当时完全理性。第一,OLTP 的天下还是行的:银行转账、机票下单、库存扣减,一次读写一整行,事务要原子,账号要一致,列存凑什么热闹?凑热闹的下场,是把最擅长的丢了,去拼最不擅长的;拼输了,交易都做不成,生意先垮。第二,列存的写是瘸腿:频繁小写、单点更新,在列存里步履维艰。瘸腿的根子,是布局决定的:同一列存一起,改一个值,整列重写;整列重写,写放大上天。分析库只读不写是前提,前提一变,优势变劣势;劣势一露,账单就到。第三,硬件会救行存:内存越来越大,全放内存不就完了?内存里的行存,扫描飞快,I/O 消失,列存的优势归零。归零的前提,是装得下;装不下,一切白搭。而数据涨得比内存快,百倍千倍地涨,内存永远在追,从没追上过。追不上的比赛,越跑差距越大。反对者赢了每一次辩论,输了数据的增长曲线:数据量涨得比内存快,百倍千倍地涨,内存永远追不上;分析的问题域越长越大,从 GB 到 TB 到 PB,行存的 I/O 浪费从“可以忍”变成“忍不起”。撞墙不是设计问题,是规模问题;规模变了,对错跟着变。变了的对错,逼着两边互相学艺:行存学列存的批量,列存学行存的事务;学到最后,界限模糊,融合成了新共识。融合的学名,叫 HTAP:混合事务与分析处理,同一套引擎,既接交易,又跑分析。分家的代价,分家的人早就列过清单:数据冗余,同一份数存两套;同步延迟,分析看到的是昨天的交易;运维复杂,两套系统两班人。HTAP 要把清单逐项勾掉:统一存储引擎,行列混存;统一计算调度,资源按需切;落盘即分析,ETL 的窗口期归零。归零的意思是,晚上不用再等装数,白天直接查当天。查当天的代价,是引擎变复杂:事务要锁,分析要扫,锁和扫抢资源,调度器当裁判。裁判不好当,当好了,一鱼两吃;当不好,两头不靠。两头不靠的意思是,事务嫌它慢,分析嫌它贵;慢和贵叠加,不如分开。分还是合,成了新一轮的站队;站队的标准,还是负载。负载的钟摆,摆向分,合就吃亏;摆向合,分就浪费。钟摆不停,站队不止;不止的站队,是数据库史的日常。日常的另一面是,没有终局:分久必合,合久必分,合分之间,全是生意。生意的本质,是负载变了;负载变了,架构就得跟着变。跟着变的,从来不只是技术,还有组织、预算、编制。一场架构变迁,牵动的是全公司的神经:DBA 要学新方言,开发要改旧查询,运维要换监控面板,老板要批新预算。预算批下来,机器到位,数据迁移,业务停摆半天;半天之后,新架构上线,旧问题解决,新问题出生。出生的问题,养大了,就是下一轮变迁的理由。理由充分,预算继续;预算继续,变迁继续。继续的尽头,是下一代架构;下一代的起点,是这一代的坑。坑填平了,路就通了;路通了,走的人多了;人多了,坑又来了。来了坑,填坑;填了坑,上路。循环往复,无穷无尽;无尽的尽头,是下一章。下一章的主角,不是行列之争,是介质本身。当存储的物理换了,所有的争论都要重来;重来的起点,是一块不会原地改写的芯片。共识的另一面是,没有银弹:行有行的地盘,列有列的疆域,地盘对了,什么都对;地盘错了,什么都错。错的代价,是推倒重来,推倒的是代码,重来的是时间。时间的单价,比机器贵得多。
闪存逼出的追加
真正的革命来自地下:存储介质换了。NAND 闪存与 NVMe 固态盘普及,随机读延迟从毫秒级暴跌到数十微秒——眨一次眼的功夫,老磁盘才找到磁道,新闪存已经读完一万次;IOPS 跃升数万倍,万倍的差距,改写了所有的假设,一度有人喊出“B 树已死”。喊早了。块的大小,决定了墙的厚度:2MB 的块,改 4KB 要擦 2MB,放大五百倍;8MB 的块,放大两千倍。放大的倍数,写在寿命里;寿命的终点,写在擦写次数里。闪存有个物理死穴:按页写入,按块擦除,不可原地覆盖——想改一个 4KB 页,要先擦掉整个 2 到 8MB 的块。擦除前必须先写,写前必须先擦,块里躺着别的数据,一起陪葬。B+ 树是原地更新的信徒:改一个键,就地重写那个节点。信徒的信仰,在磁盘时代是对的:寻道是主要成本,就地写最省事;超高并发下,随机小写如雨点,闪存翻译层(FTL)疲于奔命地回收、搬运有效页,写放大飙升,寿命哗哗地掉。信仰没变,介质变了;介质一变,信仰就成了包袱。包袱越重,跑得越慢;跑得越慢,死得越快。死的方式有两种:慢死,写放大磨掉寿命,三年变一年;急死,一次大合并卡住写入,业务超时,老板拍桌。拍桌的,比磨寿命的更疼;疼过之后,就知道换引擎。换引擎的学费,迟早要交;早交早超生,晚交多受罪。
LSM-tree 是向这面墙低头的产物,低头的姿势叫“不原地改”。改的反面,是追加:旧的不动,新的另起炉灶,炉灶多了,后台再归拢。归拢的时机,写在水位线里;水位一到,合并启动。启动的频率,写在负载里;负载越高,合得越勤。勤与不勤之间,是写放大与读放大的跷跷板。核心思想一句话:所有写入都追加到新位置,后台再批量整理。内存表(MemTable)扛住突发写入:来多少,接多少,接不下了,打包刷盘。刷盘的时机,写在水位里;水位一到,整块落盘,落盘即有序,有序即不可变。不可变的文件,读起来放心:读一半,不会变;变的那份,在下一批里躺着。躺着的旧版,等合并时再算账。文件一批接一批,只追加,不修改;旧的不删,新的照写,新旧并存,等合并算总账。后台合并(Compaction)多轮归并,小文件并成大文件,大文件并成更大文件,旧版本被覆盖,新版本留下来。留下的,是最新的真相;覆盖的,是过期的历史。历史不会删除,只会被覆盖;覆盖的厚度,就是 compaction 的深度。深度的另一面,是删除的难度:覆盖之前,旧版一直在;一直在,就删不掉。删不掉的旧版,就是下一节主权注的主角——墓碑立在那里,尸体躺在底下,等合并来收。收尸的车,叫 Compaction;车来的快慢,法律说了不算,负载说了算。负载说,忙的时候别合,等闲了再说;法律说,现在就要删干净。一个说等,一个说现在;等的代价是违法,现在的代价是停机。停机与违法之间,是运维每天的选择题;选择题没有标准答案,只有当天的 KPI。KPI 的上面,是老板;老板的上面,是董事会;董事会的上面,是股价。股价的下面,压着删除请求;请求的下面,是墓碑;墓碑的下面,是还没被覆盖的旧数据。一层压一层,压到最底,是物理。物理不认 KPI,不认董事会,不认股价;物理只认擦写次数,认块大小,认延迟。认不清物理的,交学费;交不起学费的,出局——出局的名单每年更新,里面有巨头,也有昨天还风光的明星。明星陨落的原因,一层层写在财报、架构与物理里,最后写在元素周期表里:那里没有“将就”这个元素,只有规律,而规律面前谁都得低头。不可变是 LSM 的人格:文件一旦落盘,只读不写,谁也不许改;改的欲望,留给下一批文件。不变的好处是,并发不用锁:读旧文件,写新文件,互不干扰;合并是唯一的写者,写完原子切换。交接班的瞬间,旧文件退休,新文件上岗,不丢一笔账。不变还有第二个好处:旧版本天然保留,并发读看到的永远是一致的快照,读写不打架。原子切换的瞬间,旧文件退休,新文件上岗,交接班不丢一笔账。布隆过滤器是门卫:查一个键,先问门卫在哪个文件,门卫说没有,就不进门,省掉九成无效 I/O。门卫偶尔认错人(误报),认错的代价是多开一次门;不开门的代价,是漏掉数据。两害相权,门卫的误报率调得极低,低到可以忽略。写入路径上,随机小写先攒成内存里的有序,再一次性刷成盘上的顺序大块;随机的债,在内存里还清,盘上只见顺序。顺序的代价后置到合并:合并时重写,写了又合,写放大卷土重来。但合并的写是顺序大块写,正中闪存下怀;随机的写是闪存死穴,顺序的写是闪存蜜糖。蜜糖虽甜,也有热量:写放大的账,算在介质寿命与系统能耗上,能耗的另一面是碳。碳的账单,先欠着。写入路径画出来是这样:
写请求 ──▶ 内存表(MemTable) ──满──▶ 刷盘
▼
有序不可变文件(SSTable)
一批又一批,只追加
▼
后台合并(Compaction)
多轮归并,旧版被覆盖
读请求 ──▶ 先查内存,再查文件(布隆过滤器跳过无关文件)
内存缓冲扛住突发,刷盘全是顺序大块,后台合并摊薄代价。布隆过滤器是门卫:文件里有没有这个键,先问门卫,没有就不开门,省掉九成无效 I/O。门卫偶尔认错人,把没有说成有,多开一次门;多开的代价,是一次白跑。白跑的概率,压得极低,低到可以忽略。忽略的前提,是门卫便宜:一张小小的位图,换掉整文件的读取。便宜的门卫,是 LSM 的标配;没有门卫的 LSM,读放大顶不住。合并的代价是写放大:合并本身也要写,写了又合,合了又写;写放大的账,算在介质寿命与系统能耗上,能耗的另一面是碳。碳的账单,先欠着。LSM 的三笔账,写、读、空间,顾此失彼:写优化了(顺序追加),读就得多翻几层(内存一份,各层文件各一份);合并勤了,读得快,写放大涨;合并懒了,写放大跌,读得慢,空间还被旧版本占着。三者不可兼得,调优就是选边站。站哪边,看负载:写多读少,站写;读多写少,站读;空间贵,勤合并。没有最优解,只有最配解。最配的意思是,配今天的负载,不是配明天的理想;理想会变,负载也会变,配好的参数,过半年就得重调。重调是常态,不调是懒惰;懒惰的代价,写在慢查询里。但这笔账比 B+ 树在闪存上的账便宜——顺序大块写,正中闪存下怀;随机小写,正中闪存死穴。存储老兵的总结最为刻薄也最为准确:每一次技术跃进,本质上都在向底层硬件低头。低头的对象从磁盘臂变成 NAND 块,姿势从寻道优化变成顺序追加,变的永远是上层,不变的是物理。物理不会让步,让步的永远是软件;软件不让步,就被淘汰。淘汰的名单很长,从 B 树到行存,名字一个个划掉,划掉的理由都一样:没跟上介质。跟上介质的,活下来;活下来的,叫主流。
主权注:数据归谁
正文的故事讲到这里,存储的账似乎算完了:读用列存,写用追加,硬件点头,软件跟上。但 2018 年之后,另一本账杀了进来,记账的不是工程师,是立法者。欧盟《通用数据保护条例》(GDPR)2018 年生效,第 17 条写下“被遗忘权”(删除权):数据主体有权要求彻底删除关于自己的个人数据。彻底的意思是,物理上不存在,不是标个记号。与此同时,2020 年 7 月,欧盟法院 Schrems II 判决宣布欧美“隐私盾”协议对跨大西洋传输无效:第三国必须提供与欧盟同等的保护水平,否则数据不许出境。多国跟进:国民敏感数据不得物理出境,云服务商的跨可用区全局分布式复制,被法律边境迎头拦截。数据的流动,第一次撞上主权的墙;墙的另一边,是工程师们用了二十年建成的全球复制体系。
撞得最疼的,是删除。法律说的“彻底清除”,在 LSM-tree 的世界里不存在。LSM 不原地改,删除不是擦掉,而是追加一条“墓碑”(Tombstone)标记:此键已死,查询时跳过。物理条目原样躺在 SSTable 里,躺到下一次大合并(Compaction)才被覆盖;合并的周期以天周计,冷备份里的副本以年计。三副本、不可变日志、冷备份,每一层都在说同一句话:删,只是记下来要删;真正的消失,要等。2023 年 ACM 的论文把这道难题钉死在学术记录上:墓碑保留物理条目,增加空间放大;及时持久的删除,在 LSM 引擎里是个未解的工程问题。法条要的是“现在就没有”,引擎给的是“以后就没有”。“以后”的长度,律师不接受。
对撞的本质,是两套时间观的互斥。法律的时间是宣告式的:判决一下,状态即变,权利即实现;工程的时间是渐进式的:标记先行,合并随后,覆盖最后。宣告式要求原子性,渐进式只保证最终性。被遗忘权卡在中间:用户点下删除,法律认为此刻已无数据;工程师知道,数据躺在三个副本、两份冷备、一堆墓碑里,要等几轮合并才咽气。咽气之前,一次磁盘镜像取证,死人复活。复活的不是数据,是官司。
这场对撞没有赢家,只有账单。云厂商的账单是主权合规部:数据驻留区,一个国家一个机房,机房之间不许直连;区域复制禁令,昨天的全球同步,今天的分区隔离;删除证明流程,用户一点删除,工单转三道手,法务确认、技术执行、审计留痕。每一项都是成本,成本叠成本,报价单越来越厚;用户的账单是等待:删除请求提交,收到“已处理”回执,物理覆盖发生在几周后。几周里,数据躺在墓碑底下,谁都能挖出来——挖出来的,叫取证。回执与现实之间,隔着 Compaction 的周期;合并越勤,删得越快,写得越累。立法的账单是执行难:罚单开得出去,比特删不干净,删不干净等于白罚。白罚的罚单,开一张,公信力掉一格。白罚的尴尬,逼出了一批折中:加密删除(密钥一毁,密文成砖,等于删了)、删除证明(密码学证明“已不可读”,代替“已不存在”,2026 年已有数据主体拿到这样的证明)。折中是双方的台阶:法律拿到可验证的承诺,工程保住追加的架构。但台阶终究是台阶,不是地面——“不可读”不等于“不存在”,“证明”不等于“物理消失”。删了源文档,嵌入向量还在;删了向量,备份还在。每一层删除,都漏掉下一层。抽象泄漏的经典定义,就发生在这里:上层承诺的抽象(彻底删除),被下层的现实(追加式存储)捅穿。捅穿的地方,漏出来的是信任。
主权注的结语必须诚实:合规边界正在成为与 I/O 延迟、网络分区并列的第三主导约束。数据存在哪里、能传到哪里、删了算不算删,从运维细节上升为架构前提。架构师画图之前,先问律师:数据能不能出境,存哪里算合规,删了怎么证明。律师点头之前,先看地图:地图上有国境线,国境线两边,是两套删除定义、两套驻留要求、两套罚单金额。看完地图,再看架构图;架构图上的每一条跨国箭头,都要配一张合规说明书。定义的差异,就是成本;成本的差异,就是竞争力。全球复制的旧梦,在主权的墙面前,碎成了区域云。碎片的每一块,都要单独合规;合规的每一项,都要单独付费。付费的终点,是数据的巴尔干化——一张网,碎成几十张,每张有自己的墙,墙内有自己的删法。墙内的删法各不相同,合规成了架构的第一约束。
回头看,卷七的约束在本章结成第一环:外存随机 I/O 的物理延迟。延迟是存储世界唯一的硬通货,别的都可以谈,延迟没得谈;谈不下来的,只能绕开。列存绕开读放大的墙,追加绕开原地改的墙,主权注绕不开墙,于是把墙写进合同。行存撞墙是随机读太多,闪存逼追加是随机写太贵,LSM 的全部设计就是把随机变成顺序。变的戏法万千,不变的只有物理:磁头要寻道,闪存要擦块,延迟写在介质里,谁都绕不过。绕不过就顺着来——顺序写、批量读、后台合,每一步都在顺物理的毛捋。顺毛捋的代价是复杂度搬家:从介质搬到内存,从前台搬到后台,从写时搬到合并时;搬家的终点是账单转移——介质的账变成算力的账、内存的账、电费的账。账单会转移,物理不会。物理是最后的甲方,永远是对的,也不讲道理;把不讲道理的物理翻译成讲道理的接口,是乙方的活,翻译的保真度决定上层的幸福,幸福的代价写在翻译层的复杂度里。
历史至此可以收束成一句有主语、可被反驳的断言:数据仓库的四十年,是一部存储形状向查询形状靠拢、再向介质形状低头的历史——行存输给列存,因为查询只读几列;B+ 树让位 LSM,因为闪存不许原地改;而主权注证明,还有第三种形状正在成形:合规的形状。可反驳的路标同样清楚:找出一套长期稳定承载主流分析负载、行存不改列存、B+ 树不改 LSM、且无视数据驻留与删除权要求却依然高速增长的商用数据系统,断言即破。每一次"形状胜利",都是约束换了考官:行存赢过,考官是事务;列存赢了,考官换成分析;LSM 赢了,考官换成闪存;合规正在赢,考官换成法律。考官越换越多,答案就得重写,重写的人还是那批熬夜的人。停歇的那一天,要么物理变了,要么人性变了;两样都没变,所以重写继续。
第 079 章 2000:CAP 定理与分布式折衷的宿命
2000 年的一场技术演讲上,埃里克·布鲁尔(Eric Brewer)抛出一道选择题:一致性、可用性、分区容忍性,一个分布式数据系统,最多能同时要几个?台下坐的是互联网跑马圈地的年代里最自信的一批工程师:门户、电商、搜索,家家宣称自己的系统又快又准又不倒。布鲁尔的回答是:不行。最多两个。台下先是安静,随后是经典反应:举手,质疑,举反例。反例一个个被摆上台面:加机器行不行?加带宽行不行?加钱行不行?布鲁尔的回答始终如一:加什么都不行,这是数学,不是工程。数学的意思是,与预算无关,与决心无关,只与可能有关;不可能的事,钱越多,浪费越多。浪费的学费,交了也白交,白交的每一分,都写着“早知如此”。早知的“如此”,就是 CAP 的三选二——不,是二选一。这个回答在当时近乎挑衅——一个定理说“不可能全都要”,等于给全行业泼冷水。冷水的价值,两年后才兑现:2002 年,吉尔伯特(Seth Gilbert)与林奇(Nancy Lynch)给出严格数学证明,猜想升格为定理。从此,分布式系统的每一次架构评审,都要先回答这道题:分区来了,你保谁?答不上来的,评审不通过;答了的,负责到底。
两扇门与一道墙
CAP 的三个词需要先精确定义,因为误读大多从定义松动开始。一致性:所有节点在同一时刻看到的数据完全相同,写完马上读,读到的必是最新——“最新”是硬指标,差一秒都不行。可用性:每一个请求都能收到非错误的响应——注意,只保证有答复,不保证答复是最新的;答错了不算可用,答慢了算,答旧了也算。分区容忍性:节点之间的网络断了,系统照常运转——照常的意思是,该读读,该写写,仿佛没断。仿佛二字,是全部的玄机:仿佛没断,其实断了;断了还装没断,装的代价,就是 C 与 A 之间的取舍。理解定理的最快方式,是想象两台服务器分处一条断裂的网线两侧:允许两边各自接受写入,读到的就是两份不同的数据,一致性没了;不允许任何一边写入,写请求石沉大海,可用性没了。思想实验的残酷在于,它没有技术细节可争:不断网,一切好说;网一断,二选一。网线会不会断?会。什么时候断?不知道。不知道什么时候断,意味着架构设计时必须假设它随时会断。随时会断的假设,是分布式与单机的分水岭:单机假设网不断,分布式假设网必断。分水岭的两边,是两种世界观:单机的世界,故障是例外;分布式的世界,故障是日常。例外可以祈祷不发生,日常只能做准备;准备的名字,叫预案。鱼与熊掌,不可兼得——但兼不得的从来不是任意两样,断点永远在分区发生的那一刻:一致与可用只能保一个。
证明的思路可以在半页纸上讲完。假设系统同时要三者:网络一切两半,客户端给左半写新值,给右半读旧值。要一致,右半必须等左半的消息;消息过不来(分区),要么无限等(可用性没了——请求无响应,用户看转圈),要么先回旧值(一致性没了——读到脏数据,用户看到错账)。等的代价写在用户体验里:转圈超过三秒,用户骂街;转圈超过三十秒,用户流失。脏数据的代价写在账本里:读错一次,信任崩一次;信任崩了,用户用脚投票。等,还是不等,就是全部的证明:等的代价是停服,不等的代价是撒谎。三者不可兼得,不是因为工程师不够聪明,是因为信息传不过去——光速与断线不讲道理,道理只能向物理低头。2002 年的证明,把 2000 年的直觉钉成了数学:不是“很难”,是“不可能”。直觉与数学之间,隔着证明;证明的价值,在于终结争论——直觉可以被质疑,数学不行。不行就是不行,没有例外,没有“但是”。不可能的意思是,别试了;试的每一分钱,都是学费;学的每一课,都叫 CAP。
猜想的来历值得一笔。1999 年,布鲁尔与福克斯(Armando Fox)合作写下 Harvest(收获)与 Yield(产出),讨论互联网服务在故障下的取舍;2000 年的演讲是这套思考的结晶。当时的语境是:单机三块天花板——性能(CPU 核数、磁盘 IOPS 有数)、可用性(硬件会老化、机房会断网)、扩展性(小型机贵得离谱,加机器才是正道)——逼所有人上分布式。上分布式的第一课,就是这道选择题。定理的残酷在于,它不解决任何问题,只划定边界:在边界里,怎么选都是对的;想跨出边界,门都没有。边界的价值,恰恰在于它终结了争论:从此没人再问“能不能三个全要”,只问“分区来了保谁”。问法变了,架构评审会开得快了;开得快的会,省下的时间,拿去还分区的债。
不是三选二
流传最广的误读,是把 CAP 念成“三选二”——仿佛架构师开会时可以从容地圈掉一个,剩下两个打包带走。真相恰恰相反:分区容忍性不是可选项。在分布式系统里,问题从来不是网络会不会分区——它一定会,只是什么时候,以什么方式。网线会被挖断,交换机会故障,机房会失联。P 是必选题:分布式系统没有弃选 P 的权利,只能接受它。真正的选择题只有一个:分区发生时,保一致(CP),还是保可用(AP)?CA 只存在于单机房、单网络的单体世界;一旦跨机房、跨网络,CA 自动作废,作废得无声无息,作废到出事才知道。这不是三选二,是二选一;二选一的另一面是,选之前,先承认分区一定来。承认的代价是,所有“永不断网”的架构假设一夜作废;作废的假设里,包括整整一代中间件的设计前提。
CP 与 AP 的站队史,就是互联网的产品史。CP 派宁可停服,不给脏数据:银行转账、库存扣减、订单支付,少一分不行,多一分不认;停服的底线是,钱不能错,错了银行赔,赔了上新闻,上了新闻,行长下课——ZooKeeper 宁可拒绝服务,也要保证所有节点看到同一份配置;etcd、HBase 同理。停服的底气是,钱的事不能错,错一笔,银行赔不起;赔不起的事,宁可不干。AP 派宁可给旧数据,不让服务停:社交动态晚几秒,日志晚几分钟,CDN 给个旧版本,用户毫无感知;感知的底线是,能打开,慢点无所谓,旧点无所谓,崩了不行——Cassandra、DynamoDB、Eureka 照单全收。照单全收的底气是,面的事不能停,停一分钟,流失一波用户;流失的用户,回不来。选哪派,看业务怕什么:怕错账的选 CP,怕宕机的选 AP。怕错账的典型是钱:银行转账必须强一致,到账短信可以晚,但账不能错;错一笔,对账对到天亮。怕宕机的典型是面子:微博打不开是事故,微博晚几秒是日常;事故要写报告,日常不用。钱与面子的账本不同,架构自然不同;账本相同的,架构自然趋同——银行都用 CP,社交都用 AP,不约而同。
ACID 与 BASE 的对照,是同一道题的学院版与江湖版。ACID 要原子、一致、隔离、持久,事务要么全成,要么全不成,银行用了几十年;几十年的意思,是几代工程师的青春,几代审计的签字,几代深夜的对账。BASE 要基本可用、软状态、最终一致,2000 年前后由 eBay 架构师丹·普里切特(Dan Pritchett)总结成形。基本可用的意思是,故障时允许牺牲非核心功能:大促时关掉评论,保住下单与支付。降级是分级的:一级关非核心(商品评价没了),二级简化流程(只剩默认地址),三级直接排队(给个预计等待时间)。分级的学问在于,先砍不疼的,再砍疼的,最后砍了排队——排队是最体面的拒绝:不说不行,说等一会。下单与支付的底线,用两个数字量:恢复要多快,最多丢多少。核心系统的标配是秒级恢复、零丢失——数字写在合同里,合同写进罚则里。关评论的底气是,评论晚一天没人死,下单卡一分钟全网骂。软状态的意思是,允许数据存在中间态:支付中、退款中、发货中,单子在路上,状态在中间;中间态是诚实的——钱在飞,没落地,说在飞,不说到了。最终一致的意思是,不要求此时此刻一致,只要求最终一致:银行转账“两小时内到账”,微博“几秒后可见”。秒杀的库存是最终一致的极限考场:百万人抢同一件,超卖一件就是事故。解法是预扣库存:先在缓存里原子减一,减完再说,减没了,后面的排队。原子的意思是,同一毫秒的一万个请求,减出来的数不重不漏;重了超卖,漏了少卖,都不行。缓存与数据库之间,用消息队列异步对账,主库管写,从库管读,读写分离各干各的;对不上的,定时扫出来,补偿修正。修正的意思是,错了认,认了改,改了接着卖。认错的姿势,叫乐观锁:改之前先看版本号,对上了才写,对不上说明有人先改了,重试。重试的代价是延迟,延迟的上限,写在超时里。超时的另一面,是雪崩:一个节点慢了,拖住一串,拖住的全超时,全超时的全重试,重试的洪峰,反过来压垮健康的节点。压垮的链条,叫雪崩;雪崩的起点,往往是一个不起眼的慢查询。大促的当晚,三座大山同时压顶:百万级的瞬时并发,一秒售罄的秒杀,单点故障引发的连锁反应。单体架构在这三座大山面前,连接池先耗尽,缓存接着穿透,分布式事务的账本对不上。每一座山的背后,都是 CAP 的影子:并发要可用,库存要一致,分区一来,只能二选一。大促的每一秒,都是 CAP 的现场直播。两小时与几秒,写的是忍耐度;忍耐度写进 SLA,SLA 写进合同,合同写进钱。钱的另一面是罚则:超时一分钟,赔多少;丢一笔,赔多少。罚则写得越细,承诺越不敢乱许;不敢乱许的承诺,才是真承诺。真承诺的代价,是架构师天天盯着监控;监控的屏幕,亮着全公司的命。BASE 不是放弃正确,是把正确的期限放宽:从“现在”放宽到“最终”。放宽的代价是,用户要等;等待的上限,写在体验里——两小时能忍,两天不能忍。忍的限度,就是 BASE 的边界;边界之外,回到 ACID。
一致性本身是一条光谱,从最强到最弱,档档明码标价。最强的是线性一致:读写如单机,外在表现与单副本无异,写完马上读,读到的必是最新,读到新的之后,再也读不到旧的。代价是延迟高、吞吐低,一旦分区,系统直接不可用——强一致的账单,每笔都写在等待上。然后是顺序一致:全局有个统一顺序,但未必是真实时间顺序;因果一致:有因果的不能乱序,回帖不能跑到帖子前面,无关的两条动态谁先谁后无所谓;最弱是最终一致:停更之后,终将一致,至于多久,看网络的心情。光谱的每一档,都是延迟、可用、正确之间的不同标价。标价的规律只有一条:越强越贵。贵的账单,银行愿意付(钱的事);便宜的账单,互联网公司抢着要(面的事)。付账的人不同,选的光谱位置自然不同;位置不同,吵架就多——强一致派看最终一致是偷工减料,最终一致派看强一致是迂腐浪费。吵架的本质,是账本不同;账本相同的,从来不吵。
没分区也要选
CAP 有个著名的盲区:它只讲分区发生时怎么办,没讲没分区时怎么办。没分区的日子占 99%,这 99% 里难道就没有折衷?有,而且天天在交税。2010 年,耶鲁大学的丹尼尔·阿巴迪(Daniel Abadi)补上另一半,提出 PACELC。缩写拆开读:PAC,是把 CAP 重写一遍——分区(P)来了,在可用(A)与一致(C)之间选;ELC,是补上的一半——平时(Else)无分区时,在延迟(L)与一致(C)之间选。强一致要多轮确认,确认要跨机房跑,跑一趟几十毫秒;要低延迟,就得放松一致,读本地、写异步,毫秒级返回。没有故障,也要交税;税的名字,叫等待。等待的账本,天天在结:每一次读本地,都是拿一致性换延迟;每一次跨机房确认,都是拿延迟换一致。换来换去,换的是用户体验:快一点,错一点;准一点,慢一点。快与准之间,没有免费项。
PACELC 把 CAP 从“故障时的二选一”扩展成“日常的二选一”,四种组合各归其位:分区时保可用、平时保延迟,是大多数互联网业务的答案;分区时保一致、平时也保一致,是银行的答案;分区时保可用、平时保一致,是折中的答案;分区时保一致、平时保延迟,是少见的答案。四种答案,没有高下,只有账本。账本不同,答案不同;答案相同,账本一定相同。互联网的主流答案早就写在实践里:分区时选可用(A),平时选低延迟(L)——微博宁可几秒旧,不可一秒崩。旧几秒的代价是,用户看到的上条微博晚了几秒;崩一秒的代价是,用户流失了,再也不回来。旧与崩之间,互联网选旧;旧是暂时的,崩是永久的。银行反过来:分区时选一致(C),平时选一致(C),延迟再高,账不能错。错账的代价是,对账对到天亮,信任崩到谷底;延迟的代价,只是慢。慢与错之间,银行选慢;慢是体验,错是事故。没有一种架构是全都要,也没有一种架构是什么都不要,区别只在于,账单列在哪里。账单列在延迟上,用户体感慢,慢到骂街,骂完还得用;账单列在一致上,用户看到旧数据,旧到离谱,用户当笑话看;账单列在可用上,用户看到错误页,错到宕机,用户直接走人。三张账单,总要签一张;不签的那张,叫运气。运气是架构师最不该赌的东西,却是赌得最多的东西。赌赢了的,不说自己赌的,说自己设计的;赌输了的,不说设计有问题,说运气不好。运气背了所有的锅,背了所有的功。背锅的运气,总有一天会辞职;辞职的那天,就是分区来的那天。分区来的时候,运气好的被夸,运气不好的被告警叫醒;叫醒之后,第一件事是看监控,第二件事是写事故报告,第三件事是改架构。改来改去,改的还是同一道题;同一道题,每年考一次,每次都有人不及格。不及格的人,半夜被叫醒,叫醒了写报告;写完报告,继续选边。
回头看,卷七的两条约束在这里收束。外存的随机 I/O 延迟,可以靠缓存、靠批量、靠追加绕开;网络分区的不可避免性却绕不开——网线会被挖断,交换机会故障,机房会失联。CAP 的价值不是解决问题,而是终结争论:别再问“能不能全都要”。剩下的路只有一条,用 BASE 的柔软把“最终”落到实处——消息队列靠“发了就算”,下游慢慢消费;TCC 靠“预留确认”,先占坑再填土;Saga 靠“一步一补偿”,走错一步退一步;AT 靠“自动代理”,业务无侵入。每一种都是在强一致的墙上开一扇窗,代价是补偿逻辑比正向逻辑更长,重试的边界比业务的边界更难划定。
反对的声音从定理诞生那天就没停过,每一种都值得认真对待。第一种是 ACID 够用派:银行几十年跑在强一致上,为什么要妥协?答案是规模——单机装不下,也不敢把全部身家押在一台机器上;妥协不是进步,是规模逼的。第二种是 CAP 无用论:老工程师凭经验就知道鱼与熊掌不可兼得,要定理何用?答案是经验只管自己,定理能终结全队的争论。第三种最硬,是一致性原教旨:钱的事一毫秒不一致都不能忍,最终一致就是和稀泥。这个指控在银行成立,在微博不成立——是否成立,看账本,不看信仰。三种反对的分歧,根子都在业务账本不同。
历史至此可以收束成一句可反驳的断言:CAP 定理宣告“全都要”不可能,它逼每个架构师为自己的业务标价——钱重要还是面子重要,延迟重要还是正确重要。规模不到,单机够用,CAP 是别人的故事;规模到了,CAP 就是自己的命,得亲自选边、保一边,把另一边的代价写进事故预案。
可反驳的路标同样清楚:找出一套长期运行、跨越不可靠网络、同时提供强一致与永不拒绝服务、且从未经历分区的商用分布式系统,断言即破;或者证明网络分区可以被彻底消灭,定理自然作废。在那一天到来之前,CAP 是一道必答题:没有满分,只有及格——及格的标准是分区来了不断片,而不断片的背后,是平时写在预案里的每一滴汗。这套取舍代代相传:老兵带新人,新人变老兵,交接班本越厚,深夜越安稳。敬畏不是天生的,是被一次深夜的告警教出来的;它最终沉淀为一种朴素的职业习惯——先把预案写好,再去睡觉。回到开头,回到 2000 年那道永远的选择题。
第 080 章 2003—2006:Google 三架马车与工业级海量计算
2003 年,加利福尼亚州山景城,Google 的机房里有一张看不到尽头的更换工单:集群由成百上千台普通商用 PC 拼成,磁盘会磨坏,电源会掉线,内存会翻转比特,网卡会丢包——今天活着的每一台机器,明天都未必还在。运维的日常工作随之变形:故障不再是一级响应的事故,只是队列里等待处理的工单,排在前面的永远是影响面大的那几条。企业级存储供应商对这种设备状态的评价只需要一个词:不合格。他们的设备报价高出数倍,换来的是白纸黑字的可用性合同与随叫随到的驻场工程师。就在这一年,Google 的三位工程师向 ACM 操作系统原理大会(SOSP)提交的论文把这份合同的前提整个翻了过来:硬件故障不必消灭,也消灭不了,唯一理性的做法是把它当作日常环境来设计——他们的文件系统从第一行设计起,就默认磁盘明天会坏。
便宜的机器,靠不住的机器
先把对方的话说足。二十世纪九十年代以来,银行、电信、航空的关键系统跑在 IBM、Sun、EMC 的高端设备上,那是一条被反复验证的路线:冗余电源、热插拔部件、严苛的出厂老化测试,加上一纸厂商维护合同。单机故障率低到以年计,出了事有专人兜底,账单虽然贵,事故的账单更贵。对一家需要向监管机构解释每一笔账的银行,买可靠性是唯一说得出口的选择。这套逻辑在它的适用域内没有破绽,2003 年的绝大多数企业采购决策仍然站在它一边。反对廉价集群的人手里还有一张牌:软件容错的代码本身也是成本,也是 bug 的来源——把几百台机器粘成一个系统的那层软件,复杂度远超任何一台高端设备里的固件;与其养一支写分布式系统的队伍,不如把钱付给设备厂商。在分布式系统还没有成熟范式的 2003 年,这个顾虑有充足的案例支撑。
在两条企业级路线之外,还有第三条路:传统超算。顶级超算用定制的高速互联把几千颗处理器焊成一个整体,为气象模拟、核物理这类计算密集型负载而生——那里的每台节点都昂贵而可靠,互联网络吞吐以专有设计堆出极限。数据密集型负载在它面前水土不服:PB 级的数据要喂给计算节点,瓶颈卡在存储与 I/O 上,而超算最贵的恰恰是 I/O 子系统;按超算的价钱堆出 PB 级在线存储,没有一家互联网公司的账本能允许。Google 要的也不是把一台机器变快,是把一台装不下的数据摊到一千台上算完——这是两种不同的题目,需要两套不同的机器。
Google 的账本是另一副算式。网页数据的规模以指数速度增长,预算却是线性的;同样的钱,企业级设备换来十台可靠机器,普通 PC 换来一千台随时会坏的机器。只要软件能让“随时会坏”不等于“数据丢失”,一千台的容量就压倒十台。规模还悄悄改写了故障的性质:单看一台机器,磁盘损坏是概率事件,坏一次算一次事故;机器多到上千台,“任一时刻都有机器正在坏”就从概率尾部变成了确定发生的日常背景。运维的参照系随之改变——高端设备世界里的“故障”,在这里降格为一条条普通工单。这份判断写在 GFS(Google File System)论文的开头:硬件故障是常态。论文的三位作者——桑贾伊·格玛沃特(Sanjay Ghemawat)、Howard Gobioff、Shun-Tak Leung——没有把它写成口号,而是写成了一整套设计:系统的每一层都不再追求让部件不坏,只追求部件坏了之后系统照常运转。软件容错队伍的复杂度成本,Google 用一笔回收:这套软件写一次,此后每一条业务线、每一台新机器都免费复用;设备维护合同换成了故障处理的代码,代码不会要求续约。
GFS 由此做出三个与教科书相悖的决定:只用一个 Master 管全局元数据;把文件切成 64MB 的大块;放弃严格一致,改用宽松的语义。三件事单拿出来,每一件都足以让 2003 年的存储评审员皱眉。单 Master 的赌注尤其重:全网的账本押在一台机器上,它记忆着每个文件、每块副本的去向,也握着副本放置、空间回收、故障迁移的全部决定权——全局视野是它唯一而不可替代的价值,复制、负载均衡这类决策必须看得见整个集群才做得对。代价同样明白:Master 一倒,新的元数据查询无从发起。Google 的化解之道在于把它经手的流量压到最小——数据流彻底绕行之后,Master 挂掉影响的只是“查表”这一件事,重建与恢复期间,已经在跑的读写不至于停摆。随后两年,2004 年的 MapReduce 与 2006 年的 BigTable 相继发表,三篇论文后来被合称为“三驾马车”。要理解它们为什么能拉动一家 PB 级的公司,得先从那个 64MB 的块说起。
一块 64MB 的块
GFS 的分工一句话讲完:Master 管“账”,Chunkserver 管“货”。文件被切成一个个 64MB 的块(chunk),每块默认复制三份,分散存放于多台 Chunkserver;Master 手里只有元数据——文件名对应哪些块、每块的副本分别在谁那里、谁正在被谁读写。这套账本分三册:命名空间记着整棵文件树,文件表记着每个文件由哪些块组成,块表记着每块的副本此刻在谁手里;前两册持久保存,第三册靠各 Chunkserver 心跳时动态报备——机器上下线频繁,块的位置表跟着变,放在任何一台机器的磁盘上都追不上变化。客户端要读数据,先向 Master 查询块的位置,拿到答案后直连对应的 Chunkserver 取数。控制流走 Master,数据流绕过 Master,两路分离,查表的流量再大也挤占不了搬数据的带宽。这个设计让单 Master 成为可能:Master 之所以敢只部署一台,正因为它只经手元数据——一台机器的内存与网卡,装得下、扛得住一个集群的“账本”,却无论如何扛不动一个集群的“货”。
┌──────────┐ 1.块在哪? ┌───────────────────┐
│ 客户端 │ ───────────→ │ Master(只存元数据)│
└────┬─────┘ ←─────────── │ 命名空间/块→位置表 │
│ 2.位置表 └─────────┬─────────┘
│ │ 心跳与指令
│ 3.数据直连,不经过 Master ▼
┌────▼──────────────────────────────────────┐
│ Chunkserver A(主副本)│ B(副本)│ C(副本) │
│ chunk X │ chunk X │ chunk X │
└───────────────────────────────────────────┘
64MB 这个尺寸是反复权衡后的产物。块越大,元数据表越小——Master 用一台机器的内存就能装下整个集群的块索引;块越大,客户端与 Master 的交互频率越低——一次定位就能服务 64MB 的连续读写。这对 Google 的负载恰好合身:爬虫抓回的网页、生成中的索引,都是按 GB 计的大文件,以顺序读为主。代价同样清晰:一个小文件也要独占一个块的元数据,1MB 的文件在物理上留下几十 MB 的内部碎片;一个存满小文件的集群会先撑爆 Master 的内存,再让查表延迟失控。小文件派的反对由此而来:这不是通用的文件系统,是为单一负载定制的文件系统。GFS 的设计者接受这个指控——他们的集群里几乎没有小文件,通用性从来不在需求清单上。
写入路径同样只为一类负载优化。GFS 的文件被设计成以追加为主:新数据不插进旧数据中间,只接到块尾。并发追加需要一个裁决者——Master 从每块的三份副本中指定一份为主副本,向它授予一段有效的租约;租约期内,所有客户端的追加都汇到主副本,由它统一排定先后,再按定好的顺序推给另外两份副本执行。租约到期,主副本身份归还,Master 另行授予。失败重试带来一个直接的后果:同一条记录可能被追加不止一次,文件系统不做去重,把这个麻烦留给读它的应用,语义上叫 at-least-once——至少送达一次,可能不止一次。读端的日子因此多了一道工序:应用给每条记录编号,读到重复的编号便丢弃后者——文件系统省下的一致性开销,在应用层一分不少地补回来。强一致派的批评正打在这里:重复记录、并发写入的可见性差异,这些不确定性意味着每个应用都得自带去重与校验逻辑,等于把一致性这个最难的问题摊派给所有上层。GFS 的回答是算账:它服务的爬虫与索引管道里,一条记录偶尔重复的代价远小于为杜绝重复付出的全局同步代价;账算得过来,语义就可以放宽。至于银行的账本,那从来就不是它的客户。
三份副本是宽松语义下最后的保险,维持它们的是一个持续运转的循环。每台 Chunkserver 定期向 Master 心跳,报备自己持有哪些块;心跳停了,Master 无从分辨那台机器是宕机还是网络断了,一律按失联处置,其上的块立刻进入补副本队列,由健康的机器从幸存副本重新复制,把数量补回三份。补副本的调度也讲轻重缓急:只剩一份副本的块最危险,排在队列最前,其次是副本只剩两份的块,最后才轮到常规的例行补充。磁盘坏一块,集群少一份冗余;坏十块,冗余依然够用。可靠性不再由器件保证,改由副本数量与复制速度保证——廉价与可靠两条路线真正的分水岭,就在这一步。
把一个 for 循环拆到一千台机器上
数据存下了,下一步是算。重建全库索引、按天统计关键词、遍历链接图算权重——这类任务形态相同:对海量记录执行同一种简单操作,再把中间结果聚合。单机时代,这是一个 for 循环加几个小时等待;集群时代,把一个循环拆到一千台机器上,意味着任务切分、失败重试、慢节点拖尾、中间结果分发,每一项都足以让正确的算法死在工程细节里。Google 内部这类批处理任务每天数以百计,每写一个都要重造一遍容错的轮子。
2004 年,杰夫·迪恩(Jeff Dean)与格玛沃特在操作系统设计与实现大会(OSDI)发表 MapReduce,把这个共性提炼成两个函数:map 对每条记录独立处理,产出键值对;reduce 把相同键的中间结果聚合。灵感来自 Lisp 语言里存在了几十年的两个高阶函数。写程序的人只写这两个函数,切分、调度、容错、汇总全部交给运行时。词频统计是论文自带的示例,十几行代码足够说明机制的本质:
map(String 文档名, String 文档内容):
for each 单词 w in 文档内容:
EmitIntermediate(w, "1") // 每出现一次,发一个计数
reduce(String 单词, Iterator 计数列表):
total = 0
for each c in 计数列表:
total += ParseInt(c)
Emit(单词, AsString(total)) // 该词在全库的总次数
这个例子能代表一切,靠的是两条性质。其一,每条记录的 map 处理互不依赖,天生可并行,一千台机器各算各的,不需要任何锁;其二,相同键的计算彼此独立,一个词的汇总不必等其他词,reduce 侧同样并行。凡能套进这两个性质的任务,都能借这套框架免费获得千台规模的并行;套不进去的任务,框架救不了。这套抽象真正改写的是人的账本:在此之前,写出能跑在千台机器上的程序,是少数精通分布式细节的专家的专利;在此之后,会写两个函数的普通工程师就行。认知门槛从“精通容错”降到“会用框架”,海量数据处理第一次成为一项大众技能——三驾马车后来的扩散速度,一半要记在这道被削平的门槛上。GFS 与 MapReduce 从此结成固定的流水线:爬虫把网页追加进 GFS,每日的 MapReduce 作业扫过全库,产出的索引再写回 GFS 供检索服务读取;存储与计算各司其职,又互为对方的输入输出。这套流水线的样子,后来在无数公司的数据平台上重演了一遍又一遍。
执行时,输入文件从 GFS 读入并切块,一批机器各领一块执行 map,中间结果按键的哈希分区写在本地磁盘;随后 shuffle 阶段把同一键的中间结果送往同一台机器,reduce 函数在那里完成聚合,输出写回 GFS。GFS 的 64MB 块与 map 的输入分片在这里完成了第二次咬合:分片对齐块的边界,框架才知道“这块数据在哪台机器上”,就近调度才有依据——存储切块的尺寸,直接决定了计算调度的精度。map 与 reduce 之间隔着一道栅栏:全部 map 任务完成之后,reduce 才开始拉取——框架保证的时序,让程序员不必操心“算到一半的输入”。任务失败的处理也按这个粒度:某台机器上的 map 任务失联,框架在另一台持有相同输入块的机器上重跑它;reduce 任务失败,随便找台机器重跑即可,它的输入本来就来自网络。三个机制让这个流程在千台规模上跑得动。其一是就近调度:任务优先派给数据所在的机器——数据不去找计算,计算来就数据,省下的是全集群共享的网络。其二是 Combiner:map 端先把本地中间结果预聚合一遍,一百万条“the:1”在离开这台机器之前先合并成一条“the:1000000”,shuffle 的流量大幅下降;合并不挑对象但要挑运算——求和可以就地合并,求平均的分子分母必须分开传,硬合并会算出错账。其三是备份执行:整场作业接近尾声时,总有一两个任务被慢盘或坏节点拖住,运行时把剩余任务再复制一份派给空闲机器,谁先完成用谁的结果——一个落后者拖住一千台机器的局面,就这样被一份冗余化解。
MapReduce 没有引入新的计算理论,Lisp 程序员对 map 与 reduce 再熟悉不过。它的新意在于把这层古老抽象钉在了一个新地基上:输入输出都是 GFS,调度感知数据位置,容错按任务粒度重试。哈希分区还埋着一处隐患:键的分布不均时,某个高频键的全部中间结果涌向同一台 reduce 机器,别人早已收工,它还在独自聚合——整场作业的完工时间由这台机器决定。框架给了缓解的手段,比如让分区的哈希掺入随机因素把热点摊薄,但摊薄从来无法根治,数据自己的形状才是原因。这层抽象的击穿之处同样清楚——迭代式算法、需要共享状态的计算、对延迟敏感的交互查询,都塞不进“全量扫描、两阶段走完”的模具;上一轮的输出要喂给下一轮时,中间结果落盘再读回,时间都耗在磁盘上。它是一把为批处理定制的凿子,Google 用它凿出了索引,也清楚它凿不了别的。
一张会自我合并的表
第三类需求卡在文件与批处理之间:地图服务要毫秒级取出一个区块,个性化设置要实时读出用户偏好——这是随机读小数据的在线负载,批处理管道喂不了它,而它的量级依然是 PB 级、需要上千台机器。手上现成的两条路都走不通。单机数据库复制一百份,读写可以摊开,但全局索引与跨机查询没有着落——一行数据在哪台机器上、改了之后其他副本何时跟上,每一步都是新的深渊;用 GFS 加批处理凑合,随机读一条记录要翻遍大块,延迟以秒计,在线服务等不起。传统数据库的索引长在单机的磁盘上,磁头每秒的寻道次数就是整个系统的天花板;把数据库横向切开一百份,每份的复制、恢复、调度又是全新的难题。2006 年,Google 发表 BigTable,论文开篇的自我定义只有一句话:一个稀疏的、分布式的、持久化的多维排序映射。
把这句话拆开,就是一套三维坐标:行键、列键、时间戳,三者合起来定位一个值。行按行键的字典序排好;列按“列族”组织——列族必须先行创建,数量以几百计,是访问权限控制的基本单位,其下的列键几乎无限。列族先建、列键随意的分工是这套模型里最讨巧的一处:一个网站想给每张网页新增一个“页面评级”字段,不用改动任何表结构,直接往列族下写一个新列键即可——模式的演化从一次停机变更退化成一次普通的写入,海量业务快速迭代所需要的就是这种便宜。每个单元格带一个 64 位时间戳,同一格可以保留多个版本,新的排前面,旧版本按“最多保留几版”或“存活多久”的规则回收。时间戳不只是一个排序字段:在存网页的表里,同一网址每次抓取写入一个新版本,旧版本不删,历史上的每一次变化都查得到;要省空间,就把版本数调小,把存活期调短。事务支持只有一条:单行操作是原子的,跨行事务不存在。应用要么把需要一起修改的数据挤进同一行,要么自己接受多行之间暂时的不一致——BigTable 把这个选择明明白白留给上层。
经典用例就是那张存网页的 Webtable:行键不直接写 URL,而是把它反转——www.cnn.com 写成 com.cnn.www。反转之后,同一域名的所有网页在表里物理相邻,按域名扫一遍站点变成一次顺序读。稀疏是这套模型的另一半:一张行数以亿计的表,每行只在少数几个列上有值,没有值的单元格不占任何空间——网页表的列可能包括页面内容、锚文本、语言、页面评级,一行网页通常只有其中几项。局部性是被设计出来的,稀疏是免费送的。
表按行键范围切成 tablet,这是迁移与负载均衡的单元:一个 tablet 的数据涨过阈值就一分为二,某台服务器过载就把它的几个 tablet 整体搬走。tablet 的定位走一条固定的链:根表的位置记录在 Chubby 里,根表指向元数据表,元数据表再指向用户的每一个 tablet——三次查表,从任何一个客户端出发都能找到任何一块数据的家。tablet 服务器对外服务读写,master 只负责指派与均衡,数据路径照例不经过 master——GFS 定下的“账货分离”,在这里沿用。故障处置也随之同构:tablet 服务器失联,master 把它的 tablet 重新指派给别处的服务器,新服务器取出该 tablet 的预写日志重放一遍,数据就位,服务恢复;同一天里坏掉三五台机器,集群内部自愈,不需要任何人工介入。
写入永远先记预写日志(WAL),再进内存里的 MemTable——一个跳表结构的有序映射;MemTable 写满即冻结,作为一张 SSTable 刷到 GFS 上;后台周期性地把多张 SSTable 归并成更大的。删除不抹除任何字节,只写入墓碑标记,归并时才真正丢弃。落在 GFS 上这一点顺理成章:SSTable 的持久性由 GFS 的三副本负责,BigTable 自己只管 tablet 这一层的有序与合并——每一层只解决上一层没解决的问题,三驾马车在这里咬合成一台机器。
写请求 ──→ ① WAL 追加(掉电不丢)──→ ② MemTable(跳表,内存有序)
│ 写满冻结
▼
磁盘(GFS 之上) ┌───────────────────────────────┐
│ SSTable 1 SSTable 2 ... │
│ (只读、有序键值、64KB 分块) │
└────────────────┬──────────────┘
▼ 后台归并
│ 更大的 SSTable │
└── 墓碑标记的键在归并中物理清除 ───┘
SSTable 的内部是一串有序的键值对,按 64KB 分块,块索引挂在文件尾部,一次寻址定位一个块;配合布隆过滤器——一个只占少量内存的位数组,只会说“绝对不在”,不会漏掉真正存在的键——多数查询可以跳过无关的 SSTable;相邻行键做前缀压缩,公共前缀只存一次。读一个键,要合并两个视图:内存里的 MemTable 加磁盘上的多层 SSTable,谁的时间戳新用谁的,墓碑负责拦截已删的值。这套设计源自 LSM(Log-Structured Merge-tree)思想:一切修改都变成顺序追加,随机写被彻底清除。代价在读:布隆过滤器排除大部分,排除不掉的只能逐层找;后台归并与墓碑清理还要额外付出写入与空间。写路径的省,变成读放大、写放大与空间放大三处利息。B+ 树派的反对由此而来:B+ 树两三次寻道必达,读延迟确定;LSM 的读路径深浅随归并节奏波动——对读密集负载这是明确的退步,只有写密集负载才值得付这笔利息。关系派的反对更根本:没有跨行事务、没有关系代数,BigTable 算不上数据库,而应用被迫按它的形状设计行键——数据建模的复杂度从数据库移到了每个应用手里。两派在 2006 年都占据着道德高地:一边守着三十年数据库理论对一致性的承诺,一边守着关系模型对完备表达的要求。
上千台机器需要有人主持秩序,BigTable 把这件事外包给一个叫 Chubby 的分布式锁服务:五个副本内部跑 Paxos 选出主副本,客户端靠租约维持会话——会话活着,才有资格读写;租约到期前必须续租,续不上就视为失联。BigTable 用它做五件事——保证任一时刻只有一个活跃 master、存放表定位的根信息、发现新上线的 tablet 服务器、标记废弃节点、存取元数据。依赖的软肋也随之固定:Chubby 长时间不可用,BigTable 全线停摆——定位链的第一环拿不到根表位置,所有的查表都无从开始。一个为消除成千上万个单点而生的系统,头顶悬着一个被精心保护、但终究存在的单点;工程上的应对只有一个,把 Chubby 养得足够稳,稳到停摆的概率低过集群里其他所有部件。到论文发表时,这套结构已支撑 Google 内部 60 多个项目:网站分析产品把每一条访问记录写进表里,地图服务把渲染一个区块所需的全部瓦片按行键摆好,财务部门把财报数据放进同一套存储做权限隔离的查询——批处理与在线服务跑在同一张表上;MapReduce 的作业直接把 BigTable 表当作输入输出,三驾马车在产品线上并驾。
回声:从山景城到阿帕奇
三驾马车的图纸 2006 年已经画完,复制它的人不在山景城。道格·卡廷(Doug Cutting),全文检索库 Lucene 的作者、开源搜索引擎项目 Nutch 的发起人,正被与 Google 同一道墙挡着:Nutch 要抓全网、建索引,单机存不下,脚本算不动。GFS 与 MapReduce 的论文相继发表后,卡廷照着图纸复刻:照 GFS 写出分布式文件系统 HDFS,照 MapReduce 写出同名的计算框架。2006 年,这部分代码从 Nutch 分出,独立为 Hadoop 项目。山景城用三年画完的图纸,开源世界用同样的三年摆进了阿帕奇基金会的仓库——复制的时间差,比所有人预想的都短。
复刻没有停在两件套上。照着 BigTable 的图纸,开源社区随后长出了 HBase;再往后,数据仓库工具 Hive、内存计算引擎 Spark 都建在 Hadoop 这棵树上。对应关系一张表可以说清:GFS 对 HDFS,MapReduce 对 Hadoop MapReduce,BigTable 对 HBase——三篇论文的每一份机制遗产,都在开源世界找到了继任者。连债也一并继承了过来:HDFS 的单点 NameNode、HBase 对协调服务的依赖、LSM 家族的三放大,逐一重演——开源复制的是图纸,图纸里画的债不会漏掉。三篇论文加一套开源实现,把“海量数据处理”从一家公司的专有壁垒变成了公共知识:一家初创公司用几十台二手服务器加一名管理员,就能拥有与 2004 年的 Google 同构的存储与计算能力,门槛从“买得起小型机的预算”变成“会装开源软件的手艺”。这套架构能够被复制,因为它的原料——廉价 PC 与以太网——在市场上人人买得到;真正稀缺的从来不是硬件,是那份把故障当作常态来设计的账本。
债务的清单
三驾马车的债单同样清晰。第一笔是语义的债:at-least-once 的重复记录、宽松一致的并发异常,GFS 与 BigTable 都推给了应用;设计者称之为端到端原则的胜利,应用开发者的日常则是每一处读写都要写防御性代码——去重的编号、容忍乱序的合并逻辑,一个都不能少。第二笔是负载适配的债:64MB 大块让海量小文件成为灾难,Master 的元数据随文件数膨胀——GFS 的适用域被它自己的参数悄悄划定,超出的部分要用另一套系统来补。第三笔是单点的重构:GFS 的 Master 是控制流的必经之路,BigTable 头顶的 Chubby 是一致性的根锚点;三驾马车消除了上万个小单点,又亲手安放了几个必须小心供养的大单点。第四笔是三放大:LSM 把随机写换成顺序写,读放大、写放大、空间放大三笔利息随即开始计息,后台归并的每一次停顿都是还债的动静。第五笔是模型边界的债:MapReduce 的两阶段模具容不下迭代与交互,实时查询的缺口由另外的系统去填——三驾马车解决的每一个问题,都顺手划出了一片它们解决不了的新地界。
这些债在当时都算不上致命,因为三驾马车服务的对象是搜索——它容忍重复与暂时的不一致,承受得起批处理的延迟,也接受为写吞吐付出的读代价。真正不容闪失的负载在别处:购物车里的每一件商品、下单时的每一笔扣款,容不得 at-least-once 的重复,更容不得一次长时间停摆。三驾马车的答案全是“集中”:一个 Master、一张账本、一个锁服务,用中心化的秩序换工程上的可控。2007 年,亚马逊将从相反的方向逼近同一个问题——不是更严,而是更松;不是集中,而是无主:没有 Master,没有锁服务,每台机器都对等。Google 自己,也要再等几年才回头为一致性补上原子钟——用遍布机房的原子钟与 GPS 接收机把时钟的不确定性压进数据库,为跨洋交易重新立规矩。三驾马车证明了廉价机器可以组成超算级集群;哪些负载配得上这种集群、容错必须集中还是可以撒开,是后面几章的账。
本章的判断是:三驾马车真正的发明不在 GFS、MapReduce 或 BigTable 中的任何一项技术,而在一个此前没有厂商敢签字的假设——硬件可靠性可以按批次购买、按批次更换,可靠性从器件属性降格为软件统计;谁先接受这个降格,谁就拿到从 TB 跨入 PB 的钥匙,而拒绝接受的公司,无论把单机做得多么可靠,都只能在同一笔预算下看着对手多出一百倍的容量。这个判断可以被反驳——企业级容错路线在金融机房里从未输掉它的适用域,一张维护合同买到凌晨三点有人接电话,这种确定性是任何软件统计都替代不了的;也可以反过来反驳:把可靠性写成代码的队伍一旦组建,它服务过的每一条业务线都在摊薄它的成本,最终不是两种技术的竞争,而是两种成本曲线的竞争。无论站在哪一边,此后二十年数据中心的建设方向已经写下:大体上,是在为这个降格支付利息。
第 081 章 2007:Dynamo 与高可用无主系统
黑色星期五零点,促销页面的每一次刷新都换算成订单。购物车服务的数据库开始排队:写入延迟从几毫秒爬到几百毫秒,连接池占满,告警一层层响起来。值班工程师面前的选项只有两个:让顾客的“加入购物车”按钮转圈、超时、报错——顾客转身去别家;或者把服务整个停掉,等数据库缓过来——高峰的一秒不可用,结算成真金白银的流失。购物车的写入是整条交易链路的入口,这个入口在任何时刻都不能关;偏偏假日购物季的流量一年高过一年,主库的写入瓶颈一年比一年来得早。2007 年,亚马逊的工程师把这套被假日流量反复毒打的经验写成论文,系统叫 Dynamo,发表在操作系统原理大会(SOSP)上,作者栏领头的是 Giuseppe DeCandia,通讯作者是首席技术官维纳·沃格尔斯(Werner Vogels)。论文回答的问题只有一个:在机器会宕机、网络会分区的世界里,怎么让一个存储系统永远说“行”。
不能说不的一秒
先看清亚马逊当时站在什么地方。它的平台是一套服务化架构:网站由数百个服务拼装而成,购物车、库存、价格、推荐各自独立部署、互相调用,每个服务都背着一纸服务等级协议(SLA)。以购物车服务为例,口径是峰值每秒 500 次请求、99.9% 的请求必须在 300 毫秒内返回。99.9% 这个数字的苛刻要用一天的秒数来体会:一天八万六千四百秒,千分之一的超标额度摊下来只有一分多钟——这一分多钟要留给所有的抖动、发布与故障,其余八万多秒必须全部达标。百分位的讲究在于尾巴:平均耗时再好看,只要长尾上有一批请求超时,页面上就有一批顾客盯着旋转的图标。更麻烦的是连锁反应——购物车调用库存,库存调用价格,一环超时,环环排队,端到端的 300 毫秒要靠每一环都更快才兜得住。而购物车偏偏是整条链路里被翻动最勤的一本账:顾客浏览商品的每一次点击都触发一次读取,每一次添加或删除都是一次写入;整个购物季,它的流量随促销节奏一浪高过一浪,黑色星期五零点只是浪尖。
排在购物车后面的存储,是当时业界无可争议的标准答案:关系数据库加主从复制。这套架构的合理性无需论证——数据的一致性有保证,事务和恢复是成熟产品,运营团队闭着眼睛都会用;读多写少的负载,加几个从库就能横向扩展,几十年来它就是这么用的。它的软肋只有一个,平时看不出来:所有写入都挤在一台主库上,主库是整个系统写路径的单点。主库宕机,切换从库要时间,切换期间写入停摆;主库网络不可达,分区另一侧的写入只能干等。对一个允许“短暂维护”的企业系统,这些都不致命;对购物车,主库不可写的每一秒都直接折算成流失的订单。
Dynamo 的立场由此倒转:这个系统里,写入永远不能被拒绝——论文的用语是 always writable,永远可写。宁可让顾客读到几分钟前的旧购物车,也不能让“加入购物车”失败;数据的冲突不在写入时裁决,推迟到读取时再合并,行话叫读时协调。放弃写入时的强一致,换来的是任何一台机器宕机、任何一个网络分区发生,写入照常落地。一致性、可用性与分区容忍的三角在这里被明确地掰向一角:可用性与分区容忍优先,一致性降级为最终一致——分区过去、写入追平之后,各副本终将汇合到同一份状态。“最终”什么时候到,系统不承诺时刻,只承诺方向;对购物车,几秒的窗口无伤大雅,对账本,这个窗口就是漏洞。论文给自己划的定位也准确:这是一个高可用的键值存储,只做“按键读写”这一件事,不做查询、不做事务、不做关联——砍掉的能力清单,几乎和它的承诺一样长;砍得越干净,永远可写的兑现就越轻省。
这个取舍在当时招致的双重反对都值得写足。主从派的反对是:为购物车这一个服务另起炉灶,代价是整套新系统的运维、新工具链、新故障模式,而主从复制加读缓存已经解决了绝大多数问题——这是在用大炮打蚊子。这套意见的分量要从它的账本上称:主从架构服务了数据库行业几十年,工具、人才、应急手册样样齐备,任何一家公司在 2007 年选它都不需要辩护。强一致派的反对更直白:购物车是交易的前奏,版本合并出错、旧数据覆盖新数据,最终伤害的是订单的准确性;为了写入永不拒绝,把数据正确的责任外包给每一个应用,这笔账并不便宜,账本式的业务更是想都不要想。Dynamo 团队的回答写在业务的账本里:主从架构加从库扩展的是读,写路径永远只有一条,购物车的写入增长没有上限;而拒绝写入的损失当场发生且无法挽回,读到旧数据的损失多数时候根本不发生——购物车多显示一件旧商品,顾客自己会看出来;按钮报错,顾客就走了。两边损失不对称,取舍就不难做。
环上没有主人
把主从架构的困境摆全了看,复制模型其实只有三种摆法。单主复制把写入权交给一台机器,简单清晰,代价是写路径的单点;多主复制让多个数据中心各有一台主库、互相同步,写路径分摊了,主库之间的冲突回放却成了新的泥潭;Dynamo 走第三条路——无主复制,写入权彻底摊开,每台节点对等,任何一台都能受理对任何一条数据的读写。三种摆法对应三种代价:单主花钱在可用性上,多主花钱在冲突协调上,无主把钱花在每一个读写的调用方身上。Dynamo 的判断是,对购物车这样的负载,第三种最便宜。
无主的第一个问题是“数据放在哪”。传统方案里的哈希取模在这里露了怯:集群有 N 台机器,键按哈希除 N 取余分配,看着均匀,可除数一变,几乎全部余数跟着变——10 台机器扩成 11 台,原来按 10 取余落位的键,绝大多数对新除数 11 的余数都不同,等于全库搬家;缩容同理,而且业务高峰恰恰是扩容的时候,搬家本身就要占走带宽与人力。扩容对一家假日流量年年创新高的公司是常态,全量搬家不可接受。存储系统需要一个增删节点时只动一小部分数据的分配方案。
Dynamo 采用的是一致性哈希。把哈希空间想象成一个首尾相接的环:论文选用 MD5,把 128 位的哈希值铺满整个环——选它不为加密,只为它的输出在环上散得够开、够随机,像把豆子撒进均匀的沙盘;集群里的每台节点、每一条数据的键,都各自哈希到环上的一个位置。一条键属于谁?从键的位置出发顺时针走,遇到的第一个节点就是它的家。节点的增减只影响环上相邻的一段:加一台机器,它只从顺时针方向的前任手里接管一段键;撤一台,它的键顺移给后继——其余数据原地不动,扩容的搬运量从全库缩小到环上的一小段。副本的放置沿用同一规则:从键的归属节点起,顺时针再数 N-1 个后继,共 N 份,N 的建议值是 3——三份副本容得住一台机器的损失,同时损失两份的概率在工程上可以忽略。
键 K ─┐
▼
●───●───●───●───● 顺时针方向
│ 节点A 节点B 节点C │ K → A(主)
环 │ │ K → A、B、C 各存一份
●───●───●───●───● (N = 3)
▲
节点入环 = 从前任接管一段
节点离环 = 把段落顺移给后继
朴素的一致性哈希有一个现实的缺陷:节点的位置由哈希随机决定,每台机器在环上只占一段,键的分布天然有涨有落,运气差的节点分到的键明显偏多;而机器有新有旧、有强有弱,均匀的负担落在不均匀的机器上,弱机先被压垮。Dynamo 的解法是虚拟节点:每台物理机不再占环上一个点,而是拆成成百上千个“虚拟节点”均匀撒在环上。键的随机涨落被成百上千的小段摊平,任何一台机器的负载都趋近集群均值;异构问题顺手解决——新买的大机器多配几倍虚拟节点,就多扛几倍负载,新旧机器各尽其力。虚拟节点的数量是一道工程权衡:切得太少,摊平效果打折,环上的随机涨落照样透传到机器负载上;切得太多,环上的席位暴增,成员名单与路由信息跟着膨胀,每一轮闲话要传的东西变多。Dynamo 的实践是取一个中间值——每台机器几百到上千个虚拟节点,摊平收益已经吃满,元数据的膨胀还在可忽略的量级。放置副本时还有一条硬规则:顺时针数 N 个后继时跳过同一台物理机上的虚拟节点——同一份数据的三个副本必须住在三台不同的机器上,机房的电源与交换机才带不走全部冗余。
环建好了,可写性随之而来:受理写入的节点宕机,客户端换一台继续写,环上永远有节点在岗。读写请求可以打到环上的任何一台节点,受理的那台就地充当协调者——按首选列表把写入转发给 N 台副本,把读取发给 R 台并汇总应答;没有哪台机器是必经之路,协调者的角色均匀地摊在全网,任何一台宕机都不留空缺。代价也在这里埋下:同一辆购物车,两次写入可能落在不同节点,谁也不等谁——版本从此会分叉。
两个购物车的官司
无主写入的第一个直接后果是并发冲突:分区两侧的节点同时受理了对同一辆购物车的修改,网络恢复时,同一份数据出现了两个都说得通的版本。传统数据库在这里交给事务与锁,主从架构里交给唯一的写入点——它们靠“只有一个裁判”回避了问题;Dynamo 把裁判撤了,冲突就摆上桌面。系统必须回答两个问题:两个版本谁先谁后?分不出先后时听谁的?
回答第一个问题的是向量时钟。每个版本随身携带一组计数器:节点每受理一次写入,自己的计数加一,并把见过的其他节点的计数一并抄进新版本。用一个两节点的场面走一遍:购物车的数据存在节点甲,甲受理一次写入,版本一号带着计数“甲:1”;节点乙收到这个版本后再写入,新版本的计数是“甲:1、乙:1”——它完整包含了前一个版本,系统一眼断定新压旧,旧版本安全退役,这叫语法合并,机器自己就能办。分区另当别论:网络裂开两侧,甲在左侧继续写入,计数走到“甲:3”;乙在右侧也写入,计数走到“甲:1、乙:1”;恢复后两组计数各有高低、互不包含——两次写入互不知情,是真正的并发分叉。这时系统不做裁决,把所有并存的版本连同各自的向量时钟一起交给应用——语义上的对错,机器无从知晓。
有人会问:存储为什么不肯替应用把版本合了?答案藏在信息的不对称里。存储看得见字节的异同,看不见业务的含义——购物车里的两件商品该不该共存,促销的改价与顾客的改数谁优先,这些问题的答案只存在于业务逻辑里。存储硬猜一个规则(比如比时间戳),猜错时丢的是应用的数据,而且丢得无声无息;把裁决权交还给掌握语义的一方,错也错得明明白白、改也改得到位。Dynamo 的克制源于此:它深知自己不知道什么。
购物车的合并规则是论文里反复推敲的示例:两个版本取并集。顾客在手机上加了一件商品,在电脑上加了另一件,两边离线各自写入,合并时两件都要在——加法不丢。被删掉的商品则可能出问题:一侧的删除没有同步到另一侧时,合并会让它复活——删法可丢。并集规则对“加”宽容、对“删”将就,论文给出的理由是业务上说得过去:删错一件商品,顾客再删一次,成本是点一下按钮;合并丢掉一件顾客明明加过的商品,客服电话与信任的损失要贵得多。合并的时机在读:一次读取问到 R 台副本,应答的版本一致,直接返回;应答里出现多个分叉版本,读方先执行业务给的合并逻辑,再把合并后的结果写回副本——一场官司在读取的路上开庭、调解、结案,存储系统全程只做书记员。
# 应用层合并:两版本取并集(Dynamo 把裁决权交给业务)
def merge(版本甲, 版本乙):
车 = 版本甲.商品 ∪ 版本乙.商品 # 加进去的绝不能丢
# 被删的商品可能复活 —— 业务可接受的代价
return 车
冲突处理的完整谱系不止并集一种。最省事的是最后写入胜出:给每次写入打时间戳,谁的时间戳晚听谁的——简单到不用应用参与,但它把裁决托付给了物理时钟,而机器时钟靠不了这个谱:两台机器的时钟天然有偏差,网络校时本身又有延迟与回拨,“晚写”的判定可以整体出错,真正的最新数据被悄悄覆盖,丢得无声无息;在乎数据的业务不敢用。学术界后来发展出 CRDT——把合并规则直接写进数据类型的结构,让任意顺序的合并都收敛到同一结果。并集恰好天生具备这样的性质:先后合、两边合、重复合,结果都一样——这套数学保证让购物车成了 CRDT 思想最现成的例子;在 Dynamo 成文的 2007 年,它还是纸面上的理论。Dynamo 选的是第四条路:存储把版本与因果线索原样存好、如实呈现,裁决权完整地交给应用。这份克制有它的账单——每个使用方都要写自己的合并逻辑,都要回答“什么能丢、什么不能丢”;合并代码写在了业务的关键路径上,测它比测普通逻辑难一个量级:两个版本会分叉,三个版本、跨机房的分叉,组合的数目滚雪球——这笔账记在后面的清算里。
读写要过半数
无主不等于随意:一条数据 N 份副本,写要落几份才算数,读要问几台才可信,答案是可调的三个参数——N、W、R。N 是副本总数,建议 3;W 是一次写入必须确认成功的副本数;R 是一次读取必须应答的副本数。参数背后的数学是鸽巢原理:只要 W 加 R 大于 N,任意一次读的 R 台与任意一次写的 W 台必有交集——交集里的那台机器必然保有最新写入的版本,读方比对版本,就能把最新的挑出来。
亚马逊给的默认配置是 N=3、W=2、R=2:写有两台确认、读要问两台,两头兼顾。交集的算术在默认配置上一眼可明:三台副本里,写入落在任意两台,读取问任意两台,三取二加三取二,两组之间至少有一台重叠——最新写入就躺在这台机器上。三个参数又是一副可以拧的旋钮:把 W 拧到 3、R 降到 1,写入要等全部三份副本确认,慢,但读只要问一台,快——读远多于写的业务这么配;把 W 拧到 1、R 拧到 3,写入扔给一台就走人,写吞吐拉满,读要跑遍三台挑最新——写密集的采集类负载这么配;把 W 和 R 都降到 1,读写都最快,代价是鸽巢交集不复存在,一致性只剩最终一致——能容忍读旧的场景才敢这么拧。每一档都是明码标价的交易:拧大读写的可靠性,付出的是延迟;拧小延迟,付出的是读旧的窗口。档位的选择跟着业务的读写比走:读多写少的商品详情页把 W 加大,一次慢写换回回快读;写密集的行为日志把 W 减到一,先落地再说,查证的事交给批量任务。业务按自己的脾气选档,天平停在哪个刻度,由使用方自己定——数据库第一次把一致性的松紧做成了旋钮,而不是开关。
永远可写的最后一公里:节点临时失联时写入怎么办?
正常: K → A → B → C W=2,A、B 两台确认即成
A 失联:K → B → E 顺时针顺延到 E 暂存
(E 带着 hint:本属 A)
A 恢复:E 把暂存的写入推回 A,随后删除 hint
这张图里的机制叫 hinted handoff——带提示的转交。A 只是网络抖了一下,并没有死:它的写入顺延到环上下一个健康节点 E 暂存,E 记着一条提示——这份数据本该归 A;A 回到群里,E 立刻把暂存的写入推回去,自己的存储回归平常。替工的善意也有边界:E 的暂存空间与正常业务共用磁盘,A 长期不归,暂存就会堆积到挤压本地数据的程度——永远可写写在协议里,额度写在磁盘里,物理的账谁也赖不掉。对“永远可写”的承诺而言,转交机制是最后一块拼图:短命的故障不再需要任何人工介入,甚至不再需要等待——写入在故障发生的当口就已经落了地。它同时松动了一个前提,具体到默认配置上是这样:写入暂存到了环外的 E,等 A 长期不回来,最新的值就一直只在 E 与 B 手里;此刻一次读取问了 B 和 C,B 有新值,C 没有——两台的交集里没有 E,读方拿不准最新值是否到手,鸽巢原理的前提“读写都在首选的 N 台之内”已经被打破。这套放宽在论文里有自己的名字,sloppy quorum,宽松仲裁:副本凑不齐首选名单时,宁可让数据暂时落在名单之外,也不拒绝写入。松到什么程度、要不要松,与 N、W、R 一样,都是摆在参数表上的选项。
八卦、对账与修复
主从架构里,“集群里有谁”这个问题由主库一句话定夺;无主的环上,这个问题本身也得去中心化。Dynamo 用 gossip 协议——传闲话协议——回答它:每台节点每隔一小段随机的时间,随机挑一个伙伴,互换各自的成员名单,也交换“最近谁没了心跳”的怀疑。没有一台机器掌握权威名单,但名单像闲话一样在人群里传播,一轮轮传下去,全集群的认知在有限轮数内收敛到一致——收敛的速度是节点数的对数量级,百台规模的集群,几轮闲话就够。故障检测也走同一条通道:一台节点迟迟没有心跳,先被提议进“怀疑名单”,怀疑随闲话扩散;它恢复了心跳,除名的消息同样靠闲话传开——怀疑只是标记,不是判决,避免一次网络抖动就把活节点除名。这个协议对故障的耐受度也高:传播不依赖任何固定的路径,某个包丢了、某台节点暂时不在,闲话下一轮换个伙伴照样传——信息本身就在每台节点手里各存一份,丢不掉。节点的加入、退出、失联,全部走同一条闲话通道;成员发现与故障检测在这里是一件事的两面。
闲话解决“谁是成员”,反熵解决“成员手里的副本是否一致”。副本之间会因宕机、分区、转交而产生残缺,比对与补齐在后台持续进行,这套机制在论文里叫反熵(anti-entropy)——熵在这里借用热力学的比喻:放任不管的复制过程会自发地积攒不一致,反熵就是那台持续把无序拨回有序的日常对账。朴素的比对是全量抄一遍,代价不可接受;Dynamo 用 Merkle 树把比对压缩成对数级:给一段键空间里的键逐个算哈希,作为树叶,相邻的哈希再聚合出父节点,层层向上直到树根。一百万条键的树高不过二十层;两台节点各持一棵树,先比根——根相同,整段数据分毫不差,比对结束;根不同,再比下一层,一层层向下钻,最后精确定位到少数几个有差异的键区间,只传输这几个区间。上百万条键的差异核查,被压缩成几条路径的比较;对账再勤,也不会把带宽吃光。
后台对账之外还有一条快的通道。每次读取本来就要问 R 个副本、比对版本挑最新——顺手的事:发现某些副本手里的版本旧了,读方就把最新的写回去,让落后的机器当场补齐。这条叫读修复的通道只照顾热数据——被读到的数据才有修复的机会;冷数据的残缺靠后台的 Merkle 对账慢慢扫。一快一慢两条通道互为补漏:热数据天天被读,差异活不过下一次读取;冷数据没人问津,后台扫描定期巡视;转交暂存产生的不一致也逃不出这两张网——E 暂存的写入若没能及时推回,Merkle 对账迟早发现这台机器的树根对不上,把差异补齐。副本的一致性不靠某一次仪式性的同步,靠的是这两条永不停歇的日常维护;写多勤、读多懒、机器多调皮,日常维护的节奏都接得住。
代价的清单
Dynamo 的债单同样要摊开看。第一笔记在仲裁上:sloppy quorum 把席位放宽给临时替工,W+R>N 的交集保证随之失效——读到的“最新”只在替工们的世界里最新,放进全集群未必;带着旧值复活的节点还可能把旧数据重新散播出去,最终一致兑现的时刻被一再推迟。第二笔记在冲突上:并发写入没有先后,读与写同时发生时的结果不确定;向量时钟靠得住,但它的元数据随分叉增长——每多一个分叉版本,就要多背一份计数器数组,长期不合流的分叉让版本越攒越多,读一次要比较的版本清单越来越长。应用合并逻辑写错一个边界条件,丢的就是顾客的数据——最后写入胜出那类省事的捷径,丢起数据来更悄无声息。第三笔记在业务上:删掉的商品会复活、并集的合并规则每换一个业务就要重写一遍,“加法不丢、删法可丢”的宽容只在购物车这类场景里成立;放进账本,复活的记录就是重账。第四笔记在运维上:没有主库也就没有了一目了然的控制台,成员、副本、冲突的排障都要在环上追踪闲话的痕迹——去中心化买来的每一分可用性,都用排障的复杂度付过账。
这套设计没有留在论文里。Cassandra、Riak——后来开源世界与创业公司的无主代表——都直接继承了一致性哈希环、可调仲裁与 gossip 的骨架,无主复制从此成为与单主、多主并列的第三种复制模型。环上放副本的规则还顺手解决了另一件事:首选列表不必拘泥同一个机房,副本可以跨机房安置,一条链路断掉,另一个机房里还有完整的副本——多数据中心复制这件事,在环的模型里只是选点时多想一步。回头对照上一章,两条路线的分岔一目了然:Google 的三驾马车用集中的 Master 与锁服务换取全局秩序,故障被软件容错层层兜住;Dynamo 拆掉了所有中心,用环、闲话与对账让秩序从对等节点的相互作用里自己长出来。前者回答数据规模的问题,后者回答写入可用的问题,两家公司各自的业务形状,决定了各自的架构形状。
清算这笔账的最后一行,写在抽象与泄漏的主线上:强一致曾经是一层厚实的抽象——应用只管读写,看不见副本、看不见版本、看不见分区;Dynamo 主动击穿了这层抽象,把版本、分叉与合并全部泄漏给应用。泄漏换来了永远可写,也让每一个使用方被迫成为半个分布式系统工程师:不懂向量时钟的团队,调不好 N、W、R;写不出合并逻辑的业务,接不住读时协调。抽象的债从此换了债主——从存储系统转给了应用开发的每一个团队。
而一致性这件事本身,还没有结束。Dynamo 用“最终一致”换可用性,把冲突推迟到读、裁决权推给应用;同一时期,Google 的工程师正从相反的方向逼近:不放松一致性,而是用遍布机房的原子钟与 GPS 接收机把时钟不确定性压进数据库,让跨洋交易也拿到严格一致——那是 Spanner 的故事,下一章的主角。有趣的是两边对时钟的态度:Dynamo 不敢信机器的时钟,宁可让顾客的删除复活,也不把裁决交给可能说谎的时间;Spanner 干脆花大价钱把时钟造到可信,把“先后”重新收归系统。两条路线要在几年后交汇,但 2007 年的购物车不在乎未来:它的写入高峰,再也没被拒绝过。
本章的判断是:Dynamo 真正的发明不在一致性哈希环,也不在向量时钟——两者的零件都是现成的——而是一笔此前没有存储系统敢签的交易:把一致性的解释权从数据库移交给应用,赌的是工程师写一段合并逻辑的成本,低于顾客盯着超时页面流失的损失;谁接受这笔交易,谁就把“永远可写”写进了自己的服务等级协议。这笔交易可以被反驳——合并逻辑的错误比超时更隐蔽,测试它的组合复杂度让不少团队付出过惨重的学费,账本类的业务始终没能搬进来;还可以从另一头反驳:Dynamo 赢在电商这个场景,不证明它在架构上优越——换一个写入可以短暂等待的场景,主从加从库的旧架构依旧便宜、依旧够用,无主系统买下的可用性,在那些场景里是没人消费的奢侈。但电商们用脚投出的票已经落定:高峰期的写入不能说不,这条底线后来成了所有互联网存储的默认起跑线。
第 082 章 2012:Spanner:用原子钟与 GPS 夺回全球强一致
俄勒冈数据中心的天花板下多走了一路馈线:一头是架在机房外的 GPS 接收天线,另一头接着标注为时间主机的服务器;几排机柜之外,另一些机器里塞进了不依赖任何信号的原子钟——不联网、不接天线,靠自己的物理振荡走时,它的价值要在信号全部失效的最坏时刻兑现。给数据库集群配钟,这件事在此之前属于电信与航天行业的惯例,数据库工程师对时间的全部想象力止于一台 NTP 服务器。变化由一笔账逼出来:一笔广告扣费在比利时完成,一秒之后,一笔关联交易在俄勒冈开始,两笔账必须按真实时间的先后结算——先发生的先扣,后发生的后扣,次序颠倒就是错账。要给出这个次序,系统必须知道两件事各自发生在什么时刻,而两台相隔一个大西洋的机器,各自的手表差着几十毫秒,没有谁对谁错,只有谁也不知道自己错了多少。2012 年,Corbett 等人在 OSDI 会议上发表 Spanner,它的回答是先承认表永远修不准,再把“不准多少”变成一个有界的、可查询的量。本章从那笔账开始:当一致性要求对齐的对象从数据换成时间本身,分布式系统要付出什么。
先发生的账必须先结
先把正确性要求说精确。Spanner 论文给它的名字是外部一致性(external consistency):如果事务 T1 在真实时间里结束得早于事务 T2 在真实时间里开始,那么系统给 T1 的时间戳必须小于给 T2 的时间戳。注意“真实时间”四个字:它指物理世界里事件实际发生的先后,与任何节点本地的钟面读数无关。这个要求比数据库教科书的可串行化更强:可串行化只要求执行结果等价于某种串行顺序,至于排出的顺序与真实先后是否一致,它不过问——对一个并发序列,数据库可以自由挑选任何一种合法排序,挑哪种都算履行了承诺;外部一致性删掉了这份挑选的自由,排序被钉死在物理时间的先后上。两笔账各差一秒,可串行化允许系统把后发生的排在前面,只要账目自洽;外部一致性不允许,因为它知道客户的手机就握在证据旁边——这就是论文里的电话场景:你在比利时扣了费,一秒后到俄勒冈查询,电话里听到的余额必须已经包含那笔扣费。检验它的方式也因此变得日常:不看日志,看表——扣费与查询之间只隔一次电话,客户拿物理世界的时间当裁判。余额若是旧的,客户不需要懂数据库,只需要会看表。
这个性质在文献里还有另一个名字:跨地域的线性一致。线性一致要求所有观察者看到的操作顺序与真实时间一致,单机数据库靠锁的授予顺序和日志的追加顺序近似兑现它,时间戳只是日志里的编号,不需要物理含义。分布式把这件事翻了过来——数据的副本住在多台机器上,事务的参与方分散在多个机房,任何一台机器的本地顺序都无法代表全局。跨洲的尺度上,没有任何一台机器的钟够格当裁判;顺序读不出来,只能被专门制造出来。在 Spanner 之前,行业普遍的顶替方案是事后对账:系统内不保证顺序,顺序错误留给人工核对环节去修复,账目之内欠下的债,在账目之外用人力偿还。Spanner 把这笔兜底成本搬回系统之内,换成毫秒级的等待;搬动本身,是对整个行业成本账的一次重估。Spanner 制造顺序的原料,是下一节的硬件与区间。
问题在“真实时间”无法直接观测。每台机器只有自己的晶振,晶振按各自的频率走,走多久偏多少,偏了没人知道。工程界的常规解法是 NTP:服务器定期向时间源对表,把本地钟拉回去。NTP 的目标写在它的输出格式里——它只给你一个读数,从不告诉你这个读数错多少;实际部署里,漂移几十毫秒是常态,而这几十毫秒的不确定性完全隐身。每一次读表都自带一份隐含担保:担保无凭据。对时钟同步这种抽象而言,泄漏点不在偏差本身,偏差永远存在,泄漏在偏差不可见:调用方拿到一个看起来精确到微秒的读数,没有任何接口提醒它这个数可能错了三十毫秒。跨国交易恰好卡在这个盲区里——比利时与俄勒冈两台机器的读数谁大谁小,与真实先后毫无必然关系;拿钟面读数当时间戳,排序结果就是随机的,而错账是确定的。
Google 内部对这类账目的需求积压多年。广告计费的对手方分布在全球:广告主在一个洲,点击发生在另一个洲,结算落在第三个时区,账目窗口每一秒都开着,任何顺序漏洞都对应一种真实的错扣。做法之一是把所有账目汇到一个单点去排——单点有一只钟,顺序它说了算。这条路在跨洲规模上走不通:单点是延迟的瓶颈,是可用性的死穴,还在数据主权问题上是最难安放的那个节点。要保住全球分布的架构,又要拿到只有单点才能给出的确定次序,系统就必须在完全分布的机器之间,重建一个可以比较先后的时间基准。Spanner 的全部设计都从这一步出发:先造出这样一个基准,再让事务的次序挂上去。
把不准写进接口
时间基准的物理部分是两套硬件。GPS 接收机直接听卫星的授时信号,精度高,但天线和接收器都可能坏,信号可能被楼挡住;原子钟不依赖外部信号,通电就自己走,但走久了会漂。Spanner 的每个数据中心里,时间主服务器一部分带 GPS 接收器,一部分带原子钟,互相校验:GPS 好的时候原子钟做从属,GPS 失效的间隙原子钟独立扛住——因为两次校准之间的漂移率是已知且有上界的,钟在失联期间还能给出“我最多错了多少”的承诺。其余所有服务器作为从属,每 30 秒轮询一次时间主,取回时钟偏差;在两次轮询之间,偏差按每秒 200 微秒的漂移率假设增长。几个数字标出这个体系的量级:误差 ε 通常在 1 到 7 毫秒之间锯齿状波动,均值约 4 毫秒;计划口径取的上限约 7 毫秒。
ε 的锯齿形状本身是一张可以读懂的仪表。轮询刚回来的那一刻,从属钟刚对过表,区间收到最窄;此后每过一秒,漂移假设往两侧各加 200 微秒,30 秒累计 6 毫秒——正好落进实测锯齿 1 到 7 毫秒的幅子里。看一眼距上次轮询过了几秒,就能算出此刻的区间大概多宽,误差曲线是可预测的。时间主不可达时,这套数字同样给出系统的退化方式:漂移假设继续按每秒 200 微秒放宽区间,钟面读数照常可得,只是承诺越来越宽——按区间语义,这类故障的表现是变慢,没人需要说谎。按这套数字,提交延迟对轮询链路的状态是敏感的:链路抖一次,区间宽一轮,全网等待它的提交跟着长一轮。时间的健康度,从此有了读数。
GPS 卫星授时信号 本地原子钟(无信号自走)
│ │
┌────────▼────────┐ ┌────────▼────────┐
│ 时间主机(GPS) │◄─互相校验─►│ 时间主机(钟) │
└────────┬────────┘ └────────┬────────┘
│ 每 30 秒一次轮询 │
▼ ▼
┌─────────────────────────────────────────────┐
│ Spanner 服务器时钟:tt.now() → [e, l] │
│ 承诺:真实时刻 ∈ [e, l],区间宽 2ε │
│ 两次轮询之间,ε 按 200 μs/s 漂移上界增长 │
└─────────────────────────────────────────────┘
这套硬件之上叠着整个体系真正的主角:TrueTime API。它返回一个区间 [earliest, latest],系统向调用方承诺真实时刻一定落在这个区间之内,区间宽度是 2ε。接口语义的变化值得单独说透。NTP 说“现在是 12:00:00.000”,这个陈述可对可错,调用方无从判断;TrueTime 说“现在在 12:00:00.000 与 12:00:00.008 之间”,这个陈述永远为真。前者把不确定性藏进读数,后者把不确定性摊在桌面上。
为什么每台机器自己持有区间,而不是由一台超级钟向全网广播权威时刻?这个问题值得单独回答。广播方案把时间主做成了新的单点——业务查询可以分布,读时间却要回到一个中心,每次事务都添一次网络往返,中心的抖动直接变成全网的抖动。区间方案把读表变成纯本地操作,tt.now() 是一次本地函数调用,零网络开销;时间主的职责退到后台,只在每 30 秒一次的轮询里出现。本地持有还有一层含义:各服务器的 ε 由自己上一次轮询的时刻决定,同一瞬间,刚对过表的机器区间窄,轮询已过二十几秒的机器区间宽——区间描述的是每台机器自己的不确定度,全网没有一个统一的时间读数,只有一簇各自诚实、宽窄不一的区间。裁决所需的全部信息装在每台机器自己手里,这是区间语义在架构上的回报。
工程师常把 TrueTime 理解成“Google 的钟特别准”,这是误读——论文与后续澄清反复强调,钟并不保证准,单台钟可以漂、可以坏;它保证的是误差上界诚实,区间不撒谎。宁可给出一个宽而真实的区间,不给一个窄而可疑的读数。系统设计从“信任读数”改成“与不确定区间共事”,这一步转弯,比装钟本身深刻。把这套 API 概括成“给数据库装物理钟”,漏掉了签进接口里的东西:装进来的其实是钟的误差合同——区间是合同条款,ε 是合同里的免责边界,硬件只是让条款尽量有利的一笔投资。
提交之前,等一段已知的时间
有了区间,次序的裁决就有了支点。支点是 Spanner 提交协议里那条著名的规定:事务的提交时间戳取 tt.now() 的上界(即 latest);提交返回之前,再等到 tt.now() 的下界 earliest 严格大于这个时间戳为止。
# TrueTime API
tt.now() → [earliest, latest] # 区间宽 2ε,真实时刻必在区间内
tt.after(t) → 真实时刻是否已越过 t
# 读写事务的提交(简化)
s = tt.now().latest # 提交时间戳取上界
Paxos 多数派写入,记下时间戳 s
while tt.now().earliest <= s: # commit-wait:等到整个不确定
... # 区间完全越过 s
返回客户端 # 此后任何“现在开始”的事务,
# 取到的时间戳必然更大
注意等待在流程里的位置:多数派写入之后、返回客户端之前。承诺的兑现点因此被定在客户端可见的那一刻——客户端听到的“已提交”三个字,自带一次对全网的等待,谁也不必再向别处求证。等待的代价可以直接算出来。区间宽 2ε,从提交时刻等到 earliest 越过 s,最多等约 2ε;按均值 ε 约 4 毫秒计,一笔写事务在提交点上额外付出约 8 毫秒。等待的终点定在 earliest 越过 s,而非 latest 越过 s——后者只说明真实时刻可能已经过了 s,前者才说明真实时刻必然已经过了 s;外部一致性要的是必然。等待的时机同样讲究:它必须在向客户端返回之前完成,而不能转成后台。事务先返回、等待后置的方案里,客户端会在承诺兑现之前听到“已提交”,紧接着发起的下一笔交易就落进危险窗口——承诺必须是同步的,否则它保护不了紧跟着的那次读。8 毫秒放在交互系统里是一次本地盘写入的若干倍,放在跨洲链路里却只是零头;对计费事务,它是把“可能错账”变成“不可能错账”的全价。先看这笔钱买到什么,再看它为什么没有想象中贵。
它买到的是比利时与俄勒冈那笔账的次序保证。设 T1 的真实结束时刻落在其区间内,提交时间戳 s1 取的是上界,所以 s1 不早于 T1 真实结束的时刻;T1 等到自己的 earliest 越过 s1 才向客户端返回。任何在 T1 返回之后才发起的事务 T2,其真实开始时刻已经越过了 T1 的结束时刻,而 T2 的提交时间戳同样取自己区间的上界——上界不早于真实开始,真实开始又晚于 T1 的结束,链条闭合:s1 必然小于 s2。这正是外部一致性的定义,一行不等式都没有借助任何概率假设。区间承诺、取上界、等满区间,三个动作合起来,把真实时间的先后铸进了时间戳的大小关系里。
省掉等待,错账如何发生?推演一遍。设 ε 为 4 毫秒,比利时机器的钟快了 3 毫秒、俄勒冈的钟慢了 4 毫秒,两台都在各自的 ε 之内——区间承诺分毫未破。T1 在比利时真实结束于 10.004 秒,提交时间戳若按某个“更快”的方案取区间下界,得到 10.003;T2 一毫秒后在俄勒冈真实开始于 10.005,取下界只得 9.997。后发生的账拿到了更小的时间戳,按戳排序即为颠倒,向客户承诺的“先扣的先入账”就此失守。破例不需要钟坏到离谱,偏差压着上界走就够——这正是取下界的方案不能要的原因,也是那条“等待规定”承重的地方。反例里有个细节值得掂量:两台钟都在各自的 ε 之内,区间承诺分毫未违约,违约的只是建立在其上的排序方案。责任由此划清——TrueTime 兑现的是它的合同,错的是没按合同用法使用它的人;后来者踩的多数坑,都能在这条责任线的一侧找到位置。
等待实际上贵多少,取决于通信的形状。commit-wait 期间,事务要做的 Paxos 多数派通信照常进行,等待与通信是重叠的;跨组事务要走两阶段提交,预写与提交的跨机往返也填在同一段时间里。总延迟近似取两者的较大值而非相加,这是设计者省下来的那部分。单组本地事务没有这些通信可重叠,2ε 全额自付,这是代价的上限;跨洲事务的 Paxos 往返本身以数十毫秒计,叠上去的 8 毫秒只占零头。设计者的取舍因此可以理解:让最贵的等待发生在通信最多的路径上,让通信稀薄的路径付全价、但也只付 2ε。容易漏看的是提交时间戳的取法:取 latest、放弃 earliest。取上界看似吃亏,把等待拉到最长,但它是整段证明的承重梁——取上界保证标记的时刻不早于真实发生,后续事务的比较才立得住。处处取下界可以让提交快上几毫秒,代价是上一段的反例从推演变成日常。
这套授时设施的账单没有公开过单价,可以摆上桌面的是它的结构:每个数据中心一份授时硬件、一条 30 秒一轮的轮询链路、一支盯着锯齿的值班表。它的对手方成本同样结构化:错账的赔付、对账的人工、审计的追问,以及客户在电话里听到旧余额时的信任损耗。Spanner 的赌注押在前者可预算、后者不可预算;押注的前提是业务里真有“错不起”的账——广告计费直接对应 Google 的营收,恰好是。
读,不必陪着等
写事务付 2ε,读事务如果也要陪等,这套系统就只配待在实验室。读与写的这种不对称有它的道理:读的输入是一个过去的时刻,过去已经被提交固定,可以随时复述;写的输出是一个新的时刻,必须等到这个时刻对全世界都成为过去,承诺才算落地。Spanner 的读走另一条路:多版本并发控制(MVCC)给每条数据保留带时间戳的历史版本,只读事务声明读某个时间戳的快照,数据库把这个时刻之前已提交的最新版本交给它,全程不加锁、不与写竞争。旧版本不是负担,是快照读的前提——没有历史,就没有“回到过去看一眼”的能力。只读事务也不必挤在主副本上:任何一个日志追平的副本都能供读,读的吞吐随副本数横向扩展。计费业务的读写比里读占大头:报表、对账、查询都在读,快照读免锁,意味着这些负载再多也不阻塞扣费交易;读路径的容量因此与写路径解耦,各自按各自的峰值扩容。
快照读有一个必须堵住的漏洞:时间戳取了,副本可能还没追上。数据按 Paxos 状态机复制在多个副本上,某个副本对 s 时刻之前的事务一无所知,只因为它本地还没收到那些日志;这时按 s 读,读到的不是快照,是残缺。Spanner 的解法是给每个副本维护一个安全时间(safe time):该副本已确认追平的时间下界,快照读只在安全时间越过快照时间戳的副本上执行;追不上的副本,读请求要么换副本,要么等它追上。这一步省不得——论文后来的经验澄清里,绕过安全时间检查被明确列为错误用法,省下的是几毫秒,破坏的是快照语义本身:你要么读到完整的过去,要么承认自己在读现在进行时。
Paxos 组的运转规则值得停一步。一个组拥有多个副本,写入必须在过半副本落盘才算提交;过半的巧妙在于交集——任意两个多数派至少共享一个副本,所以任何两次写入至少有一台机器同时见过双方,日志顺序就不可能分叉成两个互相不知道的平行版本。这同时是对脑裂的防御:网络把组切成两半时,只有握有多数派的一半能继续写入,另一半凑不齐票数,自动静默;网络愈合后,少数派的日志向多数派看齐,看齐的速度取决于补传的带宽,追得越勤,安全时间爬得越快。副本组跨洲布置,一笔写要拿到跨洲的多数派,单次确认就是数十毫秒的行程;读则不必跨洲——快照读只需要本地副本的日志追平,安全时间替读操办了确认。写贵读便宜的部署形态,是 commit-wait 与 MVCC 各自特性的直接投影。
把写入路径拼完整:每份数据隶属于一个 Paxos 组,组内副本通过 Paxos 就日志顺序达成多数派一致,任何一个组的多数派存活,这组数据就可写可读;跨组的原子事务由两阶段提交协调,协调者的记录本身也走 Paxos 复制,协调者宕机也不阻塞恢复。主副本持有租约,在租约期内以自己的 TrueTime 区间为该组的时间权威,写请求经它定序;租约的有效性依赖与整机同样的前提——租约期内该副本的区间必须仍然诚实,漂移假设为这个前提划出时限,期限一到,组就重新选举。租约到期的组由多数派选出新的主副本,次序的权威移交,时间戳的比较规则不变。生产的检验来自 Google 自己的账本:AdWords 广告计费迁到 Spanner 之上,支撑它的 F1 广告业务数据库成为这套设计最著名的用户——全球分布、强一致、跨洲事务,三个此前两两互斥的词,被一篇 OSDI 论文钉在了一起;同行的复述给了它一个更重的定语:第一个在全球规模上兑现外部一致性的系统。这个定语的分量在于范围:承诺不分平日与峰值、不分区域与线路,任何一次跨洲提交都按同一条不等式兑现。
后来的使用者在同三个地方反复跌倒,论文与后续澄清把它们列成了清单。第一是选型误读:把 TrueTime 当成“特别准的钟”引进自己的设计,直到发现它的承诺只是区间诚实,单机钟照样漂——可以依赖的是界,不是读数。第二是抄错比较方向:提交时间戳图快取了区间下界,等待省下一半,外部一致性的不等式从此失效,上一节的反例就是为这个错误准备的。第三是省掉安全时间检查:快照读不问副本是否追平,直接按戳取数,几毫秒的检查费省下来,读到的是缺了几笔提交的残本。三个坑都挖在承重结构上:区间、上界、安全时间,拆哪一根,塌的都是整层承诺。跌倒的门槛其实不高——承重结构走样之后,系统不会当场报错,它照常运行,只是承诺悄悄缩水;这类故障最难发现,因为它没有故障的样子。清单本身还说明一件事:这三处承重结构都不起眼——区间和上界在伪码里只占两行,安全时间只是一个内部字段;反倒是“GPS 加原子钟”的硬件故事最显眼、最容易被记住。硬件只是让 ε 变小的手段,承诺的结构才是这套设计的本体;记住硬件、抄丢结构,是模仿者跌倒的共同姿势。
反对者的账本
Spanner 不是在无人区里造钟,它是在一片刚被论证过“不该这么做”的土地上动土。就在它发表前五年,Dynamo 论文给整个行业上了一课:跨洲网络的往返以数十毫秒计,写路径每次都等多数派,峰值期的电商会把请求挡在门外;结论是电商级存储应该永远可写,一致性靠事后合并。这套论证在当时无懈可击——购物车的写被拒绝,损失当场发生;读到的旧值,损失事后可以弥补。凭什么让每一次写都为真时间的承诺付费?最终一致阵营可以这样反问;Spanner 的答复藏在正确性定义里:承诺已经写进你要买的性质,不付费的写买到的是另一种产品。五年后 Spanner 的反攻并不否认其中任何一笔计算,它换了一个问题:如果你的业务是计费呢?扣费事务读到的若是旧余额,损失就不能靠事后弥补——重复扣款与投诉官司会当场到账。Dynamo 的部署目标是购物车,Spanner 的第一批生产负载是广告计费,两边都没有算错,错的是把其中一边当成全部——此后行业有了共识:可用性与一致性之争,先是业务之争,其次才是技术之争。
技术上的反击来自两个方向,都拒绝为数据库装钟。CockroachDB 的路线是混合逻辑时钟(HLC):物理时钟读数与逻辑计数器拼成一个混合读数,物理部分提供跨节点的大致单调,逻辑计数器在同一物理毫秒之内分辨先后。它的读数仍以物理钟为底,日常机房的毫秒级偏差由物理部分承担,同毫秒内的并发靠逻辑部分排出先后。创业公司拒绝装钟,另有朴素的理由:公共云上的机器不归租户所有,租户在机房架 GPS 天线与原子钟的能力基本为零;要做一个面向云用户的分布式数据库,授时硬件从第一天就不在选项里。于是不确定性的处理从硬件搬进协议——时钟异常的协调节点直接重启,重启把不确定窗口重新拉开到一个已知量级,节点短暂离队,回来后系统带着这个量级继续兑现一致性。这笔交易清晰:省下的是跨数据中心部署授时硬件的资本与运维,付出的是极端情况下更宽的不确定窗口,加上重启动作对可用性的短暂伤害。对规模不及 Google 的公司,这笔交易多半划算:机房里的钟足够同步,物理上界的激进程度往往用不上。
Calvin 的路线更彻底,它认为问题出在“让时钟参与裁决”本身:事务先经日志确定一个全局次序,再按次序在各副本执行;次序既定,执行无需任何运行时协商,时间戳不需要物理含义,副本按同一份日志重放即自然一致。故障恢复在这个模型里也跟着简化:副本从日志重放就能重建状态,不需要额外的协调。代价同样明确:事务的读写集必须预先声明,交互式的、边读边决定下一步的事务模型装不进去;次序经日志串行,裁决成本从每一次执行挪到一次日志追加,单个事务的延迟取的是日志路径的下限,换来的回报是流水排满。三条路线当年都有充实的理由,都有真实的用户;它们与 Spanner 的分歧不是对错,是对“时间误差”这个病灶的三种疗法——买硬件压小误差、用重启兜住误差、干脆取消误差的裁决权。三条路线此后各自生长,分歧从未被裁决,只是各自找到了付得起各自代价的客户;判定标准最终落在每一家自己的账本上:你的业务允许哪种误差。
还有一类反对意见不看成本表,看地图。全球复制意味着同一笔账目的副本落在多个司法辖区,而越来越多的法域要求特定数据不出境。副本的选址因此换了一种身份:从前是容量与延迟的参数,如今同时是合规参数,部署方案里 replica location 一栏写的是律师审过的条目。Spanner 类系统给出的机制是可配置的副本布局:把数据划成地理单元,每个单元的副本钉死在指定区域内,跨区只留元数据与只读镜像;地域单元、区域钉死、跨区镜像,三个机制让“数据在哪儿”第一次成为架构可以直接回答的问题。布局也有布局的账:为合规把副本钉在一个区域,该区之外的用户读这份副本就要多付一段网络距离,合规与性能在同一张配置表上讨价还价。机制解得了布局,解不了冲突:一个全球账户的转账请求落在两个都禁止数据出境的法域之间,任何副本布局都无法同时满足两边,剩下的选择只有一个——这笔业务不做,或者由法域更高的一侧说了算。工程在此处让位于政治,这不是系统的失败,是系统诚实的地方:它把“数据住在哪里、谁能动它”从一个隐含的物理事实,变成了显式的、可谈判的配置项——谈判桌的另一侧,坐的早已不再是工程师。
时间的国境线
回头看这一章的两条线索。其一是抽象与泄漏的账:NTP 用“给你一个读数”的抽象藏起了不确定性,跨国交易击穿了它,Spanner 的回应是换一种抽象——不承诺读数,只承诺区间,把泄漏从暗处挪到明处,明码标价,按 ε 收费。其二是主导约束的迁移:Dynamo 那一代的论文里,时钟只是日志里的一个字段,分布式系统的稀缺资源是磁盘与带宽;到 Spanner,时间本身成了被工程化的对象——它的精度、它的漂移率、它的不确定区间,变成了与容量、吞吐同级的系统参数,标注在部署方案里。约束没有消失,约束换了名字:2ε 的等待、7 毫秒的上界、数十毫秒的跨洲多数派,都是新名字的费率;每一代系统都在为新名字付账。
本章的断言是:Spanner 证明了强一致与全球化并不互斥,互斥的是强一致与免费——当每台机器都有诚实的误差上界时,正确的次序可以用约 8 毫秒的等待一次性买断,CAP 三角从此不再充当命运的判决,而成了一张可以签约的价目表。这个断言可以被反驳:如果业务无法容忍任何常态化的提交等待,如果 HLC 的重启兜底或 Calvin 的预排序在不装任何授时硬件的前提下给出同等的跨洲外部一致性,那么“买断”就只是特定预算下的选择,时间仍然是那堵没有被计价拆掉的墙。
第 083 章 1998—2010:搜索的工业化:倒排索引、PageRank 与分布式检索
1998 年 8 月,Sun 微系统公司的联合创始人安迪·贝克托尔海姆(Andy Bechtolsheim)开出一张十万美元的支票,收款人一栏写着“Google Inc.”——支票开出时,这家公司还不存在,没有注册,没有办公室,也没有产品。支票付给的是斯坦福校园里的一项研究:两年前的 1996 年,拉里·佩奇(Larry Page)与谢尔盖·布林(Sergey Brin)在斯坦福开始研究如何给网页排序,1998 年写成论文《The Anatomy of a Large-Scale Hypertextual Web Search Engine》。投资人的判断依据不是产品,是论文里的排名思想——按网页之间的链接关系评估每个网页的重要性。一张尚无收款方的支票,是对“网页凭什么排在前面”这个问题的第一次市场报价——金额不大,分量在标的:工业界头一次为一种排序思想本身付钱,而不是为已经跑起来的产品。本章沿这条线走完十二年:先把检索的机械骨架(倒排索引)拆开,再看排名的思想(链接投票)如何给网页定价,再看单机索引如何被切成分片、搬进集群,最后清算一场失败案例——当一整代存储系统以规模化的名义把强一致让渡出去时,被让渡的东西以什么方式回来讨债。
一张写给未注册公司的支票
支票背后的判断题值得摆在今天来答:网页凭什么排在前面。一种答案来自页面自己——看页面用了什么词、用了多少次、放在什么位置;这种排序的全部依据是页面的自述。自述型排序有一个机制上无解的漏洞:页面说什么,写页面的人就能编什么。把想要的关键词重复一千遍、藏在读者看不见的地方,排序依据就被凭空制造出来;排名的输入是自述,作弊的输入同样是自述,防守方与进攻方用的是同一支笔。这漏洞与任何一家引擎的具体实现无关,它是“依据自述排序”这个抽象自身的击穿条件——当抽象的输入可以被利益方零成本生产时,抽象的输出就不再反映它声称要反映的东西。
佩奇与布林的答案把排序的依据从页面自述换成他述:一个网页重要,是因为别的网页链接它;链接就是投票,票多者靠前。这个改动在机制上切断了作弊的免费通道——自述可以凭空编造,他述需要别人的网页真的挂出链接,制造一张假票的成本从“敲几个字”变成“控制另一个人的网页”。链接还有一层时间属性:关键词可以一夜改写,链接是站主挂在页面上的长期承诺,改写它同样要动别人的页面。更深的一层是投票的递归:并非所有选票等值,来自重要网页的链接算更大的票,而一个网页重不重要,又取决于指向它的票。定义绕了一个圈,圈必须闭合才有输出——闭合的方式是给“重要程度”找一组自洽的数值:每个数等于指向它的那些票的加权和,票的权重又恰好是那些数本身。这样的数未必存在,存在未必唯一;随机冲浪者模型把它变成一定存在、一定唯一的问题。
随机冲浪者的图像是这样的:一个冲浪者从任意网页出发,多数时候顺着当前页面的链接随机走到下一个页面,偶尔厌倦了,跳到全网随机的一个页面。走得足够久之后,他停在各个网页上的时间比例会稳定下来——不再随出发点和步数变化。这个稳定比例就是每个网页的分数:冲浪者越常停留的页面越重要,票面分量越重的页面,被路过的次数也越多——两种说法描述的是同一个稳定状态。随机跳转这一笔在模型里至关重要:没有它,一个没有出链的死角或一小圈互指的孤岛会让冲浪者永远困在里面,比例永远定不下来;加上偶尔的全网随机跳,任何页面都有被到访的正概率,稳定分布才有保证。排序问题从此变成一个可以用机器反复计算的问题——工业化的第一个条件齐了:判断标准从争论变成计算。
支票在 1998 年 8 月开出,公司在同年成立,论文在同一年发表;1996 年的斯坦福项目走完从想法到产业的最后一程,用了两年。接下来的小节按工业化的顺序展开:先有可查的账本(索引),再有账本的定价(排名),再有账本的规模(分布式),最后有账本失守的案例(默认值)。
倒着查的账本
排序之前先解决查找:全网数百亿的网页,用户给一个词,系统如何在毫秒级找出所有含这个词的页面。顺着排的账本行不通——正排结构是“文档到词”,每个文档记着它包含哪些词;按词查文档就得翻遍每一页账,翻账的时间随文档数线性增长,规模一大必然失守。检索系统的答案是倒过来记:以词为行,每行记着包含这个词的全部文档——这就是倒排索引(inverted index),一张从词到文档列表的映射表。查询不再扫描文档,而是直接走到对应的那一行;查找的成本与库的大小脱钩,词表成了所有检索的第一跳,词表自身的查找也必须快——哈希或有序结构各显其能,属于实现层的选择,机制上的要求只有一条:从词到行的跳转不能成为瓶颈。
正排(按文档记): 倒排(按词记):
文档1 → {铜线, 电报} “电报” → [1, 3, 7, …] ← posting list
文档2 → {电话, 交换机} “铜线” → [1, 4]
文档3 → {电报, 中继} “中继” → [3, 9, 12]
查询“电报 中继”:两条 posting list 求交集 → 文档3
交集遍历:两边 docID 从小到大比,
小的一边前进;相等者收入结果
每一行的文档列表叫倒排列表(posting list),列表里记的不只是文档编号。一个完整的 posting 至少带四样东西:文档 ID,回答“哪些文档有这个词”;词频,回答“这个词在该文档里出现了多少次”,供排序参考;位置,记词出现在文档的第几个位置——短语查询靠它活命,查“机器学习”时系统必须确认“机器”和“学习”紧挨着按顺序出现,只看两个词各自的出现清单分不出“机器学习”和“学习机器”;偏移量,记词在页面上的具体位置,供摘要与高亮使用。词频当相关度用有内生偏差要修:长文档的词频天然偏高,不修的话,啰嗦的页面占尽便宜——按文档长度做归一的思路由此而来,让短文档与长文档站上同一把尺。列表本身还要压缩:文档 ID 是递增的,递增序列存差值——一百零五与一百之间只差五,存“五”比存“一百零五”省得多;原始序列 [100, 105, 110, 120] 压成差值序列 [100, 5, 5, 10],整条列表的体积缩小一个可观的量级。压缩也不是越狠越好:压得越紧,查询时解压的计算越多,存储与延迟在同一个旋钮两端,工业实现取的是折中。
写入侧的形状由这个结构决定。一篇新文档进来,它包含的每个词所在的那一行都要追加一条记录——一次写入触发多行更新,行数等于文档的词汇量;检索系统的写入因此天然带批处理的味道,攒一批、合一批,比零敲碎打划算。删除同样不干脆:从若干行里精确摘除一个文档的记录代价高,常见做法是先标记、后清理,把真删除留给后台的整理。账本的新增与作废都不便宜,这份成本在单机时代如此,进了分布式时代还要再乘一层。
账本还有一副常年被忽略的保险:索引是文档集合的派生物。原文档都在,索引坏了、乱了、丢了,从原文档重建一遍就是——重建费时间,不丢数据。索引与数据因此在工程上可以分离对待:索引所在的主机随时可以整台换掉,数据另有正本。这份底气让检索系统敢做激进的内存优化,也解释了为什么索引工程的容错叙事总是围绕“重建要多久”,而不是“数据还在不在”。这本账与上一章数据库的 B 树是远亲:数据库按主键定位一行,检索按词定位一批文档,做法不同,骨子里是同一个思想——预先按某种顺序组织数据,把查找从扫描变成跳转;第七十六章的 B 树为事务而建,倒排索引为全文而建,两条线在“排序换速度”这个支点上汇合。
存放布局上,词典与列表通常分家:词表(词典)要撑住所有查询的第一跳,常驻内存;posting list 体积大,放在磁盘上按需读入。查询的典型轨迹因此是“内存一次跳转、磁盘一次读取、内存里跑交集”——毫秒预算就摊在这三步之间,哪一步慢了,哪一步就是下一个被优化的对象。顺带说清正排的下落:它没有被扔掉,只是退到了另一份工位上——查询靠倒排找到文档编号,取回文档内容、拼装结果页,用的仍是文档到词的正排账;两本账一主一辅,各有各的岗位。
工具化的落地发生在 1999 年:道格·卡廷(Doug Cutting)发布 Lucene,一个 Java 写的全文检索引擎库。它把倒排索引、posting list、压缩与查询执行打包成可嵌入的组件,各类应用拿来即可获得检索能力——库的形态意味着它不绑定任何产品,从站内搜索到企业系统,谁都能把它装进自己的进程。此后十年,Lucene 成了搜索领域被反复封装的地基;接下来两节的两场演进,都从它的边界处开始。
毫秒的算术:交集与跳表
多词查询是这套结构的日常考验。查两个词,系统取出两条 posting list,求交集;交集之外还有并集,对应“或”的查询——并集的遍历是两边轮流取小、重复者去重,比交集还简单。难点在交集的规模:热门词的列表动辄百万条,两条百万级的列表逐项两两比对,比对次数跟着百万走,毫秒的预算立刻见底。加速的支点是列表有序——两边都按文档 ID 从小到大排,比较时哪边当前的数小,哪边前进:数小的一边在对面追上来之前,中间没有任何一项可能是答案,全部可以跳过。有序把两两比对降成单边前进,这是第一层。
第二层是跳表。列表上每隔一段架一条“快车道”指针,遍历可以整段越过;当前两边的值差距悬殊时,落后的一边走快车道一次跨过一大截,接近了再退回逐项核对。快车道不是白来的:建索引时多写指针,存储多花一份,查询时少比几次——空间换时间的交易,价格写在索引体积里。列表的有序不是巧合,是建索引时按文档 ID 归位写入的直接结果;投入顺序,收获的是此后每一次交集的效率。Lucene 的实现把 posting list 切成块,块上再架两层跳表索引:交集遍历先在块间跳跃,锁定可能的块,进块后再逐项核对。三个词以上的查询依同样原理归并,先交最短的两条——中间结果越短,后续的比对越少,顺序本身就是优化。有序、前进、跳表、选短,几件小事叠在一起,毫秒级响应才从预算表上的愿望变成交付单上的现实。
这套算术解释了检索系统一个常被忽略的性质:查询快,是因为索引把代价提前付掉了。建索引时的排序、分块、架跳表、做压缩,都是查询时刻之前的支出;用户感知的“毫秒”,是工程把时间从查询现场挪到后台批量处理的结果。工业化的本质之一就是把代价从“用的时候”挪到“没人看的时候”,倒排索引是这个原理在搜索领域的完整标本。
把一次三词查询完整走一遍,机制的拼接就都看清了。用户提交“电报 中继 天线”三个词,系统先查词典:三个词各领到自己的行号;再到磁盘取回三条 posting list,解压成文档 ID 序列。交集按选短策略开跑——先交“天线”与“中继”这两条最短的,得到的中间结果再去与“电报”的长列表求交;每一轮交集里,落后的一边走快车道整段赶路,进块后逐项核对。交集得出候选文档编号,系统按词频与位置信息排出先后,再到正排账里取回文档的标题与摘要,按偏移量把命中词高亮,组装成结果页。从词典跳转到结果组装,每一环都有名字、都有预算;用户看见的只是一个词框和十行蓝字。热门词的交集结果反复被命中,缓存一层,重复的算术连跑都不必再跑。
链接是选票,票有轻重
随机冲浪者给出的分数,换成投票的语言就是 PageRank 的全部机制:链接是选票,票的分量由投票者自己的分数决定,投票者的分数又由指向它的选票决定。这个循环定义没有起点,却有一个可以被算出来的终点——稳定分布的存在保证了那组自洽的数值存在。拿三个页面走一遍迭代,循环就落地了:A 链向 B 和 C,B 只链向 C,C 只链向 A。第一轮,A 把自己的分数对半分给 B 与 C,B、C 各自把全部分数交给下一家;第二轮,拿到分数的页面再按各自的出链分发,如此往复。几轮之后三个数不再变化——B 的分最低,因为只有半张票指向它;A 与 C 互相成全,分数高且相等。循环定义在一张小图上收敛成三个具体的数,全网不过是这张小图的亿倍放大。工程上求它不必解方程:给每个页面一个初始分数,按链接关系一轮一轮分下去,分数的波动一轮比一轮小,小到阈值以下即停;不动的那组数就是答案。随机跳转在计算里同样在场:每一轮都有一部分分数不顺着链接走,而是平均撒给全网,模拟那个偶尔厌倦的冲浪者;这一笔保证迭代收敛,也等价于给每个页面一个保底——再孤僻的页面,分数也不会被清零。
分数系统里有一条天然的守恒律:分数顺着链接流动,总量不凭空增减,一个页面的份额涨了,别的页面就要让出一点。守恒律反过来就是操纵者的困境——权重不能凭空制造,只能从别处转移;刷票者想给目标页面灌权重,灌进来的每一分都要有来处,而最有分量的来处恰恰长在最难收买的页面上。这套机制没有消灭作弊,它重写了作弊的成本曲线:从“写几个字”变成“经营一整片有分量的假页面,并骗到真权重流入”。成本曲线抬到哪里,作弊的规模就退到哪里;机制与操纵的拉锯贯穿搜索此后二十年,但规则的主动权从此握在投票这一侧。
两处边界要交代清楚,免得高估了它的管辖范围。其一,PageRank 度量的是网页的全局重要性,一次具体查询还要看词的匹配:重要性是先验分,词频与位置是当场分,最终排名把两笔分合起来算——链接投票管不了“这篇是否谈了你查的词”。值得注意的是 PageRank 完全不读页面内容:它只看链接结构,一篇写了什么对分数毫无影响;重要性的本义在此接近“位置”而非“质量”——处于链接网络枢纽位置的页面得高分,至于枢纽上放着什么,是内容分析那条线的事,两条线合流才有完整的排序。其二,分数不是算一次管终身:新页面不断出生,链接不断增删,稳定分布的形状随全网变动,分数要一轮一轮滚动重算;排序不是一件成品,是一条持续运转的流水线。迭代计算对这个节奏意外友好——每一轮只需按链接关系搬运分数,不需要把全网矩阵整个装进内存,分块迭代、磁盘倒手都能跑,规模涨上去,工程跟着换挡就是。
回头看时间线:1996 年斯坦福的项目起步,1998 年论文与公司同年落地,十万美元支票随后兑现。学术判断与商业判断在同一个点上交汇——链接投票同时回答了“网页该排哪里”与“这门生意值多少钱”。排序思想的工业化自此有了燃料,下一站是规模的账单。
把一部词典切成二十册
Lucene 解决了“怎么查”,没解决“查多大”。单机索引有一条硬边界:一台机器的内存、磁盘与处理器是有限的,网页库却持续膨胀;索引大到一台机器装不下、查不动时,再精巧的单机结构都到顶。规模化的常见切法是按文档切:全库文档分成若干分片(shard),每个分片持有一份独立的倒排索引,各归一组机器。切法本身就是一笔关键决策——按文档切,每个分片自足,绝大多数查询不需要碰全网;按词切则任何一个词的列表都可能横跨多机,任何查询都要跨机器拼装。选哪种切法,决定了此后所有复杂度的形状,工业界的天平压在按文档切这一侧。
分片架构下的查询分两步走:请求同时发往所有分片,每个分片在本地跑完整的倒排检索,各自交出本地最优的前若干条;总入口把各分片的答案归并,排出全局的次序。归并模式的代价写在片数上:片越多,单片的负担越轻、写入与查询的并行度越高,但每次查询要等的小答案也越多,归并与网络的开销随片数涨——片数是把并行度与协调成本拴在一起的那个旋钮。片怎么分也有讲究:切分依据选得好,负载摊得匀;选得不好,热点全压在同一片上,别的片闲着看戏,扩容加的机器救不了设计错了的切法。数据要搬家时同样走分片这一层:加机器,把部分分片挪过去重新平衡;减机器,反着搬。分片之外还有副本(replica):同一分片复制多份,放在不同机器上;主机掉线,副本顶上,查询压力也由主副共同分摊。副本多了,新的编排问题跟着来:分片的名册谁来记、主机换人时谁拍板——集群里得有角色管这份名册,具体的选举与协调机制,是下一卷共识算法的正题。拆册、归并、冗余,三件事把检索从单机手艺变成集群工程。
2010 年前后,Elasticsearch 在 Lucene 之上把这层集群工程补齐:底层的倒排索引、posting list、跳表交集仍是 Lucene 的,外面加的是分片编排、副本调度与一套 RESTful API。REST 这层包装的分量不轻于底层算法——调用方不需要理解 Lucene 的任何内部结构,一条 HTTP 请求就能建索引、写文档、发查询;检索工程从“读懂一个检索库”降到“会发 HTTP 请求”。认知门槛的大幅下移把检索能力交给了一批从没读过信息检索论文的后端工程师:原本只有搜索公司养得起的专职团队才建得起搜索,如今任何业务的应用层都能自己嵌一个。工具剥离认知负担、向此前被挡在门外的人赋权——这条主线在 Elasticsearch 身上兑现得近乎完整。它的第一个爆款场景甚至不在网页搜索:日志与监控。把服务器日志灌进来,按关键词过滤、按时间窗切分、聚合计数出图,ELK(Elasticsearch、Logstash、Kibana)组合成了运维部门的标配;查询的形状与网页搜索不同,底层的账本仍是同一套倒排索引。据 DB-Engines 的排名,2016 年 1 月,Elasticsearch 超过 Solr——后者同样是 Lucene 的封装;这个名次变化标记的是封装与编排路线的胜出,底层的技术账,仍然都记在 Lucene 名下。
规模化的另一本账要留到下一节清算:当规模成为最高优先级,人们开始论证规模与一致不可兼得;论证的正确结论被推广成过头的结论——为了规模抛弃一致,成了整整一代存储系统的入场券。
默认值里的窟窿
2010 年前后的 NoSQL 浪潮里,强一致被当作规模化的敌人:事务慢、锁贵、跨机协调费时,互联网规模的写入仿佛天然该用“不管一致的写法”——把强一致机制整体让渡出去,一度是这一代系统的入场姿态。这场浪潮有它的道理——单机数据库在当时的规模天花板前确实无解,最终一致的系统也确实扛住了峰值;错的是把权衡做成了默认。MongoDB 是这笔账里最有教案价值的一份:它的早期版本把一组有风险的选项设成出厂缺省,风险因此落到最没有防备的那批用户头上——其中包括大量把 MongoDB 当普通数据库使用的团队,他们没有参与过性能与持久性的辩论,却承担了辩论的结果。
账目按版本排开。1.8 之前的 MongoDB 没有日志(journal),写入常驻内存,约一分钟才刷一次盘——进程崩溃,最近一分钟的“已提交”写入一起蒸发;而这一分钟在业务里并不抽象:够一笔订单写完、够一条支付回调落地,崩溃之后这些记录无影无踪,业务方手里的回执照样写着成功。1.8 补上日志,刷盘间隔缩到约 100 毫秒,丢失窗口收窄,机制没变。写入确认这一侧走得更远:客户端驱动默认不等落盘确认,调用方想要“真正写住”的回执,得自己显式调 getLastError 去问;这套默认直到 2012 年 11 月才改——驱动从此默认 w=1,至少等主节点确认。w 是一个档位旋钮:w=1 是等一个节点,w:majority 是等多数副本,数字越大,写越慢、能丢的越少;旋钮存在本身没有争议,争议在于出厂时拧在哪一格。再往后翻:带日志同步的确认(j:true)多年之后仍非缺省;等多数副本确认的 w:majority,要等到 MongoDB 5.0 才成为默认。三档确认对应三种丢失窗口:w=1 丢的是主节点刚坏掉的那一瞬,j:true 丢的是两次刷盘之间的间隙,w:majority 丢的只剩全网多数副本同时出事的那种灾难;把三档从“全都不默认”走到“多数派成为默认”,这条路的每一公里都标着年份,走完用了十年出头。时间线上还有一处同年对照值得标注:驱动默认改成 w=1 的 2012 年 11 月,正是 Spanner 论文发表、commit-wait 把“提交就等”写进协议的那一年——同一年里,一边把等待设为默认,一边才刚刚让“至少等一下”成为默认。
MongoDB 持久性默认值的演变:
1.8 之前 无 journal,约 1 分钟刷盘一次;崩溃丢“已提交”数据
1.8 补 journal,约 100ms 刷盘间隔
── 客户端默认不等落盘确认;要确认须显式 getLastError ──
2012-11 驱动默认 w=1(至少等主节点确认)
多年后 j:true(日志同步确认)仍非默认
5.0 w:majority(多数派确认)才成为默认
对照:Spanner 的 commit-wait —— 默认就等;
这里的默认 —— 能不等就不等
比时间线更要紧的是它的含义。不安全的选项本身不是罪——任何系统都有激进与保守两档,性能敏感的用户自会选激进档;问题出在把激进档设为默认,让没做选择的用户被动做了最激进的选择。调用 write 返回“成功”时,用户按常识理解为“数据已经安全”,系统此刻的承诺只是“数据到了我的内存”——抽象在这里泄漏:持久化的抽象把“写进内存”与“写进磁盘”藏在同一个“成功”背后,击穿它的是一次断电,代价是用户以为已经存好的数据。“成功”二字是接口契约里最贵的词,它到底承诺了哪一层,本该写在文档最显眼的位置;契约写得含糊,用户就会按最强的那种理解去用——理解与承诺之间的缺口,平时看不见,崩溃那天全额结算。默认值不是技术细节,是厂商替所有未表态用户做的权衡声明;把上一章的话放在这里对照格外清楚——Spanner 的默认是提交就等满不确定区间,等是承诺的一部分,这里的默认是能不等就不等,两个默认值,两种对用户的表态。教训因此有两条:比较各系统的吞吐数字之前,先对齐各自的持久性承诺——等多数派的系统每秒写一万、不等确认的系统每秒写十万,两个数字不可比,因为卖的不是同一种东西;评审一个新存储时,先读它的默认值——默认值才是厂商真实权衡的供词,文档里的选项只是菜单。
清算到根上,这个窟窿与本章前几节是同一句话的正反面。PageRank 用链接投票给网页的权威定价,前提是票难伪造;倒排索引用有序结构给毫秒响应定价,前提是列表不撒谎;Elasticsearch 用默认接口给规模化定价,前提是默认值替用户守住底线。PageRank 与 MongoDB 共享同一个骨架:都把一项本该由专家逐例判断的事,变成机器统一执行的默认——前者把重要性判断变成链接计数,后者把持久性判断变成出厂设置;前者解放了排序,后者提醒每一处做默认的地方:机器接管的每一项判断,都要有人为它的差错买单。搜索工业化的十二年,是把“可信”从一层抽象搬进另一层抽象的十二年——每搬一次,泄漏点就挪一次窝,守在新的窝边。MongoDB 的默认值用反例把这句话又说了一遍:可以卖性能,不可以把用户没有买的东西悄悄记进账单。
工业化本身也有它的阶梯,值得在收束处排开。第一级是组件化:1999 年的 Lucene 把检索做成可嵌入的库,检索能力从搜索公司的专利变成任何应用的零件,懂倒排索引不再是使用它的前提。第二级是平台化:2010 年前后的 Elasticsearch 在组件之上补齐分片与副本的集群编排,再挂上 REST 的门面,检索从零件变成开箱即用的服务。第三级是场景化:日志与监控把检索拖出搜索框,ELK 让它成为运维的基础设施,DB-Engines 的排名则是这一级完成度的公共刻度。每升一级,上一级的成果就被下一级当作地基再封装一次,认知门槛随之再降一格;1996 年斯坦福的那间宿舍到 2016 年的排行榜首,十二年工业化的路径在两级台阶之间几乎是一条直线。
本章的断言是:搜索工业化的真正产出是一套给“信任”定价的机器——PageRank 用链接的代价给网页权威定价,倒排索引用有序结构给毫秒响应定价,而 MongoDB 的默认值丑闻反过来标出了不标价的代价:当持久性承诺混在“成功”二字里出售时,崩溃那一天的损失就是对定价失误的强制审计。这个断言可以被反驳:如果链接投票的操纵成本在实践中始终低到可以批量越过,如果默认值的教训只是早期版本的个案、此后系统的默认承诺再未大规模失信,那么“定价”就是修辞,信任的供给靠的是别的机制。
「计算机百年史」系列第 7 篇(共 10 篇)。全系列统一标签:计算机百年史。