All posts by dotte

10 种机器学习算法的要点(附 Python 和 R 代码)

前言

谷歌董事长施密特曾说过:虽然谷歌的无人驾驶汽车和机器人受到了许多媒体关注,但是这家公司真正的未来在于机器学习,一种让计算机更聪明、更个性化的技术。

也许我们生活在人类历史上最关键的时期:从使用大型计算机,到个人电脑,再到现在的云计算。关键的不是过去发生了什么,而是将来会有什么发生。

工具和技术的民主化,让像我这样的人对这个时期兴奋不已。计算的蓬勃发展也是一样。如今,作为一名数据科学家,用复杂的算法建立数据处理机器一小时能赚到好几美金。但能做到这个程度可并不简单!我也曾有过无数黑暗的日日夜夜。

谁能从这篇指南里受益最多?

我今天所给出的,也许是我这辈子写下的最有价值的指南。

这篇指南的目的,是为那些有追求的数据科学家和机器学习狂热者们,简化学习旅途。这篇指南会让你动手解决机器学习的问题,并从实践中获得真知。我提供的是几个机器学习算法的高水平理解,以及运行这些算法的 R 和 Python 代码。这些应该足以让你亲自试一试了。

我特地跳过了这些技术背后的数据,因为一开始你并不需要理解这些。如果你想从数据层面上理解这些算法,你应该去别处找找。但如果你想要在开始一个机器学习项目之前做些准备,你会喜欢这篇文章的。

广义来说,有三种机器学习算法

1、 监督式学习

工作机制:这个算法由一个目标变量或结果变量(或因变量)组成。这些变量由已知的一系列预示变量(自变量)预测而来。利用这一系列变量,我们生成一个将输入值映射到期望输出值的函数。这个训练过程会一直持续,直到模型在训练数据上获得期望的精确度。监督式学习的例子有:回归、决策树、随机森林、K – 近邻算法、逻辑回归等。

2、非监督式学习

工作机制:在这个算法中,没有任何目标变量或结果变量要预测或估计。这个算法用在不同的组内聚类分析。这种分析方式被广泛地用来细分客户,根据干预的方式分为不同的用户组。非监督式学习的例子有:关联算法和 K – 均值算法。

3、强化学习

工作机制:这个算法训练机器进行决策。它是这样工作的:机器被放在一个能让它通过反复试错来训练自己的环境中。机器从过去的经验中进行学习,并且尝试利用了解最透彻的知识作出精确的商业判断。 强化学习的例子有马尔可夫决策过程。

常见机器学习算法名单

这里是一个常用的机器学习算法名单。这些算法几乎可以用在所有的数据问题上:

  1. 线性回归
  2. 逻辑回归
  3. 决策树
  4. SVM
  5. 朴素贝叶斯
  6. K最近邻算法
  7. K均值算法
  8. 随机森林算法
  9. 降维算法
  10. Gradient Boost 和 Adaboost 算法

1、线性回归

线性回归通常用于根据连续变量估计实际数值(房价、呼叫次数、总销售额等)。我们通过拟合最佳直线来建立自变量和因变量的关系。这条最佳直线叫做回归线,并且用 Y= a *X + b 这条线性等式来表示。

理解线性回归的最好办法是回顾一下童年。假设在不问对方体重的情况下,让一个五年级的孩子按体重从轻到重的顺序对班上的同学排序,你觉得这个孩子会怎么做?他(她)很可能会目测人们的身高和体型,综合这些可见的参数来排列他们。这是现实生活中使用线性回归的例子。实际上,这个孩子发现了身高和体型与体重有一定的关系,这个关系看起来很像上面的等式。

在这个等式中:

  • Y:因变量
  • a:斜率
  • x:自变量
  • b :截距

系数 a 和 b 可以通过最小二乘法获得。

参见下例。我们找出最佳拟合直线 y=0.2811x+13.9。已知人的身高,我们可以通过这条等式求出体重。

线性回归的两种主要类型是一元线性回归和多元线性回归。一元线性回归的特点是只有一个自变量。多元线性回归的特点正如其名,存在多个自变量。找最佳拟合直线的时候,你可以拟合到多项或者曲线回归。这些就被叫做多项或曲线回归。

Python 代码

R代码

2、逻辑回归

别被它的名字迷惑了!这是一个分类算法而不是一个回归算法。该算法可根据已知的一系列因变量估计离散数值(比方说二进制数值 0 或 1 ,是或否,真或假)。简单来说,它通过将数据拟合进一个逻辑函数来预估一个事件出现的概率。因此,它也被叫做逻辑回归。因为它预估的是概率,所以它的输出值大小在 0 和 1 之间(正如所预计的一样)。

让我们再次通过一个简单的例子来理解这个算法。

假设你的朋友让你解开一个谜题。这只会有两个结果:你解开了或是你没有解开。想象你要解答很多道题来找出你所擅长的主题。这个研究的结果就会像是这样:假设题目是一道十年级的三角函数题,你有 70%的可能会解开这道题。然而,若题目是个五年级的历史题,你只有30%的可能性回答正确。这就是逻辑回归能提供给你的信息。

从数学上看,在结果中,几率的对数使用的是预测变量的线性组合模型。

在上面的式子里,p 是我们感兴趣的特征出现的概率。它选用使观察样本值的可能性最大化的值作为参数,而不是通过计算误差平方和的最小值(就如一般的回归分析用到的一样)。

现在你也许要问了,为什么我们要求出对数呢?简而言之,这种方法是复制一个阶梯函数的最佳方法之一。我本可以更详细地讲述,但那就违背本篇指南的主旨了。

Python代码

R代码

更进一步:

你可以尝试更多的方法来改进这个模型:

  • 加入交互项
  • 精简模型特性
  • 使用正则化方法
  • 使用非线性模型

3、决策树

这是我最喜爱也是最频繁使用的算法之一。这个监督式学习算法通常被用于分类问题。令人惊奇的是,它同时适用于分类变量和连续因变量。在这个算法中,我们将总体分成两个或更多的同类群。这是根据最重要的属性或者自变量来分成尽可能不同的组别。想要知道更多,可以阅读:简化决策树

来源: statsexchange

在上图中你可以看到,根据多种属性,人群被分成了不同的四个小组,来判断 “他们会不会去玩”。为了把总体分成不同组别,需要用到许多技术,比如说 Gini、Information Gain、Chi-square、entropy。

理解决策树工作机制的最好方式是玩Jezzball,一个微软的经典游戏(见下图)。这个游戏的最终目的,是在一个可以移动墙壁的房间里,通过造墙来分割出没有小球的、尽量大的空间。

因此,每一次你用墙壁来分隔房间时,都是在尝试着在同一间房里创建两个不同的总体。相似地,决策树也在把总体尽量分割到不同的组里去。

更多信息请见:决策树算法的简化

Python代码

R代码

4、支持向量机

这是一种分类方法。在这个算法中,我们将每个数据在N维空间中用点标出(N是你所有的特征总数),每个特征的值是一个坐标的值。

举个例子,如果我们只有身高和头发长度两个特征,我们会在二维空间中标出这两个变量,每个点有两个坐标(这些坐标叫做支持向量)。

现在,我们会找到将两组不同数据分开的一条直线。两个分组中距离最近的两个点到这条线的距离同时最优化。

上面示例中的黑线将数据分类优化成两个小组,两组中距离最近的点(图中A、B点)到达黑线的距离满足最优条件。这条直线就是我们的分割线。接下来,测试数据落到直线的哪一边,我们就将它分到哪一类去。

更多请见:支持向量机的简化

将这个算法想作是在一个 N 维空间玩 JezzBall。需要对游戏做一些小变动:

  • 比起之前只能在水平方向或者竖直方向画直线,现在你可以在任意角度画线或平面。
  • 游戏的目的变成把不同颜色的球分割在不同的空间里。
  • 球的位置不会改变。

Python代码

R代码

5、朴素贝叶斯

在预示变量间相互独立的前提下,根据贝叶斯定理可以得到朴素贝叶斯这个分类方法。用更简单的话来说,一个朴素贝叶斯分类器假设一个分类的特性与该分类的其它特性不相关。举个例子,如果一个水果又圆又红并且直径大约是 3 英寸,那么这个水果可能会是苹果。即便这些特性互相依赖或者依赖于别的特性的存在,朴素贝叶斯分类器还是会假设这些特性分别独立地暗示这个水果是个苹果。

朴素贝叶斯模型易于建造,且对于大型数据集非常有用。虽然简单,但是朴素贝叶斯的表现却超越了非常复杂的分类方法。

贝叶斯定理提供了一种从P(c)、P(x)和P(x|c) 计算后验概率 P(c|x) 的方法。请看以下等式:

在这里,

  • P(c|x) 是已知预示变量(属性)的前提下,类(目标)的后验概率
  • P(c) 是类的先验概率
  • P(x|c) 是可能性,即已知类的前提下,预示变量的概率
  • P(x) 是预示变量的先验概率

例子:让我们用一个例子来理解这个概念。在下面,我有一个天气的训练集和对应的目标变量“Play”。现在,我们需要根据天气情况,将会“玩”和“不玩”的参与者进行分类。让我们执行以下步骤。

步骤1:把数据集转换成频率表。

步骤2:利用类似“当Overcast可能性为0.29时,玩耍的可能性为0.64”这样的概率,创造 Likelihood 表格。

步骤3:现在,使用朴素贝叶斯等式来计算每一类的后验概率。后验概率最大的类就是预测的结果。

问题:如果天气晴朗,参与者就能玩耍。这个陈述正确吗?

我们可以使用讨论过的方法解决这个问题。于是 P(会玩 | 晴朗)= P(晴朗 | 会玩)* P(会玩)/ P (晴朗)

我们有 P (晴朗 |会玩)= 3/9 = 0.33,P(晴朗) = 5/14 = 0.36, P(会玩)= 9/14 = 0.64

