要理解DoS攻击的实现原理，必须要对TCP有一定了解。
 
转载自：http://www.cnblogs.com/superfox/articles/3749362.html
 
1.何为DoS？
 
DoS（Denial of Service）的含义即让目标机器停止提供服务或资源访问。相当于在某家店客满的时候，不再接受更多的客人，后来的客人只能在外面等着。
 
2.熟悉TCP 
  
 要理解DoS，首先要对TCP有足够的了解。TCP是在不可靠的因特网中提供可靠的、端对端的字节流通讯协议。在常见的TCP/IP通信中，IP层不保证数据包正确传送到目的地，TCP则从本地机器中接受数据流，然后将其分成不超过64K字节的数据片段，每个数据片段作为单独的IP数据包发送出去。最后在目的机器中组合成完整的数据流，TCP协议必须保证可靠性。
 
TCP传输中，发送方和接收方以数据段的形式交换数据，一个数据段包含固定的20字节+可选部分+数据。当发送方将数据段发送出去后，将启动一个定时器，接收方在接受到数据段后，将回传一个数据段，其中包含一个确认序号，表示希望收到的下一个数据段的顺序号。如果发送方在收到回传数据前定时器超时了，将判断为数据丢失，发送方将重新发送该数据段。在整个过程中，关键信息都在tcp数据头中。
 
3.TCP数据头
 
32位序号：是指发送数据包的第一个字节的序列号，
 
32位确认序号：确认序号是希望接收的字节号。以上两者均是32位。
 
4位首部长度（Data offset）：表明TCP头包含多少个32位字，用来确定TCP头的长度，因为头中有可选字段长度是不固定的（ ？）。
 
6位保留位：暂时没用，目前均为0。
 
接下来是6个比较重要的标志，它们与DoS攻击都非常相关：
 
URG:紧急指针使能位，要用到后面的紧急指针时置1。用来避免TCP流中断。
 
ACK:确认序号使能位，置1时表示确认序号有用，为0时则忽略确认序号。
 
PSH:置1时请求的数据段在接收方得到之后即可送至应用程序，而无需等到缓冲区满。
 
RST:用于复位由于某些原因导致的连接错误，也用于拒绝非法数据和请求。如果接收到RST位时，通常是发生了某些错误。
 
SYN (Synchronize Sequence Number):用于建立连接，在连接请求中，SYN=1，ACK=0，连接响应时，SYN=1，ACK=1。即两者是用于区分请求和相应。
 
FIN (no more data from sender):用于释放连接，表明发送方已经没有数据要送了。
 
接下里继续介绍16位的窗口指针：表示确认了字节后还可以发送多少字节。为0时，表示已经收到了包括确认号-1在内的所有数据段。
 
接下来的校验和紧急指针就不介绍了。
 
4.TCP三次握手
 
了解了TCP数据头，接下来就该看看三次握手过程是如何实现的，DoS攻击就是利用握手过程中的漏洞来进行的。

TCP三次握手的过程如下：
 
