时隔好几年，重温Django。

这是一篇没太多技术含量的怀旧小文。

其实我还在读书，没资格谈怀旧的，只是最近又把Django捡起来学了学写了写，便兀的想起大三的时候某个大晴天的周末午后，一个人蹲寝室在椅子上看Django的官方文档，一晃再次看这Django的文档已经是三年后了。

还记得高考完的时候家里才第一次买了电脑，在那之前我对电脑的接触也就是学校的几堂计算机课和几次去网吧的经历。还记得在考完的那个暑假，我打字奇慢，跟同学qq聊天时别人总在抱怨发了一句话我要过好久才回，而且还因为不会打问号被同学笑了好久（现在知道要按shift键啦）。在那个暑假，我才有了对电脑的初步学习，但是那时的我从来没有想过自己这样的计算机白痴以后将会靠着它来吃饭。

到了大学后，我发现自己对本专业的课提不起多大的兴趣，没有了高考的驱动，我发现再没有办法强迫自己学习不喜欢的学科。在那个时候，我也开始渐渐思考，以后自己究竟要干什么。这个时候就不得不提起我的一位大学室友了-才哥，才哥码代码水平一流，还在大二的时候就写的一手好代码，也是在他的影响下，我装了ubuntu，敲起了命令行，写起了c代码。

人在学习一项新的技能的时候总是会愿意得到正反馈，命令行里的字符显然没有能够对当时的我提供足够多的正反馈，这时我又望向了才哥，发现他在写网站。他写的网站那丰富的界面让人映像深刻，我想，我也要写一个网站。那什么web框架适合新手学习呢，我在网上搜索起来，也就是在那个时候我第一次听说了Django。于是时间走到了那个我一个人在寝室看Django文档的午后，以及到现在我都还清晰记得的看了一下午文档后感觉自己学会了不少后小兴奋的心情。

虽然网站后来因为种种原因网站没有写成（就是因为我对前端不感兴趣啦），但是那次学习Django的经历带给我的开心与兴奋让我确定了自己以后的生活与工作就离不开键盘啦。也是从那时后，自己正式开始自学计算机相关的知识和基础，再到现在已经过了三年了，时间真是种神奇的东西，在恍惚间这次我又接触了下Django，有种走了一圈回到起点的感觉。但是我知道这三年间我学会了很多，所以这次再接触Django明显没有第一次学习觉得难了。但是我知道还是有很多我不会的，还有很多我没接触过的，还是有很多我需要学习的。

我得继续不排斥新的知识，技能与事务，永远保持一颗初始化的心，积极的拥抱未知的未来，所以，继续加油吧，骚年。

Reference

既然写的是心得，就破天荒的第一次没有reference啦

前言

还是在去年年底的时候得知了kernel 4.9中添加了google推出的的一种新的tcp拥塞控制算法-BBR。当时就在自己的VPS上装上4.9的kernel，打开了BBR，测试了一下发现很好用，youtube一点都不卡。

不过遗憾的是当时并没有去了解这个算法的原理，后来就一直拖着了。这个周末终于不用在实验室加班，有了空闲时间就想找点事做，刚好想起了这个算法，搜索了一下发现中文资料并不多，就索性找到算法的原版论文，来尝试做一次分析。

BBR和现在linux 内核默认的的Cubic以及经典的Reno算法最大的不同在于对网络拥塞模型的理解。Reno以及Cubic都认为出现丢包就发生了网络拥塞，这种假设的前提是网络本身的丢包率非常低，因为这些算法不会区分这两种不同的原因导致的丢包。但是我们知道在现实中很多网络是会存在一定的丢包率的，最典型的的例子就是翻墙上国外的网站的时候。那么当网络丢包率比较高时，原先的这些算法表现如何呢？文尾给出的原始论文中有一张图，指出当网络丢包率达到百分之一时原始的算法几乎就卡住带宽接近于零了（Reno一丢包就慢启动的方式在不稳定的网络链路中根本没法有效的发包）。另外，Cubic和Reno根据丢包判断网络是否拥塞的这种方式还会导致另外一个明显的问题-Bufferbloat（缓冲区膨胀）。Bufferbloat指的是由于网络路径上的路由器都有缓存，Reno在慢启动过程中不仅会将数据包填满网络带宽，同时也会填满路径上所有路由器的缓存，直到缓存填满才会开始丢包减少发包。填满了路由器的缓存会导致后续的数据包排队过长，导致RTT突然增大增加的数据包的延时。这还会导致一个隐含的问题，为了避免丢包产生拥塞，路由器制造商会增大其缓存容量，更大的路由器缓存会导致更加严重的Bufferbloat问题，这样就在一个恶性循环中导致延时越来越大。

