Category Archives: 架构

WebSocket实战

前言

互联网发展到现在,早已超越了原始的初衷,人类从来没有像现在这样依赖过他;也正是这种依赖,促进了互联网技术的飞速发展。而终端设备的创新与发展,更加速了互联网的进化;

HTTP/1.1规范发布于1999年,同年12月24日,HTML4.01规范发布;尽管已到2012年,但HTML4.01仍是主流;虽然HTML5的草案已出现了好几个年头,但转正日期,遥遥无期,少则三五年,多则数十年;而HTML5的客户代理(对于一般用户而言,就是浏览器),则已百家争鸣,星星向荣;再加上移动终端的飞速发展,在大多数情况下,我们都可以保证拥有一个HTML5的运行环境,所以,我们来分享一下HTML5中的WebSocket协议;

本文包含以下六个方面:
1. WebSocket的前世今生
2. WebSocket是什么
3. 为什么使用WebSocket
4. 搭建WebSocket服务器
5. WebSocket API
6. 实例解析

以上六点分为两大块,前3点侧重理论,主要让大家明白WebSocket是什么,而后3点则结合代码实战,加深对WebSocket的认知。

一、WebSocket的前世今生

Web 应用的信息交互过程通常是客户端通过浏览器发出一个请求,服务器端接收和审核完请求后进行处理并返回结果给客户端,然后客户端浏览器将信息呈现出来,这种机制对于信息变化不是特别频繁的应用尚能相安无事,但是对于那些实时要求比较高的应用来说就显得捉襟见肘了。我们需要一种高效节能的双向通信机制来保证数据的实时传输。有web TCP之称的WebSocket应运而生,给开发人员提供了一把强有力的武器来解决疑难杂症。
(PS:其实,在早期的HTML5规范中,并没有包含WebSocket的定义,一些早期的HTML5书籍中,完全没有WebSocket的介绍。直到后来,才加入到当前的草案中。)

二、WebSocket是什么?

其实,从背景介绍中,我们大致的可以猜出,WebSocket是干什么用的。前面我们提到,WebSocket有web TCP之称,既然是TCP,肯定是用来做通信的,但是它又有不同的地方,WebSocket作为HTML5中新增的一种通信协议,由通信协议和编程API组成,它能够在浏览器和服务器之间建立双向连接,以基于事件的方式,赋予浏览器原生的实时通信能力,来扩展我们的web应用,增加用户体验,提升应用的性能。何谓双向?服务器端和客户端可以同时发送并响应请求,而不再像HTTP的请求和响应。

三、为什么使用WebSocket

在WebSocket出现之前,我们有一些其它的实时通讯方案,比较常用的有轮询,长轮询,流,还有基于Flash的交换数据的方式,接下来,我们一一分析一下,各种通信方式的特点。

① 轮询
这是最早的一种实现实时web应用的方案;原理比较简单易懂,就是客户端以一定的时间间隔向服务器发送请求,以频繁请求的方式来保持客户端和服务器端的数据同步。但是问题也很明显:当客户端以固定频率向服务器端发送请求时,服务器端的数据可能并没有更新,这样会带来很多无谓的请求,浪费带宽,效率低下。

② 长轮询
长轮询是对定时轮询的改进和提高,目地是为了降低无效的网络传输。当服务器端没有数据更新的时候,连接会保持一段时间周期直到数据或状态改变或者时间过期,通过这种机制来减少无效的客户端和服务器间的交互。当然,如果服务端的数据变更非常频繁的话,这种机制和定时轮询比较起来没有本质上的性能的提高。

③ 流
长轮询是对定时轮询的改进和提高,目地是为了降低无效的网络传输。当服务器端没有数据更新的时候,连接会保持一段时间周期直到数据或状态改变或者时间过期,通过这种机制来减少无效的客户端和服务器间的交互。当然,如果服务端的数据变更非常频繁的话,这种机制和定时轮询比较起来没有本质上的性能的提高。

④ 基于Flash的实时通讯方式
Flash有自己的socket实现,这为实时通信提供了可能。我们可以利用Flash完成数据交换,再利用Flash暴露出相应的接口,方便JavaScript调用,来达到实时传输数据的目的。这种方式比前面三种方式都要高效,而且应用场景比较广泛;因为flash本身的安装率很高;但是在当前的互联网环境下,移动终端对flash的支持并不好,以IOS为主的系统中根本没有flash的存在,而在android阵营中,虽然有flash的支持,但实际的使用效果差强人意,即使是配置较高的移动设备,也很难让人满意。就在前几天(2012年6月底),Adobe官方宣布,不在支持android4.1以后的系统,这基本上宣告了flash在移动终端上的死亡。

下面是轮询和长轮询的信息流转图:

对比完四种不同的实时通信方式,不难发现,除了基于flash的方案外,其它三种方式都是用AJAX方式来模拟实时的效果,每次客户端和服务器端交互时,都是一次完整的HTTP请求和应答的过程,而每一次的HTTP请求和应答都带有完整的HTTP头信息,这就增加每次的数据传输量,而且这些方案中客户端和服务端的编程实现比较复杂。

接下来,我们再来看一下WebSocket,为什么要使用它呢?高效节能,简单易用。
下图是来自websocket.org的测试结果:

在流量和负载增大的情况下,WebSocket 方案相比传统的 Ajax 轮询方案有极大的性能优势;而在开发方面,也十分简单,我们只需要实例化WebSocket,创建连接,查看是否连接成功,然后就可以发送和相应消息了。我们会在后面的实例中去详细的说明API。

四、搭建WebSocket服务器

其实,在服务器的选择上很广,基本上,主流语言都有WebSocket的服务器端实现,而我们作为前端开发工程师,当然要选择现在比较火热的NodeJS作为我们的服务器端环境了。

NodeJS本身并没有原生的WebSocket支持,但是有第三方的实现(大家要是有兴趣的话,完全可以参考WebSocket协议来做自己的实现),我们选择了“ws”作为我们的服务器端实现。

由于本文的重点是讲解WebSocket,所以,对于NodeJS不做过多的介绍,不太熟悉的朋友可以去参考NodeJS入门指南(http://www.nodebeginner.org/index-zh-cn.html)。

安装好NodeJS之后,我们需要安装“ws”,也就是我们的WebSocket实现,安装方法很简单,在终端或者命令行中输入:

npm install ws

,等待安装完成就可以了。

接下来,我们需要启动我们的WebSocket服务。首先,我们需要构建自己的HTTP服务器,在NodeJS中构建一个简单的HTTP服务器很简单,so easy。代码如下:

var app = http.createServer( onRequest ).listen( 8888 );

onRequest()作为回调函数,它的作用是处理请求,然后做出响应,实际上就是根据接收的URL,在服务器上查找相应的资源,最终返回给浏览器。
在构建了HTTP服务器后,我们需要启动WebSocket服务,代码如下:

var WebSocketServer = require('ws').Server;
var wss = new WebSocketServer( { server : app } );

从代码中可以看出,在初始化WebSocket服务时,把我们刚才构建好的HTTP实例传递进去就好。到这里,我们的服务端代码差不多也就编写完成了。怎么样?很简单吧。

五、WebSocket API

上面我们介绍了WebSocket服务端的知识,接下来,我们需要编写客户端代码了。在前面我们说过,客户端的API也是一如既往的简单:

见上图:ready state中定义的是socket的状态,分为connection、open、closing和closed四种状态,从字面上就可以区分出它们所代表的状态。


上图描述的是WebSocket的事件,分为onopen、onerror和onclose;


上图为消息的定义,主要是接收和发送消息。注意:可以发送二进制的数据。

以上个图的具体的含义就不再一一赘述,详细描述请参考:
http://www.w3.org/TR/2012/WD-websockets-20120524/
PS:由于WebSocket API(截止到2012年7月)还是草案,API文档和上文所描述的会有所不同,请以官方文档为主,这也是我为什么不详细描述API中各个属性的原因。

另外一点需要提醒大家的是:在前端开发中,浏览器兼容是必不可少的,而WebSocket在主浏览器中的兼容还是不错的,火狐和Chrome不用说,最新版的支持非常不错,而且支持二进制数据的发送和接收。但是IE9并不支持,对于国内的大多数应用场景,WebSocket无法大规模使用。

截图来自(http://tongji.baidu.com/data/browser),之所以选择百度的统计数据,是因为更加符合国内的实际情况。图中所展示的是2012年4月1日到2012年6月30日之间的统计数据,从图中不难看出IE6.0、奇虎360、IE7.0和IE8.0加起来一共占据了77%的市场,FireFox属于其他,chrome只有5.72%的份额,再一次告诉我们,我们的主战场依然是IE系。

既然是IE系,那么对于WebSocket在实际app中的应用就基本不可能了。但我们完全可以在chrome、FireFox、以及移动版的IOS浏览器中使用它。

六、实例解析

搭建好了服务端,熟悉了API,接下来,我们要开始构建我们的应用了。鉴于WebSocket自身的特点,我们的第一个demo选择了比较常见的聊天程序,我们暂且取名为chat。

说到聊天,大家最先想到的肯定是QQ,没错,我们所实现的应用和QQ类似,而且还是基于web的。因为是demo,我们的功能比较简陋,仅实现了最简单的会话功能。就是启动WebSocket服务器后,客户端发起连接,连接成功后,任意客户端发送消息,都会被服务器广播给所有已连接的客户端,包括自己。

既然需要客户端,我们需要构建一个简单的html页面,页面中样式和元素,大家可以自由发挥,只要能够输入消息,有发送按钮,最后有一个展示消息的区域即可。具体的样子大家可以看附件中的demo。

写玩HTML页面之后,我们需要添加客户端脚本,也就是和WebSocket相关的代码;前面我们说过,WebSocket的API本身很简单,所以,我们的客户端代码也很直接,如下:

var wsServer = 'ws://localhost:8888/';
var websocket = new WebSocket(wsServer);
websocket.binaryType = "arraybuffer";
websocket.onopen = onOpen;
websocket.onclose = onClose;
websocket.onmessage = onMessage;
websocket.onerror = onError;

首先,我们需要指定WebSocket的服务地址,也就是var wsServer = ‘ws://localhost:8888/’;

然后,我们实例化WebSocket,new WebSocket(wsServer),
剩下的就是指定相应的回调函数了,分别是onOpen,onClose,onMessage和onError,对于咱们的实验应用来说,onopen、onclose、onerror甚至可以不管,咱们重点关注一下onmessage。

onmessage()这个回调函数会在客户端收到消息时触发,也就是说,只要服务器端发送了消息,我们就可以通过onmessage拿到发送的数据,既然拿到了数据,接下去该怎么玩,就随便我们了。请看下面的伪代码:

function onMessage(evt) {
	var json = JSON.parse(evt.data);
	commands[json.event](json.data);
}

因为onmessage只接收字符串和二进制类型的数据,如果需要发送json格式的数据,就需要我们转换一下格式,把字符串转换成JSON格式。只要是支持WebSocket,肯定原生支持window.JSON,所以,我们可以直接使用JSON.parse()和JSON.stringify()来进行转换。
转换完成后,我们就得到了我们想要的数据了,接下来所做的工作就是将消息显示出来。实际上就是

Elements.innerHTML += data + '</br>';

上面展现了客户端的代码,服务器端的代码相对要简单一些,因为我们的服务器端使用的是第三方实现,我们只需要做一些初始化工作,然后在接收到消息时,将消息广播出去即可,下面是具体的代码:

var app = http.createServer( onRequest ).listen( 8888 );
var WebSocketServer = require('ws').Server,
	wss = new WebSocketServer( { server : app } );
wss.on('connection', function( ws ) {
	console.log('connection successful!');
	ws.on('message', function( data, flags ) {
		console.log(data);
		//do something here
	});
	ws.on('close', function() {
		console.log('stopping client');
	});
});

我们可以通过wss.clients获得当前已连接的所有客户端,然后遍历,得到实例,调用send()方法发送数据;

var clients = wss.clients, len = clients.length, i = 0;
		for( ; i < len; i = i + 1 ){
			clients[i].send( msg );
		}

说到这里,一个双向通信的实例基本完成,当然,上面都是伪代码,完整的demo请查看附件。

除了常见的聊天程序以外,大家完全可以发挥创意,构建一些“好玩”的应用;
接下来,分享另外一个应用,“你画我猜”这个应用,很多人都接触过,大致上是:某个人在屏幕上画一些图形,这些图片会实时展示在其它人的屏幕上,然后来猜画的是什么。

利用WebSocket和canvas,我们可以很轻松的构建类似的应用。当然,我们这里只是demo,并没有达到产品级的高度,这里只是为大家提供思路;
首先,我们再次明确一下,WebSocket赋予了我们在浏览器端和服务器进行双向通信的能力,这样,我们可以实时的将数据发送给服务器,然后再广播给所有的客户端。这和聊天程序的思路是一致的。

接下来,服务器端的代码不用做任何修改,在html页面中准备一个canvas,作为我们的画布。如何在canvas上用鼠标画图形呢?我们需要监听mousedown、mousemove和mouseup三个鼠标事件。说到这里,大家应该知道怎么做了。没错,就是在按下鼠标的时候,记录当前的坐标,移动鼠标的时候,把坐标发送给服务器,再由服务器把坐标数据广播给所有的客户端,这样就可以在所有的客户端上同步绘画了;最后,mouseup的时候,做一些清理工作就ok了。下面是一些伪代码:

var WhiteBoard = function( socket, canvasId ){
				var lastPoint = null,
					mouseDown = false,
					canvas = getById(canvasId),
					ctx = canvas.getContext('2d');

				var handleMouseDown = function(event) {
					mouseDown = true;
					lastPoint = resolveMousePosition.bind( canvas, event )();
				};

				var handleMouseUp = function(event) {
					mouseDown = false;
					lastPoint = null;
				};

				var handleMouseMove = function(event) {
					if (!mouseDown) { return; }
					var currentPoint = resolveMousePosition.bind( canvas, event )();
					socket.send(JSON.stringify({
						event: 'draw',
						data: {
							points: [
								lastPoint.x,
								lastPoint.y,
								currentPoint.x,
								currentPoint.y
							]
						}
					}));

					lastPoint = currentPoint;
				};			

				var init = function(){
					addEvent( canvas, 'mousedown', handleMouseDown );
					addEvent( canvas, 'mouseup', handleMouseUp );
					addEvent( canvas, 'mousemove', handleMouseMove );

					var img = new Image();
					addEvent( img, 'load', function(e){
						canvas.width = img.width;
						canvas.height = img.height;
						ctx.drawImage( img, 0, 0 );
					} );
					img.src = '/img/diablo3.png';
				};

				var drawLine = function(data) {
					var points = data.points;
					ctx.strokeStyle = 'rgb(255, 15, 255)';
					ctx.beginPath();
					ctx.moveTo( points[0] + 0.5, points[1] + 0.5 );
					ctx.lineTo( points[2] + 0.5, points[3] + 0.5 );
					ctx.stroke();
				};

				function resolveMousePosition(event) {
					var x, y;
					if (event.offsetX) {
						x = event.offsetX;
						y = event.offsetY;
					} else {  //(注意)实际开发中,这样获取鼠标相对canvas的坐标是不对的
						x = event.layerX - this.offsetLeft;
						y = event.layerY - this.offsetTop;
					}
					return { x: x, y: y };
				};

				init();

				return {
					draw : drawLine
					//ctx : ctx,
					//canvas : canvas
				}
			}( websocket, 'drawsomething' );

对于canvas不熟悉的同学,请自己去搜索一下,有许多不错的教程。其它方面,和聊天应用的思路基本一样。

最后,我们需要明确一点,WebSocket本身的优点很明显,但是作为一个正在演变中的web规范,我们必须清楚的认识到WebSocket在构建应用时的一些风险;虽然本身有很多局限性,但是这项技术本身肯定是大势所趋,WebSocket在移动终端,在chrome web store都有用武之地,我们可以进行大胆的尝试,让我们在技术的革新中不被淘汰。

Resources:
http://www.w3.org/TR/websockets/
W3 API的官方文档,有详细的接口设计文档和实现步骤
http://tools.ietf.org/html/rfc6455
WebSocket协议
http://tools.ietf.org/html/rfc6202
Known Issues and Best Practices for the Use of Long Polling and Streaming in Bidirectional HTTP
http://msdn.microsoft.com/en-us/library/ie/hh673567(v=vs.85).aspx
msdn中关于WebSocket的介绍
https://developer.mozilla.org/en/WebSockets
http://caniuse.com/#feat=websockets
Compatibility tables for support of HTML5, CSS3, SVG and more in desktop and mobile browsers.

数据库分库分表

在文章开头先抛几个问题:

  • 什么时候才需要分库分表呢?我们的评判标准是什么?
  • 一张表存储了多少数据的时候,才需要考虑分库分表?
  • 数据增长速度很快,每天产生多少数据,才需要考虑做分库分表?

这些问题你都搞清楚了吗?相信看完这篇文章会有答案。

 

为什么要分库分表?
 
首先回答一下为什么要分库分表,答案很简单:数据库出现性能瓶颈。用大白话来说就是数据库快扛不住了。数据库出现性能瓶颈,对外表现有几个方面:

 

  • 大量请求阻塞

在高并发场景下,大量请求都需要操作数据库,导致连接数不够了,请求处于阻塞状态。

 

  • SQL 操作变慢

如果数据库中存在一张上亿数据量的表,一条 SQL 没有命中索引会全表扫描,这个查询耗时会非常久。

 

  • 存储出现问题

业务量剧增,单库数据量越来越大,给存储造成巨大压力。

 

从机器的角度看,性能瓶颈无非就是CPU、内存、磁盘、网络这些,要解决性能瓶颈最简单粗暴的办法就是提升机器性能,但是通过这种方法成本和收益投入比往往又太高了,不划算,所以重点还是要从软件角度入手。

 

数据库相关优化方案
 
数据库优化方案很多,主要分为两大类:软件层面、硬件层面。软件层面包括:SQL 调优、表结构优化、读写分离、数据库集群、分库分表等;

 

硬件层面主要是增加机器性能。

 

SQL 调优
 
 
SQL 调优往往是解决数据库问题的第一步,往往投入少部分精力就能获得较大的收益。SQL 调优主要目的是尽可能的让那些慢 SQL 变快,手段其实也很简单就是让 SQL 执行尽量命中索引。

 

1)开启慢 SQL 记录
 
如果你使用的是 Mysql,需要在 Mysql 配置文件中配置几个参数即可。 
slow_query_log=onlong_query_time=1slow_query_log_file=/path/to/log

 
2)调优的工具
 