客户端发送SYN（SEQ=x）报文给服务器端，进入SYN_SEND状态。 
 服务器端收到SYN报文，回应一个SYN （SEQ=y）ACK(ACK=x+1）报文，进入SYN_RECV状态。 
 客户端收到服务器端的SYN报文，回应一个ACK(ACK=y+1）报文，进入Established状态。 
 三次握手完成，TCP客户端和服务器端成功地建立连接，可以开始传输数据了。下面以一个具体的示例把上述过程再描述一遍，尤其注意表述中哪些是说使能位，哪些是说序号。 
 1.客户端发送一个带SYN位的请求（此时SYN标志位为1，ACK标志位为0，因为请求不需要用到确认号），向服务器表明连接请求，假定请求序号为10，那么“32位序号”（SYN）=10，确认序号(ACK)=0 。发送之后，等待服务器的反应。
 
 2.服务收到该请求报文后，检查是否在LISTEN的指定端口，如果不是则拒绝，是的话就接受请求：假定服务器自身的SYN内码为100，确认序号则是客户端请求序号+1，即10+1=11，所以发送响应报文SYN=100，ACK=11(两个使能位均为1)

 3.客户端接收到该消息后，将发送最后一个连接确认到服务器。SYN位是服务器发送的ACK位，而ACK位则是服务器发送的SYN位+1，即SYN=11，ACK=101。至此，连接建立，可以开始发送数据了。

理解难点：三次握手的宏观过程很好理解，但是微观细节有一点绕。需要把握两点，SYN和ACK的标志位只能取0或1，它们只是使能标志，起辅助作用。上述过程的描述中更多指的是它们分别对应的序号内容，SYN对应于TCP头中的“32位序号”，ACK对应于“32位确认序号”。另外一个把握的难点在于，客户端与服务器端之间两个序号内容的交叉交换，特别要体会ACK=对方SYN+1的这种处理方式的目的所在。
 
5.未连接队列(服务器的缓冲区队列Backlog Queue)
 
服务器不会在每次接收到SYN请求的时候立即与客户端建立连接，而是为连接请求分配内存空间，建立会话，并放到一个等待队列之中。如果这个队列已满，就不再接受新的请求，即新的请求将被直接丢弃，这就是拒绝服务。

如果服务器接收到一个RST置位的信息，就判断这是一个有错误的数据段，会根据客户端IP，把对应的连接从缓冲队列中清除掉。这对IP欺骗有影响，也可以作为DoS攻击。

通过了解TCP协议和连接过程，我们要对Server进行DoS攻击，只需要抓住两点：

a.让服务器的缓冲区满，不接受新的请求；

b.使用IP欺骗，使得正常连接被复位，从而影响合法用户。

这两点是DoS攻击的基本思想，具体实现起来有如下方法：
 
SYN FLOOD
 
利用服务器的连接缓冲区，和特殊程序，设置TCP的Header，向服务器不断成倍发送具有只有SYN标志的TCP连接请求。当服务器接收之后，判断为均是没有建立起来的连接请求，于是给这些请求建立会话，排到缓冲区队列中。

直到你发送的SYN请求超过了服务器的缓冲区，服务器便不再接受其他的合法请求了。你可以持续的进行SYN请求，从而致使缓冲区里都是你发送的SYN请求。
 
IP欺骗DoS攻击
 
这种攻击利用RST位来实现。假设有一个合法用户（1.1.1.1）与服务器建立了正常的连接，攻击者构造攻击TCP数据，伪装自己的IP也是1.1.1.1，并向服务器发送一个带有RST位的数据段。此时服务器收到该数据段后，便认为从1.1.1.1发送的请求连接有错，便从缓冲区中将该连接清除，从而导致合法用户与服务器断开了连接。如果合法用户要继续传输数据，就得重新发送合法的连接请求。

在进行IP欺骗DoS攻击时，通常伪造大量的合法用户IP进行攻击，向目标发送RST数据，使得服务器拒绝对合法用户服务。
 
带宽DoS攻击
 
 如果你的连接带宽足够大，而服务器的带宽有限，你可以通过发送大量请求来攻击，以消耗服务器的缓冲区和带宽。若配合SYN进行，威力不小。这种属于初级DoS攻击，对攻击者资源要求较高。
 
自身消耗的DoS攻击
 
这种攻击方法比较古老，只有老式的系统有这种bug，比如Win95，Cisco IOSv.10.x等过时的系统。

这种攻击是将请求客户端IP和端口弄成主机的IP端口相同，发送给主机。使得主机自己给自己发送TCP请求连接。这种自连接的行为将很快耗费资源导致当机。目前这种攻击对于身份认证系统还是威胁巨大。（ ？）



以上这些攻击方法都是充分利用了TCP协议的漏洞，还有其他DoS攻击手段：
 
塞满服务器硬盘
 
如果服务器可以没有限制的执行写操作，那么都能成为塞满硬盘造成DoS攻击的主要途径。

1.发送垃圾邮件：通常邮件服务器与WEB服务器都放在一起，破坏者通过发送大量的垃圾邮件，将邮件队列塞满，从而把邮箱撑爆或是硬盘塞满。

2.填满日志记录：入侵者通过构造大量的错误信息，让服务器记录这些信息，甚至可能造成日志文件非常庞杂，塞满硬盘。同时，让管理员痛苦的面对大量的日志文件，极难发现其入侵的真正途径。

3.合理利用策略：一般服务器都有关于账户锁定的策略，如某账户连续3次登录失败，则会自动锁定。这点也会被破坏者利用。他们伪装一个合法账号登录多次，致使该账户被锁定，然后合法用户便无法登录了。（这种攻击方法真是无聊到爆！）

 
采样的几种方法
 
拒绝采样
蒙特卡罗法采样
Metropolis-Hastings算法
 


 采样是指通过模拟的方式来采集符合某个分布
$p(x)$的一些样本，一般来说，要采集的分布比较复杂。
 
拒绝采样
 
拒绝采样，也叫接受-拒绝采样。顾名思义，在采样过程中，我们会接受一些样本，也会拒绝一些样本，使得样本最终的分布符合期望。
 
假设原始分布$p(x)$难以直接采样，我们先将$p(x)$归一化，得到$\hat{p}(x)$。然后引入一个比较容易采样的分布$q(x)$和一个常数$k$，使得$kq(x)$可以覆盖$\hat{p}(x)$，即$kq(x)>\hat{p}(x)$，$q(x)$为提议分布。
 
比如我们要采集一个分布$p(x)=\frac{1}{2}\frac{1}{\sqrt{2\pi \sigma }}\exp -\frac{(x-0.3{)}^2}{2{\sigma }^2}+\frac{3}{2}\frac{1}{\sqrt{2\pi \sigma }}\exp -\frac{-(x-0.8{)}^2}{2{\sigma }^2}$，其归一化后多了一个系数$\frac{1}{0.632455}$。我们选择正态分布$q(x)=\frac{1}{\sqrt{2\pi \sigma }}\exp -\frac{(x-0.6{)}^2}{2\ast 0.4^2}$为提议分布，$k$取为10。如下图所示：
 
 观测$\hat{p}(x)$的分布，我们在0到1.2之间根据提议分布抽取样本$\hat{x}$，计算$\alpha (\hat{x})=\frac{\hat{p}(\hat{x})}{kq(\hat{x})}$，并以$\alpha (\hat{x})$的概率接受这个样本。
 
def normal(x,u,sigma):
  p=np.exp(-(x-u)**2/(2*sigma**2))/(np.sqrt(2*np.pi)*sigma)
  return p
  
def f1(x):
  sigma=0.1  
  return (0.5/np.sqrt(2*np.pi*sigma)*np.exp(-(x-0.3)**2/2.0/sigma**2)+1.5/np.sqrt(2.0*np.pi*sigma)*np.exp(-(x-0.8)**2/2.0/sigma**2))/0.632455
  
x_t=[0]
for t in range(100000):
  
  x_=np.random.normal(0.6,0.4)
  alpha=f1(x_)/5/normal(x_,0.6,0.4)
  u=np.random.uniform(0,1)
  if u<alpha:
    x_t.append(x_)
 
最终采样结果如下：
 
 
拒绝采样法的难点在于：如何找到合适的提议分布，尤其是当样本维度很高的时候。
 
蒙特卡罗法采样
 
在高维空间中，蒙特卡罗法是一种更好的采样方法。其核心思想是将采样过程看作一个马尔可夫链。$x_1,x_2,...,x_{t-1},x_t,x_{t+1},...$.
 第$t+1$次的采样依赖于第$t$次抽取的样本$x_t$和状态转移分布$q(x|x_t)$。如果这个马尔可夫链的平稳分布为$p(x)$，那么在状态平稳时抽取的样本就服从$p(x)$的分布。
 
Metropolis-Hastings算法
 
Metropolis-Hastings算法简称MH算法，是一种常用的蒙特卡罗采样法。
 
在MH算法中，假设第$t$次采样的样本为$x_t$，首先根据提议分布$q(x|x_t)$抽取一个样本$\hat{x}$，并以概率$A(\hat{x},x_t)$来接受$\hat{x}$作为第$t+1$次的采样样本$x_{t+1}$。
 $A(\hat{x},x_t)=\text{min}(1,\frac{p(\hat{x})q(x_t|\hat{x})}{p(x_t)q(\hat{x}|x_t)})$
 这里相当于对马尔可夫链的状态转移概率做了修正:$q^{\prime }(\hat{x}|x_t)=q(\hat{x}|x_t)A(\hat{x},x_t)$
 修正后的马尔可夫链可达平稳状态，且平稳分布为$p(x)$。
 其证明可以参考：《神经网络与深度学习》，邱锡鹏，2019 中关于采样的章节。
 
我们在接受-拒绝采样中举的例子，也可以用MH方法来进行采样。
 
################ M-H sampling
x_m=[0]
for t in range(200000):
  x_=np.random.normal(x_m[-1],0.1)
#  alpha=f1(x_)*normal(x_,x_m[-1],0.1)/f1(x_m[-1])/normal(x_m[-1],x_,0.1)
  alpha=f1(x_)*normal(x_m[-1],x_,0.1)/f1(x_m[-1])/normal(x_,x_m[-1],0.1)
#  print(normal(x_m[-1],x_,1)/normal(x_,x_m[-1],1))
  alpha=min(alpha,1)
  u=np.random.uniform(0,1)
  if u<alpha:
    x_m.append(x_)
 
结果如下：
 

 
 
 1. 前言
 
 
熟悉机器学习的童鞋都知道，优化方法是其中一个非常重要的话题，最常见的情形就是利用目标函数的导数通过多次迭代来求解无约束最优化问题。实现简单，coding 方便，是训练模型的必备利器之一。
 
 
 
 
 
 2. 几个数学概念
 
 
 1) 梯度（一阶导数）
 
 
考虑一座在 (x1, x2) 点高度是 f(x1, x2) 的山。那么，某一点的梯度方向是在该点坡度最陡的方向，而梯度的大小告诉我们坡度到底有多陡。注意，梯度也可以告诉我们不在最快变化方向的其他方向的变化速度（二维情况下，按照梯度方向倾斜的圆在平面上投影成一个椭圆）。对于一个含有 n 个变量的标量函数，即函数输入一个 n 维 的向量，输出一个数值，梯度可以定义为：
 
 
 
 
  
  
 
 
 
2) Hesse 矩阵（二阶导数）
 
 
Hesse 矩阵常被应用于牛顿法解决的大规模优化问题(后面会介绍)，主要形式如下：
 
 
 
 
  
  
 当 f(x) 为二次函数时，梯度以及 Hesse 矩阵很容易求得。二次函数可以写成下列形式： 
 
 
 
 
 
  
  
 其中 x为列向量，A 是 n 阶对称矩阵，b 是 n 维列向量， c 是常数。
 f(x) 梯度是 Ax+b, Hesse 矩阵等于 A
 。 
 
 
 