现在,P(会玩 | 晴朗)= 0.33 * 0.64 / 0.36 = 0.60,有更大的概率。

朴素贝叶斯使用了一个相似的方法,通过不同属性来预测不同类别的概率。这个算法通常被用于文本分类,以及涉及到多个类的问题。

Python代码

R代码

6、KNN(K – 最近邻算法)

该算法可用于分类问题和回归问题。然而,在业界内,K – 最近邻算法更常用于分类问题。K – 最近邻算法是一个简单的算法。它储存所有的案例,通过周围k个案例中的大多数情况划分新的案例。根据一个距离函数,新案例会被分配到它的 K 个近邻中最普遍的类别中去。

这些距离函数可以是欧式距离、曼哈顿距离、明式距离或者是汉明距离。前三个距离函数用于连续函数,第四个函数(汉明函数)则被用于分类变量。如果 K=1,新案例就直接被分到离其最近的案例所属的类别中。有时候,使用 KNN 建模时,选择 K 的取值是一个挑战。

更多信息:K – 最近邻算法入门(简化版)

我们可以很容易地在现实生活中应用到 KNN。如果想要了解一个完全陌生的人,你也许想要去找他的好朋友们或者他的圈子来获得他的信息。

在选择使用 KNN 之前,你需要考虑的事情:

  • KNN 的计算成本很高。
  • 变量应该先标准化(normalized),不然会被更高范围的变量偏倚。
  • 在使用KNN之前,要在野值去除和噪音去除等前期处理多花功夫。

Python代码

R代码

7、K 均值算法

K – 均值算法是一种非监督式学习算法,它能解决聚类问题。使用 K – 均值算法来将一个数据归入一定数量的集群(假设有 k 个集群)的过程是简单的。一个集群内的数据点是均匀齐次的,并且异于别的集群。

还记得从墨水渍里找出形状的活动吗?K – 均值算法在某方面类似于这个活动。观察形状,并延伸想象来找出到底有多少种集群或者总体。

K – 均值算法怎样形成集群:

  1. K – 均值算法给每个集群选择k个点。这些点称作为质心。
  2. 每一个数据点与距离最近的质心形成一个集群,也就是 k 个集群。
  3. 根据现有的类别成员,找出每个类别的质心。现在我们有了新质心。
  4. 当我们有新质心后,重复步骤 2 和步骤 3。找到距离每个数据点最近的质心,并与新的k集群联系起来。重复这个过程,直到数据都收敛了,也就是当质心不再改变。

如何决定 K 值:

K – 均值算法涉及到集群,每个集群有自己的质心。一个集群内的质心和各数据点之间距离的平方和形成了这个集群的平方值之和。同时,当所有集群的平方值之和加起来的时候,就组成了集群方案的平方值之和。

我们知道,当集群的数量增加时,K值会持续下降。但是,如果你将结果用图表来表示,你会看到距离的平方总和快速减少。到某个值 k 之后,减少的速度就大大下降了。在此,我们可以找到集群数量的最优值。

Python代码

R代码

8、随机森林

随机森林是表示决策树总体的一个专有名词。在随机森林算法中,我们有一系列的决策树(因此又名“森林”)。为了根据一个新对象的属性将其分类,每一个决策树有一个分类,称之为这个决策树“投票”给该分类。这个森林选择获得森林里(在所有树中)获得票数最多的分类。

每棵树是像这样种植养成的:

  1. 如果训练集的案例数是 N,则从 N 个案例中用重置抽样法随机抽取样本。这个样本将作为“养育”树的训练集。
  2. 假如有 M 个输入变量,则定义一个数字 m<<M。m 表示,从 M 中随机选中 m 个变量,这 m 个变量中最好的切分会被用来切分该节点。在种植森林的过程中,m 的值保持不变。
  3. 尽可能大地种植每一棵树,全程不剪枝。

若想了解这个算法的更多细节,比较决策树以及优化模型参数,我建议你阅读以下文章:

  1. 随机森林入门—简化版
  2. 将 CART 模型与随机森林比较(上)
  3. 将随机森林与 CART 模型比较(下)
  4. 调整你的随机森林模型参数

Python

R代码

9、降维算法

在过去的 4 到 5 年里,在每一个可能的阶段,信息捕捉都呈指数增长。公司、政府机构、研究组织在应对着新资源以外,还捕捉详尽的信息。

举个例子:电子商务公司更详细地捕捉关于顾客的资料:个人信息、网络浏览记录、他们的喜恶、购买记录、反馈以及别的许多信息,比你身边的杂货店售货员更加关注你。

作为一个数据科学家,我们提供的数据包含许多特点。这听起来给建立一个经得起考研的模型提供了很好材料,但有一个挑战:如何从 1000 或者 2000 里分辨出最重要的变量呢?在这种情况下,降维算法和别的一些算法(比如决策树、随机森林、PCA、因子分析)帮助我们根据相关矩阵,缺失的值的比例和别的要素来找出这些重要变量。

想要知道更多关于该算法的信息,可以阅读《降维算法的初学者指南》

Python代码

R Code

10、Gradient Boosting 和 AdaBoost 算法

当我们要处理很多数据来做一个有高预测能力的预测时,我们会用到 GBM 和 AdaBoost 这两种 boosting 算法。boosting 算法是一种集成学习算法。它结合了建立在多个基础估计值基础上的预测结果,来增进单个估计值的可靠程度。这些 boosting 算法通常在数据科学比赛如 Kaggl、AV Hackathon、CrowdAnalytix 中很有效。

更多:详尽了解 Gradient 和 AdaBoost

Python代码

R代码

GradientBoostingClassifier 和随机森林是两种不同的 boosting 树分类器。人们常常问起这两个算法之间的区别。

结语

现在我能确定,你对常用的机器学习算法应该有了大致的了解。写这篇文章并提供 Python 和 R 语言代码的唯一目的,就是让你立马开始学习。如果你想要掌握机器学习,那就立刻开始吧。做做练习,理性地认识整个过程,应用这些代码,并感受乐趣吧!

from:http://blog.jobbole.com/92021/

Java中的纤程库 – Quasar

最近遇到的一个问题大概是微服务架构中经常会遇到的一个问题:

服务 A 是我们开发的系统,它的业务需要调用 BCD 等多个服务,这些服务是通过http的访问提供的。 问题是 BCD 这些服务都是第三方提供的,不能保证它们的响应时间,快的话十几毫秒,慢的话甚至1秒多,所以这些服务的Latency比较长。幸运地是这些服务都是集群部署的,容错率和并发支持都比较高,所以不担心它们的并发性能,唯一不爽的就是就是它们的Latency太高了。

简化的微服务架构简化的微服务架构

系统A会从Client接收Request, 每个Request的处理都需要多次调用B、C、D的服务,所以完成一个Request可能需要1到2秒的时间。为了让A能更好地支持并发数,系统中使用线程池处理这些Request。当然这是一个非常简化的模型,实际的业务处理比较复杂。

可以预见,因为系统B、C、D的延迟,导致整个业务处理都很慢,即使使用线程池,但是每个线程还是会阻塞在B、C、D的调用上,导致I/O阻塞了这些线程, CPU利用率相对来说不是那么高。

当然在测试的时候使用的是B、C、D的模拟器,没有预想到它们的响应是那么慢,因此测试数据的结果还不错,吞吐率还可以,但是在实际环境中问题就暴露出来了。

概述

最开始线程池设置的是200,然后用HttpUrlConnection作为http client发送请求到B、C、D。当然HttpUrlConnection也有一些坑,比如Persistent ConnectionsCaveats of HttpURLConnection,跳出坑后性能依然不行。

通过测试,如果B、C、D等服务延迟接近0毫秒,则HttpUrlConnection的吞吐率(线程池的大小为200)能到40000 requests/秒,但是随着第三方服务的响应时间变慢,它的吞吐率急剧下降,B、C、D的服务的延迟为100毫秒的时候,则HttpUrlConnection的吞吐率降到1800 requests/秒,而B、C、D的服务的延迟为100毫秒的时候HttpUrlConnection的吞吐率降到550 requests/秒。

增加http.maxConnections系统属性并不能显著增加吞吐率。

如果增加调用HttpUrlConnection的线程池的大小,比如增加到2000,性能会好一些,但是B、C、D的服务的延迟为500毫秒的时候,吞吐率为3800 requests/秒,延迟为1秒的时候,吞吐率为1900 requests/秒。

虽然线程池的增大能带来性能的提升,但是线程池也不能无限制的增大,因为每个线程都会占用一定的资源,而且随着线程的增多,线程之间的切换也更加的频繁,对CPU等资源也是一种浪费。

切换成netty(channel pool),与B、C、D通讯的性能还不错, latency为500ms的时候吞吐率能达到10000 requests/秒,通讯不成问题,问题是需要将业务代码改成异步的方式,异步地接收到这些response后在一个线程池中处理这些消息。

下面列出了一些常用的http client:

  • JDK’s URLConnection uses traditional thread-blocking I/O.
  • Apache HTTP Client uses traditional thread-blocking I/O with thread-pools.
  • Apache Async HTTP Client uses NIO.
  • Jersey is a ReST client/server framework; the client API can use several HTTP client backends including URLConnection and Apache HTTP Client.
  • OkHttp uses traditional thread-blocking I/O with thread-pools.
  • Retrofit turns your HTTP API into a Java interface and can use several HTTP client backends including Apache HTTP Client.
  • Grizzly is network framework with low-level HTTP support; it was using NIO but it switched to AIO .
  • Netty is a network framework with HTTP support (low-level), multi-transport, includes NIO and native (the latter uses epoll on Linux).
  • Jetty Async HTTP Client uses NIO.
  • Async HTTP Client wraps either Netty, Grizzly or JDK’s HTTP support.
  • clj-http wraps the Apache HTTP Client.
  • http-kit is an async subset of clj-http implemented partially in Java directly on top of NIO.
  • http async client wraps the Async HTTP Client for Java.