在这样的环境中，BBR出现了。BBR采用了跟原来的拥塞控制算法完全不同的模型，它不再根据丢包来判断是否发生拥塞，它直接测量网络的RTT和带宽。这里就要解释下拥塞控制所要达到的最优化目标了，对于一个网络链路，在优的条件下在网络上传输的数据包应该等于时延带宽积，也就是这些数据包完全填满了网络链路而没有填满链路上路由器的缓存。为了计算这个网络的时延带宽积，BBR分别测量的网络的最小时延和最大带宽来得到拥塞控制的最优化目标。

仔细想想，BBR所追求的才应该是拥塞控制的本质，而从Reno开始的一系列算法都是采取填满链路直到丢包的思路，而BBR的实现更加合理一些。

实现介绍

下面就类似Reno的方式简单说说BBR几个阶段和步骤。

首先类似于Reno，BBR也有慢启动过程，但是所不同的是，在慢启动过程初期BBR会测量RTT的值作为RTT的初始值，Reno慢启动过程一直到丢包才结束，而像上面说的BBR不会等到丢包，而是在不停的策略带宽，当带宽不再增长的时候就结束慢启动，将这时测量到的带宽当做带宽的初始值。

因为上一阶段测量慢启动结束点时BBR向网络中多占用了网络，那么就需要在这一阶段将多发出去的网络上的数据包排空，这时BBR进入drain（排空）阶段。指数降低发包的速率，随着网络中的数据包不断被接收排空，时延会不断下降，当时延不再降低时排空阶段结束，进入下一阶段。

排空阶段结束后，BBR进入稳定状态，在稳定转态下BBR交替测量网络的时延和带宽。下面讲讲具体测量的方式：

对于带宽，BBR以8个RTT为一个周期，在第一个RTT中将发包的速率增加25%，在第二个RTT中降低25%，后面六个RTT使用前面测量到的带宽发送数据。

对于时延，BBR以10秒钟作为一个周期，以这10秒钟的RTT的最小值作为新的RTT，如果在这10秒钟没有出现比当前RTT更小的值，那么网络的时延可能已经增大了，这时就进入时延探测阶段，在这个阶段中，BBR只发送4个数据包，用最小的RTT作为新的RTT值。

需要注意的一个点

对上面BBR的算法做点解释：
对于时延和带宽必须交替测量，不能同时测量，因为为了测量最小的RTT值，网络必须没有满，这时的带宽必然不是最大的。而为了测量最大的带宽，网络以满，RTT已经增大。所以这两个量就像是粒子的位置和动量一样没有办法同时测量的。

另外BBR用10秒钟作为一个周期，来测量RTT的值，所以对于短暂的RTT抖动并不敏感，这也是BBR算法和vegas算法不一样的地方。

小结

根据上面的分析，BBR其实比较适合的还是有一定丢包率的网络链路，在这种链路上BBR能够获得更好的带宽和更低的时延。但是尽管有如此多的有点，我们也要清楚BBR并不是万能的，在网络队列比较深的时候，如果Reno算法在BBR规定的10秒内还没有填满路由器的缓存也就是没有发生丢包的时候，BBR是弱于现在使用Reno和Cubic算法的。每种算法都有它合适的场景。

更多的分析可以看看参考链接中给出的论文，很好读也很好懂。

Reference

BBR paper
BBR ppt

这段时间一直被老师压着在实验室干活，有段时间没有写博客了，抽个空记录下去年写的一个简单的协程的实现。

协程

老规矩，先上wiki定义。在我理解上，协程本质上就是用户态线程，出现的目的是用来缓解系统线程过多时带来的系统调用和切换开销，另外一种横向对比的技术就是callback，这两者之间的对比都在我之前的一篇博客中有过介绍。

现在有很多语言都内置了对协程的支持，比如go还有python。当然goroutine和我们常理解的coroutine还是有些不同的，这些不同就留给以后我再抽空来写一篇介绍吧，今天主要是介绍如何用c在linux下实现一个简洁的协程库。

特性

既然已经有这么多语言支持协程了，那其实我在一开始考虑实现的时候就有想过实现的参考对象。从复杂度上来讲，我没有考虑支持类似于goroutine那样的M:N的调度器，反倒是python早期用generator来实现coroutine的模型比较合适。但是c语言是跑在系统的栈上的，不是像python那样在堆上有PyFrameObject对象，所以我还需要自己处理协程栈。

既然选定了参考对象，那么就可以列出要实现的协程库的几点特性。

1 支持yield和resume来实现手工切换

2 在yield和resume中支持协程间变量的传递

3 合适的处理协程切换时栈的切换

协程切换的实现