常常会用到 explain 这个命令来查看 SQL 语句的执行计划,通过观察执行结果很容易就知道该 SQL 语句是不是全表扫描、有没有命中索引。

 

select id, age, gender from  user where name = ‘爱笑的架构师’;
返回有一列叫“type”,常见取值有: 

ALL、index、range、 ref、eq_ref、const、system、NULL(从左到右,性能从差到好)

 

ALL 代表这条 SQL 语句全表扫描了,需要优化。一般来说需要达到range 级别及以上。

 

表结构优化
 
 
以一个场景举例说明:“user”表中有 user_id、nickname 等字段,“order”表中有order_id、user_id等字段,如果想拿到用户昵称怎么办?一般情况是通过 join 关联表操作,在查询订单表时关联查询用户表,从而获取导用户昵称。

 

但是随着业务量增加,订单表和用户表肯定也是暴增,这时候通过两个表关联数据就比较费力了,为了取一个昵称字段而不得不关联查询几十上百万的用户表,其速度可想而知。

 

这个时候可以尝试将 nickname 这个字段加到 order 表中(order_id、user_id、nickname),这种做法通常叫做数据库表冗余字段。这样做的好处展示订单列表时不需要再关联查询用户表了。

 

冗余字段的做法也有一个弊端,如果这个字段更新会同时涉及到多个表的更新,因此在选择冗余字段时要尽量选择不经常更新的字段。

 

架构优化
 
 
当单台数据库实例扛不住,我们可以增加实例组成集群对外服务。当发现读请求明显多于写请求时,我们可以让主实例负责写,从实例对外提供读的能力;

 

如果读实例压力依然很大,可以在数据库前面加入缓存如 redis,让请求优先从缓存取数据减少数据库访问。

 

缓存分担了部分压力后,数据库依然是瓶颈,这个时候就可以考虑分库分表的方案了,后面会详细介绍。

 

硬件优化
 
 

硬件成本非常高,一般来说不可能遇到数据库性能瓶颈就去升级硬件。

 

在前期业务量比较小的时候,升级硬件数据库性能可以得到较大提升;但是在后期,升级硬件得到的收益就不那么明显了。

 

分库分表详解
 
单应用单数据库
 
 
在早期创业阶段想做一个商城系统,基本就是一个系统包含多个基础功能模块,最后打包成一个 war 包部署,这就是典型的单体架构应用。

商城项目使用单数据库

 

如上图,商城系统包括主页 Portal 模板、用户模块、订单模块、库存模块等,所有的模块都共有一个数据库,通常数据库中有非常多的表。

 

因为用户量不大,这样的架构在早期完全适用,开发者可以拿着 demo到处找(骗)投资人。

 

一旦拿到投资人的钱,业务就要开始大规模推广,同时系统架构也要匹配业务的快速发展。

 

多应用单数据库
 
 
在前期为了抢占市场,这一套系统不停地迭代更新,代码量越来越大,架构也变得越来越臃肿,现在随着系统访问压力逐渐增加,系统拆分就势在必行了。为了保证业务平滑,系统架构重构也是分了几个阶段进行。

 

第一个阶段将商城系统单体架构按照功能模块拆分为子服务,比如:Portal 服务、用户服务、订单服务、库存服务等。

 

多应用单数据库

 

如上图,多个服务共享一个数据库,这样做的目的是底层数据库访问逻辑可以不用动,将影响降到最低。

 

多应用多数据库
 
随着业务推广力度加大,数据库终于成为了瓶颈,这个时候多个服务共享一个数据库基本不可行了。我们需要将每个服务相关的表拆出来单独建立一个数据库,这其实就是“分库”了。 

单数据库的能够支撑的并发量是有限的,拆成多个库可以使服务间不用竞争,提升服务的性能。

 

多应用多数据库

 

如上图,从一个大的数据中分出多个小的数据库,每个服务都对应一个数据库,这就是系统发展到一定阶段必要要做的“分库”操作。

 

现在非常火的微服务架构也是一样的,如果只拆分应用不拆分数据库,不能解决根本问题,整个系统也很容易达到瓶颈。

 

分表
 
 
说完了分库,那什么时候分表呢?如果系统处于高速发展阶段,拿商城系统来说,一天下单量可能几十万,那数据库中的订单表增长就特别快,增长到一定阶段数据库查询效率就会出现明显下降。

 

因此,当单表数据增量过快,业界流传是超过500万的数据量就要考虑分表了。当然500万只是一个经验值,大家可以根据实际情况做出决策。

 

那如何分表呢?

 

分表有几个维度,一是水平切分和垂直切分,二是单库内分表和多库内分表。

 

1)水平拆分和垂直拆分
 
就拿用户表(user)来说,表中有7个字段:id,name,age,sex,nickname,description,如果 nickname 和 description 不常用,我们可以将其拆分为另外一张表:用户详细信息表,这样就由一张用户表拆分为了用户基本信息表+用户详细信息表,两张表结构不一样相互独立。但是从这个角度来看垂直拆分并没有从根本上解决单表数据量过大的问题,因此我们还是需要做一次水平拆分。

拆分表

 

还有一种拆分方法,比如表中有一万条数据,我们拆分为两张表,id 为奇数的:1,3,5,7……放在 user1, id 为偶数的:2,4,6,8……放在 user2中,这样的拆分办法就是水平拆分了。

 

水平拆分的方式也很多,除了上面说的按照 id 拆表,还可以按照时间维度取拆分,比如订单表,可以按每日、每月等进行拆分。

 

  • 每日表:只存储当天的数据。
  • 每月表:可以起一个定时任务将前一天的数据全部迁移到当月表。
  • 历史表:同样可以用定时任务把时间超过 30 天的数据迁移到 history表。

 

总结一下水平拆分和垂直拆分的特点:

 

  • 垂直切分:基于表或字段划分,表结构不同。
  • 水平切分:基于数据划分,表结构相同,数据不同。

 

2)单库内拆分和多库拆分
 
拿水平拆分为例,每张表都拆分为了多个子表,多个子表存在于同一数据库中。比如下面用户表拆分为用户1表、用户2表。

单库拆分

 

在一个数据库中将一张表拆分为几个子表在一定程度上可以解决单表查询性能的问题,但是也会遇到一个问题:单数据库存储瓶颈。

 

所以在业界用的更多的还是将子表拆分到多个数据库中。比如下图中,用户表拆分为两个子表,两个子表分别存在于不同的数据库中。

 

多库拆分

 

一句话总结:分表主要是为了减少单张表的大小,解决单表数据量带来的性能问题。

 

 
分库分表带来的复杂性
 
既然分库分表这么好,那我们是不是在项目初期就应该采用这种方案呢?不要激动,冷静一下,分库分表的确解决了很多问题,但是也给系统带来了很多复杂性,下面简要说一说。
 
跨库关联查询
 
在单库未拆分表之前,我们可以很方便使用 join 操作关联多张表查询数据,但是经过分库分表后两张表可能都不在一个数据库中,如何使用 join 呢? 

有几种方案可以解决:

 

  • 字段冗余:把需要关联的字段放入主表中,避免 join 操作;
  • 数据抽象:通过ETL等将数据汇合聚集,生成新的表;
  • 全局表:比如一些基础表可以在每个数据库中都放一份;
  • 应用层组装:将基础数据查出来,通过应用程序计算组装;

 

分布式事务
 
 
单数据库可以用本地事务搞定,使用多数据库就只能通过分布式事务解决了。常用解决方案有:基于可靠消息(MQ)的解决方案、两阶段事务提交、柔性事务等。 

排序、分页、函数计算问题
 
 
在使用 SQL 时 order by, limit 等关键字需要特殊处理,一般来说采用分片的思路:先在每个分片上执行相应的函数,然后将各个分片的结果集进行汇总和再次计算,最终得到结果。

 

分布式 ID
 
如果使用 Mysql 数据库在单库单表可以使用 id 自增作为主键,分库分表了之后就不行了,会出现id 重复。 

常用的分布式 ID 解决方案有:

 

  • UUID
  • 基于数据库自增单独维护一张 ID表
  • 号段模式
  • Redis 缓存
  • 雪花算法(Snowflake)
  • 百度uid-generator
  • 美团Leaf
  • 滴滴Tinyid

 

这些方案后面会写文章专门介绍,这里不再展开。

 

多数据源
 
 
分库分表之后可能会面临从多个数据库或多个子表中获取数据,一般的解决思路有:客户端适配和代理层适配。业界常用的中间件有:

 

  • shardingsphere(前身 sharding-jdbc)
  • Mycat

 

 
总结
 
如果出现数据库问题不要着急分库分表,先看一下使用常规手段是否能够解决。分库分表会给系统带来巨大的复杂性,不是万不得已建议不要提前使用。作为系统架构师可以让系统灵活性和可扩展性强,但是不要过度设计和超前设计。在这一点上,架构师一定要有前瞻性,提前做好预判。大家学会了吗?

 

作者丨雷架
来源丨公众号:爱笑的架构师(ID:DancingOnYourCode)
dbaplus社群欢迎广大技术人员投稿,投稿邮箱:editor@dbaplus.cn

A Detailed Look at RFC 8446 (a.k.a. TLS 1.3)

For the last five years, the Internet Engineering Task Force (IETF), the standards body that defines internet protocols, has been working on standardizing the latest version of one of its most important security protocols: Transport Layer Security (TLS). TLS is used to secure the web (and much more!), providing encryption and ensuring the authenticity of every HTTPS website and API. The latest version of TLS, TLS 1.3 (RFC 8446) was published today. It is the first major overhaul of the protocol, bringing significant security and performance improvements. This article provides a deep dive into the changes introduced in TLS 1.3 and its impact on the future of internet security.

An evolution

One major way Cloudflare provides security is by supporting HTTPS for websites and web services such as APIs. With HTTPS (the “S” stands for secure) the communication between your browser and the server travels over an encrypted and authenticated channel. Serving your content over HTTPS instead of HTTP provides confidence to the visitor that the content they see is presented by the legitimate content owner and that the communication is safe from eavesdropping. This is a big deal in a world where online privacy is more important than ever.

The machinery under the hood that makes HTTPS secure is a protocol called TLS. It has its roots in a protocol called Secure Sockets Layer (SSL) developed in the mid-nineties at Netscape. By the end of the 1990s, Netscape handed SSL over to the IETF, who renamed it TLS and have been the stewards of the protocol ever since. Many people still refer to web encryption as SSL, even though the vast majority of services have switched over to supporting TLS only. The term SSL continues to have popular appeal and Cloudflare has kept the term alive through product names like Keyless SSL and Universal SSL.

Timeline

In the IETF, protocols are called RFCs. TLS 1.0 was RFC 2246, TLS 1.1 was RFC 4346, and TLS 1.2 was RFC 5246. Today, TLS 1.3 was published as RFC 8446. RFCs are generally published in order, keeping 46 as part of the RFC number is a nice touch.

TLS 1.2 wears parachute pants and shoulder pads

MC Hammer
MC Hammer, like SSL, was popular in the 90s

Over the last few years, TLS has seen its fair share of problems. First of all, there have been problems with the code that implements TLS, including HeartbleedBERserkgoto fail;, and more. These issues are not fundamental to the protocol and mostly resulted from a lack of testing. Tools like TLS Attacker and Project Wycheproof have helped improve the robustness of TLS implementation, but the more challenging problems faced by TLS have had to do with the protocol itself.

TLS was designed by engineers using tools from mathematicians. Many of the early design decisions from the days of SSL were made using heuristics and an incomplete understanding of how to design robust security protocols. That said, this isn’t the fault of the protocol designers (Paul Kocher, Phil Karlton, Alan Freier, Tim Dierks, Christopher Allen and others), as the entire industry was still learning how to do this properly. When TLS was designed, formal papers on the design of secure authentication protocols like Hugo Krawczyk’s landmark SIGMA paper were still years away. TLS was 90s crypto: It meant well and seemed cool at the time, but the modern cryptographer’s design palette has moved on.

Many of the design flaws were discovered using formal verification. Academics attempted to prove certain security properties of TLS, but instead found counter-examples that were turned into real vulnerabilities. These weaknesses range from the purely theoretical (SLOTH and CurveSwap), to feasible for highly resourced attackers (WeakDHLogJamFREAKSWEET32), to practical and dangerous (POODLEROBOT).

TLS 1.2 is slow

Encryption has always been important online, but historically it was only used for things like logging in or sending credit card information, leaving most other data exposed. There has been a major trend in the last few years towards using HTTPS for all traffic on the Internet. This has the positive effect of protecting more of what we do online from eavesdroppers and injection attacks, but has the downside that new connections get a bit slower.

For a browser and web server to agree on a key, they need to exchange cryptographic data. The exchange, called the “handshake” in TLS, has remained largely unchanged since TLS was standardized in 1999. The handshake requires two additional round-trips between the browser and the server before encrypted data can be sent (or one when resuming a previous connection). The additional cost of the TLS handshake for HTTPS results in a noticeable hit to latency compared to an HTTP alone. This additional delay can negatively impact performance-focused applications.

Defining TLS 1.3

Unsatisfied with the outdated design of TLS 1.2 and two-round-trip overhead, the IETF set about defining a new version of TLS. In August 2013, Eric Rescorla laid out a wishlist of features for the new protocol:
https://www.ietf.org/proceedings/87/slides/slides-87-tls-5.pdf

After some debate, it was decided that this new version of TLS was to be called TLS 1.3. The main issues that drove the design of TLS 1.3 were mostly the same as those presented five years ago:

  • reducing handshake latency
  • encrypting more of the handshake
  • improving resiliency to cross-protocol attacks
  • removing legacy features

The specification was shaped by volunteers through an open design process, and after four years of diligent work and vigorous debate, TLS 1.3 is now in its final form: RFC 8446. As adoption increases, the new protocol will make the internet both faster and more secure.

In this blog post I will focus on the two main advantages TLS 1.3 has over previous versions: security and performance.

Trimming the hedges

hedge
Creative Commons Attribution-Share Alike 3.0