这个列表摘自 High-Concurrency HTTP Clients on the JVM,不止于此,这篇文章重点介绍基于java纤程库quasar的实现的http client库,并比较了性能。我们待会再说。

回到我前面所说的系统,如何能更好的提供性能?有一种方案是借助其它语言的优势,比如Go,让Go来代理完成和B、C、D的请求,系统A通过一个TCP连接与Go程序交流。第三方服务B、C、D的Response结果可以异步地返回给系统A。

Go的优势在于可以实现request-per-goroutine,整个系统中可以有成千上万个goroutine。 goroutine是轻量级的,而且在I/O阻塞的时候可以不占用线程,这让Go可以轻松地处理上万个链接,即使I/O阻塞也没问题。Go和Java之间的通讯协议可以通过Protobuffer来实现,而且它们之间只保留一个TCP连接即可。

当然这种架构的修改带来系统稳定性的降低,服务A和服务B、C、D之间的通讯增加了复杂性。同时,因为是异步方式,服务A的业务也要实现异步方式,否则200个线程依然等待Response的话,还是一个阻塞的架构。

通过测试,这种架构可以带来稳定的吞吐率。 不管服务B、C、D的延迟有多久,A的吞吐率能维持15000 requests/秒。当然Go到B、C、D的并发连接数也有限制,我把最大值调高到20000。

这种曲折的方案的最大的两个弊病就是架构的复杂性以及对原有系统需要进行大的重构。 高复杂性带来的是系统的稳定性的降低,包括部署、维护、网络状况、系统资源等。同时系统要改成异步模型,因为系统业务线程发送Request后不能等待Go返回Response,它需要从Client接收更多的Request,而收到Response之后它才继续执行剩下的业务,只有这样才不会阻塞,进而提到系统的吞吐率。

将系统A改成异步,然后使用HttpUrlConnection线程池行不行?
HttpUrlConnection线程池还是导致和B、C、D通讯的吞吐率下降,但是Go这种方案和B、C、D通讯的吞吐率可以维持一个较高的水平。

