CAP定理和NoSQL

CAP定理(CAP theorem)是由大牛 Eric Brewer 在2000年PODC上首次提出的。起先它是个猜想,Brewer 认为在分布式计算系统中对某个数据不存在一个算法同时满足数据一致性(consistency),读操作是否总能读到前一个写操作的结果,即是说在分布式环境中,多点读出的数据是否是同一份最新的数据副本;可用性(Availability),时刻能进行对数据的读写访问,所有的请求都应该成功并且收到返回;分区容错(partition-tolerance),无论任何消息丢失,系统都可用。2002年 Gilbert 和 Lynch 证明了 Brewer 的猜想使之成为了定理。

NoSQL 一定程度上就是基于这个理论提出来的,因为传统的关系型数据库都具有 ACID (原子性、一致性、隔离性、持久性)属性,对一致性要求很高。NoSQL 数据库都以水平扩展著称,为了提高系统性能和可扩展性,所以在 CAP 的选择上面,都倾向于坚持P,牺牲C(consistency)或牺牲A(Availability)来进行设计。

CAP选择
考虑CA:放弃 partition-tolerance 意味着把所有的机器搬到一台机器内部,一旦某个操作失败,整个系统就出错。代表是传统的关系型数据库、Vertica(Column-oriented)等,这些数据库对于分区容忍性方面比较不感冒,主要采用复制(Replication)来保证数据的安全性。
考虑CP:这种系统将数据分布在多个网络分区的节点上,并保证这些数据的一致性,但是对于可用性的支持方面有问题。一旦遇到 partition 事件,受影响的服务需要等待数据一致,因此在等待期间就无法对外提供服务,只能对部分数据进行读写。在多个节点上控制这一点会相当复杂,像 Google 的一般做法是将主分区归属在单一个数据中心里面,然后交给 Paxos 算法去解决跨区域的问题。代表有 BigTable(Column-oriented)、HBase(Column-oriented)、MongoDB(Document)、Redis(Key-value)。
考虑AP:系统只要每次对写都返回成功,对读都返回固定的某个值。Werner Vogel(Amazon CTO)认为不一致是可以容忍的,这有两个理由:一是可以在高并发条件下提高读写性能;二是处理一些分区状况——多数决模型(majority model)有可能使系统的一部分表现为不可用,虽然那些节点正运行良好。他在2008年发布在 ACM Queue上 的一篇数据库方面的重要文章,阐述了 NoSQL 数据库的理论基石——最终一致性(Eventual Consistency)。Quorum NRW策略和Gossip协议可以用来维护最终一致性。这类系统的代表有 Dynamo(Key-value)、Voldemort(Key-value)、Cassandra(Column-oriented)。