3) Jacobi 矩阵
 
 
Jacobi 矩阵实际上是向量值函数的梯度矩阵，假设F:Rn→Rm 是一个从n维欧氏空间转换到m维欧氏空间的函数。这个函数由m个实函数组成:。这些函数的偏导数(如果存在)可以组成一个m行n列的矩阵(m by n)，这就是所谓的雅可比矩阵：
 
 
 
 
  
  
 总结一下, 
 
 
 
a) 如果 f(x) 是一个标量函数，那么雅克比矩阵是一个向量，等于 f(x) 的梯度， Hesse 矩阵是一个二维矩阵。如果 f(x) 是一个向量值函数，那么Jacobi 矩阵是一个二维矩阵，Hesse 矩阵是一个三维矩阵。
 
 
b) 梯度是 Jacobian 矩阵的特例，梯度的 jacobian 矩阵就是 Hesse 矩阵（一阶偏导与二阶偏导的关系）。
 
 
 
 
 
 3. 优化方法
 
 
1) Gradient Descent
 
 
Gradient descent 又叫 steepest descent，是利用一阶的梯度信息找到函数局部最优解的一种方法，也是机器学习里面最简单最常用的一种优化方法。Gradient descent 是 line search 方法中的一种，主要迭代公式如下：
 
 
 
 
  
  
 
 
其中，