In the last two decades, we as a society have learned a lot about how to write secure cryptographic protocols. The parade of cleverly-named attacks from POODLE to Lucky13 to SLOTH to LogJam showed that even TLS 1.2 contains antiquated ideas from the early days of cryptographic design. One of the design goals of TLS 1.3 was to correct previous mistakes by removing potentially dangerous design elements.

Fixing key exchange

TLS is a so-called “hybrid” cryptosystem. This means it uses both symmetric key cryptography (encryption and decryption keys are the same) and public key cryptography (encryption and decryption keys are different). Hybrid schemes are the predominant form of encryption used on the Internet and are used in SSHIPsecSignalWireGuard and other protocols. In hybrid cryptosystems, public key cryptography is used to establish a shared secret between both parties, and the shared secret is used to create symmetric keys that can be used to encrypt the data exchanged.

As a general rule, public key crypto is slow and expensive (microseconds to milliseconds per operation) and symmetric key crypto is fast and cheap (nanoseconds per operation). Hybrid encryption schemes let you send a lot of encrypted data with very little overhead by only doing the expensive part once. Much of the work in TLS 1.3 has been about improving the part of the handshake, where public keys are used to establish symmetric keys.

RSA key exchange

The public key portion of TLS is about establishing a shared secret. There are two main ways of doing this with public key cryptography. The simpler way is with public-key encryption: one party encrypts the shared secret with the other party’s public key and sends it along. The other party then uses its private key to decrypt the shared secret and … voila! They both share the same secret. This technique was discovered in 1977 by Rivest, Shamir and Adelman and is called RSA key exchange. In TLS’s RSA key exchange, the shared secret is decided by the client, who then encrypts it to the server’s public key (extracted from the certificate) and sends it to the server.

image4

The other form of key exchange available in TLS is based on another form of public-key cryptography, invented by Diffie and Hellman in 1976, so-called Diffie-Hellman key agreement. In Diffie-Hellman, the client and server both start by creating a public-private key pair. They then send the public portion of their key share to the other party. When each party receives the public key share of the other, they combine it with their own private key and end up with the same value: the pre-main secret. The server then uses a digital signature to ensure the exchange hasn’t been tampered with. This key exchange is called “ephemeral” if the client and server both choose a new key pair for every exchange.

image3

Both modes result in the client and server having a shared secret, but RSA mode has a serious downside: it’s not forward secret. That means that if someone records the encrypted conversation and then gets ahold of the RSA private key of the server, they can decrypt the conversation. This even applies if the conversation was recorded and the key is obtained some time well into the future. In a world where national governments are recording encrypted conversations and using exploits like Heartbleed to steal private keys, this is a realistic threat.

RSA key exchange has been problematic for some time, and not just because it’s not forward-secret. It’s also notoriously difficult to do correctly. In 1998, Daniel Bleichenbacher discovered a vulnerability in the way RSA encryption was done in SSL and created what’s called the “million-message attack,” which allows an attacker to perform an RSA private key operation with a server’s private key by sending a million or so well-crafted messages and looking for differences in the error codes returned. The attack has been refined over the years and in some cases only requires thousands of messages, making it feasible to do from a laptop. It was recently discovered that major websites (including facebook.com) were also vulnerable to a variant of Bleichenbacher’s attack called the ROBOT attack as recently as 2017.

To reduce the risks caused by non-forward secret connections and million-message attacks, RSA encryption was removed from TLS 1.3, leaving ephemeral Diffie-Hellman as the only key exchange mechanism. Removing RSA key exchange brings other advantages, as we will discuss in the performance section below.

Diffie-Hellman named groups

When it comes to cryptography, giving too many options leads to the wrong option being chosen. This principle is most evident when it comes to choosing Diffie-Hellman parameters. In previous versions of TLS, the choice of the Diffie-Hellman parameters was up to the participants. This resulted in some implementations choosing incorrectly, resulting in vulnerable implementations being deployed. TLS 1.3 takes this choice away.

Diffie-Hellman is a powerful tool, but not all Diffie-Hellman parameters are “safe” to use. The security of Diffie-Hellman depends on the difficulty of a specific mathematical problem called the discrete logarithm problem. If you can solve the discrete logarithm problem for a set of parameters, you can extract the private key and break the security of the protocol. Generally speaking, the bigger the numbers used, the harder it is to solve the discrete logarithm problem. So if you choose small DH parameters, you’re in trouble.

The LogJam and WeakDH attacks of 2015 showed that many TLS servers could be tricked into using small numbers for Diffie-Hellman, allowing an attacker to break the security of the protocol and decrypt conversations.

Diffie-Hellman also requires the parameters to have certain other mathematical properties. In 2016, Antonio Sanso found an issue in OpenSSL where parameters were chosen that lacked the right mathematical properties, resulting in another vulnerability.

TLS 1.3 takes the opinionated route, restricting the Diffie-Hellman parameters to ones that are known to be secure. However, it still leaves several options; permitting only one option makes it difficult to update TLS in case these parameters are found to be insecure some time in the future.

Fixing ciphers

The other half of a hybrid crypto scheme is the actual encryption of data. This is done by combining an authentication code and a symmetric cipher for which each party knows the key. As I’ll describe, there are many ways to encrypt data, most of which are wrong.

CBC mode ciphers

In the last section we described TLS as a hybrid encryption scheme, with a public key part and a symmetric key part. The public key part is not the only one that has caused trouble over the years. The symmetric key portion has also had its fair share of issues. In any secure communication scheme, you need both encryption (to keep things private) and integrity (to make sure people don’t modify, add, or delete pieces of the conversation). Symmetric key encryption is used to provide both encryption and integrity, but in TLS 1.2 and earlier, these two pieces were combined in the wrong way, leading to security vulnerabilities.

An algorithm that performs symmetric encryption and decryption is called a symmetric cipher. Symmetric ciphers usually come in two main forms: block ciphers and stream ciphers.

A stream cipher takes a fixed-size key and uses it to create a stream of pseudo-random data of arbitrary length, called a key stream. To encrypt with a stream cipher, you take your message and combine it with the key stream by XORing each bit of the key stream with the corresponding bit of your message.. To decrypt, you take the encrypted message and XOR it with the key stream. Examples of pure stream ciphers are RC4 and ChaCha20. Stream ciphers are popular because they’re simple to implement and fast in software.

A block cipher is different than a stream cipher because it only encrypts fixed-sized messages. If you want to encrypt a message that is shorter or longer than the block size, you have to do a bit of work. For shorter messages, you have to add some extra data to the end of the message. For longer messages, you can either split your message up into blocks the cipher can encrypt and then use a block cipher mode to combine the pieces together somehow. Alternatively, you can turn your block cipher into a stream cipher by encrypting a sequence of counters with a block cipher and using that as the stream. This is called “counter mode”. One popular way of encrypting arbitrary length data with a block cipher is a mode called cipher block chaining (CBC).

encryption
decryption

In order to prevent people from tampering with data, encryption is not enough. Data also needs to be integrity-protected. For CBC-mode ciphers, this is done using something called a message-authentication code (MAC), which is like a fancy checksum with a key. Cryptographically strong MACs have the property that finding a MAC value that matches an input is practically impossible unless you know the secret key. There are two ways to combine MACs and CBC-mode ciphers. Either you encrypt first and then MAC the ciphertext, or you MAC the plaintext first and then encrypt the whole thing. In TLS, they chose the latter, MAC-then-Encrypt, which turned out to be the wrong choice.

You can blame this choice for BEAST, as well as a slew of padding oracle vulnerabilities such as Lucky 13 and Lucky Microseconds. Read my previous post on the subject for a comprehensive explanation of these flaws. The interaction between CBC mode and padding was also the cause of the widely publicized POODLE vulnerability in SSLv3 and some implementations of TLS.

RC4 is a classic stream cipher designed by Ron Rivest (the “R” of RSA) that was broadly supported since the early days of TLS. In 2013, it was found to have measurable biases that could be leveraged to allow attackers to decrypt messages.

image2
AEAD Mode

In TLS 1.3, all the troublesome ciphers and cipher modes have been removed. You can no longer use CBC-mode ciphers or insecure stream ciphers such as RC4. The only type of symmetric crypto allowed in TLS 1.3 is a new construction called AEAD (authenticated encryption with additional data), which combines encryption and integrity into one seamless operation.

Fixing digital signatures

Another important part of TLS is authentication. In every connection, the server authenticates itself to the client using a digital certificate, which has a public key. In RSA-encryption mode, the server proves its ownership of the private key by decrypting the pre-main secret and computing a MAC over the transcript of the conversation. In Diffie-Hellman mode, the server proves ownership of the private key using a digital signature. If you’ve been following this blog post so far, it should be easy to guess that this was done incorrectly too.

PKCS#1v1.5

Daniel Bleichenbacher has made a living identifying problems with RSA in TLS. In 2006, he devised a pen-and-paper attack against RSA signatures as used in TLS. It was later discovered that major TLS implemenations including those of NSS and OpenSSL were vulnerable to this attack. This issue again had to do with how difficult it is to implement padding correctly, in this case, the PKCS#1 v1.5 padding used in RSA signatures. In TLS 1.3, PKCS#1 v1.5 is removed in favor of the newer design RSA-PSS.

Signing the entire transcript

We described earlier how the server uses a digital signature to prove that the key exchange hasn’t been tampered with. In TLS 1.2 and earlier, the server’s signature only covers part of the handshake. The other parts of the handshake, specifically the parts that are used to negotiate which symmetric cipher to use, are not signed by the private key. Instead, a symmetric MAC is used to ensure that the handshake was not tampered with. This oversight resulted in a number of high-profile vulnerabilities (FREAK, LogJam, etc.). In TLS 1.3 these are prevented because the server signs the entire handshake transcript.

tls12

The FREAK, LogJam and CurveSwap attacks took advantage of two things:

  1. the fact that intentionally weak ciphers from the 1990s (called export ciphers) were still supported in many browsers and servers, and
  2. the fact that the part of the handshake used to negotiate which cipher was used was not digitally signed.

The on-path attacker can swap out the supported ciphers (or supported groups, or supported curves) from the client with an easily crackable choice that the server supports. They then break the key and forge two finished messages to make both parties think they’ve agreed on a transcript.

FREAK

These attacks are called downgrade attacks, and they allow attackers to force two participants to use the weakest cipher supported by both parties, even if more secure ciphers are supported. In this style of attack, the perpetrator sits in the middle of the handshake and changes the list of supported ciphers advertised from the client to the server to only include weak export ciphers. The server then chooses one of the weak ciphers, and the attacker figures out the key with a brute-force attack, allowing the attacker to forge the MACs on the handshake. In TLS 1.3, this type of downgrade attack is impossible because the server now signs the entire handshake, including the cipher negotiation.

signed transcript

Better living through simplification

TLS 1.3 is a much more elegant and secure protocol with the removal of the insecure features listed above. This hedge-trimming allowed the protocol to be simplified in ways that make it easier to understand, and faster.

No more take-out menu

In previous versions of TLS, the main negotiation mechanism was the ciphersuite. A ciphersuite encompassed almost everything that could be negotiated about a connection:

  • type of certificates supported
  • hash function used for deriving keys (e.g., SHA1, SHA256, …)
  • MAC function (e.g., HMAC with SHA1, SHA256, …)
  • key exchange algorithm (e.g., RSA, ECDHE, …)
  • cipher (e.g., AES, RC4, …)
  • cipher mode, if applicable (e.g., CBC)

Ciphersuites in previous versions of TLS had grown into monstrously large alphabet soups. Examples of commonly used cipher suites are: DHE-RC4-MD5 or ECDHE-ECDSA-AES-GCM-SHA256. Each ciphersuite was represented by a code point in a table maintained by an organization called the Internet Assigned Numbers Authority (IANA). Every time a new cipher was introduced, a new set of combinations needed to be added to the list. This resulted in a combinatorial explosion of code points representing every valid choice of these parameters. It had become a bit of a mess.

take-out menu

TLS 1.2

prix fixe

TLS 1.3

TLS 1.3 removes many of these legacy features, allowing for a clean split between three orthogonal negotiations:

  • Cipher + HKDF Hash
  • Key Exchange
  • Signature Algorithm

negotiation

This simplified cipher suite negotiation and radically reduced set of negotiation parameters opens up a new possibility. This possibility enables the TLS 1.3 handshake latency to drop from two round-trips to only one round-trip, providing the performance boost that will ensure that TLS 1.3 will be popular and widely adopted.

Performance

When establishing a new connection to a server that you haven’t seen before, it takes two round-trips before data can be sent on the connection. This is not particularly noticeable in locations where the server and client are geographically close to each other, but it can make a big difference on mobile networks where latency can be as high as 200ms, an amount that is noticeable for humans.

1-RTT mode

TLS 1.3 now has a radically simpler cipher negotiation model and a reduced set of key agreement options (no RSA, no user-defined DH parameters). This means that every connection will use a DH-based key agreement and the parameters supported by the server are likely easy to guess (ECDHE with X25519 or P-256). Because of this limited set of choices, the client can simply choose to send DH key shares in the first message instead of waiting until the server has confirmed which key shares it is willing to support. That way, the server can learn the shared secret and send encrypted data one round trip earlier. Chrome’s implementation of TLS 1.3, for example, sends an X25519 keyshare in the first message to the server.

DH in 1.2
DH in 1.3

In the rare situation that the server does not support one of the key shares sent by the client, the server can send a new message, the HelloRetryRequest, to let the client know which groups it supports. Because the list has been trimmed down so much, this is not expected to be a common occurrence.

0-RTT resumption

A further optimization was inspired by the QUIC protocol. It lets clients send encrypted data in their first message to the server, resulting in no additional latency cost compared to unencrypted HTTP. This is a big deal, and once TLS 1.3 is widely deployed, the encrypted web is sure to feel much snappier than before.

In TLS 1.2, there are two ways to resume a connection, session ids and session tickets. In TLS 1.3 these are combined to form a new mode called PSK (pre-shared key) resumption. The idea is that after a session is established, the client and server can derive a shared secret called the “resumption main secret”. This can either be stored on the server with an id (session id style) or encrypted by a key known only to the server (session ticket style). This session ticket is sent to the client and redeemed when resuming a connection.

For resumed connections, both parties share a resumption main secret so key exchange is not necessary except for providing forward secrecy. The next time the client connects to the server, it can take the secret from the previous session and use it to encrypt application data to send to the server, along with the session ticket. Something as amazing as sending encrypted data on the first flight does come with its downfalls.

Replayability

There is no interactivity in 0-RTT data. It’s sent by the client, and consumed by the server without any interactions. This is great for performance, but comes at a cost: replayability. If an attacker captures a 0-RTT packet that was sent to server, they can replay it and there’s a chance that the server will accept it as valid. This can have interesting negative consequences.

0-rtt-attack-@2x

An example of dangerous replayed data is anything that changes state on the server. If you increment a counter, perform a database transaction, or do anything that has a permanent effect, it’s risky to put it in 0-RTT data.

As a client, you can try to protect against this by only putting “safe” requests into the 0-RTT data. In this context, “safe” means that the request won’t change server state. In HTTP, different methods are supposed to have different semantics. HTTP GET requests are supposed to be safe, so a browser can usually protect HTTPS servers against replay attacks by only sending GET requests in 0-RTT. Since most page loads start with a GET of “/” this results in faster page load time.

Problems start to happen when data sent in 0-RTT are used for state-changing requests. To help prevent against this failure case, TLS 1.3 also includes the time elapsed value in the session ticket. If this diverges too much, the client is either approaching the speed of light, or the value has been replayed. In either case, it’s prudent for the server to reject the 0-RTT data.

For more details about 0-RTT, and the improvements to session resumption in TLS 1.3, check out this previous blog post.

Deployability

TLS 1.3 was a radical departure from TLS 1.2 and earlier, but in order to be deployed widely, it has to be backwards compatible with existing software. One of the reasons TLS 1.3 has taken so long to go from draft to final publication was the fact that some existing software (namely middleboxes) wasn’t playing nicely with the new changes. Even minor changes to the TLS 1.3 protocol that were visible on the wire (such as eliminating the redundant ChangeCipherSpec message, bumping the version from 0x0303 to 0x0304) ended up causing connection issues for some people.