c语言并不支持函数的挂起和恢复，那么在切换协程的时候我们就必须要手工保存上下文，便于在恢复的时候使用。那所谓的上下文其实就是函数使用的寄存器和栈上的所有变量。既然要操作系统的栈，c语言就不合适了，只能使用汇编，当然linux本身也提供了ucontex来实现上下文切换，当然还有setjmp和longjmp也可以做到这一点。

在实现的时候我使用了linux的ucontext，总共有四个函数，最常用的就是makecontext和swapcontext，函数顾名思义，makecontext是用来修改上下文，把上下文的入口改成某个函数，并且可以传递参数给这个函数。swapcontext实现上下文切换。我简单看了看这两个函数的实现，有点类似于linux kernel中进程切换的实现，但是这比kernel中的schedule函数的是实现简单多了。

协程间变量的传递

类似于python的generator，yield可以将某个变量传回给主程序。这里不同的协程只是用户空间看起来而已，对于系统，都是同一个系统线程，他们共享地址空间，所以对于不同协程间变量的共享和传递，我们可以简单的在将一个协程要传递的变量放在堆中的某个位置上，然后将这个位置告诉给要切换过去的协程即可。位置的话就用某个类成员变量即可。

栈的处理

其实协程栈的处理相对而言方式有很多种。在这里我是用的是copy stack，就是为每个协程在堆中中保存它的栈，在协程切换的时候将系统当前的栈拷贝到当前运行的协程中，然后将要切换过去的栈拷贝到系统栈上。

这样做的优点是简单，缺点是切换中拷贝带来的开销在某些应用中不能容忍。好在我实现的协程库要求每个协程有最大的栈大小，一般而言开销并不会太大。其他的实现方式还有segmented stack，按需分配，开销相对要小一些，但是实现起来也比较复杂，这种方式gcc是支持的。

其他

我还实现了一个简单的调度器，用来处理不同协程的调度。但是仅仅只是考虑本系统线程内的协程，没有做多线程上的调度。golang的调度器就有多个系统线程，用来处理所有goroutine的调度，还可以使用工作窃取算法来平衡不同系统线程的负载。

另外，对于网络编程而言，可以考虑hook系统调用，将fd设置为非阻塞状态，在read或者write可能阻塞的时候将对应的fd挂载到epoll上面去，然后返回调度器，根据epoll的返回的可读或可写fd来选取下一个协程来运行。

Reference

Coroutine

面阿里一面的时候问了我innodb中mvcc的实现，当时并没有回答出全部的细节，只是说了innodb中没有真正的mvcc，是通过undo段来假装实现的，跟理论上的mvcc并不一样，有妥协。面完了突然想到这一点，就去翻了下mysql的Reference Manual，算是做个补遗吧。

定义

老规矩，先解释下定义。MVCC (Multiversion Concurrency Control)，就是多版本并发控制的缩写。在数据库中出现的原因是实现事务不同隔离级别的传统的加锁方式性能消耗实在太大，而现实中的很多应用都是读多写少，传统的悲观锁的方式不能满足需求，才引出了今天广泛应用的mvcc。

其基本原理是将数据同版本结合起来，在读的时候可以选择特定的版本，当读写不同版本时可以不用阻塞读。MVCC是一种后验性的，读不阻塞写，写也不阻塞读，等到提交的时候才检验是否有冲突，由于没有锁，所以读写不会相互阻塞，从而大大提升了并发性能。其实我们通常使用的版本管理系统git就是mvcc的，每个人都可以在本地修改，只有在提交时才检测冲突，是一种最终一致性系统。

理论上mvcc实现的是有条件的更新，只有在版本匹配的情况下才能更新数据，避免了长时间的锁定，是一种乐观锁。

InnoDB的实现

innodb的默认事务隔离级别是RR也就是Repeatable-Read。这个隔离级别下重复的读不会见到不同的数据，其实现就是通过给数据行加上不同的版本，实现一致性读。

innodb的数据行具体的格式这里就不列出了，只指出跟今天要解释的相关的两个，一个是6个字节的DB_TRX_ID，另外一个是7个字节的DB_ROLL_PTR。DB_TRX_ID 用来表示不同的事务号，通过这个来实现事务不同的版本。DB_ROLL_PTR就是innodb实现mvcc的主要方式，可以把它理解为一个指针，这个指针指向undo段中的上一个版本的数据。

具体实现多版本的时候就是通过这个版本号和指针来实现的。select操作的时候会使用当前版本号，然后对于每行数据会检查数据的版本号，只有数据的版本号小于select的版本号同时数据还没有被删除的情况下才会读出这行数据。update的时候会新增一行数据，在这行数据上修改，同时将DB_ROLL_PTR指向之前那行的数据，事务回滚的时候就可以通过这行数据来恢复操作前的状态。