是第 k 次迭代我们选择移动的方向，在 steepest descent 中，移动的方向设定为梯度的负方向，

是第 k 次迭代用 line search 方法选择移动的距离，每次移动的距离系数可以相同，也可以不同，有时候我们也叫学习率（learning rate）。
 
 
 在数学上，移动的距离可以通过 line search 令导数为零找到该方向上的最小值，但是在实际编程的过程中，这样计算的代价太大，我们一般可以将它设定位一个常量。考虑一个包含三个变量的函数，计算梯度得到。设定 learning rate = 1，算法代码如下： 
 
 
 
 
  
# Code from Chapter 11 of Machine Learning: An Algorithmic Perspective
# by Stephen Marsland (http://seat.massey.ac.nz/personal/s.r.marsland/MLBook.html)

# Gradient Descent using steepest descent

from numpy import *

def Jacobian(x):
    return array([x[0], 0.4*x[1], 1.2*x[2]])

def steepest(x0):

    i = 0 
    iMax = 10
    x = x0
    Delta = 1
    alpha = 1

    while i<iMax and Delta>10**(-5):
        p = -Jacobian(x)
        xOld = x
        x = x + alpha*p
        Delta = sum((x-xOld)**2)
        print 'epoch', i, ':'
        print x, '\n'
        i += 1