Despite the fact that future flexibility was built into the TLS spec, some implementations made incorrect assumptions about how to handle future TLS versions. The phenomenon responsible for this change is called ossification and I explore it more fully in the context of TLS in my previous post about why TLS 1.3 isn’t deployed yet. To accommodate these changes, TLS 1.3 was modified to look a lot like TLS 1.2 session resumption (at least on the wire). This resulted in a much more functional, but less aesthetically pleasing protocol. This is the price you pay for upgrading one of the most widely deployed protocols online.

Conclusions

TLS 1.3 is a modern security protocol built with modern tools like formal analysis that retains its backwards compatibility. It has been tested widely and iterated upon using real world deployment data. It’s a cleaner, faster, and more secure protocol ready to become the de facto two-party encryption protocol online. Draft 28 of TLS 1.3 is enabled by default for all Cloudflare customers, and we will be rolling out the final version soon.

Publishing TLS 1.3 is a huge accomplishment. It is one the best recent examples of how it is possible to take 20 years of deployed legacy code and change it on the fly, resulting in a better internet for everyone. TLS 1.3 has been debated and analyzed for the last three years and it’s now ready for prime time. Welcome, RFC 8446.

from:https://blog.cloudflare.com/rfc-8446-aka-tls-1-3/

基于大中台小前台模式设计高并发电商架构

一、什么是大中台(业务中台、数据中台、技术中台等)

大中台小前台的组织模式最近在业界很火热,此模式最早在芬兰著名移动游戏公司Supercell实施。在Supercell公司内部以小前台的方式组织了若干个开发团队,每个开发团队包含开发一款游戏所需的各种角色,从而在开发团队内部可以快速决策、快速开发。而支撑这些开发团队的基础设施(机房、网络、架构组件等)、游戏引擎、内部开发测试发布上线工具等则由“部落”(即中台)部门提供。“部落”部门可以根据需要扩展为多个小分队,亦即中台部门划分成多个,但各个小分队都保持共同目标。“部落”作为中台部门,赋能前台业务开发团队,中台部门本身并不直接提供游戏给消费者。

在国内,2015年阿里巴巴业务种类纷繁复杂,业务之间交叉依赖,业务团队众多,不能及时响应业务需求。2015年12月张勇宣布启动中台战略,构建符合DT时代的更具备创新性和灵活性的“大中台,小前台”的组织机制和业务机制,实现管理模式创新。即将产品技术力量和数据运营能力从前台剥离,成为独立的中台,包括搜索事业部、共享业务事业部、数据平台事业部等,为前台即零售电商事业群提供服务。从而前台得到精简,保持足够的敏捷度,更好地满足业务发展和创新需求。2017年5月出版了《企业IT架构转型之道:阿里巴巴中台战略思想和架构实践》,随后很多互联网公司快速跟进中台战略:2017年12月滴滴构建业务中台、2018年12月京东宣布前台、中台、后台组织架构[1]。进入2019年,大中台小前台模式更是在各个公司如火如荼地进行中。

那么中台是什么?中台是一种组织机制和业务机制。在公司组织架构层面通过组织架构调整,物理拆分成独立的中台部门。在公司业务层面通过把公共能力下沉为服务,并做好服务间连接,持续赋能业务部门。可类比航母(大中台)携带和赋能舰载机(小前台)作战(如图1);也可类比为中台生产各种乐高颗粒,传感器和执行器(如图2)。前台把这些颗粒打包集成为各种乐高套装,再加上不同的文档和包装,以及少量个性颗粒(比如特定IP的积木,星战主题积木块),快速形成不同产品卖给不同用户。另一方面,如果开发了10000种SKU的乐高套装,反过来会形成一个强大的乐高积木中台,几乎无所不能,前台产品越多,中台也越强大,中台越强大,前台产品开发也越简单,竞争力极强。

图1 航空母舰和舰载机

图2 乐高颗粒和产品

公司执行好大中台小前台模式,首先需要进行组织架构调整,比如阿里巴巴大中台小前台组织架构(如图3)如下:中台事业群和小前台事业群。其中中台事业群包括:搜索事业部、共享业务事业部(用户、商品、交易等)、数据技术及产品部(OLAP)、基础架构事业部等;小前台事业群包括电商事业群、蚂蚁金服集团、阿里云事业群、菜鸟网络、大文娱集团、阿里妈妈等其他。

图3 阿里巴巴大中台小前台组织架构

公司的交付物是产品,为了让公司更好地完成产品的交付,需要做好业务架构、数据架构、技术架构三个层面。其中业务架构(OLTP)包括个性化的业务架构(小前台)和公共业务架构(中台),数据架构(OLAP)包括个性化的数据架构(小前台)和公共数据架构(中台),技术架构即技术支撑(中台)。这三个层面的架构,我们可以进一步抽象和拆分个性化部分和公共部分。其中个性化的部分即小前台部分,公共部分即中台部分。因此公司的中台分为业务中台、数据中台和技术中台。
假如公司的业务架构采用了目前主流的微服务架构模式(如图4),其中大中台部分包括:网关层、公共业务逻辑层、数据访问层、DB、Cache、配置中心、注册中心,小前台部分包括:业务逻辑层、App端。

图4 业务架构

假如公司的数据架构采用了目前主流的Hadoop生态架构模式(如图5),其中大中台部分包括:PAAS层(数据传输、数据计算、数据存储)、DAAS层(数据源、数据仓库、数据集市 /数据模型),小前台部分包括:DA(Data Application)(留存应用、画像应用、业务报表应用、数据智能应用)。

图5 数据架构

假如公司的技术架构采用了目前主流的技术栈(如图6),其中大中台部分包括:基础平台(消息平台、分布式锁平台、APM、立体监控平台、任务调度平台等)、基础组件(Web框架、RPC框架、分布式事务、数据库中间件等)、服务网格、存储体系(RDBMS、NoSQL、NewSQL)、容器弹性云等。

图6 技术架构

二、什么是小前台

从公司组织架构上来看,公司的个性化业务部门属于小前台,从公司业务服务上来看,公司的个性化业务服务属于小前台。

三、大中台小前台模式适用场景

大中台小前台模式特别有利于业务复制尝试和需要大量尝试创新的新业务,假如把公司的发展周期划分为0-1阶段为初创公司,1-10阶段为高速成长型公司,10-100阶段为稳定发展型公司。那么此模式比较适合10-100阶段,1-10阶段可以开始尝试了,但不适合0-1的初创公司阶段。
大中台需要通过抽象、封装共性能力和知识,可供需要使用的小前台使用(提供内部产品、服务、赋能等),从而使让前台更灵活,降低创新成本,支持更快更轻的试错和创新。

四、大中台小前台电商架构如何设计实践

在电商行业实施大中台小前台的业务架构模式,需要结合业务领域做好两个层面的工作,第一,在公司业务层面通过把公共能力下沉为服务;第二,做好服务的连接,并持续赋能业务部门。
在电商行业内,公共能力下沉为服务,比如把用户、商品、交易、支付、营销、搜索、推荐、风控等服务抽象后下沉为独立的服务。如图7所示的业务架构,其中网关层、公共业务逻辑层、数据访问层、DB、Cache以及注册中心、配置中心等属于电商的公共能力,为电商的中台服务。APP端、小程序端、个性化业务逻辑层等个性化的服务属于小前台部分。

图7 电商业务架构

在电商行业构建大中台小前台的模式中,第二步需要做好公共能力下沉服务的全连接,使得小前台业务可以做到一键接入。如何做好公共服务的全连接呢?首先需要从公司层面定义好业务线的标识标准,比如采用三级体系结构,如表1所示:

表1 业务线标识三级体系结构

公司统一了业务线三级体系结构后,需要提供统一的业务注册中心,使得业务通过业务注册中心完成所有业务线三级体系结构的注册以及查询。其次公司层面需要统一的业务线分发配置服务,分发配置服务的作用是把每个小前台业务需要连接的中台服务集中配置(比如手机前台业务需要接入商品中台、搜索中台、客服中台、交易中台等配置策略),并且配置小前台业务数据分发到每个中台服务的具体的接入策略(比如手机前台业务接入到搜索服务中台,手机业务哪些字段需要建立索引等接入策略),详见表2所示:

表2 业务线分发配置策略

在公司层面具备了统一的业务注册中心和分发配置服务后,需要进一步建立分发连接中心,分发连接中心需要分发两方面的内容:策略流和数据流,第一是策略流,分发业务线分发配置策略到各个中台服务,比如在表2中需要把业务线ID为1的商品数据类型的接入策略分发到表2中配置的商品中台服务、搜索中台服务、推荐中台服务、客服中台服务、数据中台服务等,并把订单数据类型的接入策略分发到表2中配置的搜索中台服务、客服中台服务等。这些中台服务收到分发连接中心的前台数据接入中台策略后,解析这些接入策略,后续对数据流的处理按照这些接入策略进行,完成策略的全连接。第二是数据流,当小前台业务产生相应的数据时,会分发到对应的中台服务。比如手机前台产生商品数据,由分发连接中心分发给相应的商品中台、搜索中台、推荐中台、客服中台、数据中台等,完成数据的全连接。
公司大中台小前台连接生态如图8所示,包含了小前台业务1、业务注册中心、分发配置服务、业务分发连接中心、各个中台服务,图8中包含了一个业务的策略流(黑色连接线)和数据流(红色连接线)具体的分发连接关系。

图8 大中台小前台连接生态

公司具备了大中台小前台的连接生态后,那么小前台业务产生的数据(比如手机业务的商品数据)如何存储呢?以小前台业务产生的商品数据为例,包括了商品公共的数据以及小前台业务个性化的数据。针对商品公共数据和商品个性化数据,存储有两种方案,一是商品公共数据存储在中台部门,商品个性化数据存储在小前台业务部门;第二种方案是商品公共数据和商品个性化数据全部存储在中台部门,有利用数据的统一存储和管理,并且使得业务查询等接入也非常简单。推荐大家使用第二种数据存储方案(同时同学们思考下第一种存储方案带来的问题有哪些?),那么针对商品的公共数据和个性化数据设计存储表结构:商品公共数据表 +商品业务个性化扩展数据表,其中商品公共数据表包含了所有业务线商品公共的字段,如表3所示:商品ID、发布人、分类ID、价格、发布时间、商品库存、商品状态等等。

图3 商品公共数据表

其中商品个性化数据表(如表4)采用Key,Value扩展列的方式进行存储,比如Key的类型可以固定几种类型:比如Long类型、Double类型、String类型,业务个性化数据都使用固定的几种数据类型来表示和存储,列中Key的含义在映射表(如表5)中指定了每个Key具体的的业务字段含义。

表4 商品业务个性化扩展数据表

表5 商品个性化字段映射数据表

通过以上大中台小前台的连接生态以及公共数据表和业务个性化数据表的存储方式,使得大中台小前台模式在公司内得以很好的落地和实践。
参考文献:

[1] 中台战略-中台建设与数字商业:机械工业出版社

from: 欢迎关注公众号 架构之美

从分布式一致性算法到区块链共识机制

引言

分布式一致性是一个很“古典”的话题,即在分布式系统中,如何保证系统内的各个节点之间数据的一致性或能够就某个提案达成一致。这个问题想必对于很多技术同学而言并不陌生,几乎在所有的分布式系统中都会遇到,比如hdfs、mq、zookeeper、kafka、redis、elasticsearch等。然而这个问题却历久弥新,随着分布式网络的蓬勃发展与复杂化,对于该问题解法的探索也一直在进行中。

而近年来,随着区块链技术的兴起,特别是开放网络中的公有链与有权限网络中的联盟链的蓬勃发展,一致性问题再次得到关注,并从新的视角来审视该问题。

本文将从传统的分布式一致性问题说起,再次重温我们需要面对的问题挑战、已有的理论研究、以及相应的一致性算法,并简要分析这些一致性算法的适用性与局限性,以及这些传统一致性算法与崭新的区块链技术的结合。另外,将从区块链中一致性问题的全新视角“人的可信”出发,重点阐述公有链领域中的共识算法与机制。因此,本文围绕“一致性”技术问题,重点从技术视角阐述传统计算机科学中的分布式一致性算法与区块链中的共识机制的关联,以及公有链对于一致性问题的重新思考。

分布式一致性问题的挑战

要清楚理解分布式一致性,首先需要对分布式网络的特性有清晰的认识。那么分布式网络具有哪些特点呢?或者通俗理解,在分布式网络中,可能遇到哪些问题呢?

Crash Fault

故障错误(Crash Fault)很好理解,就是说分布式网络中:

  • 节点或副本可能随时宕机、可能暂停运行但随后又恢复;
  • 网络可能随时中断;
  • 发送的消息可能在传递的过程中丢失,对方一直收不到;
  • 发送的消息可能出现延迟,过了很久对方才能收到;
  • 消息在传递的过程中可能出现乱序;
  • 网络可能出现分化,如中美集群因通信不畅,而导致整体网络分化为中美两个子网络;

这些问题,其实就是我们在分布式环境中最常实际遇到的问题,这些问题实质上都是由于分布式系统中的物理硬件的不可靠、不稳定所带来的必然风险,比如:网络(信道)不可能是永远稳定可靠的、物理机磁盘或CPU等不可能是永远良好的。故障错误可以说是分布式系统中必须考虑并解决的最基本、最常见的一类错误。

Byzantine Fault

上文的故障错误,仍然基于一个很简单的假设:节点要么不正常工作或响应,要么能正常工作或响应,但不能口是心非、阳奉阴违、表里不一,即可以不干事、但不能干坏事。一旦网络中存在作恶节点,可能会随意篡改或伪造数据,那么一致性问题的难度就大幅增加。我们常把这类存在“捣乱者”,可能会篡改或伪造数据或响应信息的错误,称之为拜占庭错误(Byzantine Fault),而前面所说的故障类错误也称之为非拜占庭错误。

拜占庭这一称呼,源于Lamport最初的论文,可以说是分布式领域最复杂、最严格的容错模型。简而言之,n个将军准备一起进攻某个城堡,每个将军都可以选择进攻或是撤退,但所有将军必须行动一致才能成功。各个将军之间相隔很远,不能直接通讯,必须通过信使来传递消息。但是信使并不可靠,信使可能过了很久才送到消息、可能一直也没有把消息送到、甚至可能会故意篡改消息;而将军也并不可靠,里面可能存在叛徒,并不按照提案来行动。显然,这个故事中的信使用来代表分布式网络中的不可靠信道,而将军就是各个不可靠的节点。

拜占庭问题示意图