所以，通过上面的分析我们发现，innodb并没有实现真正理论上的mvcc，它只是通过DB_ROLL_PTR指向undo段中的数据，没有实现核心的多版本共存，undo段中的数据类似于一个单链表是串行化实现的。之所以做这种实现上的妥协，是因为理想的mvcc对于一次修改多行数据的事物回滚可能会造成丢失更新。

小结

本篇只是简单的介绍了下innodb对mvcc的实现，发现它跟理论上的mvcc还是有不同的地方，只是利用了undo log中的信息而且写操作还是使用的悲观锁。具体的细节参考的是mysql的reference manual，顺便说一句，这里面对mysql介绍的很详细，可惜好多都没有读过 (逃

Reference

InnoDB Multi-Versioning

Memory Model可以简单的理解为内存的可见性，在多线程程序中是一个非常重要的概念，这次想系统的总结一下相关的知识。

背景

在并发编程中，一般有两种编程模型，一种是通过shared memory，一种是通过交换message。两种模型中语言的代表前者比如c++，后者比如go。在共享内存的模型中就有cpu与内存读写的动作，一般的情况是某一个线程往内存中的某个位置写了一个值，另外一个线程在同一位置读到这个值，这样两个线程间就有了通信。那这里的问题在于我们并不能假设多线程的读写顺序会按照我们预想的那样完成。

编译器或者cpu在操作的时候往往为了性能的优化会交换我们程序中读写操作的顺序，这是在单核单线程时代就一直有的优化手段，在单线程程序中，编译器或cpu会保证这样的优化不会影响程序的正确性，比如说他们不会交换有依赖关系的读写操作。

但是当随着技术的发展，摩尔定律由于功耗墙等一系列的原因失效后，各个cpu厂商开始堆砌多核的时代。当多线程的程序运行的时候，编译器或者cpu没法保证优化的正确性了，因为一个核并不能知道另外一个核上在跑着哪段代码。出于这样的现状，我们必须引入内存模型的概念，通过定义不同的内存模型，好让多线程程序运行的结果符合我们的预期。

不同的Memory Model会对编译器和cpu有着不同的优化限制，在较弱的模型中，编译器和cpu有着比较大的优化自由度，而在强一些的模型中，编译器和cpu就必须准守模型的约束，禁用某些优化的手段，甚至不能优化。

编译器乱序

Memory Model描述了cpu读取或写入内存的顺序，编译器可以在编译期交换我们程序读写的顺序，cpu在执行期也有可能乱序执行。所以在没有设定内存模型的语言中，比如c语言，下面的代码可能会出乎你的预料：

1
2
3

int num_a=0, num_b=0;
num_a=num_b+1;
num_b=0;

上面的代码如果gcc开启O2的优化，查看汇编代码你就会发现num_a和num_b的操作顺序被交换的，这就是程序的乱序执行，虽然顺被被交换，但是程序在单线程下的语义的正确性并没有被改变，所以这样的优化是可行的。

如果我们想要禁用编译器的优化带来的乱序效果，我们可以使用GNU内联汇编 asm volatile(“” ::: “memory”) 来消去编译器乱序。不过这样的设置只会影响编译器，并不会转化成程序的汇编指令，所以对cpu的乱序执行是没有效果的。

CPU乱序

cpu由于硬件优化的原因也有可能乱序执行程序，不过不同的cpu有不同的内存模型，也就是对乱序的种类有不同的限制。比如我们常见的intel的X86 cpu就是强内存模型的，它只有可能执行storeload乱序，也就是读操作也许会和不同变量的写操作交换顺序，但是不会和同一个变量的写交换顺序，那样就会影响程序语义的正确性，X86 cpu会遵循程序的因果性。

另外像嵌入式产品中常用的Arm cpu就是弱内存模型，它允许更多种类的乱序。这里我插入一张参考链接中的图片来说明乱序的种类：

可以看到对于X86而言，一个核的写操作在其他核看起来顺序是一样的，不同核的写操作顺序是没有保证的。之所以X86只允许这一种乱序，是因为写操作比较费时间，所以在架构上会将写的值直接放进一个叫store buffer的地方，这样就会导致其他核可能不能马上看见这次写操作。

对于cpu的乱序我们也有办法加以改变，对于cpu乱序，我们可以用内存屏障指令防止某些或者全部种类的乱序执行。对于X86而言，lfence代表load barrier，rfence代表store barrier，mfence代表full barrier。

在程序中我们可以写到 asm volatile(“mfence” ::: “memory”)，这样即使禁止编译器乱序又是禁止cpu乱序。

锁

其实上面禁止乱序的指令我们在平时的程序中很难见到，主要是因为锁的语义中已经带有禁止乱序概念。

以spin_lock为例，锁要完成的任务有两点，1) 在同一时刻只让一个线程进入临界区 2) 防止临界区中的代码被乱序到临界区外去执行。这第二点就是所得acquire和release语义，acquire语义指的是acquire之后的所有内存读写操作不能被提前到acquire之前，realease语义指的是realease之前的所有内存读写操作不能被放到realease之后。这两个语义对编译器和cpu的乱序执行做出了限制。从而保证临界区中的代码在锁操作的范围内执行。