x0 = array([-2,2,-2])
steepest(x0)
 
 
 
 
Steepest gradient 方法得到的是局部最优解，如果目标函数是一个凸优化问题，那么局部最优解就是全局最优解，理想的优化效果如下图，值得注意一点的是，每一次迭代的移动方向都与出发点的等高线垂直：
 
 
 
 
  
  
 需要指出的是，在某些情况下，最速下降法存在锯齿现象（ zig-zagging）将会导致收敛速度变慢: 
 
 
 
粗略来讲，在二次函数中，椭球面的形状受 hesse 矩阵的条件数影响，长轴与短轴对应矩阵的最小特征值和最大特征值的方向，其大小与特征值的平方根成反比，最大特征值与最小特征值相差越大，椭球面越扁，那么优化路径需要走很大的弯路，计算效率很低。
 
 
2) Newton’s method
 
 
在最速下降法中，我们看到，该方法主要利用的是目标函数的局部性质，具有一定的“盲目性”。牛顿法则是利用局部的一阶和二阶偏导信息，推测整个目标函数的形状，进而可以求得出近似函数的全局最小值，然后将当前的最小值设定近似函数的最小值。相比最速下降法，牛顿法带有一定对全局的预测性，收敛性质也更优良。牛顿法的主要推导过程如下：
 
 
第一步，利用 Taylor 级数求得原目标函数的二阶近似：
 
 
 
 
  
  
 第二步，把 x 看做自变量， 所有带有 x^k 的项看做常量，令一阶导数为 0 ，即可求近似函数的最小值： 
 
 
 
 
 
  
  
 即： 
 
 
 
 
 
  
  
 第三步，将当前的最小值设定近似函数的最小值（或者乘以步长)。 
 
 
 
与 1) 中优化问题相同，牛顿法的代码如下：
 
 
Newton.py
 
 
 
  
# Code from Chapter 11 of Machine Learning: An Algorithmic Perspective
# by Stephen Marsland (http://seat.massey.ac.nz/personal/s.r.marsland/MLBook.html)

# Gradient Descent using Newton's method
from numpy import *

def Jacobian(x):
    return array([x[0], 0.4*x[1], 1.2*x[2]])

def Hessian(x):
    return array([[1,0,0],[0,0.4,0],[0,0,1.2]])

def Newton(x0):

    i = 0
    iMax = 10
    x = x0
    Delta = 1
    alpha = 1
    
    while i<iMax and Delta>10**(-5):
        p = -dot(linalg.inv(Hessian(x)),Jacobian(x))
        xOld = x
        x = x + alpha*p
        Delta = sum((x-xOld)**2)
        i += 1
    print x
    
