莫非我就是被时代呼唤的数学人

sjjt2391png

最近中美贸易战,华为成了焦点。任老爷子一席大论,据说有 27 次提到了数学;紧接着,某著名公号的一篇《时代呼唤数学家》又刷了屏,直把数学家推到了风口浪尖,让人感觉数学的春天就要来了。熟悉我所做工作的朋友也来问我:是不是有很多人来找我了。其实惭愧,并没有多少,所以写个文章蹭蹭热点宣传一下。

我是在用数学搞软件,但距离主流数学很远,而且远未成功,不敢妄称为“家”,因此把标题改了下,谦虚些说是数学人吧。

我在做什么?

我们在搞号称 IT 三大核心技术之一的数据库!另外两大是 CPU 和操作系统。CPU 太硬,我毫无发言权;操作系统略知一二,发言权也不多。数据库领域嘛,确实是比较熟悉的。


我国的数据库做得怎样呢?

N 年前,除了国外巨头外,只有几个国家队在搞数据库(所谓国家队,其实也是企业,但主要由政府资金来支持)。不客气说,国家队做得很差。这无关从业人员的能力和情怀,而是路子方向的问题。国家队做数据库,并不是因为有需求刺激,而就是为了做而做,技术路线也基本是抄(有些直接拿开源改),这要能做好才是奇怪的事情。去年中兴事件时,我写了一篇文章《国产数据库通通都没戏!》说这个现象。

近年来,有许多企业加入数据库开发的行列。企业队和国家队的根本不同在于,企业队有明确的需求,也就是很清楚地知道要解决的问题。特别是互联网行业中巨大用户量的应用,继续使用国外数据库,要么撑不住,要么买不起。在需求的刺激下,做出来的产品在某些方面就能够达到世界领先水平了。在竞争中的国家队也开始企业化转型,能力也在不断提升。

不过,过去的国家队固然没什么建树,今天的企业队也仍然只是在工程上进行优化,使自家产品比国外产品更适合某类场景,并没有获得压倒性的优势。面临的技术难题也只是得到了一定程度的缓解,没有从根本上解决。

其实不仅国内,全世界范围也是这样。大家都只是在工程上做些优化,甚至有些搞法也只能叫改造不能说是优化。比如 NoSQL 产品,在吞吐率上做了提升,但严重牺牲了计算能力,还放弃了某些场合很重要的一致性能力;某些 NewSQL 产品为了扩展能力和一致性做了妥协;而近年来热门的大数据库平台 Hadoop,原本试图颠覆传统关系型数据仓库,但搞来搞去又在回归到 SQL 去了。

我怎么做数据库?

我们发明新数学

现在的数据库在用什么数学呢?

目前主流数据库是关系数据库,之所以这么叫,是因为它的数学基础被称为关系代数,这是少有的几项计算机领域专用的数学。

关系代数已经发明近五十年了,五十年前的应用需求以及硬件环境,和今天比的差异是很巨大了,继续延用五十年前的理论来解决今天的问题,是不是听着就感觉太陈旧了?然而现实就是这样,由于存量用户太多,而且也还没有成熟的新技术出现,基于关系代数设计的 SQL,今天仍然是最重要的数据库开发语言。虽然这几十年来也有一些改进完善,但根子并没有变,面对当代的复杂需求和硬件环境,关系数据库并没有那么得心应手了。

旧瓶难再装新酒。


要说清这个问题,我们要看数据库到底在干什么事情?

数据库这个产品,名字中有个库字,会让人觉得它主要是为了存储的。其实不然,简单的存储很容易解决,数据库真正干的事有两条:计算、交易!存储也是为这两件事服务的。

计算问题

先说计算,也就是我们常说的 OLAP 能力。这里我更愿意用计算这个词,而不用分析(OLAP 中的 A)。计算的概念更广泛且更务实一些,它并不单指加加减减,查找、关联都可以看成是某种计算。

什么样的计算体系才算好呢?

又是两条:写着简单、跑得快

写着简单,很好理解,就是让程序员很快能写出来代码来,这样单位时间内可以完成更多的工作;跑得快更容易理解,我们当然希望更短时间内获得计算结果。


那么,关系数据库,或者说 SQL,在这两方面做得怎么样呢?

SQL 语句很象英语,有些查询可以当英语来读和写(网上多得很,就不举例了),这应当算是满足写着简单这一条了吧。