这两点中的第二点很容易被忽略，第一点我们都知道是通过CAS去实现，那第二点其实在加锁和释放锁的时候通过lock前缀指令和memory指令实现的。后面有时间的话，我想写一篇如何写一个性能不那么差的自旋锁的实现。

但是要注意的是，锁没有对临界区内的操作的顺序有任何限制，只能靠语言的内存模型来限制。这就是为什么在C++11之前不加内存屏障的DCLP是不行的原因，不过这一点在C++11中已经修复了。

另外，参考链接中的第二条对内存模型有一系列的文章描述，说的都很好，非常值的推荐阅读。

Reference

Memory Model WIKI)

Preshing on programming

到这里，Minirpc一开始设计的基本功能都差不多完成了，但是还是有很多可以改善的地方。

回顾写的整个过程，从一开始思路不清晰，到后面一点点的完善，还是学到了不少的东西的。

后面还会抽时间继续完善，现在想到的几个需要完善的地方，比如添加长连接的支持，再比如现在的测试代码不全，没有覆盖所有的可能(这是遗留下来的问题，一开始就没有怎么写测试)。

到最后面，如果可以的话，想添加上服务注册发现节点，这需要实现分布式一致性协议，这个完成难度比较大，但是可以试一试。

完成了上一篇说的网络层，我终于可以实现client端和server端的互联了。那么现在是时候动手实现自己的Rpc框架了。

ProtoBuf

google开源的序列化框架，在开始实现Minirpc之前就已经准备使用它了。不光是实现高效使用方便的序列化/反序列化协议，它还提供了实现rpc的接口，看来google一开始就是打算在它的上面实现rpc框架的，当然就是现在的gRpc。

ProtoBuf的使用我就不多说，官网有参考文档。既然协议如此高效，我还稍微看了下它的编码方式，最主要的是varint编码和ZigZag编码，看来protobuf为了节省传输数据的大小无所不用其极啊。

RpcConnection

这应该是实现中最重要的类，管理着server端的rpc连接。目前有缺陷的地方时暂时还没有实现长连接，这里写下准备实现长连接的设计。

为了实现长连接，在client端需要根据不同server的ip地址建立几条少数的链接，在server端，需要使用心跳包来维持建立的长连接，即使断开无效链接。另外，如果链接数过多，可以使用时间轮的方法来踢掉长久没有响应的空闲链接。

RpcConnection在代码中是使用智能指针管理的，这里就有所有权的关系，就是确定谁拥有RpcConnection。在实现上我犯过一个小错误，就是在将普通指针换成智能指针的过程中，混用了普通指针和智能指针，导致测试运行程序的时候core dump了，显示double free。这里需要注意，资源要全部交给智能指针管理，不能自己再用裸指针了。

连接池

由于现在实现中都是短链接，频繁的断开建立链接需要消耗很多的资源和不少的时间，在server端，我使用了连接池。如果新的连接到来，就从连接池中取出一个空闲连接，连接关闭后将其放回连接池。

负载均衡

一开始没有设计多线程，仅仅在server端只有一个工作线程。最后面在服务器上运行测试的时候，发现性能比较差，才决定在服务端加上多线程的。

最后面的架构是是一个IO线程负责accept新的连接，将新到来的连接按照简单的round-robin算法用线程安全的接口放入四个工作线程，此后，连接就由工作线程管理了。这样改变了之后，性能有所提高(但是还是不满意，后面还要继续优化)。

Reference

ProtoBuf文档

一个后台应用基本上可以笼统的分为网络连接层，逻辑业务层和数据存储层三层。就像我在之前开篇里提到过的，MiniRpc没有做消息的持久化存储，所有基本上只有两层： 网络连接层和逻辑层。这一篇我就来记录下网络层中的一些技术选型和各种自己给自己挖的坑。

ReactorLoop

linux下做tcp高并发绕不开的IO模式-Reactor模式。在Reactor模式中，事件分离者等待某个事件或者可应用或个操作的状态发生（比如文件描述符可读写，或者是socket可读写），事件分离者就把这个事件传给事先注册的事件处理函数或者回调函数，由后者来做实际的读写操作。

在代码中我直接实现了ReactorLoop的类封装。为了完成这样的工作，需要抽象化出关注的事件Event和具体的IO复用机制IOMUtiplex。