x0 = array([-2,2,-2])
Newton(x0)
 
 
 
 
上面例子中由于目标函数是二次凸函数，Taylor 展开等于原函数，所以能一次就求出最优解。
 
 
牛顿法主要存在的问题是：
 
 
Hesse 矩阵不可逆时无法计算
矩阵的逆计算复杂为 n 的立方，当问题规模比较大时，计算量很大，解决的办法是采用拟牛顿法如 BFGS, L-BFGS, DFP, Broyden’s Algorithm 进行近似。
如果初始值离局部极小值太远，Taylor 展开并不能对原函数进行良好的近似
 
 
3) Levenberg–Marquardt Algorithm
 
 
Levenberg–Marquardt algorithm 能结合以上两种优化方法的优点，并对两者的不足做出改进。与 line search 的方法不同，LMA 属于一种“信赖域法”(trust region)，牛顿法实际上也可以看做一种信赖域法，即利用局部信息对函数进行建模近似，求取局部最小值。所谓的信赖域法，就是从初始点开始，先假设一个可以信赖的最大位移 s（牛顿法里面 s 为无穷大），然后在以当前点为中心，以 s 为半径的区域内，通过寻找目标函数的一个近似函数（二次的）的最优点，来求解得到真正的位移。在得到了位移之后，再计算目标函数值，如果其使目标函数值的下降满足了一定条件，那么就说明这个位移是可靠的，则继续按此规则迭代计算下去；如果其不能使目标函数值的下降满足一定的条件，则应减小信赖域的范围，再重新求解。
 
 
LMA 最早提出是用来解决最小二乘法曲线拟合的优化问题的，对于随机初始化的已知参数 beta， 求得的目标值为：
 
 
 
 
  
  
 对拟合曲线函数进行一阶 Jacobi 矩阵的近似： 
 
 
 
 
 
  
  
 进而推测出 S 函数的周边信息： 
 
 
 
 
 
  
  
 位移是多少时得到 S 函数的最小值呢？通过几何的概念，当残差垂直于 J 矩阵的 span 空间时， S 取得最小（至于为什么？请参考之前博客的最后一部分) 
 
 
 
 
 
  
  
 我们将这个公式略加修改，加入阻尼系数得到： 
 
 
 
 
 
  
  
 就是莱文贝格－马夸特方法。这种方法只计算了一阶偏导，而且不是目标函数的 Jacobia 矩阵，而是拟合函数的 Jacobia 矩阵。当大的时候可信域小，这种算法会接近最速下降法，小的时候可信域大，会接近高斯-牛顿方法。 
 
 
 
算法过程如下：
 
 
给定一个初识值 x0
当并且没有到达最大迭代次数时
重复执行: 
   
算出移动向量
计算更新值：
计算目标函数真实减少量与预测减少量的比率
if，接受更新值
else if，说明近似效果很好，接受更新值，扩大可信域（即减小阻尼系数）
else: 目标函数在变大，拒绝更新值，减小可信域（即增加阻尼系数）
 
直到达到最大迭代次数
 
 
维基百科在介绍 Gradient descent 时用包含了细长峡谷的 Rosenbrock function
 
 
 
 
  
  
 展示了 zig-zagging 锯齿现象： 
 
 
 
 
 
  
  
 用 LMA 优化效率如何。套用到我们之前 LMA 公式中，有： 
 
 
 
 
 
  
  
 代码如下： 
 
 
 
LevenbergMarquardt.py
 
 
 
  
# Code from Chapter 11 of Machine Learning: An Algorithmic Perspective
# by Stephen Marsland (http://seat.massey.ac.nz/personal/s.r.marsland/MLBook.html)

# The Levenberg Marquardt algorithm
from numpy import *

def function(p):
    r = array([10*(p[1]-p[0]**2),(1-p[0])])
    fp = dot(transpose(r),r) #= 100*(p[1]-p[0]**2)**2 + (1-p[0])**2
    J = (array([[-20*p[0],10],[-1,0]]))
    grad = dot(transpose(J),transpose(r))
    return fp,r,grad,J