CAP 的三选二也不是绝对的非黑即白的有或无,这三种性质都可以在程度上衡量:可用性在0%到100%之间连续变化的,一致性分很多级别,连分区也可以细分为不同含义。虽然不可能在同一时刻满足 Consistency、Availability 和 Partition-tolerance 全部的3个要求,但是 Guy Pardon 的文章 A CAP Solution(Proving Brewer Wrong 将条件放松到系统可以分时达到 CAP,提出了一个满足 CAP 的解决方案。Twitter 的首席工程师 Nathan Marz 的文章 How to beat the CAP theorem 提出正是因为要不断的更新数据库中的数据,再加上 CAP ,才导致那些即便使用最终一致性的系统也会变得无比复杂。如果系统中不存在会改变的数据(append-only immutable data),所有的更新都作为创建新数据的方式存在,数据的处理由 CRUD 变为 CR,把读数据转化为一次请求(对整个数据集执行一个函数操作),这样就可以避免最终一致性的复杂性,转而拥抱 CAP。

卷积神经网络

卷积神经网络(Convolutional Neural Networks:CNN)是人工神经网络(ANN)的一种,是深度学习的一种学习算法。它在图像识别和分类、自然语言处理广告系统中都有应用。

有意思是,卷积神经网络的提出其实就是来自于生物视觉模型。1981年的诺贝尔医学奖,颁发给了David Hubel、Torsten Wiesel。他们的工作给人们呈现了视觉系统是如何将来自外界的视觉信号传递到视皮层,并通过一系列处理过程(包括边界检测、运动检测、立体深度检测和颜色检测),最后在大脑中构建出一幅视觉图像。这个发现激发了人们对于神经系统的进一步思考,神经-中枢-大脑的工作过程,或许是一个不断迭代、不断抽象的过程。如下图所示,从原始信号摄入开始(瞳孔摄入像素Pixels),首先进行初步处理(大脑皮层某些细胞发现边缘和方向),抽象(大脑判定眼前的物体的形状是圆形的),然后进一步抽象(大脑进一步判定该物体是只气球)。

convolutional deep belief network

六十年代的生理学的发现,促成了计算机人工智能在四十年后的突破性发展。1989年,Yann LeCun (纽约大学教授,现Facebook AI研究室主任) 提出了卷积神经网络,这是第一个真正成功训练多层网络结构的学习算法,但在当时的计算能力下效果欠佳。直到2006年,Geoffrey Hinton提出基于深信度网(Deep Belief Net)和限制波尔兹曼机(Restricted Boltzmann Machine)的学习算法,重新点燃了人工智能领域对于神经网络的热情。

卷积神经网络现在计算机视觉领域表现出众。ImageNet Classification with Deep Convolutional Neural Networks,这篇发表于NIPS2012的文章,是Hinton与其学生为了回应别人对于Deep Learning的质疑而将CNN结合GPU并行技术用于Imagenet Challenge(图像识别目前最大的数据库,被誉为计算机视觉圣杯),最终取得了非常惊人的结果。他们的算法在2012年取得世界最好结果,使分类错误率从26.2%下降到16%。2013年Matthew Zeiler的算法继续将错误率下降到11.2%。Matthew Zeiler还创立了Clarifai,让我们可以有机会使用他们的图像识别算法对图片标注分类或图像搜索。

imageNet classification with CNN
The convnet from Krizhevsky et al.'s NIPS 2012 ImageNet classification paper.

在月初Kaggle结束的Galaxy Zoo challenge中,参赛者要对星系图像进行分类(Spiral/Elliptical, Merging/Not merging, Clockwise/Anti-clockwise),获胜的算法也是使用了卷积神经网络。Sander Dieleman已放出了代码和详尽的文档: My solution for the Galaxy Zoo challenge

2014年3月,Facebook刚刚公布了他们在CVPR2014的文章:DeepFace: Closing the Gap to Human-Level Performance in Face Verification。他们用四百万人脸图片训练了一个九层的卷积神经网络来获得脸部特征,神经网络处理的参数高达1.2亿。他们在著名的公共测试数据集LFW(labeled face in the wild,1:1地判断是否两个照片是一个人)上达到了97.25%的正确率。这个数字已经基本接近人眼的辨识水平。北京Face++团队的算法达到97.27%的正确率,在美图秀秀中就有应用,他们的主页提供了API、demo展示和论文。现在的最新进展是,香港中文大学基于 Fisher Discriminant Analysis的算法将Face Verification正确率提高到98.52%,超过了人类水平(97.53%)。

faceplusplus system overview
System overview in Face++ paper in ICCV2013

除了计算机视觉领域,卷积神经网络在人工智能和robotics也有很大潜力。Hinton的另外一个学生创立了人工智能公司DeepMind,没有商业产品,只凭一篇论文,就已被Google招聘式收购。 他们使用深度学习(CNN)结合强化学习(Reinforcement Learning),在Stella模拟机上让机器自己玩了7个Atari 2600的游戏,结果不仅战胜了其他机器人,甚至在其中3个游戏中超越了人类游戏专家。很有意思,具体可以见InfoQ的看DeepMind如何用Reinforcement learning玩游戏,以及论文原文Playing Atari with Deep Reinforcement Learning

2014年公开课计划

整个寒假都没有可以跟的课,老外果然都过圣诞节去了。新的一年有三门课非常给力:Convex Optimization、Statistical Learning和Networks, Crowds and Markets。

Convex Optimization的老师是经典教材《Convex Optimization》的作者Stephen Boyd。

Statistical Learning,老师是Trevor Hastie和Rob Tibshirani,俩人都是大名鼎鼎的《The Elements of Statistical Learning》、《An Introduction to Statistical Learning, with Applications in R》作者之一。《The Elements of Statistical Learning》的另一个作者Jerome Friedman发明了Gradient Boosting。

edX上Networks, Crowds and Markets在3月3日开课,这门课的老师也很强大:Cornell的Jon Kleinberg, David Easley, Eva Tardos。Jon Kleinberg是社交网络研究的神牛,2013年还拿了ACM SIGKDD 2013 Innovation Award。David Easley和Jon Kleinberg合著了《Networks, Crowds and Markets》;Eva Tardos和Jon Kleinberg合著了《Algorithm Design》的作者。这两本都是我比较喜欢的教材。《Networks, Crowds and Markets》之前读到一半,正好这次可以跟着课把书读完。

椭圆曲线和Dual_EC_DRBG后门

这两天爆出NSA收买RSA将NSA推荐的算法,Dual_EC_DRBG,设置为BSafe中默认的随机数生成算法。为了推广这种算法,其实早在2007年NSA就执意将其写入了NIST(美国国家标准技术管理委员会)的确定性随机数生成器推荐标准(Special Publication 800-90,SP800-90),即使它速度极慢。同年Dual_EC_DRBG就在Crypto 2007会议上被指出存在被植入后门的可能,但不能认定算法设计者是否知道后门的参数,也不能认定NIST有意在算法中植入后门。2013年9月Edward Snowden泄漏的内部备忘录显示NSA曾向某加密算法植入后门,再到12月路透社爆出RSA被收买,现在看起来是NSA精心选取参数值下后门。有意思的是,比特币也使用了ECC来生成随机数,但是比特币神秘创始人中本聪在2009年发明比特币的时采用了小众的secp256k1的曲线参数而不是有问题的secp256r1(NIST P-256),神奇地躲过了密码学子弹。
那么Dual_EC_DRBG漏洞在哪,为什么随机数生成器的漏洞会让加密算法被攻破?先要从椭圆曲线和随机数生成器说起。

椭圆曲线
椭圆曲线密码学(Elliptic curve cryptography,ECC)由Koblitz和Miller分别独立提出,是迄今为止安全性最高的一种公钥密码算法。椭圆曲线E的形式是:

y^2=x^3+ax+b, a,b \in F_p

有限域Fq,q一般是2的m次方或大素数p,也可以是某素数p的m次方。参数a,b确定椭圆曲线E。
它的安全性基于有限域椭圆曲线离散对数问题(Elliptic Curve Discrete Logarithm Problem,ECDLP)的难解性:
给定素数p和椭圆曲线E,对Q=dG,在已知G,Q的情况下求出小于p的正整数d。可以证明由d和G计算Q容易,而由Q和G计算d则是指数级的难度。
G对应为椭圆曲线E的基点,d为私钥由自己选择,然后生成对应公钥Q=dG,得到密钥对(d, Q),私钥自己保存,(p, a, b, G, Q)是已知的,但是由p和G计算私钥d很难,保证了加密算法的强度。
还有2种公钥密码体制分别基于大整数分解问题(Integer Factorization Problem,IFP)的难解性,如RSA,和有限域离散对数问题(Discrete Logarithm Problem,DLP)的难解性,如Diffie-Hellman、ElGamal。但是ECC问题要比DLP问题更难解,并且ECC用更少的密钥长度提供相同的加密强度。
这次出问题的Dual_EC_DRBG,全称Dual Elliptic Curve Deterministic Random Bit Generation,是基于椭圆曲线的确定性随机数生成器。

随机数生成器
随机数在密码学中具有十分重要的地位,被广泛用于密钥产生、初始化向量、时间戳、认证挑战码、密钥协商、大素数产生等等方面。随机数产生器用于产生随机数,分为非确定性随机数生成器和确定性随机数生成器两类:
非确定性随机数生成器(NRBG)基于完全不可预测的物理过程。确定性随机数生成器(伪随机数生成器,DRBG)在指定初始种子之后,利用某些算法产生一个确定的比特序列,“确定性”因此得名。如果种子是保密的而且算法设计得很完善,那么可以认为输出的比特序列是不可预测的。
加密算法需要高度随机性的“种子”来生成密钥,因此随机数生成器会直接影响加密强度和安全性,脆弱的随机数生成器被攻破会击溃整个加密算法,比如Android随机生成数字串安全密钥中的漏洞就导致了部分比特币的失窃。

Dual_EC_DRBG后门
这个后门的发现可以追溯到六年前,NIST在2007年发布了确定性随机数产生器推荐标准SP800-90修订版。这是一个推荐性的标准,描述了一些产生随机比特流的方法,这些随机比特流可能被用于直接或者间接的产生随机数,并用于相关使用密码学的应用中。NIST SP800-90提供了4种标准算法:Hash_DRBG(基于SHA系列算法)、HMAC_DRBG(基于HMAC函数)、CTR_DRBG(基于分组密码函数AES)、Dual_EC_DRBG(基于椭圆曲线)。
在4个月后的Crypto 2007会议上,Dan Shumow和Niels Fergusonsuo作了一个报告,宣称标准中的Dual_EC_DRBG设计存在严重漏洞,具体可以参看报告On the Possibility of a Back Door in the NIST SP800-90 Dual Ec Prng...智商不够用了,我的理解是:
P, Q是ECC上两个基点,且满足eQ=P,点Q常量可以确定万能钥匙。如果攻击者知道私钥d满足Q=dP,计算eQ=P是容易的,存在a*e=1 mod p。反过来如果攻击者知道e,以及一些已知的随机值,攻击者可以计算出点G,然后可能能确定DRBG的内部状态,并预测DRBG后来的输出。一个“局外人”可能并不知道这种特殊关系的存在,但是如果知道了P和Q之间关系的“密钥”,攻击者可以利用Dual_EC_DRBG存在的后门得到该算法后续所有的随机数值,从而破坏不可预测的性质,预测其使用的密钥,进而攻破整个加密算法。

DES S-BOX的传说
DES中S盒来路不明是密码学届的一个著名的谜团,也和NSA有关。1975,IBM刚搞出DES(Data Encryption Standard)时候,NSA就对S-Box做了修改,并将密钥长度由128bit缩减为56bit,但未说明原因,直到80年代差分分析被公开学术界发现后,人们发现针对DES16轮的差分攻击效率甚至不如穷举,于是怀疑在设计DES的S盒和加密轮数时,差分攻击的方法就已经被发现了,而NSA那个修改证明是为了对抗可能的差分分析。

神经网络与数据压缩

神经网络除了用于Regreesion和Classification,还可以与用于数据压缩Data Compression。自联想神经网络Auto-Associative Neural Network是三层BP网络,它的特点是输出是对输入的一种重构,即输出等于输入或者允许输入输出有一定的误差存在。如果中间层Hidden Layer节点少于输入层Input Layer,中间层可以用更少节点表示输入层的数据同时可以在输出层重构出输入层数据,这就是数据压缩和解压的过程。

从另一个角度来看,中间层提取出数据中最重要的特征,用更少维度表示输入数据。如果我们在网络中不使用sigmoid函数,而使用线性函数,这就是主成分分析PCA模型。

在深度学习中,上述结构被称作自编码神经网络Autoencoder Neural Network。

close