IOMutiplex

在linux下实现IO多路复用最常用的系统调用就是epoll了，至于其他在unix网络编程中提到的select由于设计之初没有考虑大量连接的情况，所以每次都要轮询所有连接，效率不高基本已经很少使用了（另外不得不提到的一点是网上一搜都说epoll比select高效是因为使用了mmap减少文件描述符的拷贝，这个很不靠谱啊，我读过源代码没有找到这方面的内容，不知道是从哪里开始以讹传讹的）。

在MiniRpc中，我一开始直接封装了epoll来做使用，后来想起来FreeBSD下类似的系统调用是kqueue，为了统一IO多路复用的机制，后面我重构成共同继承一个公共的基类IOMutiplex。由于我使用的是linux，所以没有做kqueue的封装，多添加了一个poll的类封装，当然，默认情况下使用的是epoll。

Event

Event类抽象出ReactorLoop关注的事件。实际基本流程是通过ReactorLoop注册到IOMutiplex上。同时实现基于回调机制，Event还要添加关注的EventHandler，一般是读或者写。

技术细节

大体的连接层框架就是上面的这些，基本上参考了libvent的设计（后来发现redis也是这么做的），下面我谈谈自己在实际完成的过程中遇到的要注意的地方。

线程安全

使用多线程模型还是类似于Redis的单线程模型是在开发的一开始就应该定好的。这一点上我几乎是到最后面才决定从单线程转多线程的，那么就面临一个问题，epoll的并发操作。

根据man page，当一个线程阻塞在epoll_wait调用上时，另一个线程并发的往其添加fd是线程安全的，但是并发的删除fd是未定义的行为。

MiniRpc中client端是用户线程向ReactorLoop添加新建立连接的fd，server端是多线程应用，为了实现线程安全，我最后面限定所有需要需要跨ReactorLoop的操作必须继承task类，在ReactorLoop中添加了一个vector，用来接收其他线程推送的task，在ReactorLoop线程从epoll_wait返回处理完活跃连接后，处理vector中存储的task事件，在这些task事件中添加或者删除关注的fd。

这样做是线程安全了，但是vector需要靠mutex保护，锁的竞争可能会影响性能，后面需要想想解决的方案。

Buffer

实现中Buffer类也是中途决定添加的，看来还是经验不足啊。对于非阻塞IO，MiniRpc必须提供Buffer来缓存message，这样才能做到异步调用。在实现上，Buffer类就是简单的包裹了vector并提供了需要的接口供其他类调用，vector数据连续，如果更加在乎性能的话，可以仿照libevent或者STL中的deque的设计，将buffer设计成即是链表有是连续的存储，提高性能。

非阻塞的connect

Reactor模式要求在处理io操作的时候耗时尽可能的少，如果connect还是像传统那样阻塞住的话，则至少需要一个RTT的时间。所以需要换成非阻塞的connect，用select看是否可读可写，最后用getsocketop看是否连接出错，通过以上判断后才是成功连接。

资源所有权

下一篇也会提到这个，因为实在太重要了，在这上面吃了不少的亏。

在一开始划分模块设计类的时候并没有考虑类的所有权关系，导致测试的后core dump不断，valgrind也检测出不少的内存的泄露错误。后来的解决办法就是尽可能的将new/delete替换成shared_ptr，这样做后内存泄露是没了，却又引发了其他的问题，具体问题下一篇在来介绍吧。

总结

一开始是没有网络连接层的设计，准备直接用libevent的，但是看完了它的大体框架后动了自己写一个的心思。现在看来，基本满足了后面rpc对网络连接层的需要，但肯定还是有很多不足，还需要多多完善。

这篇文章根据16年暑假准备开始写Rpc库之前写的笔记整理的。

Rpc即远程服务调用，使用非常广泛，也有很多的开源实现，比如google的gRpc、微信的phxrpc,阿里的Dubbo。之所以重新造轮子开始纯粹是为了练手。到现在为止一开始设想的基本功能差不多都已经实现了，翻了翻EverNote，发现在编码测试重构的过程中还是遇到了不少问题，有设计上一开始没有考虑清楚的，有编码上的低级bug，还有一些调试上的，所以就想着从EverNote中整理出几篇博客记录一下。

这是第一篇，先介绍下如果要写一个自己的Rpc库所先需要基本概念。

消息模式：

一个Rpc系统中最重要的就是消息模式，消息模式定义了对传输消息的保证，常见的模式有：

• at least once ：指消息至少发送一次，可能超过一次
• at most once ：指消息最多发送一次，可能不发送

在实现中如何区分两者呢？很好理解，就是Rpc系统是否有持久化和重传功能，如果消息在指定时间内没有相应，就会触发重传，这就实现了at least once 。如果没有重传，就是at most once。