def lm(p0,tol=10**(-5),maxits=100):
    
    nvars=shape(p0)[0]
    nu=0.01
    p = p0
    fp,r,grad,J = function(p)
    e = sum(dot(transpose(r),r))
    nits = 0
    while nits<maxits and linalg.norm(grad)>tol:
        nits += 1
        fp,r,grad,J = function(p)
        H=dot(transpose(J),J) + nu*eye(nvars)

        pnew = zeros(shape(p))
        nits2 = 0
        while (p!=pnew).all() and nits2<maxits:
            nits2 += 1
            dp,resid,rank,s = linalg.lstsq(H,grad)
            pnew = p - dp
            fpnew,rnew,gradnew,Jnew = function(pnew)
            enew = sum(dot(transpose(rnew),rnew))
            rho = linalg.norm(dot(transpose(r),r)-dot(transpose(rnew),rnew))
            rho /= linalg.norm(dot(transpose(grad),pnew-p))
            
            if rho>0:
                update = 1
                p = pnew
                e = enew
                if rho>0.25:
                    nu=nu/10
            else: 
                nu=nu*10
                update = 0
        print fp, p, e, linalg.norm(grad), nu

p0 = array([-1.92,2])
lm(p0)
 
 
 
 
大概 5 次迭代就可以得到最优解 (1, 1).
 
 
Levenberg–Marquardt algorithm 对局部极小值很敏感，维基百科举了一个二乘法曲线拟合的例子，当使用不同的初始值时，得到的结果差距很大，我这里也有 python 代码，就不细说了。
 
 
4) Conjugate Gradients
 
 
共轭梯度法也是优化模型经常经常要用到的一个方法，背后的数学公式和原理稍微复杂一些，光这一个优化方法就可以写一篇很长的博文了，所以这里并不打算详细讲解每一步的推导过程，只简单写一下算法的实现过程。与最速梯度下降的不同，共轭梯度的优点主要体现在选择搜索方向上。在了解共轭梯度法之前，我们首先简单了解一下共轭方向：
 
 
 
 
  
  
 共轭方向和马氏距离的定义有类似之处，他们都考虑了全局的数据分布。如上图，d(1) 方向与二次函数的等值线相切，d(1) 的共轭方向 d(2) 则指向椭圆的中心。所以对于二维的二次函数，如果在两个共轭方向上进行一维搜索，经过两次迭代必然达到最小点。前面我们说过，等值线椭圆的形状由 Hesse 矩阵决定，那么，上图的两个方向关于 Hessen 矩阵正交，共轭方向的定义如下： 
 
 
 
 
 
  
  
 如果椭圆是一个正圆， Hessen 矩阵是一个单位矩阵，上面等价于欧几里得空间中的正交。 
 
 
 
在优化过程中，如果我们确定了移动方向（GD：垂直于等值线，CG：共轭方向），然后在该方向上搜索极小值点（恰好与该处的等值线相切），然后移动到最小值点，重复以上过程，那么 Gradient Descent 和 Conjugate gradient descent 的优化过程可以用下图的绿线与红线表示：
 
 
 
 
  
  
 讲了这么多，共轭梯度算法究竟是如何算的呢？ 
 
 
 
给定一个出发点 x0 和一个停止参数 e, 第一次移动方向为最速下降方向:
while: 
   
用 Newton-Raphson 迭代计算移动距离，以便在该搜索方向移动到极小，公式就不写了，具体思路就是利用一阶梯度的信息向极小值点跳跃搜索
移动当前的优化解 x：
用 Gram-Schmidt 方法构造下一个共轭方向，即, 按照的确定公式又可以分为 FR 方法和 PR 和 HS 等。
 
 
 
在很多的资料中，介绍共轭梯度法都举了一个求线性方程组 Ax = b 近似解的例子，实际上就相当于这里所说的
 
 
还是用最开始的目标函数     来编写共轭梯度法的优化代码：
 
 
 
 
 
 
  
# Code from Chapter 11 of Machine Learning: An Algorithmic Perspective
# by Stephen Marsland (http://seat.massey.ac.nz/personal/s.r.marsland/MLBook.html)

# The conjugate gradients algorithm

from numpy import *

def Jacobian(x):
    #return array([.4*x[0],2*x[1]])
    return array([x[0], 0.4*x[1], 1.2*x[2]])