考虑到Go的优势,那么能不能在Java中使用类似Go的这种goroutine模型呢?那就是本文要介绍的Java纤程库: [Quasar](http://docs.paralleluniverse.co/quasar/)。

实际测试结果表明Go和Netty都是两种比较好的解决方案,而且Netty的性能惊人的好,不好的地方正如前面所讲,我们需要将代码改成异步的处理。线程池中的业务单元用Netty发送完Request之后,不要等待Response, Response的处理交给另外的线程来处理,同时注意不要在Netty的Handler里面处理业务逻辑。要解决的问题就变成如何更高效的处理Response了,而不是第三方系统阻塞的问题。

quasar初步

以下介绍Java的另一个解决方案,也就是Java中的coroutine库,因为最近刚刚看这个库,感觉挺不错的,而且用它替换Thread改动较少。

Java官方并没有纤程库。但是伟大的社区提供了一个优秀的库,它就是Quasar。

创始人是Ron Pressler和Dafna Pressler,由Y Combinator孵化。

Quasar is a library that provides high-performance lightweight threads, Go-like channels, Erlang-like actors, and other asynchronous programming tools for Java and Kotlin.

Quasar提供了高性能轻量级的线程,提供了类似Go的channel,Erlang风格的actor,以及其它的异步编程的工具,可以用在Java和Kotlin编程语言中。Scala目前的支持还不完善,我想如果这个公司能快速的发展壮大,或者被一些大公司收购的话,对Scala的支持才能提上日程。

你需要把下面的包加入到你的依赖中:

  • Core (必须) co.paralleluniverse:quasar-core:0.7.5[:jdk8] (对于 JDK 8,需要增加jdk8 classifier)
  • Actor co.paralleluniverse:quasar-actors:0.7.5
  • Clustering co.paralleluniverse:quasar-galaxy:0.7.5
  • Reactive Stream co.paralleluniverse:quasar-reactive-streams:0.7.5
  • Kotlin co.paralleluniverse:quasar-kotlin:0.7.5

Quasar fiber依赖java instrumentation修改你的代码,可以在运行时通过java Agent实现,也可以在编译时使用ant task实现。

通过java agent很简单,在程序启动的时候将下面的指令加入到命令行:

1
-javaagent:path-to-quasar-jar.jar

对于maven来说,你可以使用插件maven-dependency-plugin,它会为你的每个依赖设置一个属性,以便在其它地方引用,我们主要想使用 ${co.paralleluniverse:quasar-core:jar}:

1
2
3
4
5
6
7
8
9
10
11
12
<plugin>
<artifactId>maven-dependency-plugin</artifactId>
<version>2.5.1</version>
<executions>
<execution>
<id>getClasspathFilenames</id>
<goals>
<goal>properties</goal>
</goals>
</execution>
</executions>
</plugin>

然后你可以配置exec-maven-plugin或者maven-surefire-plugin加上agent参数,在执行maven任务的时候久可以使用Quasar了。

官方提供了一个Quasar Maven archetype,你可以通过下面的命令生成一个quasar应用原型:

1
2
3
4
5
6
7
8
git clone https://github.com/puniverse/quasar-mvn-archetype
cd quasar-mvn-archetype
mvn install
cd ..
mvn archetype:generate -DarchetypeGroupId=co.paralleluniverse -DarchetypeArtifactId=quasar-mvn-archetype -DarchetypeVersion=0.7.4 -DgroupId=testgrp -DartifactId=testprj
cd testprj
mvn test
mvn clean compile dependency:properties exec:exec

如果你使用gradle,可以看一下gradle项目模版:Quasar Gradle template project

最容易使用Quasar的方案就是使用Java Agent,它可以在运行时instrument程序。如果你想编译的时候就使用AOT instrumentation(Ahead-of-Time),可以使用Ant任务co.paralleluniverse.fibers.instrument.InstrumentationTask,它包含在quasar-core.jar中。

Quasar最主要的贡献就是提供了轻量级线程的实现,叫做fiber(纤程)。Fiber的功能和使用类似Thread, API接口也类似,所以使用起来没有违和感,但是它们不是被操作系统管理的,它们是由一个或者多个ForkJoinPool调度。一个idle fiber只占用400K内存,切换的时候占用更少的CPU,你的应用中可以有上百万的fiber,显然Thread做不到这一点。这一点和Go的goroutine类似。

Fiber并不意味着它可以在所有的场景中都可以替换Thread。当fiber的代码经常会被等待其它fiber阻塞的时候,就应该使用fiber。
对于那些需要CPU长时间计算的代码,很少遇到阻塞的时候,就应该首选thread

以上两条是选择fiber还是thread的判断条件,主要还是看任务是I/O blocking相关还是CPU相关。幸运地是,fiber API使用和thread使用类似,所以代码略微修改久就可以兼容。

Fiber特别适合替换哪些异步回调的代码。使用FiberAsync异步回调很简单,而且性能很好,扩展性也更高。

类似Thread, fiber也是用Fiber类表示:

1
2
3
4
5
6
new Fiber<V>() {
@Override
protected V run() throws SuspendExecution, InterruptedException {
// your code
}
}.start();

与Thread类似,但也有些不同。Fiber可以有一个返回值,类型为泛型V,也可以为空Void。run也可以抛出异常InterruptedException

你可以传递SuspendableRunnableSuspendableCallable 给Fiber的构造函数:

1
2
3
4
5
new Fiber<Void>(new SuspendableRunnable() {
public void run() throws SuspendExecution, InterruptedException {
// your code
}
}).start();

甚至你可以调用Fiber的join方法等待它完成,调用get方法得到它的结果。

Fiber继承Strand类。Strand类代表一个Fiber或者Thread,提供了一些底层的方法。

逃逸的Fiber(Runaway Fiber)是指那些陷入循环而没有block、或者block fiber本身运行的线程的Fiber。偶尔有逃逸的fiber没有问题,但是太频繁会导致性能的下降,因为需要调度器的线程可能都忙于逃逸fiber了。Quasar会监控这些逃逸fiber,你可以通过JMX监控。如果你不想监控,可以设置系统属性co.paralleluniverse.fibers.detectRunawayFibersfalse

fiber中的ThreadLocal是fiber local的。InheritableThreadLocal继承父fiber的值。

Fiber、SuspendableRunnable 、SuspendableCallable 的run方法会抛出SuspendExecution异常。但这并不是真正意义的异常,而是fiber内部工作的机制,通过这个异常暂停因block而需要暂停的fiber。

任何在Fiber中运行的方法,需要声明这个异常(或者标记@Suspendable),都被称为suspendable method。

反射调用通常都被认为是suspendable, Java8 lambda 也被认为是suspendable。不应该将类构造函数或类初始化器标记为suspendable。

synchronized语句块或者方法会阻塞操作系统线程,所以它们不应该标记为suspendable。Blocking线程调用默认也不被quasar允许。但是这两种情况都可以被quasar处理,你需要在Quasar javaagent中分别加上mb参数,或者ant任务中加上allowMonitorsallowBlocking属性。

quasar原理

Quasar最初fork自Continuations Library

如果你了解其它语言的coroutine, 比如Lua,你久比较容易理解quasar的fiber了。 Fiber实质上是 continuation, continuation可以捕获一个计算的状态,可以暂停当前的计算,等隔一段时间可以继续执行。Quasar通过instrument修改suspendable方法。Quasar的调度器使用ForkJoinPool调度这些fiber。

Fiber调度器FiberScheduler是一个高效的、work-stealing、多线程的调度器。

默认的调度器是FiberForkJoinScheduler,但是你可以使用自己的线程池去调度,请参考FiberExecutorScheduler

当一个类被加载时,Quasar的instrumentation模块 (使用 Java agent时) 搜索suspendable 方法。每一个suspendable 方法 f通过下面的方式 instrument:
它搜索对其它suspendable方法的调用。对suspendable方法g的调用,一些代码会在这个调用g的前后被插入,它们会保存和恢复fiber栈本地变量的状态,记录这个暂停点。在这个“suspendable function chain”的最后,我们会发现对Fiber.park的调用。park暂停这个fiber,扔出 SuspendExecution异常。

g block的时候,SuspendExecution异常会被Fiber捕获。 当Fiber被唤醒(使用unpark), 方法f会被调用, 执行记录显示它被block在g的调用上,所以程序会立即跳到f调用g的那一行,然后调用它。最终我们会到达暂停点,然后继续执行。当g返回时, f中插入的代码会恢复f的本地变量。

过程听起来很复杂,但是它只会带来3% ~ 5%的性能的损失。

下面看一个简单的例子, 方法m2声明抛出SuspendExecution异常,方法m1调用m2和m3,所以也声明抛出这个异常,最后这个异常会被Fiber所捕获:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public class Helloworld {
static void m1() throws SuspendExecution, InterruptedException {
String m = “m1”;
System.out.println(“m1 begin”);
m = m2();
m = m3();
System.out.println(“m1 end”);
System.out.println(m);
}
static String m2() throws SuspendExecution, InterruptedException {
return “m2”;
}
static String m3() throws SuspendExecution, InterruptedException {
return “m3”;
}
static public void main(String[] args) throws ExecutionException, InterruptedException {
new Fiber<Void>(“Caller”, new SuspendableRunnable() {
@Override
public void run() throws SuspendExecution, InterruptedException {
m1();
}
}).start();
}
}

反编译这段代码 (一般的反编译软件如jd-gui不能把这段代码反编译java文件,Procyon虽然能反编译,但是感觉反编译有错。所以我们还是看字节码吧):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
@Instrumented(suspendableCallSites={16, 17}, methodStart=13, methodEnd=21, methodOptimized=false)
static void m1()
throws SuspendExecution, InterruptedException
{
// Byte code:
// 0: aconst_null
// 1: astore_3
// 2: invokestatic 88 co/paralleluniverse/fibers/Stack:getStack ()Lco/paralleluniverse/fibers/Stack;
// 5: dup
// 6: astore_1
// 7: ifnull +42 -> 49
// 10: aload_1
// 11: iconst_1
// 12: istore_2
// 13: invokevirtual 92 co/paralleluniverse/fibers/Stack:nextMethodEntry ()I
// 16: tableswitch default:+24->40, 1:+64->80, 2:+95->111
// 40: aload_1
// 41: invokevirtual 96 co/paralleluniverse/fibers/Stack:isFirstInStackOrPushed ()Z
// 44: ifne +5 -> 49
// 47: aconst_null
// 48: astore_1
// 49: iconst_0
// 50: istore_2
// 51: ldc 2
// 53: astore_0
// 54: getstatic 3 java/lang/System:out Ljava/io/PrintStream;
// 57: ldc 4
// 59: invokevirtual 5 java/io/PrintStream:println (Ljava/lang/String;)V
// 62: aload_1
// 63: ifnull +26 -> 89
// 66: aload_1
// 67: iconst_1
// 68: iconst_1
// 69: invokevirtual 100 co/paralleluniverse/fibers/Stack:pushMethod (II)V
// 72: aload_0
// 73: aload_1
// 74: iconst_0
// 75: invokestatic 104 co/paralleluniverse/fibers/Stack:push (Ljava/lang/Object;Lco/paralleluniverse/fibers/Stack;I)V
// 78: iconst_0
// 79: istore_2
// 80: aload_1
// 81: iconst_0
// 82: invokevirtual 108 co/paralleluniverse/fibers/Stack:getObject (I)Ljava/lang/Object;
// 85: checkcast 110 java/lang/String
// 88: astore_0
// 89: invokestatic 6 com/colobu/fiber/Helloworld:m2 ()Ljava/lang/String;
// 92: astore_0
// 93: aload_1
// 94: ifnull +26 -> 120
// 97: aload_1
// 98: iconst_2
// 99: iconst_1
// 100: invokevirtual 100 co/paralleluniverse/fibers/Stack:pushMethod (II)V
// 103: aload_0
// 104: aload_1
// 105: iconst_0
// 106: invokestatic 104 co/paralleluniverse/fibers/Stack:push (Ljava/lang/Object;Lco/paralleluniverse/fibers/Stack;I)V
// 109: iconst_0
// 110: istore_2
// 111: aload_1
// 112: iconst_0
// 113: invokevirtual 108 co/paralleluniverse/fibers/Stack:getObject (I)Ljava/lang/Object;
// 116: checkcast 110 java/lang/String
// 119: astore_0
// 120: invokestatic 7 com/colobu/fiber/Helloworld:m3 ()Ljava/lang/String;
// 123: astore_0
// 124: getstatic 3 java/lang/System:out Ljava/io/PrintStream;
// 127: ldc 8
// 129: invokevirtual 5 java/io/PrintStream:println (Ljava/lang/String;)V
// 132: getstatic 3 java/lang/System:out Ljava/io/PrintStream;
// 135: aload_0
// 136: invokevirtual 5 java/io/PrintStream:println (Ljava/lang/String;)V
// 139: aload_1
// 140: ifnull +7 -> 147
// 143: aload_1
// 144: invokevirtual 113 co/paralleluniverse/fibers/Stack:popMethod ()V
// 147: return
// 148: aload_1
// 149: ifnull +7 -> 156
// 152: aload_1
// 153: invokevirtual 113 co/paralleluniverse/fibers/Stack:popMethod ()V
// 156: athrow
// Line number table:
// Java source line #13 -> byte code offset #51
// Java source line #15 -> byte code offset #54
// Java source line #16 -> byte code offset #62
// Java source line #17 -> byte code offset #93
// Java source line #18 -> byte code offset #124
// Java source line #19 -> byte code offset #132
// Java source line #21 -> byte code offset #139
// Local variable table:
// start length slot name signature
// 53 83 0 m String
// 6 147 1 localStack co.paralleluniverse.fibers.Stack
// 12 99 2 i int
// 1 1 3 localObject Object
// 156 1 4 localSuspendExecution SuspendExecution
// Exception table:
// from to target type
// 49 148 148 finally
// 49 148 156 co/paralleluniverse/fibers/SuspendExecution
// 49 148 156 co/paralleluniverse/fibers/RuntimeSuspendExecution
}

这段反编译的代码显示了方法m被instrument后的样子,虽然我们不能很清楚的看到代码执行的样子,但是也可以大概地看到它实际在方法的最开始加入了此方法的栈信息的检查(#0 ~ #49,如果是第一次运行这个方法,则直接运行,
然后在一些暂停点上加上一些栈压入的处理,并且可以在下次执行的时候直接跳到上次的暂停点上。

官方的工程师关于Quasar的instrument操作如下:

  • Fully analyze the bytecode to find all the calls into suspendable methods. A method that (potentially) calls into other suspendable methods is itself considered suspendable, transitively.
  • Inject minimal bytecode in suspendable methods (and only them) that will manage an user-mode stack, in the following places:
    • At the beginning we’ll check if we’re resuming the fiber and only in this case we’ll jump into the relevant bytecode index.
    • Before a call into another suspendable method we’ll push a snapshot of the current activation frame, including the resume bytecode index; we can do it because we know the structure statically from the analysis phase.
    • After a call into another suspendable method we’ll pop the top activation frame and, if resumed, we’ll restore it in the current fiber.

我并没有更深入的去了解Quasar的实现细节以及调度算法,有兴趣的读者可以翻翻它的代码。如果你有更深入的剖析,请留下相关的地址,以便我加到参考文档中。

曾经, 陆陆续续也有一些Java coroutine的实现(coroutine-libraries), 但是目前来说最好的应该还是Quasar。

Oracle会实现一个官方的纤程库吗?目前来说没有看到这方面的计划,而且从Java的开发进度上来看,这个特性可能是遥遥无期的,所以目前还只能借助社区的力量,从第三方库如Quasar中寻找解决方案。

更多的Quasar知识,比如Channel、Actor、Reactive Stream 的使用可以参考官方的文档,官方也提供了多个例子

Comsat介绍

Comsat又是什么?

Comsat还是Parallel Universe提供的集成Quasar的一套开源库,可以提供web或者企业级的技术,如HTTP服务和数据库访问。

Comsat并不是一套web框架。它并不提供新的API,只是为现有的技术如Servlet、JAX-RS、JDBC等提供Quasar fiber的集成。

它包含非常多的库,比如Spring、ApacheHttpClient、OkHttp、Undertow、Netty、Kafka等。

性能对比

刘小溪在CSDN上写了一篇关于Quasar的文章:次时代Java编程(一):Java里的协程,写的挺好,建议读者读一读。

它参考Skynet的测试写了代码进行对比,这个测试是并发执行整数的累加:
测试结果是Golang花了261毫秒,Quasar花了612毫秒。其实结果还不错,但是文中指出这个测试没有发挥Quasar的性能。因为quasar的性能主要在于阻塞代码的调度上。
虽然文中加入了排序的功能,显示Java要比Golang要好,但是我觉得这又陷入了另外一种错误的比较, Java的排序算法使用TimSort,排序效果相当好,Go的排序效果显然比不上Java的实现,所以最后的测试主要测试排序算法上。 真正要体现Quasar的性能还是测试在有阻塞的情况下fiber的调度性能。

HttpClient

话题扯的越来越远了,拉回来。我最初的目的是要解决的是在第三方服务响应慢的情况下提高系统 A 的吞吐率。最初A是使用200个线程处理业务逻辑,调用第三方服务。因为线程总是被第三方服务阻塞,所以系统A的吞吐率总是很低。

虽然使用Go可以解决这个问题,但是对于系统A的改造比较大,还增加了系统的复杂性。Netty性能好,改动量还可以接受,但是不妨看一下这个场景,系统的问题是由http阻塞引起。

这正是Quasar fiber适合的场景,如果一个Fiber被阻塞,它可以暂时放弃线程,以便线程可以用来执行其它的Fiber。虽然整个集成系统的吞吐率依然很低,这是无法避免的,但是系统的吞吐率确很高。

Comsat提供了Apache Http Client的实现: FiberHttpClientBuilder

1
2
3
4
final CloseableHttpClient client = FiberHttpClientBuilder.
create(2). // use 2 io threads
setMaxConnPerRoute(concurrencyLevel).
setMaxConnTotal(concurrencyLevel).build();

然后在Fiber中久可以调用:

1
String response = client.execute(new HttpGet(“http://localhost:8080”), BASIC_RESPONSE_HANDLER);

你也可以使用异步的HttpClient:

1
2
3
4
5
6
final CloseableHttpAsyncClient client = FiberCloseableHttpAsyncClient.wrap(HttpAsyncClients.
custom().
setMaxConnPerRoute(concurrencyLevel).
setMaxConnTotal(concurrencyLevel).
build());
client.start();

Comsat还提供了Jersey Http Client: AsyncClientBuilder.newClient()

甚至提供了RetrofitOkHttp的实现。

经过测试,虽然随着系统B、C、D的响应时间的拉长,吞吐率有所降低,但是在latency为100毫秒的时候吞吐率依然能达到9900 requests/秒,可以满足我们的需求,而我们的代码改动的比较小。

综上所述,如果想彻底改造系统A,则可以使用Go库重写,或者使用Netty + Rx的方式去处理,都能达到比较好的效果。如果想改动比较小,可以考虑使用quasar替换线程对代码进行维护。

我希望本文不要给读者造成误解,以为Java NIO/Selector这种方式不能解决本文的问题,也就是第三方阻塞的问题。 事实上Java NIO也正是适合解决这样的问题, 比如Netty性能就不错,但是你需要小心的是, 不要让你的这个client对外又变成阻塞的方式,而是程序应该异步的去发送request和处理response。当然本文重点不是介绍这种实现,而是介绍Java的线程库,它可以改造传统的代码,即使有阻塞,也只是阻塞Fiber,而不是阻塞线程,这是另一个解决问题的思路。

另一篇关于Quasar的文档: 继续了解Java的纤程库 – Quasar

参考文档

from:http://colobu.com/2016/07/14/Java-Fiber-Quasar/

快速搭建大数据分析环境

Hadoop 发行版的选择

大数据应用, Hadoop 仅仅是一个基础, 要用起来还需要安装很多组件, 比如Hive, Mahout, Sqoop, ZooKeeper 等等, 不得不需要考虑兼容性的问题: 版本是否兼容,组件是否有冲突,编译能否通过等, 一大堆事情. 真正要在企业中要用Hadoop, 我一般不推荐直接使用apache hadoop, 使用第三方发行包最稳定/最省事了.
第三方发行商, 有 Cloudera, Hortonworks, MapR, Cloudera 用户数最多, 另外 Hadoop之父目前也供职于Cloudera, 选它基本上没错.

我推荐: Cloudera 发行版
***

CDH 和 Cloudera Manager 是什么

CDH (Cloudera’s Distribution, including Apache Hadoop), 是Cloudera发行的Hadoop发行版,基于稳定的Hadoop版, 并集成了许多补丁, 可以直接在生产环境中使用.

Cloudera Manager 是 Cloudera 推出的大数据解决方案, 已经在安装/配置/监控方面做了大量的工作.它不仅包含CDH, 而且集成了很多常用的组件, 比如 HBASE, Hue, Impala, Kudu, Oozie, Kafka, Sentry, Solr, Spark, YARN, ZooKeeper 等, 它分为两个版本Cloudera Express 和 Cloudera Enterprise . Cloudera Express免费使用, Cloudera Enterprise 需要支付费用. Express版和Enterprise版差异不算大, 而且可以商用, 缺的只有非常高级的功能以及官方支持.

Cloudera Express和Enterprise的差异: Express版本最高支持50个节点, 足够大多数商业应用使用. http://www.cloudera.com/documentation/enterprise/latest/topics/cm_ig_feature_differences.html

我推荐: Cloudera Express版

Cloudera 产品下载和安装

考虑到网速和墙的因素, 建议离线的方式安装, 即Manual Installation Using Cloudera Manager Tarballs安装方式.
几个参考文章:
离线安装Cloudera Manager 5和CDH5(最新版5.1.3) 完全教程
Cloudera Manager 5 和 CDH5 本地(离线)安装指南
CDH5 集群中 Spark 集群模式的安装过程配置过程


使用虚拟机搭建体验大数据平台

使用VM是最快的体验环境搭建方式了, Cloudera 提供 QuickStart VM, 我们还有另一个选择, 即 Oracle Big Data Lite VM.
VirtualBox 以及extension pack下载
Cloudera quickstart VM 下载页面 或直接下载链接
Oracle Big data lite VM下载页面:
quickstart VM 配置教程

Cloudera quickstart VM 下载介质较小, 不到5GB, Oracle Big data lite VM大多了, 要30GB. 我推荐Cloudera quickstart VM.
Cloudera quickstart VM中的几个Accounts,
OS:
username: cloudera ,password: cloudera
username: root ,password: cloudera
MySQL:
username: root ,password: cloudera
username: other accounts ,password: cloudera
Hue and Cloudera Manager等服务:
username: cloudera ,password: cloudera

在Oracle VM中, 最重要的东西有:

  • Oracle Enterprise Linux 6.7, 基本上可以等同于CentOS 6.7
  • Oracle Database 12.1, 包括一些大数据方面的增强
  • CDH 5.4.7, 挺新的
  • Cloudera Manager 5.4.7

Oracle VM 推荐的最低配置:

  • Host OS 必须是64 bit
  • 分配 2 core
  • 最少 4 GB 内存
  • 初始分配50GB硬盘空间, 需打开自动扩展

VirtualBox虚拟机的网络设置的注意事项:
VirtualBox虚拟机网络默认采用NAT(网络地址转换模式)模式, 在该模式下, 虚拟机可以通过主机来连接上internet网络, 非常简单, 我也一直使用这种模式.
虚拟机和主机关系:
只能单向访问, 虚拟机可以通过网络访问到主机, 主机无法通过网络访问到虚拟机.
虚拟机和网络其他主机的关系:
只能单向访问, 虚拟机访问到网络上的其他主机, 但这些主机无法访问到虚拟机.
虚拟机和虚拟机的关系:
互相不能访问
主机有没有办法访问虚拟机?
办法是有的, 通过端口转发即可, 其实quickstart VM已经给我们将VM上常用的大数据服务端口作了映射.比如 VM hue 端口 8888, 映射到host的同一端口上了.
为了防止guest OS和host OS的ssh 22端口冲突, 我将VM的22端口映射到2022, 将VM的Oracle 1521端口映射成主机的2521端口.

安装python环境

hdfs client: 我推荐使用 snakebite 这个pure python 版hdfs client 目前还不支持python 3. https://github.com/spotify/snakebite
Anaconda, 因为snakebite 的缘故, 我还是使用 Anaconda Python2.7版本

可用于大数据分析的几个dataset

from:http://www.cnblogs.com/harrychinese/p/big_data_platform_quickstart.html

深度学习框架的评估与比较

人工智能无疑是计算机世界的前沿领域,而深度学习无疑又是人工智能的研究热点,那么现在都有哪些开源的深度学习工具,他们各自的优缺点又是什么呢?最近zer0nbamos在GitHub上发表了一篇文章,对CaffeCNTKTensorFlowTheanoTorch等深度学习工具从网络、模型能力、接口、部署、性能、架构、生态系统、跨平台等方面做了比较

网络和模型能力

Caffe可能是第一个主流的工业级深度学习工具,它开始于2013年底,具有出色的卷积神经网络实现。在计算机视觉领域Caffe依然是最流行的工具包,它有很多扩展,但是由于一些遗留的架构问题,它对递归网络和语言建模的支持很差。此外,在Caffe中图层需要使用C++定义,而网络则使用Protobuf定义。

CNTK由深度学习热潮的发起演讲人创建,目前已经发展成一个通用的、平台独立的深度学习系统。在CNTK中,网络会被指定为向量运算的符号图,运算的组合会形成层。CNTK通过细粒度的构件块让用户不需要使用低层次的语言就能创建新的、复杂的层类型。

TensorFlow是一个理想的RNN(递归神经网络) API和实现,TensorFlow使用了向量运算的符号图方法,使得新网络的指定变得相当容易,但TensorFlow并不支持双向RNN和3D卷积,同时公共版本的图定义也不支持循环和条件控制,这使得RNN的实现并不理想,因为必须要使用Python循环且无法进行图编译优化。

Theano支持大部分先进的网络,现在的很多研究想法都来源于Theano,它引领了符号图在编程网络中使用的趋势。Theano的符号API支持循环控制,让RNN的实现更加容易且高效。

Torch对卷积网络的支持非常好。在TensorFlow和Theano中时域卷积可以通过conv2d来实现,但这样做有点取巧;Torch通过时域卷积的本地接口使得它的使用非常直观。Torch通过很多非官方的扩展支持大量的RNN,同时网络的定义方法也有很多种。但Torch本质上是以图层的方式定义网络的,这种粗粒度的方式使得它对新图层类型的扩展缺乏足够的支持。与Caffe相比,在Torch中定义新图层非常容易,不需要使用C++编程,图层和网络定义方式之间的区别最小。

接口

Caffe支持pycaffe接口,但这仅仅是用来辅助命令行接口的,而即便是使用pycaffe也必须使用protobuf定义模型。

CNTK的使用方式与Caffe相似,也是通过指定配置文件并运行命令行,但CNTK没有Python或者任何其他高级语言的接口。

TensorFlow支持Python和C++两种类型的接口。用户可以在一个相对丰富的高层环境中做实验并在需要本地代码或低延迟的环境中部署模型。

Theano支持Python接口。

Torch运行在LuaJIT上,与C++、C#以及Java等工业语言相比速度非常快,用户能够编写任意类型的计算,不需要担心性能,唯一的问题就是Lua并不是主流的语言。

模型部署

Caffe是基于C++的,因此可以在多种设备上编译,具有跨平台性,在部署方面是最佳选择。

CNTK与Caffe一样也是基于C++并且跨平台的,大部分情况下部署非常简单。但是它不支持ARM架构,这限制了它在移动设备上的能力。

TensorFlow支持C++接口,同时由于它使用了Eigen而不是BLAS类库,所以能够基于ARM架构编译和优化。TensorFlow的用户能够将训练好的模型部署到多种设备上,不需要实现单独的模型解码器或者加载Python/LuaJIT解释器。但是TensorFlow并不支持Windows,因此其模型无法部署到Windows设备上。

Theano缺少底层的接口,并且其Python解释器也很低效,对工业用户而言缺少吸引力。虽然对大的模型其Python开销并不大,但它的限制摆在那,唯一的亮点就是它跨平台,模型能够部署到Windows环境上。

Torch的模型运行需要LuaJIT的支持,虽然这样做对性能的影响并不大,但却对集成造成了很大的障碍,使得它的吸引力不如Caffe/CNTK/TensorFlow等直接支持C++的框架。

性能

在单GPU的场景下,所有这些工具集都调用了cuDNN,因此只要外层的计算或者内存分配差异不大其表现都差不多。本文的性能测试是基于Soumith@FB的ConvNets基准测试来做的。

Caffe 简单快速。

CNTK 简单快速。

TensorFlow仅使用了cuDNN v2,但即使如此它的性能依然要比同样使用cuDNN v2的Torch要慢1.5倍,并且在批大小为128时训练GoogleNet还出现了内存溢出的问题

Theano在大型网络上的性能与Torch7不相上下。但它的主要问题是启动时间特别长,因为它需要将C/CUDA代码编译成二进制,而TensorFlow并没有这个问题。此外,Theano的导入也会消耗时间,并且在导入之后无法摆脱预配置的设备(例如GPU0)。

Torch非常好,没有TensorFlow和Theano的问题。

另外,在多GPU方面,CNTK相较于其他的深度学习工具包表现更好,它实现了1-bit SGD和自适应的minibatching。

架构

Caffe的架构在现在看来算是平均水准,它的主要痛点是图层需要使用C++定义,而模型需要使用protobuf定义。另外,如果想要支持CPU和GPU,用户还必须实现额外的函数,例如Forward_gpuBackward_gpu;对于自定义的层类型,还必须为其分配一个int类型的id,并将其添加到proto文件中。

TensorFlow的架构清晰,采用了模块化设计,支持多种前端和执行平台。

Theano 的架构比较变态,它的整个代码库都是Python的,就连C/CUDA代码也要被打包为Python字符串,这使得它难以导航、调试、重构和维护。

Torch7和nn类库拥有清晰的设计和模块化的接口。

跨平台

Caffe、CNTK和Theano都能在所有的系统上运行,而TensorFlow和Torch则不支持Windows。

from:http://www.infoq.com/cn/news/2016/01/evaluation-comparison-deep-learn

分布式系统的事务处理

当我们在生产线上用一台服务器来提供数据服务的时候,我会遇到如下的两个问题:

1)一台服务器的性能不足以提供足够的能力服务于所有的网络请求。

2)我们总是害怕我们的这台服务器停机,造成服务不可用或是数据丢失。

于是我们不得不对我们的服务器进行扩展,加入更多的机器来分担性能上的问题,以及来解决单点故障问题。 通常,我们会通过两种手段来扩展我们的数据服务:

1)数据分区:就是把数据分块放在不同的服务器上(如:uid % 16,一致性哈希等)。

2)数据镜像:让所有的服务器都有相同的数据,提供相当的服务。