在我的实现中并不是at most once但也不是严格意义上的at least once。MiniRpc带有超时重传功能，但是没有对消息进行持久化，如果内存耗尽或者进程崩溃就会造成消息的丢失。这有点类似于ZeroMq。

另外多说一句，现实系统中由于网络并非百分百可靠，所以并不存在just once的模式。

调用模型：

前面的模式针对的消息的传输次数，那这里的调用模型针对的是调用方，分为同步和异步模型。

• 同步模型 ：指Client端阻塞在Rpc调用处，一直等到结果返回或者调用超时
• 异步模型 ：指Client端不用等待结果返回

MiniRpc同时支持上面两种模型。同步模型很好实现，直接阻塞即可，为了实现异步模型，我们需要注册回调函数供返回消息时调用。

调用基本流程：

我第一次接触到Rpc时觉得有点神奇，因为一台机器居然可以调用另外一台机器上的函数，其实稍微一想就会明白这就是一个加了Buff的网络库。

为了使用Rpc，需要在Client端和Server端各添加一个stub。

Client端的stub负责将方法、参数等组装成能够进行网络传输的消息体，同时找到服务地址，发送消息。

Server端的stub接收到消息后，根据提取出的信息，调用对应的函数，将结果打包发送给Client端。

所有这一切都对用户透明，所以在用户看来仅仅是调用一个函数，并不关心函数是在哪台机器上运行，只用等待结果即可，不用纠缠于细节，Rpc可以极大的减轻用户的负担。

网络模型

知道了一次Rpc调用的基本流程，我们就知道所有的Rpc都是要经过网络的，选择恰当的网络模型对于实现Rpc是至关重要的。

MiniRpc使用的是Reactor模型，基于linux提供的高效的epoll系统调用，同时加入了多线程模型，来应对耗时长的调用。

实现中网络层这一块的细节我会放在第二篇来讲解。

消息格式

确定了网络模型后，我们就可以在Client和Server直接收发消息了，那么接下来就是顺理成章的要确定收发的消息格式了。

消息一般分两种，request和reply，分别是Client到Server和Server回到Client。

Request：按照最直观的理解，我们需要在消息头添加上函数名和对应的参数，只有知道了名称server端才知道该调用那个函数。
其他还需要调用的超时时间，如果在这个时间内没有消息返回的话就会放弃本次调用，将超时异常返回给Client端。如果是异步调用还需要添加requestId，才能识别不同的异步调用。

Reply：包含返回值和已经函数调用的状态，同时还要包含RequestId。

序列化

序列化是可选的，一般选择序列化都是为了方便网络传输，如果不在乎消息的大小，直接使用JSON传输也是可以的。

MiniRpc选用了ProtoBuf来实现序列化，能尽量减小消息的格式，缺点是二进制协议不具备可读性。

服务发现

除了原始的通过ip和port提供服务以外，最好我们能将服务发现的过程自动化。

Server端将提供的服务提交给服务提供节点，Client端每次调用服务的时候从服务提供节点获取对应服务的server的ip和端口，再去连接server。

这就要求服务提供节点具有极高的容错性，避免出现单点故障，所以一般使用Zookeeper或者其他实现了类paxos协议的机器群。

这篇文章根据16年读bitcoin的论文写的笔记扩展而来的。

最近读了这篇关于bitcoin的论文，觉得很有意思。记得还是读大学的时候，有一段时间新闻里比特币炒的特别火热，身边也有同学认识的人很早之前买的比特币小赚了一笔，网上到处都是挖矿的帖子。那时是第一次听说比特币的概念，一直不是很能理解脱离了国家政府发行的货币有什么意义？数字货币又是怎样防止造假的？这背后的技术除了比特币以外还有别的用处吗？

直到读了这篇论文，我大概弄懂了bitcoin的基本流程，这里我想要尝试着回答一下上面的几个问题，如有谬误，欢迎指出。

什么是比特币

认识一个新的事物，先了解一下它的定义。参考wiki，bitcoin是一种全球通用的加密互联网货币，它的主要特点是采用点对点网络开发的区块链技术，实现了去中心化的数字安全货币。

好了，定义就以上这些，如果看这有点头晕没有关系，这是正常的，现在你只用知道每个比特币使用者都有一个数字账户，账户里存放着比特币，比特币是一种去中心化的数字货币，它最主要的用途就是在网上交易。下面我们就来一一了解它会遇到什么问题，又是怎样解决的。

比特币会遇到哪些问题

作为一种货币，虽然是数字没有实体的，它依然会遇到其他货币遇到的问题，比如如何防止被伪造？如何判断重复使用？如何防止别人偷窃你的金钱？