def Hessian(x):
    #return array([[.2,0],[0,1]])
    return array([[1,0,0],[0,0.4,0],[0,0,1.2]])

def CG(x0):

    i=0
    k=0

    r = -Jacobian(x0)
    p=r

    betaTop = dot(r.transpose(),r)
    beta0 = betaTop

    iMax = 3
    epsilon = 10**(-2)
    jMax = 5

    # Restart every nDim iterations
    nRestart = shape(x0)[0]
    x = x0

    while i < iMax and betaTop > epsilon**2*beta0:
        j=0
        dp = dot(p.transpose(),p)
        alpha = (epsilon+1)**2
        # Newton-Raphson iteration
        while j < jMax and alpha**2 * dp > epsilon**2:
            # Line search
            alpha = -dot(Jacobian(x).transpose(),p) / (dot(p.transpose(),dot(Hessian(x),p)))
            print "N-R",x, alpha, p
            x = x + alpha * p
            j += 1
        print x
        # Now construct beta
        r = -Jacobian(x)
        print "r: ", r
        betaBottom = betaTop
        betaTop = dot(r.transpose(),r)
        beta = betaTop/betaBottom
        print "Beta: ",beta
        # Update the estimate
        p = r + beta*p
        print "p: ",p
        print "----"
        k += 1
        
        if k==nRestart or dot(r.transpose(),p) <= 0:
            p = r
            k = 0
            print "Restarting"
        i +=1

    print x

x0 = array([-2,2,-2])
CG(x0)
 
 
 

 看到耗子叔这篇对于分布式事务处理的几种方式写的很清晰，原文：https://coolshell.cn/articles/10910.html
 
 当我们在生产线上用一台服务器来提供数据服务的时候，我会遇到如下的两个问题：
 
 1）一台服务器的性能不足以提供足够的能力服务于所有的网络请求。
 
 2）我们总是害怕我们的这台服务器停机，造成服务不可用或是数据丢失。
 
 于是我们不得不对我们的服务器进行扩展，加入更多的机器来分担性能上的问题，以及来解决单点故障问题。 通常，我们会通过两种手段来扩展我们的数据服务：
 
 1）数据分区：就是把数据分块放在不同的服务器上（如：uid % 16，一致性哈希等）。
 
 2）数据镜像：让所有的服务器都有相同的数据，提供相当的服务。
 
 对于第一种情况，我们无法解决数据丢失的问题，单台服务器出问题时，会有部分数据丢失。所以，数据服务的高可用性只能通过第二种方法来完成——数据的冗余存储（一般工业界认为比较安全的备份数应该是3份，如：Hadoop和Dynamo）。 但是，加入更多的机器，会让我们的数据服务变得很复杂，尤其是跨服务器的事务处理，也就是跨服务器的数据一致性。这个是一个很难的问题。 让我们用最经典的Use Case：“A帐号向B帐号汇钱”来说明一下，熟悉RDBMS事务的都知道从帐号A到帐号B需要6个操作：
 
从A帐号中把余额读出来。
对A帐号做减法操作。
把结果写回A帐号中。
从B帐号中把余额读出来。
对B帐号做加法操作。
把结果写回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特性，需要引入一个作为协调者的组件来统一掌控所有节点(称作参与者)的操作结果并最终指示这些节点是否要把操作结果进行真正的提交(比如将更新后的数据写入磁盘等等)。 两阶段提交的算法如下：
 
 第一阶段：
 
协调者会问所有的参与者结点，是否可以执行提交操作。
各个参与者开始事务执行的准备工作：如：为资源上锁，预留资源，写undo/redo log……
参与者响应协调者，如果事务的准备工作成功，则回应“可以提交”，否则回应“拒绝提交”。
 
 第二阶段：
 
如果所有的参与者都回应“可以提交”，那么，协调者向所有的参与者发送“正式提交”的命令。参与者完成正式提交，并释放所有资源，然后回应“完成”，协调者收集各结点的“完成”回应后结束这个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》，如果英文痛苦，你可以看看译文（译者不详）。