对于第一种情况,我们无法解决数据丢失的问题,单台服务器出问题时,会有部分数据丢失。所以,数据服务的高可用性只能通过第二种方法来完成——数据的冗余存储(一般工业界认为比较安全的备份数应该是3份,如:Hadoop和Dynamo)。 但是,加入更多的机器,会让我们的数据服务变得很复杂,尤其是跨服务器的事务处理,也就是跨服务器的数据一致性。这个是一个很难的问题。 让我们用最经典的Use Case:“A帐号向B帐号汇钱”来说明一下,熟悉RDBMS事务的都知道从帐号A到帐号B需要6个操作:

  1. 从A帐号中把余额读出来。
  2. 对A帐号做减法操作。
  3. 把结果写回A帐号中。
  4. 从B帐号中把余额读出来。
  5. 对B帐号做加法操作。
  6. 把结果写回B帐号中。

为了数据的一致性,这6件事,要么都成功做完,要么都不成功,而且这个操作的过程中,对A、B帐号的其它访问必需锁死,所谓锁死就是要排除其它的读写操作,不然会有脏数据的问题,这就是事务。那么,我们在加入了更多的机器后,这个事情会变得复杂起来:

1)在数据分区的方案中:如果A帐号和B帐号的数据不在同一台服务器上怎么办?我们需要一个跨机器的事务处理。也就是说,如果A的扣钱成功了,但B的加钱不成功,我们还要把A的操作给回滚回去。这在跨机器的情况下,就变得比较复杂了。