让我一一来看比特币对上面问题的解决方法。

如何防止偷窃？

这个问题比较好解决，只要用到密码学中的非对称加密的概念。每个用户接受比特币的地址由用户的公钥哈希得来，而私钥只有用户自己持有，在每一笔用户的交易上，用户都要用自己的私钥签名，这就是数据签名。收到钱的其他用户可以用公钥验证数字签名是否正确，这样就可以防止别人伪装成自己跟其他人交易了。这样做的缺点就是，一旦私钥被他人获取，就想到于你自己的钱包丢了，里面的钱都被人偷窃走啦。

如何防止被伪造？

那么假设我就是我自己，不是别人伪装的，但是我自己的钱包里没有钱，我想伟钊出一些钱来使用，比如我没有钱但却给张三发出了转账100元的信息，张三如何判断我到底到底有没有这100元呢？

想想现实生活中我们使用的人民币是怎样解决这个问题的？没错，就是给没张钱一个独一无二的序列号。仿照着，我们的比特币也可以这样做，通过一个中心化的类似于银行的节点，为每个比特币发放一个唯一的序列号，用户收到别人的转账后可以这个中心节点查询这次转账的钱是否有效，用户可以向中心节点确认两个信息，一是这个序列号对应的钱是否属于转账者，二是他是否还没有把这张钱花掉。如果这两点都是真的，那么用户就可以确认接受这次转账。

如何防止使用两次(double send)？

如何防止一张钱被使用两次呢？按照有中心节点的上面的做法，比如我有一张100元的钱，我同时给张三和李四发送转账100元的消息，他们都会跟中心节点联系，只有一个人会收到中心节点确认的消息，另外一个人会收到钱已经被使用了的消息，那么他就会拒绝接受这次转账。

看上去上面已经解决了这个问题，那还有什么好说的呢？上面的流程正确的前提是这个中心节点是安全而且可靠的，如果中心节点有意欺骗张三和李四，那么他们都会确认这次转账，这一张100元就被使用了两次。这个才是比特币要解决的问题的大头。

区块链

为了解决上面中心节点不可靠的问题，比特币的发明者直接放弃了中心节点，改为使用p2p。为了验证一次交易是否成功，收到转账的节点会将这次转账信息广播给整个网络，交由网络上的所有节点来判断这次交易是否有效。

那什么是区块链(block chain)呢？区块链是一串使用密码学方法相关系产生的数据块（称为“区块”，block）。新增的数据块总能链接到上一个区块，即整条区块链的尾部。kafka的一个工程师写个一篇文章，其中有提到整个数据库中的数据可以看做一连串日志记录后的结果，在这里比特币点对点网络将所有的交易历史都存储在“区块链”（blockchain）中，所以区块链可以看作记录着比特币交易的账本。区块链就是一个分布式数据，数据存储在每个客户端上，里面有每一张钱交易的所有历史，无需中心节点来分配序列号，一张钱从出生开始的所有流程都在区块链中存在。

一旦一次交易被”确认”，一个区块就被产生，链接在区块链的尾部。这里的关键是如何确定产生一个区块而又不会被伪造，比如如果我们设计的是类似于paxos协议一样，一次交易被整个网络中的大多数节点接受，就会产生一个区块，但是如果伪造者伪造出一大堆虚假的ip地址来冒充节点，就可以绕开其他人的判断，引导接受者确认交易。这里的关键是我们要选择一种伪造者不容易伪造两次的方法。

比特币选择的时计算量。计算量代表了一个机器的计算能力，伪造者只有拥有比一个网络更强更多的计算量才能误导接受者，而这是成本很高很难做到的。

具体的实现细节是，增对每个新增加的区块，需要计算hash的结果，关键是需要计算出的结果中必须要有指定个数的前导零，网络中的节点可以在消息中加上一个数比如10，然后计算hash，看前导零是否满足要求，如果不满足，换一个数再试。这就要求hash函数有足够的安全性，不能被逆向。比特币选的sha-256。

这样的计算没有什么取巧的途径，只能不断计算不能重试，这就需要很强的计算量才行。通过这样的手段，将伪造者挡在了门外。

分叉

其实上面的方法并不能避免区块链的分叉。考虑这样一种情况，如果有两台机器同时计算出了指定前导零的hash，并且同时广播给了网络，网络上的节点验证了计算出的结果是对的就会更新自己的区块链，那么现在网络上的区块链在末尾就有了分叉。

怎么解决这个问题呢？接受它。接受分叉，但是会不停的跟踪两个分叉，只要有一个分叉比另外一个更长，就转到更长的分叉上去。这样做的原理是，永远靠近计算能力更强的分支。

Reference

Bitcoin 论文

How the Bitcoin protocol actually works