(https://lisk.io/academy/blockchain-basics/how-does-blockchain-work/byzantine-fault-tolerance-explained)

应对风险—Fault Tolerance

如何在充满风险与不确定的分布式网络中,寻找到某种确定性与一致性,使得整个分布式网络输出稳定可靠的一致性结果,就是分布式一致性算法要解决的核心问题。显而易见,解决故障类错误更容易一些,通常把这类一致性算法叫做故障容错算法(Crash Fault Tolerance)或者非拜占庭容错算法。而拜占庭类错误,因为有恶意篡改的可能性存在,复杂性更高、解决难度更大,通常把解决这类问题的算法称作拜占庭容错算法(Byzantine Fault Tolerance)。

那么我们忍不住要问,两类容错算法的界限在哪里?或者说两类错误都在什么样的场景下出现?恶意篡改这种情况真的需要考虑吗?问题的答案可能取决于我们所处的网络环境与业务场景。

CFT

通常而言,如果系统处于可信的内部网络环境中,只需要考虑故障容错(CFT)可能就足够了。比如我们经常见到的公司内的分布式存储、消息队列、分布式服务等各种分布式组件,其实只需要考虑故障容错就足够了。因为公司内整个网络是封闭的,又有多重防火墙的保护,外界很难接入或攻击;各个节点是由公司统一部署的,机器或运行的软件遭到篡改的可能性极小;此时的分布式网络环境相对“单纯”,我们唯一的敌人只是:通信网络与机器硬件。我们需要考虑的是网络的延迟、不稳定,以及机器随时可能出现的宕机、故障。

BFT

而拜占庭类错误(BFT),是把整个分布式网络放到了更大的环境中去看,除了物理硬件之外,还考虑了一些“人”的因素。毕竟,机器是不会作恶的,作恶的只有人。假如我们所处的分布式网络是较为开放的网络,比如行业内几十上百家公司组成的联盟网络;或者是完全开放的网络,比如任何人都可以随意接入到网络中;而节点机器和上面部署的软件也是由各个公司或个人自己提供和部署的,那么如果利益足够大,很可能会有人对网络中的某个节点发起DDoS攻击、故意篡改软件代码改变其执行逻辑、甚至可能故意篡改磁盘上持久化的数据。显然,我们此时面临的挑战更大了,我们除了要考虑通信网络和机器硬件的不可靠之外,还必须要考虑和应对系统中的“捣乱者”。

不可能三角

这些实践中遇到的问题,也引发了诸多计算科学家进行了非常多的理论研究。这些理论研究对于工程技术人员而言或许过于抽象繁琐,有些甚至是无趣的数学问题,但这些理论对于指导我们解决这些问题意义重大。这些理论相当于是告诉了我们这类问题解法的理论极限,以及哪些方向可以探索、哪些方向是死路一条。站在前人的肩膀上,才不至于花毕生精力去研制“永动机”。这些理论大家应该都有所了解,这里只简单回顾。

FLP impossibility

早在1985年,Fisher、Lynch、Paterson三位科学家就发表了关于分布式一致性问题的不可能定理:在完全异步的分布式网络中,故障容错问题无法被解决。( We have shown that a natural and important problem of fault-tolerant cooperative computing cannot be solved in a totally asynchronous model of computation. )说得更直白点:在异步网络中,不可能存在能够容忍节点故障的一致性算法,哪怕只有一个节点故障。并且这里并没有考虑拜占庭错误,而是假设网络非常稳定、所有的消息都能被正确传递、并且仅被传递一次,即便如此都不可能找到能容忍哪怕只有一个节点失效的一致性协议,可见该结论有多强。( In this paper, we show the surprising result that no completely asynchronous consensus protocol can tolerate even a single unannounced process death. We do not consider Byzantine failures, and we assume that the message system is reliableit delivers all messages correctly and exactly once. )

当然了,这只是理论上的。它的意义在于告诉我们此类问题的理论极限,并不意味着此类问题在实践中也不可能被“解决”。如果我们愿意放宽限制、做出牺牲,在工程上是可以找到切实可行的解法的。

FLP不可能定理的最大适用前提是异步网络模型。何为同步、异步模型呢?

  • 所谓异步模型,是说从一个节点到另一个节点的消息延迟是有限的,但可能是无界的(finite but can be unbounded)。这就意味着如果一个节点没有收到消息,它无法判断消息到底是丢失了,还是只是延迟了。也就是说,我们无法通过超时时间来判断某个节点是否故障。
  • 所谓同步模型,是说消息传递的延迟是有限的,且是有界的。这就意味着我们可以通过经验或采样精确估算消息的最大可能延迟,从而可以通过超时时间来确定消息是否丢失、节点是否故障。

所幸的是,我们所处于的真实的网络世界更接近同步模型,在很多场景上,我们都可以通过经验或采样确定最大超时时间。举个通俗点的例子:你给朋友快递了一本书,朋友过了3天还没收到,此时朋友很难判断到底是快递延迟了,还是快递出问题送丢了。但是如果过了一个月,朋友仍没收到书,基本就可以断定快递送丢了。而背后的推论就是基于经验或统计:通常快递都能在1-2周内送达。显然,异步模型其实是反映了节点间通讯的最差情况、极端情况,异步模型包含了同步模型,即能在异步模型上有效的一致性协议,在同步模型上也同样有效。而同步模型是对异步模型做了修正和约束,从而使得更接近真实世界,也使得在实践中一致性问题有可能得到有效解。

另外,即便是在异步网络模型下,FLP也并不意味着一致性永远无法达成,只是说无法保证在有界的时间(in bounded time)内达成。在实践上,如果放宽对bounded time的限制,仍然是有可能找到实践中的解法的。

而根据DLS的研究

(http://groups.csail.mit.edu/tds/papers/Lynch/jacm88.pdf ),一致性算法按照网络模型可以分为三大类:

  • 部分同步网络模型(partially synchronous model)中的一致性协议可以容忍最多1/3的任意错误。这里的部分同步模型是指网络延迟是有界的,但是我们无法提前得知。这里的容错也包含了拜占庭类错误。
  • 异步网络模型(asynchronous model)中的确定性协议无法容忍错误。这里的异步模型即是前文所说的网络延迟是无界的。该结论其实就是FLP不可能定理的含义,在完全异步网络中的确定性协议不能容忍哪怕只有一个节点的错误。
  • 同步网络模型(synchronous model)可以达到惊人的100%容错,虽然对错误节点超过1/2时的节点行为有限制。这里的同步模型是指网络延迟一定是有界的,即小于某个已知的常数。

从另一个角度来理解,FLP实际上考虑了分布式系统的3个属性:安全(safety)、活性(liveness)、容错:

  • 安全是说系统内各个节点达成的值是一致的、有效的。safety其实是保证系统一致性运行的最低要求,其核心是cannot do something bad,即不能干坏事、不能做错事。
  • 活性是说系统内各个节点最终(在有限时间内)必须能够达成一致,即系统必须能够向前推进,不能永远处于达不成一致的状态。liveness其实是更高要求,意味着不能只是不干坏事,也不能一直不干事,you must do something good,即必须使得整个系统能良好运转下去。
  • 容错是说该协议在有节点故障的情况下也必须能有效。

FLP不可能定理其实意味着在异步网络中,不可能存在同时满足这三者的分布式一致性协议。因为分布式环境中,节点故障几乎是必然的,因此容错是必须要考虑的因素,所以FLP不可能定理就意味着一致性协议在能做到容错的情况下,没办法同时做到安全性与系统活性。通常在实践中,我们可以做出部分牺牲,比如牺牲一部分安全性,意味着系统总能很快达成结论,但结论的可靠性不足;或者牺牲一部分系统活性,意味着系统达成的结论非常可靠,但可能长时间、甚至永远都在争论中,无法达成结论。所幸的是,很多时候现实世界的鲁棒性很强,使一致性协议失效的倒霉事件发生的概率也很可能极低。

FLP不可能定理示意图

(https://www.slideshare.net/oryband/the-stellar-blockchain-and-the-story-of-the-federated-consensusblockchain-academy)

另外,FLP并未排除Las Vegas类随机算法,许多一致性算法采用了这种随机性来规避FLP不可能定理对于确定性异步网络的限制。此类非确定性一致性算法涉及Las Vegas规则:网络最终一定能达成一致,但是达成一致所需要的时间可能是无界的。此类算法每轮共识决策都有一定的概率,并且系统在T秒内能够达成一致的概率P随着时间T的增加而指数增长并趋近于1。事实上,该方法被许多成功的一致性算法所采用,是在FLP不可能定理笼罩下的安全地带(escape hatch),后面将会讲到比特币的共识机制就是采用了这样的方法。

CAP theorem

众所周知、大名鼎鼎的CAP原理,从另一个维度,简单明了、直截了当地告诉我们:可用性、一致性与网络分区容错性这三者不可能同时实现,而只能实现任意其中的两个。( “Of three properties of shared-data systems (data consistency, system availability and tolerance to network partitions) one can only achieve two at any given time”.) CAP与FLP看起来有相似之处,其实二者并不尽相同,二者是从不同的维度思考问题,另外即使是很相似的概念,内涵也并不完全一样。比如:

  • FLP面对的是分布式一致性问题,而CAP面对的是分布式网络中的数据同步与复制。
  • FLP是说在异步网络模型中,三者不可能同时实现;而CAP是说在所有场景下,三者都不可能同时实现。
  • FLP中的liveness强调的是一致性算法的内在属性;而CAP中的availability强调的是一致性算法对外呈现的外在属性。

理论上,只能从CAP三者中选择两者,然而,这种选择的边界并非是非此即彼的(not binary),很多时候混合考虑不同程度的各个因素,结果可能是更好的。( The whole spectrum in between is useful; mixing different levels of Availability and Consistency usually yields a better result.)

CAP理论示意图

(https://www.researchgate.net/figure/Visualization-of-CAP-theorem_fig2_282679529)

在实践中,我们通常需要根据实际业务场景做折中权衡。比如:

  • 传统的关系型数据库如mysql等多采用ACID(atomicity, consistency, isolation and durability)理论,通过同步事务操作保证了强一致性;因节点较少(一般只有主从),可用性也比较一般;网络拓扑较为简单,而弱化了分区容错性。
  • NoSQL存储系统如hbase等多采用BASE(Basically Available、Soft state、Eventually consistent)理论,通过多节点多副本保证了较高的可用性;另外因节点数增多、网络环境也更复杂,也考虑了网络分区容错性;但一致性较弱,只能保证最终一致性。
ACID与BASE对比

(https://people.eecs.berkeley.edu/~brewer/cs262b-2004/PODC-keynote.pdf)

当然,这些并不是定论,各个系统都在各自不断的进化完善中,今天的结论明天可能就会被打破。更好的系统一定是不断探索适合自己的场景,找到更佳的平衡点。

分布式一致性算法

面对分布式环境中各种真实、复杂的问题与挑战,基于理论上的指引,各种应对现实问题的解法也被提出。我们这里不探究各类算法的实现细节与具体差异,仅做大体介绍,以便放到更大的维度,从整体上做比较。

Paxos

最大名鼎鼎的分布式一致性算法当属Lamport提出的paxos算法,虽然其复杂性也同样“臭名昭著”。Lamport开创性地提出了一种在工程实践上切实可行的、能够最大程度地保证分布式系统一致性的机制。paxos被广泛应用在诸多分布式系统中,如Chubby、Zookeeper等。在basic paxos(单一法令,即每次仅对一个值进行决策)中有两种角色:proposer可以处理客户端请求、主动提出某个议案值;acceptor被动响应proposer发出的信息、对提案进行投票、持久化存储决策过程中的值和状态。(为简化模型,可以忽略learner角色,不影响模型决策。)

如图所示,共识决策过程采用了两阶段提交:

  • 第1阶段,广播Prepare RPC命令,即找出协议决定的最终值、阻断尚未完成的旧提案;
  • 第2阶段,广播Accept RPC命令,即要求acceptor接受共识协商出的特定值。而multi-paxos是由多个basic paxos实例组成,可以对一系列的值进行决议。

Paxos之所以在实践中可行,其实也做了诸多假设和约束。从处理的问题上来看,Paxos仅能处理故障容错,并不难处理拜占庭错误,所以属于非拜占庭容错算法。从FLP的视角,Paxos做到了故障容错和安全性,但放弃了liveness(safe but not live),也就是说该算法可能永远无法结束,或者说永远无法达成共识,虽然这种可能性极小。从CAP的视角,Paxos只保证了CP,即做到了分区容错性和一致性,但弱化了可用性。有时为了增强paxos系统的可用性,可以考虑增加learner角色的数目。

即便并不完美,Paxos在实践中仍然是可靠、有效且久经考验的。Paxos本质上是异步系统的分布式一致性协议,并且在该领域具有支配地位。Chubby之父甚至声称世界上只有一种一致性算法,那就是paxos( there is only one consensus protocol, and that’s Paxos),其他一致性算法都是paxos的broken version。Paxos之所以在实践中有效是因为可能影响paxos系统liveness和可用性的条件并不容易被触发,即便真的出现,所带来的代价也可能并非是难以接受的。

Basic Paxos RPC通信与决策过程

(https://ongardie.net/static/raft/userstudy/paxos.pdf)

Raft

有感于Paxos的晦涩难懂,Ongaro在2014年提出了更容易理解的Raft算法。Raft把易于理解、易于工程实现提到了很高的重要级别,甚至是raft的初心和存在理由,因而在不影响功能性的前提下,尽可能多地做了易于理解的精细设计。

Raft算法是leader-based的非对称模型,系统中的任意一个节点在任意时刻,只能处于leader、follower、candidate这3种状态之一。初始状态所有节点都是follower状态,follower想变成leader必须先成为candidate,然后发起选举投票;如果投票不足,则回到follower状态;如果投票过半,则成为leader;成为leader后出现故障,若故障恢复后已有新leader,则自动下台,回归follower状态。

Raft还引入了term的概念用于及时识别过期信息,类似于zookeeper中的epoch;term值单向递增,每个term内至多一个leader;若不同term的信息出现冲突,则以term值较大的信息为准。

Raft还采用了心跳包和超时时间,leader为了保持自己的权威,必须不停地向集群中的其他节点发送心跳包;一旦某个follow在超过了指定时间(election timeout)仍没有收到心跳包,则就认为leader已经挂掉,自己进入candidate状态,开始竞选leader。

不难发现,raft的leader选举是通过heartbeat和随机timeout时间来实现的;而日志复制(log replication)阶段是以强leadership来实现的:leader接收client的command,append到自身log中,并将log复制到其他follower;而raft对安全性的保证是通过只有leader可以决定是否commit来实现的。

详细的竞选、复制等过程,这里不再赘述,有兴趣的同学可以参考笔者之前的文章(https://yq.aliyun.com/articles/675031 )。值得一提的是,raft中的leader选举过程和leader任期内的正常运作过程都比较简单,复杂的其实是leader的变更过程。

然而,虽然raft的原理机制与paxos不尽相同,但二者所解决的问题,以及所采取的折中权衡策略,可以认为是类似的。也就是说raft仍然只能解决故障错误,仍然强调了故障容错与安全性、一致性,弱化了liveness和可用性。

Raft协议概览

(https://ongardie.net/static/raft/userstudy/raft.pdf)

PBFT

自从1982年Lamport提出拜占庭将军问题之后,虽然有诸多关于拜占庭容错解决方案的讨论,但长期以来,此类问题的解决方案都效率低下、运行缓慢、复杂度过高,直到1999年Castro和Liskov提出实用拜占庭容错算法(Practical Byzantine Fault Tolerance),首次将此类算法的复杂度从指数级降到了多项式级,TPS可以达到几千,也使得节点故意作恶类问题在实践中找到了可行的解法。可以证明,如果系统内作恶节点数目不超过总节点数目的1/3,PBFT算法就能生效。

在PBFT中,所有的节点被顺序编号,其中1个是leader,其余的都是backup。系统内的所有节点间都互相通讯,依据多数原则达成一致。PBFT中的每轮共识都被称为一个view,而在不同的view之间,leader都会发生变化;如果超过给定的时间,leader没有广播出消息,则leader就会通过view change协议被替换掉。通过这种replica timeout机制,保证了crashed或malicious leader会被检测出来,从而通过重新选举新的leader,而进入到新的view中。

如图所示,从客户端发起请求到收到回复结果,可以分为5个阶段,而共识过程采用了3阶段协议。下面简要叙述5个阶段的大致过程:

  1. 发起:客户端(client c)向集群发起服务请求m;
  2. pre-prepare阶段:leader节点(replica 0)验证请求消息m的有效性,并在其view内为该请求m分配序列号n,并向所有backup节点(replica 1-3)广播关于该分配的pre-prepare消息;
  3. prepare阶段:backup节点验证请求消息m的有效性,并接受序列号n。若该节点同意该分配方案,则向其他所有节点广播出相应的prepare消息;这一阶段其实是要求所有replica达成全局一致的顺序。
  4. commit阶段:所有节点(包含主备)一旦收到来自集群的同意分配消息,则向其他所有节点广播出commit消息;这一阶段,所有replica已经对顺序达成一致,并对收到请求已做确认。
  5. 执行并返回:节点收到来自集群的commit消息后,执行请求m,并返回消息给客户端;客户端等到接收到来自f+1个不同节点的相同回复,则认为请求已成功执行;其中f表示集群中潜在故障节点的最大数目。这里所有节点都向client直接返回消息也是为了避免主节点在请求期间出问题。
PBFT算法正常运作过程

(http://www.pmg.csail.mit.edu/papers/bft-tocs.pdf)

PBFT基于异步网络模型做到了安全性,但需要依赖消息超时时间来做周期性的同步。因为采用了leader-based方案,消息同步过程很快,也做到了完全的顺序写入。但是leader的重新选举过程很困难,某些恶意leader可以在临近timeout窗口期时才发送消息,这样会导致系统严重缓慢。而利用这一不利特点,可以攻击网络使正确的leader看起来也出问题,从而导致无穷无尽的leader选举过程。

PBFT与Paxos、Raft相比,所能处理应对的问题更为完备,除了能应对故障崩溃类错误之外,还能处理存在“捣乱者”的恶意篡改类拜占庭错误。然而,从所采取的折中权衡策略来看,PBFT仍然与Paxos、Raft很类似。从FLP的视角来看,PBFT同样更关注容错性和安全性,而弱化了liveness。从CAP的角度,PBFT同样强调网络分区容错与一致性,而弱化了可用性。

即便如此,只要故障或作恶节点不超过总节点数的1/3,PBFT在实践中还是有效可行的。而拜占庭容错算法(BFT)也不止PBFT一种,BFT类算法也在不断进化,如Lamport就提出过改进版的Paxos算法BFT Paxos以处理拜占庭错误,近来也有人结合PBFT与Raft提出了 BFT Raft 算法。但从问题领域与原理机制上来说,仍然与原有的思路和框架较为类似,不再一一赘述。

适用场景

从Paxos、Raft到PBFT,再到目前层出不穷的Paxos变种、Raft变种、BFT类混合新算法,分布式一致性算法在不断发展、完善、进化。甚至各大公司也在结合自己的业务实际,研发各种适合自己场景的分布式一致性算法。这些算法虽然并不完美,但都在适合自己场景的业务实践中发挥着重大作用。那么这些算法的适用场景到底是什么?自身又有哪些局限性呢?

对于Paxos、Raft这类非BFT算法而言,只能处理机器硬件故障,而无法处理存在作恶节点的情况。显然,这类非BFT算法只能运行在非常可信的网络环境中,比如公司内部网络中,在这样的较为封闭的网络中,访问需要严格授权,从而保证各个节点的身份是已知的、可信的,基本排除了节点作恶的可能性,这类算法才能有效运行。

而BFT类算法,对于网络环境的要求不再那么苛刻,即使存在作恶节点,只要作恶节点数目不超过总节点数的1/3,整个系统依然是安全的。但问题就在于,你怎么知道网络中到底有多少作恶节点?作恶节点占总节点的比例到底有多高?显然,如果网络的接入是需要权限控制的,那么这个问题就相对容易解决。比如10家业务关联公司组成的联盟网络,只有这10家授权的公司才能访问,即便里面有个别公司(少于3家)蓄意作恶、妄图篡改数据,整个系统仍然是安全可靠的。在这种permissoned网络中,隐含着对于网络中可能作恶节点数目的预估,即便真的作恶了,也能方便快速地定位出其真实身份,间接提高了网络的安全性。

局限性

然而,在permissonless(开放权限、无权限控制)的公有网络中,BFT类算法很可能会有问题。因为,如果分布式网络是开放的,谁都能进进出出,而接入网络系统的成本又很低,那么没人知道网络中到底可能有多少作恶节点,即便真有作恶,也很难定位出真实身份。比如,一种比较典型的女巫攻击(Sybil attack)场景,作恶者可以通过大量伪造身份来控制集群中的大量节点,从而控制整个分布式网络。

另外,BFT类算法最大的局限性还在于仅能协调少量的节点,如几个到几十个,若节点数目成千上万,整个系统的性能将会非常低下,甚至可能无法达成共识,从而影响系统的liveness和可用性。想必大家已经注意到,在PBFT的三阶段协议中,都需要多点广播(multicast):在pre-prepare阶段,主节点向所有备节点广播;在prepare节点,备节点向其他所有节点广播;在commit阶段,各个节点向其他所有节点广播。由此可见,通讯次数的数量级是节点数目的平方,当节点数目庞大时,这种两两广播的机制将会是灾难,系统几乎不可能在较短时间内达成一致。

综上可知,这些传统的分布式一致性算法,无论是Paxos、Raft,还是PBFT,通常适用于存在权限控制的、节点数目较少的、较为可信的分布式网络环境中。

在联盟链中的应用

事实上,这些传统的一致性算法在区块链时代也焕发了新的活力,得到了进一步的认识和使用。在网络环境较为可信的联盟链场景中,这些一致性算法得到了大量的应用。联盟链因如下特点而被业内看好其应用前景:

  • 接入需授权:联盟链并不完全对外开放,一般只有几家或几十家企业组成,只有经过授权的公司或组织才能加入到网络中,并且一般是实名认证参与。
  • 数据保护:联盟链信息数据并不完全对外开放,而只有授权方可见。这对于保护行业或公司的数据安全比较重要,如跨境转账中的交易信息等对于银行业至关重要、链上税务系统中的税务信息也很敏感。
  • 可监管:联盟链中一般可以设立监管观察节点,对于敏感信息进行审计与监管,满足合法性要求。

在当前阶段,联盟链不失为快速落地、解决行业痛点的不错选择,也是对区块链后续发展的积极探索。因为联盟链需要授权才能参与,这其实相当于已经提前建立了相当程度的信任,网络环境较为可信,网络中的恶意行为和攻击行为发生的可能性都非常低,并且即便发生也很容易快速追责。因此在这样的场景下,传统的一致性算法也可以得到应用。比如:

  • HyperLedger Fabric(https://www.hyperledger.org/projects/fabric ) 在v1.0中可以使用Solo和Kafka pubsub系统来实现ordering;在v1.4版本也引入了Raft算法

    (https://hyperledger-fabric.readthedocs.io/en/release-1.4/orderer/ordering_service.html );目前这些均是CFT类算法,而raft的引入主要也是为后期支持BFT类算法铺平道路( Raft is the first step toward Fabric’s development of a byzantine fault tolerant (BFT) ordering service. As we’ll see, some decisions in the development of Raft were driven by this. )。

  • R3 Corda

    (https://www.r3.com/corda-platform/ )也采用了可插拔式的共识算法设计,不仅可以选择高速度、高可信环境的Raft算法,也可以选择低速度、低可信环境的BFT类算法

    (https://docs.corda.net/key-concepts-notaries.html )。

  • 以太坊企业联盟EEA

    (https://entethalliance.org/ )也支持BFT类算法、Raft算法,以及PoET算法

    (https://entethalliance.org/wp-content/uploads/2018/05/EEA-TS-0001-0-v1.00-EEA-Enterprise-Ethereum-Specification-R1.pdf )。

  • 蚂蚁区块链BaaS平台

    (https://tech.antfin.com/blockchain )也采用了PBFT算法。

Permissionless网络的挑战

那么我们忍不住要问,如果网络是完全开放的、无需权限许可的(permissionless),谁都可以随时进出,那么整个系统还能在有限的时间内达成一致吗?如果网络中的节点数目不再是几十个,而是一万个,那么又该如何协调这些数量庞大的节点呢?

在回答这些问题之前,其实更应该反问:为什么需要网络是完全开放、无需许可的?什么场景会需要一万个节点?这到底是伪需求,还是真实存在的场景?这个问题的答案直接关系到区块链中公有链的存在意义,而要回答这个问题,我们需要回到分布式系统的初心和目的。

去中心化的意义

我们为什么需要分布式系统?显然,这个问题不难回答,通常的理解,分布式系统可以增强容错能力(Fault tolerance),毕竟系统依赖众多不同的节点,而众多节点同时失败的可能性远低于一个节点发生故障的可能性;另外,分布式系统还可以抵御攻击(Attack resistance),毕竟攻击或摧毁众多节点的难度远大于攻击单点的难度。

然而,以上这些依然是局限在物理硬件的维度,都是用来降低机器物理硬件发生故障的可能性,而没有考虑“人”的因素。如果一个系统足够重要,比如电子货币系统等,除了考虑机器故障之外,更多需要考虑的是人的因素。部署节点的人会不会故意作恶呢?如何防止系统内不同节点间的腐败串通呢?

如下图所示,以太坊创始人Vitalik Buterin曾经深入地探讨过去中心化的含义。如果说传统的分布式系统做到了architectural decentralization(系统有多少物理机器构成?系统能够容忍最多多少台机器同时故障?),考虑的是fault tolerance和attack resistance;那么现在我们需要考虑的是如何做到political decentralization,如何能够collusion resistance? 到底有多少人或组织最终控制了系统内的节点?如何防止这些人之间的腐败串通?如果说传统的分布式系统考虑的问题是网络或机器硬件的可信,那现在我们想考虑的是“人的可信”:是否存在这样的技术手段来防范人的作恶?如何确保重要网络中的大部分节点不被一个人或一个组织恶意控制?

去中心化的三个维度

(https://medium.com/@VitalikButerin/the-meaning-of-decentralization-a0c92b76a274)

值得一提的是,这个问题的必要性依然充满争议,很多人根本不曾想过、或者认为根本没有必要考虑人的腐败串通,也可能认为对于这个问题技术也无能为力,毕竟这与我们生活的真实世界相去甚远。我们生活在一个中心化平台拥有极高声誉、提供信用背书、控制一切规则流程的世界,比如极少有人担心银行会故意做假账,侵吞你在银行的资产,毕竟大家普遍认为银行是值得信赖的。如果认为银行都不可信,那很可能一切商业活动都无法开展。

然而,我们只是“假设”银行是可信的,在“信任”与“怀疑”之间,我们只是被迫选择了信任,毕竟不信任银行,商业活动无法开展,经济也将停滞。然而实际上,并没有切实可行的措施来向所有人“证明”银行是可信的。

如果你认为这个问题是必要的、有意义的,那么能否找到一种解决方案,可以让这个世界变得更可信,让你不再需要“被迫相信”某个陌生人,而是提供一种“证明”,足以确保与你交易的某个陌生人是可信的?Don’t Trust, Please Verify. 你不需要相信我,你也不必相信我,你只需要去验证我。

如果要解决这个问题,所有人的身份应该是对等的,每个人都可以平等、自由地参与决策过程,每个人都可以自由地进出“议会”,这事实上是一种技术上的democracy,隐含的技术要素是:网络必须是permissonless的,谁都可以随时加入随时离开;节点之间必须是对等的,可以直接通讯;无任何中间人,无任何中心权威存在,完全的点对点(peer to peer);每个节点都有希望成为记账者。

因为网络无权限控制,完全的开放、透明、民主,所以参与的节点数目很可能非常众多,节点作恶的可能性也很高。那如何在这种permissionless的、节点数目众多、存在较大作恶可能的分布式网络环境中,通过某种机制协调节点间的行为,保证整个系统的一致性呢?显然,如前所述的一致性算法并不能做到这一点,我们需要寻求新的解法。

另外,去中心化可能是区块链领域最充满争议的词汇。一些人认为去中心化是区块链的价值观和公有链的灵魂与存在前提,应该尽可能地保证系统的去中心化程度;而另一些人认为完全的去中心化过于理想、不太可能实现,应该结合实际场景,在兼顾效率的情况下考虑弱中心化或多中心化。这里抛开价值判断,单纯从技术角度理性分析,去中心化程度越高确实系统的安全性会越高,所以在公有链的系统设计中确实应该尽可能地保证系统的去中心化程度。不过,结合Vitalik Buterin对于去中心化含义的诠释,在追求去中心化的过程中,我们不应该停留在单纯的表面上看起来的去中心化,而应该综合考虑去中心化的各个维度,结合实际情况,做出必要的trade-off。

PoW

对开放网络中的分布式一致性问题比较创新的解法当属比特币中的Proof-of-work(PoW、工作量证明)机制。

不得不提的Bitcoin

2008年10月31日,中本聪发表了比特币白皮书

《Bitcoin: A Peer-to-Peer Electronic Cash System》,天才般地为此类问题提供了创造性的解决思路,使得协调复杂网络环境中的成千上万节点成为可能。事实上,中本聪并不是为了解决这个技术问题而发表了比特币白皮书。相反,中本聪想象的更加宏大,他创造性地发明了比特币这种完全点对点的电子现金系统,以消除传统支付中需要依赖的可信第三方中间人,而在实现的过程中恰好依赖并解决了开放网络中众多节点间的一致性问题。也可以说,比特币所解决的最核心问题是点对点网络中电子货币的双花问题。然而,比特币的实现机制绝不仅仅是分布式网络技术问题,还结合了密码学、经济学、博弈论等思想,并以一种非确定性的概率方式实现了节点间的一致性。因此,单纯地称为算法已不太能准确表达其含义,可能叫作共识机制(consensus mechanism)更为恰当,因为其实现的确依赖了一整套的完整策略与制度。这里我们不过多阐述比特币的思想意义与实现细节,而仅聚焦在其共识机制的实现上。

比特币实际上是电子签名链,币的owner可以通过对前一个交易的哈希值和下一个owner的公钥进行签名,并将签名添加到币的末尾,从而实现转账。接受者通过校验签名来验证币的owner构成的链。然而,问题是币的接受者没有办法确保币的owner没有进行双花(double-spend),即有可能某个币的owner将同一个币先后转给了两个人。因此我们需要一种机制来让接收者确保币的前一个owner并没有在此之前将币转给其他人,为了确保这一点,唯一的办法就是让所有人知晓所有的交易。而在无可信第三方的情况下,想实现这一点,所有的交易必须广播给所有人。因此我们需要一个系统,其中的所有参与者对他们接收币的顺序达成一致,形成唯一的顺序记录历史。不难发现,这其实就是分布式一致性问题。

而比特币提供的方案就是需要一个由所有节点组成的时间戳服务器(timestamp server),时间戳服务器可以对交易区块的哈希加盖时间戳,并将该哈希广播出去。每一个时间戳都在其哈希中包含了前一个时间戳,从而形成一条链,而每一个新的时间戳都是对其之前所有时间戳的确保与强化。为了在点对点的网络中实现分布式的时间戳服务器,比特币采用了工作量证明机制(proof-of-work,PoW)。PoW涉及在做哈希运算时,需要寻找某个值,使得总体哈希值的开头前几位都为零,而所需要的平均工作量随着零位数目的增多而指数增加。另外,该哈希没有任何规律,为了保证开头前几位为零,只能通过暴力的方法不断地随机试错。一旦消耗了足够的CPU的算力,找到了符合条件的哈希值,则该区块就无法变更,除非再耗费CPU重做一遍。

另外,PoW也解决了大多数决策问题。在比特币中,最长的那条链就代表了大多数的决策。因为如果诚实的节点控制了大部分的算力,则诚实的链就会快速增长并超过其他链。如果想篡改某个过去的区块,攻击者必须重做相应的区块和其后面所有区块的PoW任务,然后追赶并赶超诚实的节点。这种难度是非常巨大的,从数学上不难证明,随着后续节点数目的增多,较慢的攻击者想追赶上来的概率指数下降,一般认为经过6个区块之后,想追赶上来几乎是不可能的。另外,PoW任务的难度并不是固定的,而是用移动平均的方法动态调整的,这主要是考虑到硬件运算速率的提高和挖矿人数的增减变化,算的快就加大难度、算的慢就减小难度,通过动态调节难度使得比特币的出块时间大致稳定在10分钟左右。

整个网络的运行过程如下:

  1. 新交易广播到所有节点。
  2. 每个节点都将收到的交易打包到一个区块内。
  3. 每个节点都为该区块不断尝试改变nonce,做PoW任务,以使得该区块的哈希符合指定条件。
  4. 一旦某个节点完成了PoW任务,则它将该区块广播给其他所有节点。
  5. 其他节点收到该区块后,验证区块内交易的有效性,验证通过则接受该区块。
  6. 节点如何表达自己接受了该区块呢?那就在添加下一个区块的时候,将该已接受区块的哈希值作为下一个区块的前一个哈希值(previous hash)。
比特币交易过程

(https://www.giottus.com/Bitcoin)

关于交易、挖矿等细节,这里不过多阐述,有兴趣的同学可以参考笔者之前的入门介绍文章(https://www.atatech.org/articles/126343 )。简而言之,在比特币中总是以最长链的信息为准,若某个节点发现了比自己更长的链会自动切换到最长的链工作。

我们忍不住要问,既然PoW成本如此之高,那如何激励大家贡献算力、成为节点,以保证整个比特币网络的安全呢?比特币中提供了两种激励策略:

  1. 挖出某个区块的节点会得到一定量的比特币,这其实也是比特币唯一的发行机制(一级市场),所有的比特币都只能通过挖矿的形式被挖出然后进入流通领域;
  2. 矿工处理交易信息可以得到一定量的手续费,这其实是存量比特币的流通(二级市场),而当比特币的2100万枚被完全挖出后,激励策略就只能依靠手续费这种方式了。

这些激励策略也隐含地鼓励了节点保持诚实,若某个贪婪的攻击者真的拥有了过半的CPU算力,他不得不做出选择:到底是篡改交易记录,把他已经花出去的比特币再转回来呢?还是老老实实地挖矿赚钱新币和手续费呢?很可能,老老实实地挖矿是更有利的,毕竟能赚到的币比其他所有节点加起来都要多;而破坏比特币体系也将会破坏自身财富的有效性,毕竟若比特币不再可靠,其价值也会迅速崩溃。这里多提一点,攻击者并不像一般人想象的那样可以为所欲为、任意篡改或伪造交易记录,他能做的只可能是将其最近花出去的比特币偷回来。

PoW为什么有效?

比特币在没有任何组织或团体维护的情况下,仅仅依靠社区志愿者自发维护,稳定运行了10年之久,期间从未发生过重大问题,这不能不说是个奇迹,也足以证明了比特币背后共识机制的有效性。我们忍不住要问,为什么比特币能够做到?为什么比特币背后的共识机制能够如此有效?bitnodes数据显示目前比特币节点数目超过1万(比特币节点类型较多,不同口径数量可能不一致,这里仅考虑全节点)。为什么比特币能够在permissionless的网络环境中,协调上万的节点保持一致性?

笔者粗浅的认为,可能有以下几个原因:

  • 有效的激励策略:通过激励策略有效地激励了更多节点参与到比特币的点对点网络中,节点越多比特币网络越安全。
  • PoW:挖矿出块需要消耗CPU算力,人为地制造障碍、增加成本,提高了攻击者的作恶成本。
  • 博弈论思想:激励策略也考虑了博弈平衡,理性节点保持诚实的收益更大。
  • 通讯效率:比特币节点间的通讯效率并不低效,大家可能注意到其中也涉及到了交易和区块的广播,不过这种广播并非是两两广播,而是由某个节点(发生交易或算出PoW的节点)将信息广播到其他所有节点。另外,交易广播并不要求触达所有节点,只要有许多节点接受,不久之后就会被打包。2014年也有Miller等人(Anonymous Byzantine Consensus from Moderately-Hard Puzzles: A Model for Bitcoin)严格证明,消息复杂度并不随网络大小而增大,而是一个常数。另外,区块广播也容许消息丢失,若某个节点未收到某个区块,则当它接收到下个区块时,会意识到自己遗漏了上个区块,而主动向其他节点请求该区块。
  • 概率性的一致性:相比其他一致性算法,比特币的共识机制最特别的是不再追求确定性的一致性,而是追求概率性的一致性。当某个区块刚被挖出的时候,其包含的交易信息并非被所有节点最终确认、其包含的数据并非是最终一致性的结果,还是有可能被攻击者篡改的;但是随着后续节点数目的增多,这种被篡改的可能性指数下降,最终一致性的概率显著增大;一旦后续节点超过6个(也就是经过约60分钟),这种一致性就可以被认为是确定的、最终的。

显然,比特币的共识机制不再拘泥于分布式算法层面,而是包含了更多经济学、博弈论、概率论等思想,因此可能叫作共识机制更为恰当。不过,我们仍然可以将比特币的PoW共识机制放到一致性问题的框架内来思考,从FLP和CAP的角度来看:

  1. 比特币最大程度地考虑了故障容错和网络分区容错,这也是对网络openness的必要要求,因为开放网络环境极其复杂,谁都可以随时进出,节点遍布全球各地,机器故障、网络分化、系统攻击随时可能发生,容错是必须需要考虑应对的。而利用PoW机制,比特币不仅做到了故障容错,而且结合密码学非对称加密技术,也可以做到拜占庭容错,抵御恶意篡改与攻击。
  2. 比特币尽可能地保证了liveness和availability,比特币的出块时间总是在10分钟左右,这也就意味着系统总可以在10分钟内达成一致;比特币网络十年来不曾瘫痪,从这个角度来讲确实将可用性做到了极致。然而,我们必须指出,比特币的可用性与我们通常理解的互联网领域的可用性是有很大差异的。互联网领域的系统可用性,不仅要求系统稳定运行不宕机,还对服务体验如响应时间有明确要求。如果你用支付宝转账,不是随时可转、3秒到账,而是告诉你系统繁忙,需要等待10分钟、甚至30分钟,这显然会被认为服务不可用。然而,这一现象在比特币中一直在发生,比特币每10分钟一个区块,而区块大小只有1M,装不下太多交易,若同一时间交易过多,只能一直等待,直到能被下一个区块打包进去,所以经常可能需要等待20分钟、30分钟、甚至更久。从这一角度对比来看,其实比特币网络放宽了对响应时间的要求,做到了比较基本的可用性:读的可用性极高,而写的可用性很低。
  3. 比特币对于safety和consistency,不再追求确定性,而是采用了概率性的保障,基本可以认为保证了最终安全性和最终一致性,只不过这里的“最终”依然是有时间条件的、基于概率的。比如,如果我刚刚给你转账了一个比特币,没人敢说这个结果是确定的、最终的,但是随着时间的推移,不断有新的区块被挖出,我转账的交易信息也会被更多的节点确认、被更多的后续区块强化,这一结果确定性的概率不断增大,一旦过了足够的时间(如1个小时),我们从概率角度可以认为结果被篡改的可能性极低,系统达成最终一致性的概率极高,从实践上就可以认为系统保证了最终的一致性。

综合来看,不难看出,比特币的PoW共识机制在FLP和CAP的限制下,做到了比较好的折中权衡,在实践中确实提供了开放复杂网络中分布式一致性问题的可行解法,比特币近十年来的稳定可靠运行也有力地证明了这一点。

另外,比特币的PoW算法也被Miller等人(https://socrates1024.s3.amazonaws.com/consensus.pdf:Anonymous Byzantine Consensus from Moderately-Hard Puzzles: A Model for Bitcoin)严谨地分析并证明:

  • 比特币网络可以看作是由近似无穷节点组成的,每个节点贡献一小部分算力,并且相应地每个节点都有较小概率可以创造区块。
  • PoW算法依赖于同步网络模型。在该模型中,若网络延迟为0,则算法可以容忍50%错误;而以目前真实观测的网络延迟来看,比特币可以容忍49.5%的错误;若网络延迟等于区块时间(即10分钟),则只能容忍33%的错误;若网络延迟接近无穷,则算法的容错也趋近于0。
  • 比特币PoW算法具有扩展性(scalable),这是因为共识时间和消息复杂度都与网络大小(网络中的节点数目)无关,而只与错误节点的相应算力有关,可以认为是一个无量纲常数。

可见,PoW算法不仅在实践中可靠,在理论上也能经受考验。PoW算法采用了同步模型与随机概率来规避FLP的确定性异步模型不可能定理。而PoW独立于网络大小的可扩展性,与PBFT算法O(n2)复杂度相比优势巨大:节点越多,系统效率并未降低,而系统却更安全。

PoW到底是什么?

我们忍不住要问,PoW机制到底有何神奇之处呢?

其实,大家可能也意识到了,PoW的思想并不高深,事实上也并非是中本聪首创。早在1993年这一思想就被提出用于对抗垃圾邮件(Pricing via Processing or Combatting Junk Mail),但直到中本聪创造比特币之前,这一思想都尚未得到广泛应用。PoW思想的精髓就在于故意制造障碍、增加参与者的成本,以尽量降低参与者的恶意企图。比如要求请求者做些额外的工作以检测DDoS攻击、垃圾邮件等,也比如最常见的登录网站需要输入验证码,也是为了增加登录成本,防止网站被攻击。这类任务最核心的特征是非对称:对于服务请求者来说,完成任务必须有一定难度;而对服务提供者来说,验证任务必须很简单快速。对于比特币PoW而言,显然符合非对称性:不断试错,寻找使哈希符合条件的nonce(随机数)需要消耗大量算力,而验证寻找到的nonce是否符合条件只需要做一次简单的哈希运算验证即可。

比特币的PoW本质上是one-CPU-one-vote,一个CPU投一票。为什么选择CPU,而不是IP地址呢?这仍然是基于任务难度考虑,若是one-IP-one-vote,则系统可以被拥有大量IP地址的人(如ip供应商)轻易控制。相对而言,至少在当时(尚未出现ASIC和FPGA)CPU仍然是比较昂贵的硬件,想拥有大量的算力(CPU+电力)并不容易。当然,这其实也隐含地为比特币的价值提供了现实锚定:虚拟的货币体系通过算力找到了现实物理世界的价值锚定,虽然在很多人看来这种算力的消耗是毫无意义、浪费能源的。

也有很多人提出如何降低比特币的挖矿成本,当然这种思考尝试有其积极意义,这种工作量证明的成本需要适宜:难度过大、成本过高确实浪费能源较多,不过比特币网络的安全性也得到了提高;难度过小、成本过低则会起不到防攻击的目的,进而也会降低比特币网络的安全性。这其实是一个需要做tradeoff的问题,也是一个偏主观的价值判断,取决于大众对比特币的认识和定位。价值判断总是充满了主观偏见,目前对于比特币的争论如此之大,其实也正是因为社会大众尚未达成共识,尚未构建出对于比特币未来共同一致的想象。

简言之,比特币的PoW是一整套的机制,包含了技术上的权衡、经济和博弈的考量,这一整套的策略和机制共同保障了比特币网络的安全可靠。

PoW机制的局限性

凡事没有完美,PoW机制也不可例外地存在局限,其实从大家对比特币的诸多批评也可见一二,通常地大家认为PoW机制存在以下局限性:

  1. 成本过高、浪费能源:大家对比特币浪费能源的批评声不绝于耳,digiconomist数据显示,比特币的全年电力消耗基本与新西兰相当,也相当于澳大利亚用电量的1/5;而每笔比特币转账交易的成本是每10万笔visa转账交易的3倍。虽然有时候这种对比有失公允(比特币交易即清算,而visa除交易成本之外还有额外的清算成本),也有不少人并不以为然。前文也提到这其实也是一种主观价值判断,但这毕竟是一种声音,有时候也是切实的痛点,比如恐怕没人愿意用比特币买杯咖啡,毕竟手续费可能会比咖啡还贵。而罪魁祸首当然是PoW机制所需要的CPU算力消耗,因此不断有人尝试改进,甚至提出新的解决思路。
  2. 效率低下:大家习惯了互联网的便捷,习惯了秒级到账和百万级别的TPS,对于比特币交易动辄需要等待几十分钟,每秒钟仅能支持7笔交易,显然不太满意。虽然这种对比也并不公正,毕竟银行系统后台只有几个机房、最多百台机器,并且交易只进入到了其中某台机器,事后的清算环节才保证了最终一致性;而比特币无任何单点,协调的是上万台机器,并且交易即清算。不过这种效率的低下也确实是事实,也不断有人尝试改进,如把比特币每个区块的size limit调大,让其每个区块能打包更多的交易,bitcoin cash就是这么干的;再如把比特币的出块时间改小,让其更快出块,litecoin就是这么干的。但即便如此,PoW为了保证网络安全性而要求的巨大的工作量证明成本,也注定了网络的效率很难有质的提升。
  3. 中心化风险:随着ASIC和FPGA等特制挖矿芯片的出现,普通个人PC想挖出比特币几乎是天方夜谭。挖矿越来越集中到有实力研发芯片的巨头企业上,而矿池(为了平滑收益大量节点组成联盟共同挖矿、平分收益)的出现也加剧了这一趋势。另外,对比特币block size limit的调大,也会导致运行比特币全节点需要庞大的存储空间,以至于无法在普通PC上运行,而只能运行在特制的大型计算机上。这些中心化的倾向无疑都会损害比特币网络的安全性,毕竟由全世界各个角落的普通PC构成的比特币网络的安全性远远高于由几个巨头公司直接或间接控制的比特币网络。虽然这一问题的争议更大,仁者见仁,但仍然有很多人在尝试寻求新的解决思路。

PoS

在这些新的解决思路中,无疑最引人注目的就是Proof-of-stake(PoS、权益证明),同样面对开放复杂网络中的一致性问题,提出了全新的解决方案。

基本思想

2011年在bitcointalk论坛一个名为QuantumMechanic的用户率先提出了proof-of-stake的思想

(https://bitcointalk.org/index.php?topic=27787.0 ),而后不断发展完善,得到越来越多人的信赖。

PoS的基本思想大致如下:

  • 所有节点不再同时竞争挖矿,而是每次仅有1个节点做验证者:在比特币网络中,所有节点都需要做PoW任务,也就是说都需要做复杂的哈希运算而消耗大量CPU算力,而只有最先找到答案的节点才能获得奖励。这种所有节点间的同时竞争挖矿无疑需要消耗大量资源,那么是否可以每次只有一个节点工作呢?如果可以,那怎么选定这个幸运儿呢?PoS中不再需要挖矿,不再有miner,而是每次只需要选出一个节点作为validator去验证区块的有效性。如果某个节点被选为validator来验证下一个区块,它将验证该区块内的所有交易是否有效。如果所有交易都验证有效,则该节点对该区块进行签名,并添加到区块链上。作为回报,该validator将会收到这些交易相关的交易费用。显然,在PoS中每次共识只有一个节点付出了劳动,且该劳动非常轻松,从而达到了节约资源的目的。
  • 想成为validator必须提供保证金:为了防止validator作恶,想成为validator必须提前往指定账户存入代币作为保证金或抵押担保金,一旦被发现作恶,则保证金即会被罚没,而诚实工作将会得到激励。显然,只要作恶带来的收益不超过保证金额度,节点就会老老实实地保持诚实。
  • 被选为validator并不是完全随机的,而是被选定概率与提供的保证金金额成正比:例如Alice提供100个币的保证金,而Bob提供500个币的保证金,则Bob被随机选为validator从而产出下一个区块的概率是Alice的5倍。这其实就类似于股份制公司,按照出资比例来划分发言权、最终受益权等,大股东出资多、承担责任大、相应的回报也大。
PoW与PoS对比图

(https://hackernoon.com/consensus-mechanisms-explained-pow-vs-pos-89951c66ae10)

不难发现,PoS也是采用了经济和博弈的思想,通过激励策略和惩罚机制来确保了网络的安全可靠。

PoS为什么有效?

PoS协议仍然符合传统的拜占庭容错算法研究的结论。目前围绕PoS的研究可以分为两条主线:一条围绕同步网络模型、一条围绕部分异步网络模型。而基于链的PoS算法几乎总是依赖于同步网络模型,并且其有效性与安全性可以像PoW算法一样被严格证明(https://nakamotoinstitute.org/static/docs/anonymous-byzantine-consensus.pdf )。

另外,从CAP的角度来看,基于链的PoS算法与PoW算法类似,也是尽可能地做到了容错性,另外在可用性与一致性之间,更多地保证了可用性。

如果说传统的一致性算法(Paxos、Raft和PBFT)实现的是确定性的最终性(finality)或一致性,那么PoS与PoW类似,转而寻求概率性的最终一致性。从传统CAP的视角,这其实是对一致性的弱化,然而从实践可行性的视角来看,也是一种全新的思维和突破。

而从PoS的设计策略来看,也可以分为两大阵营(https://arxiv.org/pdf/1710.09437.pdf ):

  • 一类是如前所述的chain-based PoS,主要是模仿PoW机制,通过伪随机地把区块创造权分配给stakeholders来模拟挖矿过程,典型代表如PeerCoin、Blackcoin等。其安全性与有效性可以参考类比pow来看。
  • 另一类是BFT based PoS,基于近30年来的BFT类一致性算法研究。基于BFT算法来设计PoS的思想最初在Tendermint中提出,以太坊2.0中的Casper也遵从了这一传统并做了一些修改完善。这类PoS的安全性与有效性可以参考BFT类算法来看,如可以从数学上证明,只要协议参与者的2/3以上节点都诚实地遵照协议,不管网络延迟有多大,算法都能保证最终状态不会出现冲突区块。不过此类算法也并不完美,特别是针对51%攻击问题,也尚未完全解决,目前该领域仍然处于开放探索阶段。

PoS的争论

PoS的思想并不复杂,而其中比较容易被诟病的恰恰就是这种与现实世界类似的按出资比例获取收益的制度。大家对现实世界的马太效应已经非常警惕,这种制度显然容易带来富者越富、穷者越穷的结果:拥有更多代币的人,将会有更多机会成为validator,从而参与网络并获得更多收益。

然而,对这一问题的看法争议很大,很多人提出了完全不同的看法,认为PoS相比PoW更公平、更有助于对抗中心化趋势。理由主要是:PoW挖矿依赖现实世界的物理硬件和电力资源,而这很容易带来规模经济(Economies of scale)优势。购买10000台矿机的公司相比购买1台矿机的个人更有议价权,甚至可以自主研发成本更低的矿机;而拥有10000台矿机的矿场,对电费的议价权也更高,甚至可以搬迁到电费便宜的国家和地区的电站旁边,甚至可以自建成本更低的电站。由此带来的后果就是越庞大的组织的综合挖矿成本越低,而这正是现实世界真实已经发生的事实。相比之下,PoS不需要依赖现实硬件,不存在规模经济优势,在不考虑价格操纵的情况下,买1个币的价格和买10000个币的价格是线性增加的,从这个角度理解,PoS可能更公平,更有助于去中心化。

对PoS的另一个担忧是其安全性,毕竟PoS不再像PoW那样做复杂的CPU运算以证明自己。在PoW中,若想发动攻击,需要控制51%的算力(近来也有研究发现只需25%算力即有可能攻击成功),这也就意味着需要拥有大部分的矿机和算力资源。而在PoS中,若想控制整个体系,需要拥有51%的代币。究竟哪个更安全?其实也不太好讲,不过可以从现实世界的例子来看,如果比特币算法切换为PoS,则控制比特币体系需要大约比特币市值的一半,大概是400~1600亿美金(比特币价格区间5000~20000美金),显然这一数字远远高于矿机成本,想拥有这么大资金量发动攻击几乎是不可能的,从这个角度来讲,PoS可能更安全。

除此之外,PoS因为部署成本很低(对硬件要求很低),在真实世界中会导致代币非常容易分叉,从而产生一堆山寨币,而PoW不存在这个问题。因为PoW依赖硬件挖矿,若想把比特币的某个参数改改,这很容易;但真想跑起来,则需要大量算力的支持,需要争取大量miner的支持,比如bitcoin cash从bitcoin中分叉出来就历经波折。而PoS完全没这个顾虑,随便某个人都可以下载开源代码、随意改下,拉几个节点就可以声称自己创造了一种全新的代币,比如从EOS(代币名)中可以轻易分叉出几十上百个山寨兄弟币,每个都声称自己很独特。这确实是事实,不过也不太容易说孰好孰坏。

PoS的改进优化

PoS机制中最关键的当属下一个区块validator或creator的选择机制,究竟谁来做这个幸运儿?前文所说的根据账户资金按比例按概率选择其实是最简单的一种方式,这种方式确实容易导致有钱人获得一劳永逸的收益,从而损害网络中其他参与者的积极性。目前有很多种思路来改善这一问题,其中比较有意思的是coin age-based方法,在选择creator的时候,除了考虑资金量,还会考虑coin age(币龄)。所谓的coin age指的是币在某个账户上的停留时间,比如1个币转入指定账户经过10天,可以认为币龄是10,而每次币发生变动币龄都会从0开始重新计算。通过这样,可以限制大资金量节点频繁成为creator,比如可以设定币龄达到30才有机会成为creator,而成为creator之后币龄立即清零。这其实是限制了大参与者的利益,为其他中小参与者提供了更多的参与机会。

基于PoS改进的比较有名的方案当属Delegated Proof-of-Stake(DPoS),其中采用了代理人委托机制。在DPoS中不再是所有节点都有可能成为creator,而是节点间相互投票,只有得票最高的一些节点才可能参与区块创造过程。具体如下:

  • 代理人的职责包含保证自身节点持续运行、收集交易信息并打包到区块中、签名验证并广播区块、解决网络中可能存在的一致性问题。
  • 对于大多数DPoS链来说,网络中的所有持币人(token holders)都可以向代理人投票,且投票权与持币数量成正比。用户也可以不直接投票,而把投票权委托给其他人来代表他们投票。
  • 投票是动态的、可变的,意味着某个代理人随时可能被选进来或选出去。而一旦某个代理人被发现作恶或欺诈,就将失去收入和名誉,这就起到了激励代理人保持诚实、保证网络安全的目的。代理人可以将收到的区块奖励按比例分给向他投票的用户(这其实相当于贿选,在有些方案中不被允许)。
  • 不像传统的PoS,代理人不再需要持有大量的代币,而是必须相互竞争从持币者那里争取投票。
  • DPoS限制了交易区块的验证者人数,这相当于牺牲了一定程度的去中心化,但却带来了效率的提升,因为网络达成共识所需的工作量大幅降低。
DPoS选举validator/witness过

(https://www.nichanank.com/blog/2018/6/4/consensus-algorithms-pos-dpos)

不难发现,DPoS通过引入投票机制,尽可能地保证了节点的广泛参与;而对validator数目的限制(一般是21-101个),尽可能地提高了系统的运行效率。虽然充满很大争议,DPoS仍然不失为一种可行的解法,越来越多的区块链系统也在尝试对其进行改进和探索。

在公有链中的应用

在公有链中,众多项目都采用了PoS机制,比较有名的有:

  • 以太坊

    (Ethereum:https://www.ethereum.org/ ):目前阶段以太坊仍然采用的是PoW挖矿机制,不过作为以太坊的创始人和公有链领域的领军人物Vitalik Buterin对于PoS机制显然更为青睐,也多次阐述过PoS的设计哲学(https://medium.com/@VitalikButerin/a-proof-of-stake-design-philosophy-506585978d51 ),以及PoS相比PoW的优势(https://github.com/ethereum/wiki/wiki/Proof-of-Stake-FAQ#what-are-the-benefits-of-proof-of-stake-as-opposed-to-proof-of-work )。目前以太坊正在开发基于PoS的Casper协议(https://arxiv.org/pdf/1710.09437.pdf),预计将于今年下半年发布,这种从PoW到PoS的转变也标志着以太坊进入2.0时代。如下图所示,在以太坊2.0 phase0阶段,将会发布采用Casper协议的PoS beacon chain,作为coordination layer(https://github.com/ethereum/wiki/wiki/Sharding-roadmap )。

以太坊2.0 layers和phases

(https://docs.ethhub.io/ethereum-roadmap/ethereum-2.0/eth-2.0-phases/)

  • EOS(https://eos.io/ ):作为DPoS思想的提出者Daniel Larimer发起了EOS公有链项目,其中众多节点会一起竞争,期望成为拥有记账权的21个Supernodes中的其中一员。这种类似现实世界议会制度的设计引起了非常大的争议,而超级节点的竞选也可能蕴含着巨大的商业利益,这些都已经超越了技术讨论的范畴,在此不做过多讨论。

Proof of X?

其实,PoS机制的兴起除了其本身具备的低成本、高效率、去中心化等特点之外,还在于它打开了一扇新的大门——基于博弈论机制来设计如何降低中心化风险的一系列技术,如何预防中心化垄断巨头的形成,以及在已有巨头的情况下如何防范它们损害网络( Proof of stake opens the door to a wider array of techniques that use game-theoretic mechanism design in order to better discourage centralized cartels from forming and, if they do form, from acting in ways that are harmful to the network)。

而随着近年来区块链(特别是公有链)的蓬勃发展,其他各种Proof of机制也层出不穷。从这里面的诸多机制中都可以看到PoS思想的影子,即如何从经济角度和博弈视角来设计制度尽可能地保证去中心化、安全性与高效率。下面对这些机制做简要说明:

  • Leased Proof of Stake:持币量非常低的众多节点可以将代币出租给其他节点,从而形成合力,增加成为validator的几率;而一旦选举胜出得到奖励,则按比例分配手续费,其实与矿池的思想比较类似。
  • Proof of Elapsed Time:所有节点都必须等待一定的时间才能成为记账者,而等待时间是完全随机的。而要想保证公平,核心的两个问题是:如何保证等待时间确实是完全随机的?如何保证某个节点真的等待了指定的时间?目前的解法依赖于Intel的特殊CPU硬件Intel SGX 系统,目前通常也仅能应用在permissioned网络环境中,如前所述的以太坊企业联盟EEA中。
  • Proof of Activity:PoA同时结合了PoW和PoS的思想。在PoA中,起始过程与PoW类似,仍然是miners间竞争解题挖矿,只不过所挖的区块仅仅包含头信息和矿工地址。而一旦区块被挖出,则系统自动切换成PoS模式,区块头信息指向一个随机的持币者(stakeholder),由该持币者来验证该pre-mined区块。
  • Proof of Importance:有感于PoS机制倾向于鼓励人持币而不是流通、也容易导致富者越富的问题,PoI在计算节点对系统的重要性上吸纳了更多的维度:除了考虑币的数量、币在账户上的停留时间之外,还考虑了交易对手(与其他账户的净交易越多分数越高)以及最近30天交易数目和大小(交易越频繁、数额越大分数越高)。
  • Proof of Capacity:也称作Proof of Space,思想与PoW类似,只是不再以CPU算力为衡量标准,而是以存储空间来衡量。
  • Proof of Burn:矿工必须烧毁一定量的代币,即将一定量的代币转入eater address(黑洞地址,只进不出,即私钥未知的地址),以此来证明自己。本质上与PoW的思想接近,只是工作量证明消耗了算力资源,而PoB直接消耗了代币本身。
  • Proof of Weight:PoWeight是在PoS考虑代币量的基础之上,增加考虑了更多的权重因子。比如FileCoin(IPFS分布式文件系统上的代币)考虑了你拥有的IPFS数据大小;其他的一些权重因子也包含但不限于Proof-of-Spacetime、Proof-of-Reputation等。
一致性算法概览

(https://101blockchains.com/consensus-algorithms-blockchain/)

不难发现,虽然这些Proof-of机制层出不穷、不尽相同,但其要解决的核心本质问题是相同的,即:让谁来成为能够记账的幸运儿?这些Proof-of机制只不过是采取了各种不同的策略来制定游戏规则,让各个节点尽可能公平地证明自己,从中公平地选出幸运儿。所有这些策略,包括基于CPU算力、持有代币数量、存储空间大小、随机等待时间、销毁代币数量、节点活跃度、节点贡献度等,都是在特定的场景下对于开放网络中一致性问题的探索。

一切关乎信任

从PoW到PoS,再到Proof of “Everything you can think”,对于permissionless网络中的一致性问题一直在探索中。“一致性”的内涵也在发生变化,从传统的如何防范网络与机器硬件的故障,保证网络节点间的数据一致性,到开放网络中,如何防范网络中人的作恶,保证网络中节点数据间的真实一致。可以说是从硬件的可信,迈进了“人的可信”,公有链技术也被视为“信任的机器”。不过显然,人的可信问题过于复杂,甚至也超越了单纯的技术范畴。目前阶段所能做到的也远远未能保证“人的可信”,更多的仍停留在人对于机器的信任、人对于“协议”的信任。不过可喜的是,我们终于迈出了这一步,开始直面这个棘手的问题,探索创新性的解法。

信任的机器

(https://www.economist.com/leaders/2015/10/31/the-trust-machine)

总结

这个世界充满了不确定性,计算机科学也一样。从计算机出现开始,我们就不得不面对机器硬件的不确定性:意外故障可能带来的问题。从互联网兴起开始,我们就不得不面对网络的不确定性:通讯消息可能的延迟、乱序、丢失。而应对不确定性问题最自然的解法就是冗余,通过大量节点来实现系统整体的安全性,避免单点故障,增强容错能力和抵御攻击的能力。正是基于此,才带来了大型分布式网络的蓬勃发展,而如何在不确定的网络和节点间寻找到某种确定性,协调众多节点间的一致性,正是分布式一致性算法需要解决的问题。能够应对故障类错误的CFT算法包括最经典的Paxos算法和更简单的Raft算法,可以在网络中正常节点超过一半的情况下保证算法的有效性。这类算法通常应用在环境可信的封闭网络中,协调几个到几十个节点间的一致性,如公司内部的分布式存储、分布式服务协议、分布式消息系统等。另外,也可以应用于由少数机构组成的需要授权才能访问的联盟链网络中。

然而,不确定的不止是网络与机器本身,还有控制网络中各个节点的人的行为。如何在可能存在捣乱者恶意篡改数据或攻击网络的情况下,保证分布式网络的一致性,正是拜占庭容错类算法BFT需要考虑的问题。BFT类算法中最常见的就是PBFT算法,可以在网络中正常节点超过1/3的情况下保证算法的有效性。即便如此,PBFT对于网络中恶意行为的应对能力仍然是有限的,另外其性能也会随着网络中节点数目的增多而显著下降。这些局限性也导致PBFT算法仅能用于环境较为可信的、有权限控制的网络中,协调几个到几十个节点间的一致性,比如联盟链场景中。

而在无权限控制的permissionless开放网络中,不确定性更加严峻,特别是网络节点背后的人的行为的不确定性。如何防止网络中的控制人之间通过腐败串通组成寡头,从而控制网络中的过半节点,达到控制、损害、攻击网络的目的,即是开放网络需要考虑的问题。从这一角度看,开放网络中的一致性还隐含了安全性的前提:即不仅要求节点间能够达成共识,还要求该共识确实是由节点众多控制人真实表达而形成的。而为了达到这种一致性与安全性,不仅需要实现物理硬件节点在结构上的decentralization,还需要尽可能地保证节点背后实际控制人的decentralization。为了实现这一点,需要保证任何人都可以随时部署运行网络协议而成为网络中的节点、可以随时进出网络;节点之间点对点通讯,无任何中心化控制节点;节点的角色是完全对等的,按照规则有公平的可能性参与记账。而如何协调开放网络中数量庞大的上万个节点间的行为,保证网络的一致性与安全性,即是公有链共识机制要解决的问题。其中,最典型的当属比特币首创的基于工作量证明的PoW共识机制,以及随后兴起的基于权益证明的PoS共识机制。这些共识机制不再局限于技术上的一致性本身,而是更多地引入了经济学和博弈论的思想,从经济和博弈的角度尽可能保证网络的一致性与安全性。

从传统的封闭分布式网络环境中的一致性,到有权限控制的联盟链场景中的一致性,再到无权限控制的公有链开放网络环境中的共识机制,面对的问题越来越复杂,应对的挑战也越来越严峻。从单纯的技术视角来看,其中对于consensus的研究是一脉相承的,这些一致性算法或共识机制同样也都受到传统分布式一致性理论研究中FLP impossibility和CAP theorem的制约。Paxos、Raft和PBFT都强调了fault tolerance与safety/consistency,而弱化了liveness与availability。而PoW与PoS则采用了全新的视角来考虑该问题,尽可能地保证了fault tolerance,以及liveness与availability,放弃了对于安全性与一致性确定性的追求,而仅仅以概率性的方式追求最终的safety与consistency。

另外,对于consensus的思考,也在不断深入,从单纯的节点间的数据一致性,到强调节点背后的人之间的共识与认同;从保证网络与硬件的可信,到尽可能地确保组成网络的节点背后的人的可信。虽然人与人之间的可信非常复杂,也超越了单纯的技术范畴,可喜的是我们已经走在路上,而目前在该领域正在进行的创新性的积极探索,也必将让世界变得更加可信。

注:本文篇幅较长、写作时间跨度较长、本人水平也有限,所参考资料可能有疏漏或个人理解偏差,欢迎大家指正、讨论、交流、建议,后续将进行更新。

参考资料

  1. An Overview of Blockchain Technology: Architecture, Consensus, and Future Trends
  2. https://101blockchains.com/consensus-algorithms-blockchain/
  3. Comparative Analysis of Blockchain Consensus Algorithms
  4. https://draveness.me/consensus
  5. https://yeasy.gitbooks.io/blockchain_guide/content/distribute_system/consensus.html
  6. http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.67.6951&rep=rep1&type=pdf
  7. https://dba.stackexchange.com/questions/18435/cap-theorem-vs-base-nosql
  8. https://www.quora.com/What-is-the-difference-between-CAP-and-BASE-and-how-are-they-related-with-each-other
  9. http://ug93tad.github.io/flpcap/
  10. https://ramcloud.stanford.edu/~ongaro/userstudy/paxos.pdf

    更多参考资料请点击阅读原文进入查看!