2)在数据镜像的方案中:A帐号和B帐号间的汇款是可以在一台机器上完成的,但是别忘了我们有多台机器存在A帐号和B帐号的副本。如果对A帐号的汇钱有两个并发操作(要汇给B和C),这两个操作发生在不同的两台服务器上怎么办?也就是说,在数据镜像中,在不同的服务器上对同一个数据的写操作怎么保证其一致性,保证数据不冲突?

同时,我们还要考虑性能的因素,如果不考虑性能的话,事务得到保证并不困难,系统慢一点就行了。除了考虑性能外,我们还要考虑可用性,也就是说,一台机器没了,数据不丢失,服务可由别的机器继续提供。 于是,我们需要重点考虑下面的这么几个情况:

1)容灾:数据不丢、结点的Failover

2)数据的一致性:事务处理

3)性能:吞吐量 、 响应时间

前面说过,要解决数据不丢,只能通过数据冗余的方法,就算是数据分区,每个区也需要进行数据冗余处理。这就是数据副本:当出现某个节点的数据丢失时可以从副本读到,数据副本是分布式系统解决数据丢失异常的唯一手段。所以,在这篇文章中,简单起见,我们只讨论在数据冗余情况下考虑数据的一致性和性能的问题。简单说来:

1)要想让数据有高可用性,就得写多份数据。

2)写多份的问题会导致数据一致性的问题。

3)数据一致性的问题又会引发性能问题

这就是软件开发,按下了葫芦起了瓢。

一致性模型

说起数据一致性来说,简单说有三种类型(当然,如果细分的话,还有很多一致性模型,如:顺序一致性,FIFO一致性,会话一致性,单读一致性,单写一致性,但为了本文的简单易读,我只说下面三种):

1)Weak 弱一致性:当你写入一个新值后,读操作在数据副本上可能读出来,也可能读不出来。比如:某些cache系统,网络游戏其它玩家的数据和你没什么关系,VOIP这样的系统,或是百度搜索引擎(呵呵)。

2)Eventually 最终一致性:当你写入一个新值后,有可能读不出来,但在某个时间窗口之后保证最终能读出来。比如:DNS,电子邮件、Amazon S3,Google搜索引擎这样的系统。

3)Strong 强一致性:新的数据一旦写入,在任意副本任意时刻都能读到新值。比如:文件系统,RDBMS,Azure Table都是强一致性的。

从这三种一致型的模型上来说,我们可以看到,Weak和Eventually一般来说是异步冗余的,而Strong一般来说是同步冗余的,异步的通常意味着更好的性能,但也意味着更复杂的状态控制。同步意味着简单,但也意味着性能下降。 好,让我们由浅入深,一步一步地来看有哪些技术:

Master-Slave

首先是Master-Slave结构,对于这种加构,Slave一般是Master的备份。在这样的系统中,一般是如下设计的:

1)读写请求都由Master负责。

2)写请求写到Master上后,由Master同步到Slave上。

从Master同步到Slave上,你可以使用异步,也可以使用同步,可以使用Master来push,也可以使用Slave来pull。 通常来说是Slave来周期性的pull,所以,是最终一致性。这个设计的问题是,如果Master在pull周期内垮掉了,那么会导致这个时间片内的数据丢失。如果你不想让数据丢掉,Slave只能成为Read-Only的方式等Master恢复。

当然,如果你可以容忍数据丢掉的话,你可以马上让Slave代替Master工作(对于只负责计算的结点来说,没有数据一致性和数据丢失的问题,Master-Slave的方式就可以解决单点问题了) 当然,Master Slave也可以是强一致性的, 比如:当我们写Master的时候,Master负责先写自己,等成功后,再写Slave,两者都成功后返回成功,整个过程是同步的,如果写Slave失败了,那么两种方法,一种是标记Slave不可用报错并继续服务(等Slave恢复后同步Master的数据,可以有多个Slave,这样少一个,还有备份,就像前面说的写三份那样),另一种是回滚自己并返回写失败。(注:一般不先写Slave,因为如果写Master自己失败后,还要回滚Slave,此时如果回滚Slave失败,就得手工订正数据了)你可以看到,如果Master-Slave需要做成强一致性有多复杂。

Master-Master

Master-Master,又叫Multi-master,是指一个系统存在两个或多个Master,每个Master都提供read-write服务。这个模型是Master-Slave的加强版,数据间同步一般是通过Master间的异步完成,所以是最终一致性。 Master-Master的好处是,一台Master挂了,别的Master可以正常做读写服务,他和Master-Slave一样,当数据没有被复制到别的Master上时,数据会丢失。很多数据库都支持Master-Master的Replication的机制。