且慢!我们在教科书上看到的 SQL 经常只有两三行,这些 SQL 确实算是写着简单的,但如果我们尝试一些稍复杂化的问题呢?

我经常举的一个其实还算简单的例子:计算一支股票最长连续上涨了多少天?用 SQL 写出来是这样的:

SELECT MAX(连续日数) FROM

(SELECT COUNT(*) 连续日数 FROM

(SELECT SUM( 涨跌标志) OVER (ORDER BY 交易日) 不涨日数 FROM

( SELECT 交易日,

CASE WHEN 收盘价 >LAG(收盘价) OVER( ORDER BY 交易日 THEN 0 ELSE 1 END 涨跌标志

FROM 股票 ))

GROUP BY 不涨日数 )

这个语句的工作原理就不解释了,程序员们可以自己尝试一下。

这曾经是我公司的招聘考题,通过率不足 20%;因为太难,后来把它改了一种方式:把 SQL 语句写出来让应聘者解释它在算什么,通过率依然不高。这说明什么?说明 SQL 即难懂又难写!


再看跑得快的问题,还是一个经常拿出来的简单例子:1 亿条数据中取前 10 名。这个任务用 SQL 写出来并不复杂:

SELECT TOP 10 x FROM T ORDER BY x DESC

但是,这个语句对应的执行逻辑是先对所有数据进行大排序,然后再取出前 10 个,后面的不要了。大家知道,排序是一个很慢的动作,会多次遍历数据,如果数据量大到内存装不下,那还需要外存做缓存,性能还会进一步急剧下降。如果严格按这句 SQL 体现的逻辑去执行,这个运算无论如何是跑不快的。然而,很多程序员都知道这个运算并不需要大排序,也用不着外存缓存,一次遍历用一点点内存就可以完成,也就是存在更高性能的算法。可惜的是,用 SQL 却写不出这样的算法,只能寄希望于数据库的优化器足够聪明,能把这句 SQL 转换成高性能算法执行,但情况复杂时数据库的优化器也未必靠谱。


看样子,SQL,也就是关系数据库,在这两方面做得并不好。这两个并不复杂的问题都是这样,现实中数千行的 SQL 代码中,这种难写且跑不快的情况比比皆是。

为什么 SQL 做得不够好呢?


要回答这个问题,我们需要分析一下用程序实现计算到底是在干什么。

本质上讲,编写程序的过程,就是把解决问题的思路翻译成计算机可执行的精确化形式语言的过程。举例来说,就象小学生解应用题,分析问题想出解法之后,还要列出四则运算表达式。用程序计算也是一样,不仅要想出解决问题的方法,还要把解法翻译成计算机能理解执行的动作才算完成。

用于描述计算方法的形式语言,其核心在于所采用的代数体系。所谓代数体系,简单说就是一些数据类型和其上的运算规则,比如小学学到的算术,就是整数和加减乘除运算。有了这套东西,我们就能把想做的运算用这个代数体系约定的符号写出来,也就是代码,然后计算机就可以执行了。

如果这个代数体系设计时考虑不周到,提供的数据类型和运算不方便,那就会导致描述算法非常困难。这时候会发生一个怪现象:翻译解法到代码的难度远远超过解决问题本身

举个例子,我们从小学习用阿拉伯数字做日常计算,实施加减乘除都很方便,所有人都天经地义认为数值运算就该是这样的。其实未必!我想大多数人都知道还有一种叫做罗马数字的东西,我不知道罗马数字体系是不是还有我们熟悉的加减乘除运算(它那个数字体系无法象阿拉伯数字这样方便地实施这些运算,很可能运算定义也不同了),我也一直很困惑古罗马人是如何上街买菜的

这样,我们知道了,程序难写很大程度是代数的问题。


再看跑不快的原因。

软件没办法改变硬件的性能,CPU 和硬盘该多快就是多快。不过,我们可以设计出低复杂度的算法,也就是计算量更小的算法,这样计算机执行的动作变少,自然也就会快了。但是,光想出算法还不够,还要把这个算法用某种形式语言写得出来才行,否则计算机不会执行。而且,写起来还要比较简单,都要写很长很麻烦,也没有人会去用。所以呢,对于程序来讲,跑得快和写着简单其实是同一个问题,背后还是这个形式语言采用的代数的问题。如果这个代数不好,就会导致高性能算法很难实现甚至实现不了,也就没办法跑得快了。就象上面说的,用 SQL 写不出我们期望的小内存单次遍历算法,能不能跑得快就只能寄希望于优化器。


我们再做个类比:

在国内上过小学的同学大概都知道高斯计算 1+2+3+…+100 的小故事。普通人就是一步步地硬加 100 次,高斯小朋友很聪明,发现 1+100=101、2+99=101、…、50+51=101,结果是 50 乘 101,很快算完回家午饭了。

听过这个故事,我们都会感慨高斯很聪明,能想到这么巧妙的办法,即简单又迅速。这没有错,但是,大家容易忽略一点:在高斯的时代,人类的算术体系(也是一个代数)中已经有了乘法!象前面所说,我们从小学习四则运算,会觉得乘法是理所当然的,其实并不是,乘法是后于加法被发明出来的。如果高斯的年代还没有乘法,即使有聪明的高斯,也没办法快速解决这个问题。


现在,我们可以回答前面的问题:为什么关系数据库在我们期望的那两个方面做得不够好?

问题出在关系代数上,关系代数就象只有加法还没发明乘法的算术体系,很多事做不好是必然的。

而且,不幸的是,这个问题是理论上的,在工程上无论如何优化也无济于事,只能有限改善,不能根除。不过,绝大部分的数据库开发者并不会想到这一层,或者说为了照顾存量用户的兼容性,也没打算想到这一层。于是,主流数据库界一直在这个圈圈里打转转。

那么该怎么办呢?也就是如何让计算写着更简单、跑得更快呢?

发明新的代数!有“乘法”的代数。

嗯,数学来了!

交易问题

说完计算,我们再说说交易,也就是常说的 OLTP 能力。

现在是云计算的时代,几乎所有的数据库厂商都在忙着上云。但是,目前这个数据库真地适合上云吗?

其实,包括某些世界巨头在内的所谓云数据库,就是把家里的数据库物理地搬到云服务器上而已,其它方面仍然只是工程上的改造,在强一致性和可扩展性之间进行一定的权衡妥协,应用开发过程和传统数据库没有太大区别。当然,我们不能说这就不算是云应用,但这种机制并未体现云应用的基本特征。

云应用的基本特征在于数据结构的多样性

云应用将打破企业界限,不象传统应用每个用户做一个,而是云服务商提供一个系统面对所有用户;应用也不象以前那样一期一期做下去,而要永远在线,只能热升级。不同用户的数据结构不完全一样,同一个用户在不同时段的数据结构也会变,这样就会积累大量不同结构的数据要一起存储和计算。这是关系数据库在设计时没有被考虑过的问题,因为关系代数几乎没有设计针对多样性结构数据的处理能力。

继续采用关系数据库(或其变种)应对云应用,就会面临个性化和海量用户之间的矛盾:想要海量用户,就要牺牲个性化(所有用户面对同样数据结构的应用);想要个性化(各有各的数据结构)就要牺牲用户量(只服务相对数量较少的用户)。但是云应用恰恰要求个性化和大用户量这两个特征并存。


交易数据库还有个重要指标是保证一致性(网上解释很多,这里不赘述)。关系数据库虽然能够实现一致性,但资源消耗严重,这会导致并发能力下降,而多并发又是云应用常有的特征。

关系数据库实现一致性的成本过高,原因在于它的数据组织机制,这由参与操作的数据类型决定,而数据类型是被关系代数规定的。和前面说的多样性一样,想要实现低成本的一致性,就要打破关系代数,换一种方式组织和存储数据。

嗯,还是数学!

在路上

用了这么多篇幅说明当前数据库采用的代数体系有问题,这是一回事。而发明一个新的代数体系,那完全是另一回事。仅仅改进某一项运算并不算很困难,但要将各种数据类型和运算整合在一个体系中,保证封闭和自洽,这就会是一个巨大的挑战。

这里就封闭和自洽解释一下。封闭性是指任何计算结果必须仍然属于定义过的数据类型,一个不满足封闭性的代数无法连续地运算。比如整数对加减乘封闭,而对除法不封闭,在整数范围内就不能连续随意地做四则运算,要么对除法做限制,要么把整数扩展到有理数。而自洽性是指这些运算不能出现矛盾的结果,比如我们要约定不能除以 0,否则把某个数除以 0 规定成任何数都能推出逻辑矛盾,这个体系就没法计算出正确的东西。封闭性和自洽性是合理代数体系必须满足的条件。

同时在应用方面,为了让它有足够的描述能力,也就是让我们常见的需求都能轻松用基本数据类型和运算组合出来,这就希望数据类型和运算尽量多。但是,为了降低整体的复杂度和相应的学习成本,又要让数据类型和运算尽量少。这一多一少的权衡也是个学问。数学上有个最小完备集这个概念,大体就是这个意思,我们设计的数据类型和运算要正好够,没有多余的也没有不足的。


结果呢,我们用了十年时间,历经四次推倒重构,今天才终于能把 OLAP 功能发布出来,而解决 OLTP 的云数据库仍在实验环境中打磨。

当年我在清华 BBS 上的网名就是“十年磨一剑”,一语成谶。

十年磨出个什么东西呢?

磨出了新的代数!我们起了个数学味道的名字:离散数据集。基于这个代数,我们设计了新的形式语言,起名为 SPL(Structured Process Language)。

这篇文章内不合适详细解释离散数据集的内容了,我只把前面的例子用 SPL 写出来,简单感受一下。

一支股票最长连续上涨多少天:

股票.sort(交易日).group@o(收盘价 < 收盘价 [-1]).max(~.len())

计算思路和前面的 SQL 是一样的,但因为引入了有序运算后,表达起来要容易得多,不再绕了。

1 亿条数据中取前 10 名:

T.groups(;top(-10,x))

SPL 有更丰富的集合数据类型,这条语句就表述了单次遍历上实施简单聚合的高效算法,不必大排序。


高性能是大数据技术的永恒追求。在新代数支持下,我们能把数据库计算的性能提高到什么程度呢?

几个月前,我就去年做过一场性能测试写过一篇文章《怎样让国产芯片性能超越 Intel》:** 用 SPL 在低性能芯片上实现的高性能算法,能远远超越 SQL 在高性能芯片上写出的低性能算法。** 这是数学的力量!

我们也敢于和传统数据库叫板,包括国际巨头在内,面对 SQL 写出的慢代码,改用 SPL 后平均能提速一个数量级。这是数学的底气!

感谢数学

《感谢数学》是我在 15 年前纪念陈省身教授逝世时写的文章,其中解释了数学给我了什么,今年有机会应同学之邀又做了一次题为“感谢数学”的讲座,进一步诠释了数学对我的意义。这些内容,同时也可以解释我为什么可以做这个东西,或者应当问得更直白一些:我为什么敢做这个东西

要撼动有如此深厚巨大用户基础的关系数据库,把用户从多年的使用习惯中扳出来,当真是谈何容易。我知道有无数从业人员因为兼容性而放弃创新,我自己也被无数次地好心劝过这路线太艰难。

“有数学,就有信心!”

数学给了我严格和抽象的思维。多一点严格认真,就能发现更多别人看不到的盲点;多一点抽象能力,就能比别人看得更深更远。

马车总归是马车,再优化它还是马车,还是要靠马拉动。初生的汽车,操作上当然会有各种不习惯,功能上也会有众多不如意,甚至还可能跑散架了。但它是汽车,是用发动机驱动的,假以时日不断完善,它的巨大优势必将全面碾压马车。


在计算机的帮助下,人类第一次有了机械化处理大规模数据的能力。同时,也不可避免地遭遇许多以往不曾面对过的新问题。这些问题可能涉及到计算机的基础理论,无法简单地使用工程方法去处理,而需要发展出新的数学体系,采用新的模型才能解决。

然而,与工程上取得的巨大成功相比,计算机科学在理论方面却非常单薄,只能数出可计算性、关系代数等几个为数不多的领域。计算机界使用的数学,大部分是几十年甚至上百年前早就被数学家们发明过的。

三百年前刚发明微积分的年代,各种猜想定理层出不穷,数学家们时不时就能把名字写进我们的教科书,这些名垂青史的成果现在看来并不复杂(当时提出来并不容易),普通理工科学生都能理解。这完全不同于当代主流数学领域,不学二十年根本无法和人交流。

现在的计算机数学也正当时,处于最容易出成果的时代。我也有信心,终有一天,离散数据集理论也会写进大学教科书!