另外,如果多个Master对同一个数据进行修改的时候,这个模型的恶梦就出现了——对数据间的冲突合并,这并不是一件容易的事情。看看Dynamo的Vector Clock的设计(记录数据的版本号和修改者)就知道这个事并不那么简单,而且Dynamo对数据冲突这个事是交给用户自己搞的。就像我们的SVN源码冲突一样,对于同一行代码的冲突,只能交给开发者自己来处理。(在本文后后面会讨论一下Dynamo的Vector Clock)

Two/Three Phase Commit

这个协议的缩写又叫2PC,中文叫两阶段提交。在分布式系统中,每个节点虽然可以知晓自己的操作时成功或者失败,却无法知道其他节点的操作的成功或失败。当一个事务跨越多个节点时,为了保持事务的ACID特性,需要引入一个作为协调者的组件来统一掌控所有节点(称作参与者)的操作结果并最终指示这些节点是否要把操作结果进行真正的提交(比如将更新后的数据写入磁盘等等)。 两阶段提交的算法如下:

第一阶段

  1. 协调者会问所有的参与者结点,是否可以执行提交操作。
  2. 各个参与者开始事务执行的准备工作:如:为资源上锁,预留资源,写undo/redo log……
  3. 参与者响应协调者,如果事务的准备工作成功,则回应“可以提交”,否则回应“拒绝提交”。

第二阶段

  • 如果所有的参与者都回应“可以提交”,那么,协调者向所有的参与者发送“正式提交”的命令。参与者完成正式提交,并释放所有资源,然后回应“完成”,协调者收集各结点的“完成”回应后结束这个Global Transaction。
  • 如果有一个参与者回应“拒绝提交”,那么,协调者向所有的参与者发送“回滚操作”,并释放所有资源,然后回应“回滚完成”,协调者收集各结点的“回滚”回应后,取消这个Global Transaction。

我们可以看到,2PC说白了就是第一阶段做Vote,第二阶段做决定的一个算法,也可以看到2PC这个事是强一致性的算法。在前面我们讨论过Master-Slave的强一致性策略,和2PC有点相似,只不过2PC更为保守一些——先尝试再提交。 2PC用的是比较多的,在一些系统设计中,会串联一系列的调用,比如:A -> B -> C -> D,每一步都会分配一些资源或改写一些数据。比如我们B2C网上购物的下单操作在后台会有一系列的流程需要做。如果我们一步一步地做,就会出现这样的问题,如果某一步做不下去了,那么前面每一次所分配的资源需要做反向操作把他们都回收掉,所以,操作起来比较复杂。现在很多处理流程(Workflow)都会借鉴2PC这个算法,使用 try -> confirm的流程来确保整个流程的能够成功完成。 举个通俗的例子,西方教堂结婚的时候,都有这样的桥段:

1)牧师分别问新郎和新娘:你是否愿意……不管生老病死……(询问阶段)

2)当新郎和新娘都回答愿意后(锁定一生的资源),牧师就会说:我宣布你们……(事务提交)

这是多么经典的一个两阶段提交的事务处理。 另外,我们也可以看到其中的一些问题, A)其中一个是同步阻塞操作,这个事情必然会非常大地影响性能。 B)另一个主要的问题是在TimeOut上,比如,

1)如果第一阶段中,参与者没有收到询问请求,或是参与者的回应没有到达协调者。那么,需要协调者做超时处理,一旦超时,可以当作失败,也可以重试。

2)如果第二阶段中,正式提交发出后,如果有的参与者没有收到,或是参与者提交/回滚后的确认信息没有返回,一旦参与者的回应超时,要么重试,要么把那个参与者标记为问题结点剔除整个集群,这样可以保证服务结点都是数据一致性的。

3)糟糕的情况是,第二阶段中,如果参与者收不到协调者的commit/fallback指令,参与者将处于“状态未知”阶段,参与者完全不知道要怎么办,比如:如果所有的参与者完成第一阶段的回复后(可能全部yes,可能全部no,可能部分yes部分no),如果协调者在这个时候挂掉了。那么所有的结点完全不知道怎么办(问别的参与者都不行)。为了一致性,要么死等协调者,要么重发第一阶段的yes/no命令。

两段提交最大的问题就是第3)项,如果第一阶段完成后,参与者在第二阶没有收到决策,那么数据结点会进入“不知所措”的状态,这个状态会block住整个事务。也就是说,协调者Coordinator对于事务的完成非常重要,Coordinator的可用性是个关键。 因些,我们引入三段提交,三段提交在Wikipedia上的描述如下,他把二段提交的第一个段break成了两段:询问,然后再锁资源。最后真正提交。三段提交的示意图如下:

三段提交的核心理念是:在询问的时候并不锁定资源,除非所有人都同意了,才开始锁资源

理论上来说,如果第一阶段所有的结点返回成功,那么有理由相信成功提交的概率很大。这样一来,可以降低参与者Cohorts的状态未知的概率。也就是说,一旦参与者收到了PreCommit,意味他知道大家其实都同意修改了。这一点很重要。下面我们来看一下3PC的状态迁移图:(注意图中的虚线,那些F,T是Failuer或Timeout,其中的:状态含义是 q – Query,a – Abort,w – Wait,p – PreCommit,c – Commit)

从上图的状态变化图我们可以从虚线(那些F,T是Failuer或Timeout)看到——如果结点处在P状态(PreCommit)的时候发生了F/T的问题,三段提交比两段提交的好处是,三段提交可以继续直接把状态变成C状态(Commit),而两段提交则不知所措

其实,三段提交是一个很复杂的事情,实现起来相当难,而且也有一些问题。

看到这里,我相信你有很多很多的问题,你一定在思考2PC/3PC中各种各样的失败场景,你会发现Timeout是个非常难处理的事情,因为网络上的Timeout在很多时候让你无所事从,你也不知道对方是做了还是没有做。于是你好好的一个状态机就因为Timeout成了个摆设

一个网络服务会有三种状态:1)Success,2)Failure,3)Timeout,第三个绝对是恶梦,尤其在你需要维护状态的时候

Two Generals Problem(两将军问题)

Two Generals Problem 两将军问题是这么一个思维性实验问题: 有两支军队,它们分别有一位将军领导,现在准备攻击一座修筑了防御工事的城市。这两支军队都驻扎在那座城市的附近,分占一座山头。一道山谷把两座山分隔开来,并且两位将军唯一的通信方式就是派各自的信使来往于山谷两边。不幸的是,这个山谷已经被那座城市的保卫者占领,并且存在一种可能,那就是任何被派出的信使通过山谷是会被捕。 请注意,虽然两位将军已经就攻击那座城市达成共识,但在他们各自占领山头阵地之前,并没有就进攻时间达成共识。两位将军必须让自己的军队同时进攻城市才能取得成功。因此,他们必须互相沟通,以确定一个时间来攻击,并同意就在那时攻击。如果只有一个将军进行攻击,那么这将是一个灾难性的失败。 这个思维实验就包括考虑他们如何去做这件事情。下面是我们的思考:

1)第一位将军先发送一段消息“让我们在上午9点开始进攻”。然而,一旦信使被派遣,他是否通过了山谷,第一位将军就不得而知了。任何一点的不确定性都会使得第一位将军攻击犹豫,因为如果第二位将军不能在同一时刻发动攻击,那座城市的驻军就会击退他的军队的进攻,导致他的军对被摧毁。

2)知道了这一点,第二位将军就需要发送一个确认回条:“我收到您的邮件,并会在9点的攻击。”但是,如果带着确认消息的信使被抓怎么办?所以第二位将军会犹豫自己的确认消息是否能到达。

3)于是,似乎我们还要让第一位将军再发送一条确认消息——“我收到了你的确认”。然而,如果这位信使被抓怎么办呢?

4)这样一来,是不是我们还要第二位将军发送一个“确认收到你的确认”的信息。

靠,于是你会发现,这事情很快就发展成为不管发送多少个确认消息,都没有办法来保证两位将军有足够的自信自己的信使没有被敌军捕获。

这个问题是无解的。两个将军问题和它的无解证明首先由E.A.Akkoyunlu,K.Ekanadham和R.V.Huber于1975年在《一些限制与折衷的网络通信设计》一文中发表,就在这篇文章的第73页中一段描述两个黑帮之间的通信中被阐明。 1978年,在Jim Gray的《数据库操作系统注意事项》一书中(从第465页开始)被命名为两个将军悖论。作为两个将军问题的定义和无解性的证明的来源,这一参考被广泛提及。

这个实验意在阐明:试图通过建立在一个不可靠的连接上的交流来协调一项行动的隐患和设计上的巨大挑战。

从工程上来说,一个解决两个将军问题的实际方法是使用一个能够承受通信信道不可靠性的方案,并不试图去消除这个不可靠性,但要将不可靠性削减到一个可以接受的程度。比如,第一位将军排出了100位信使并预计他们都被捕的可能性很小。在这种情况下,不管第二位将军是否会攻击或者受到任何消息,第一位将军都会进行攻击。另外,第一位将军可以发送一个消息流,而第二位将军可以对其中的每一条消息发送一个确认消息,这样如果每条消息都被接收到,两位将军会感觉更好。然而我们可以从证明中看出,他们俩都不能肯定这个攻击是可以协调的。他们没有算法可用(比如,收到4条以上的消息就攻击)能够确保防止仅有一方攻击。再者,第一位将军还可以为每条消息编号,说这是1号,2号……直到n号。这种方法能让第二位将军知道通信信道到底有多可靠,并且返回合适的数量的消息来确保最后一条消息被接收到。如果信道是可靠的话,只要一条消息就行了,其余的就帮不上什么忙了。最后一条和第一条消息丢失的概率是相等的。

两将军问题可以扩展成更变态的拜占庭将军问题 (Byzantine Generals Problem),其故事背景是这样的:拜占庭位于现在土耳其的伊斯坦布尔,是东罗马帝国的首都。由于当时拜占庭罗马帝国国土辽阔,为了防御目的,因此每个军队都分隔很远,将军与将军之间只能靠信差传消息。 在战争的时候,拜占庭军队内所有将军必需达成一致的共识,决定是否有赢的机会才去攻打敌人的阵营。但是,军队可能有叛徒和敌军间谍,这些叛徒将军们会扰乱或左右决策的过程。这时候,在已知有成员谋反的情况下,其余忠诚的将军在不受叛徒的影响下如何达成一致的协议,这就是拜占庭将军问题。

Paxos算法

Wikipedia上的各种Paxos算法的描述非常详细,大家可以去围观一下。

Paxos 算法解决的问题是在一个可能发生上述异常的分布式系统中如何就某个值达成一致,保证不论发生以上任何异常,都不会破坏决议的一致性。一个典型的场景是,在一个分布式数据库系统中,如果各节点的初始状态一致,每个节点都执行相同的操作序列,那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列,需要在每一条指令上执行一个「一致性算法」以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中,是分布式计算中的重要问题。从20世纪80年代起对于一致性算法的研究就没有停止过。

Notes:Paxos算法是莱斯利·兰伯特(Leslie Lamport,就是 LaTeX 中的”La”,此人现在在微软研究院)于1990年提出的一种基于消息传递的一致性算法。由于算法难以理解起初并没有引起人们的重视,使Lamport在八年后1998年重新发表到ACM Transactions on Computer Systems上(The Part-Time Parliament)。即便如此paxos算法还是没有得到重视,2001年Lamport 觉得同行无法接受他的幽默感,于是用容易接受的方法重新表述了一遍(Paxos Made Simple)。可见Lamport对Paxos算法情有独钟。近几年Paxos算法的普遍使用也证明它在分布式一致性算法中的重要地位。2006年Google的三篇论文初现“云”的端倪,其中的Chubby Lock服务使用Paxos作为Chubby Cell中的一致性算法,Paxos的人气从此一路狂飙。(Lamport 本人在 他的blog 中描写了他用9年时间发表这个算法的前前后后)

注:Amazon的AWS中,所有的云服务都基于一个ALF(Async Lock Framework)的框架实现的,这个ALF用的就是Paxos算法。我在Amazon的时候,看内部的分享视频时,设计者在内部的Principle Talk里说他参考了ZooKeeper的方法,但他用了另一种比ZooKeeper更易读的方式实现了这个算法。

简单说来,Paxos的目的是让整个集群的结点对某个值的变更达成一致。Paxos算法基本上来说是个民主选举的算法——大多数的决定会成个整个集群的统一决定。任何一个点都可以提出要修改某个数据的提案,是否通过这个提案取决于这个集群中是否有超过半数的结点同意(所以Paxos算法需要集群中的结点是单数)。

这个算法有两个阶段(假设这个有三个结点:A,B,C):

第一阶段:Prepare阶段

A把申请修改的请求Prepare Request发给所有的结点A,B,C。注意,Paxos算法会有一个Sequence Number(你可以认为是一个提案号,这个数不断递增,而且是唯一的,也就是说A和B不可能有相同的提案号),这个提案号会和修改请求一同发出,任何结点在“Prepare阶段”时都会拒绝其值小于当前提案号的请求。所以,结点A在向所有结点申请修改请求的时候,需要带一个提案号,越新的提案,这个提案号就越是是最大的。

如果接收结点收到的提案号n大于其它结点发过来的提案号,这个结点会回应Yes(本结点上最新的被批准提案号),并保证不接收其它<n的提案。这样一来,结点上在Prepare阶段里总是会对最新的提案做承诺。

优化:在上述 prepare 过程中,如果任何一个结点发现存在一个更高编号的提案,则需要通知 提案人,提醒其中断这次提案。

第二阶段:Accept阶段

如果提案者A收到了超过半数的结点返回的Yes,然后他就会向所有的结点发布Accept Request(同样,需要带上提案号n),如果没有超过半数的话,那就返回失败。

当结点们收到了Accept Request后,如果对于接收的结点来说,n是最大的了,那么,它就会修改这个值,如果发现自己有一个更大的提案号,那么,结点就会拒绝修改。

我们可以看以,这似乎就是一个“两段提交”的优化。其实,2PC/3PC都是分布式一致性算法的残次版本,Google Chubby的作者Mike Burrows说过这个世界上只有一种一致性算法,那就是Paxos,其它的算法都是残次品。

我们还可以看到:对于同一个值的在不同结点的修改提案就算是在接收方被乱序收到也是没有问题的。

关于一些实例,你可以看一下Wikipedia中文中的“Paxos样例”一节,我在这里就不再多说了。对于Paxos算法中的一些异常示例,大家可以自己推导一下。你会发现基本上来说只要保证有半数以上的结点存活,就没有什么问题。

多说一下,自从Lamport在1998年发表Paxos算法后,对Paxos的各种改进工作就从未停止,其中动作最大的莫过于2005年发表的Fast Paxos。无论何种改进,其重点依然是在消息延迟与性能、吞吐量之间作出各种权衡。为了容易地从概念上区分二者,称前者Classic Paxos,改进后的后者为Fast Paxos。

总结

下图来自:Google App Engine的co-founder Ryan Barrett在2009年的google i/o上的演讲《Transaction Across DataCenter》(视频: http://www.youtube.com/watch?v=srOgpXECblk

前面,我们说过,要想让数据有高可用性,就需要冗余数据写多份。写多份的问题会带来一致性的问题,而一致性的问题又会带来性能问题。从上图我们可以看到,我们基本上来说不可以让所有的项都绿起来,这就是著名的CAP理论:一致性,可用性,分区容忍性,你只可能要其中的两个。

NWR模型

最后我还想提一下Amazon Dynamo的NWR模型。这个NWR模型把CAP的选择权交给了用户,让用户自己的选择你的CAP中的哪两个

所谓NWR模型。N代表N个备份,W代表要写入至少W份才认为成功,R表示至少读取R个备份。配置的时候要求W+R > N。 因为W+R > N, 所以 R > N-W 这个是什么意思呢?就是读取的份数一定要比总备份数减去确保写成功的倍数的差值要大。

也就是说,每次读取,都至少读取到一个最新的版本。从而不会读到一份旧数据。当我们需要高可写的环境的时候,我们可以配置W = 1 如果N=3 那么R = 3。 这个时候只要写任何节点成功就认为成功,但是读的时候必须从所有的节点都读出数据。如果我们要求读的高效率,我们可以配置 W=N R=1。这个时候任何一个节点读成功就认为成功,但是写的时候必须写所有三个节点成功才认为成功。

NWR模型的一些设置会造成脏数据的问题,因为这很明显不是像Paxos一样是一个强一致的东西,所以,可能每次的读写操作都不在同一个结点上,于是会出现一些结点上的数据并不是最新版本,但却进行了最新的操作。

所以,Amazon Dynamo引了数据版本的设计。也就是说,如果你读出来数据的版本是v1,当你计算完成后要回填数据后,却发现数据的版本号已经被人更新成了v2,那么服务器就会拒绝你。版本这个事就像“乐观锁”一样。

但是,对于分布式和NWR模型来说,版本也会有恶梦的时候——就是版本冲的问题,比如:我们设置了N=3 W=1,如果A结点上接受了一个值,版本由v1 -> v2,但还没有来得及同步到结点B上(异步的,应该W=1,写一份就算成功),B结点上还是v1版本,此时,B结点接到写请求,按道理来说,他需要拒绝掉,但是他一方面并不知道别的结点已经被更新到v2,另一方面他也无法拒绝,因为W=1,所以写一分就成功了。于是,出现了严重的版本冲突。

Amazon的Dynamo把版本冲突这个问题巧妙地回避掉了——版本冲这个事交给用户自己来处理。

于是,Dynamo引入了Vector Clock(矢量钟?!)这个设计。这个设计让每个结点各自记录自己的版本信息,也就是说,对于同一个数据,需要记录两个事:1)谁更新的我,2)我的版本号是什么。

下面,我们来看一个操作序列:

1)一个写请求,第一次被节点A处理了。节点A会增加一个版本信息(A,1)。我们把这个时候的数据记做D1(A,1)。 然后另外一个对同样key的请求还是被A处理了于是有D2(A,2)。这个时候,D2是可以覆盖D1的,不会有冲突产生。

2)现在我们假设D2传播到了所有节点(B和C),B和C收到的数据不是从客户产生的,而是别人复制给他们的,所以他们不产生新的版本信息,所以现在B和C所持有的数据还是D2(A,2)。于是A,B,C上的数据及其版本号都是一样的。

3)如果我们有一个新的写请求到了B结点上,于是B结点生成数据D3(A,2; B,1),意思是:数据D全局版本号为3,A升了两新,B升了一次。这不就是所谓的代码版本的log么?

4)如果D3没有传播到C的时候又一个请求被C处理了,于是,以C结点上的数据是D4(A,2; C,1)。

5)好,最精彩的事情来了:如果这个时候来了一个读请求,我们要记得,我们的W=1 那么R=N=3,所以R会从所有三个节点上读,此时,他会读到三个版本:

    • A结点:D2(A,2)
    • B结点:D3(A,2;  B,1);
    • C结点:D4(A,2;  C,1)

6)这个时候可以判断出,D2已经是旧版本(已经包含在D3/D4中),可以舍弃。

7)但是D3和D4是明显的版本冲突。于是,交给调用方自己去做版本冲突处理。就像源代码版本管理一样。

很明显,上述的Dynamo的配置用的是CAP里的A和P。

我非常推大家都去看看这篇论文:《Dynamo:Amazon’s Highly Available Key-Value Store》,如果英文痛苦,你可以看看译文(译者不详)。

from:http://coolshell.cn/articles/10910.html