SDN实战团分享(三十):Microflow性能调优分享

编者按:本文系SDN实战团技术分享系列,我们希望通过SDNLAB提供的平台传播知识,传递价值,欢迎加入我们的行列。

分享嘉宾
--------------------------------------------------------------------------------------------------
分享介绍:张攀:BII天地互连的工程师,在公司里负责SDN产品和技术的开发,同时在ONF、OPNFV、ONOS等社区也有大量标准、开源,项目搭建等工作,目前在ONF担任工作组的副主席。
--------------------------------------------------------------------------------------------------
Hello大家好,很高兴可以在这里和大家分享一下我的个人开源项目Microflow的相关工作。

我是BII天地互连的工程师,在公司里负责SDN产品和技术的开发,同时在ONF、OPNFV、ONOS等社区也有大量标准、开源,项目搭建等工作,目前在ONF担任工作组的副主席。

因为之前在做SDN控制器性能测试的缘故,对目前主流的开源控制器的性能都做了一些定量的测评,结果显示并不令人满意。

上周的那个paper里也同样认为当下控制器的性能是限制SDN网络部署的瓶颈,虽说分析得并不全面,但也部分说明了现状。

分析过CBench的源码,也在公司带领开发自己的测试工具,其实CBench的测试方法,并不能恰当地模拟真实的网络环境,给出的结果应当说还是明显偏高的。

基于以上认识,起了念想要自己去做一个轻量、高效,同时又可以解决切实问题的控制器。初衷并不是想要像时下流行的那般去改变什么,而更多的是对一次心血来潮的长久的珍视。

设计任何软件当然首先是对架构的设计,在Microflow的实现过程中,主要侧重的还是对性能优化的考虑。这一部分涉及一些硬件运行的原理,同时也参考了Nginx\redis\memcached\DPDK\Linux kernel的软件设计。在接下来的分享里,我会首先介绍一下控制器的架构,然后重点介绍几个性能优化的技术。最后简要介绍一下Microflow的开发现状和路线图作为总结。

针对Microflow的架构调整过好几版,实现了之后测一测,发现不太理想于是弃掉重来。所有的调整均是出于性能和资源占用的考虑,务求达到简洁高效可拓展的目的。当前的架构设计如下图:

采用Epoll做socket的异步I/O,接收到的OpenFlow数据直接进入消息处理队列。系统或上层APP注册消息处理方法,以响应特定事件。同时将设备信息、主机信息、拓扑信息统一管理和维护,为上层应用提供查询、分析、计算等服务。另外集成一个HTTP的服务器提供WEB界面和REST的接口。

在线程设置方面,socket I/O由独立的线程处理,消息处理(事件响应)由另外的线程负责,Microflow会处理各个线程与CPU的亲和性关系,数量可以根据CPU核心数目调整(一般不超过核心数量),另有独立的线程负责Timer/Log/HTTP请求/等事务。

多线程的好处是可以充分利用多个CPU核心,但必然带来竞争和死锁等问题。在Microflow中,消息队列,网络资源的哈希表和储存空间就都成了线程之间的共享内存,对共享内存的加锁带来的进程阻塞将成为新的性能瓶颈。在Microflow中对读写访问密集的内容都采用了无锁化的处理,后面会有介绍。

下面介绍几个Microflow采用的性能优化技术

性能优化的目标,就是伺候好CPU,让它能愉快得满速率运行。对CPU来说,它需要的无非是指令和数据。可以更快地取得数据(指令也是一种数据)去计算,可以用更精简的指令完成计算任务,就是所有性能优化的目的。

最理想的情况,就是CPU需要什么数据,什么数据就在它的缓存里。因为缓存和内存速度上的巨大差距,必须利用好CPU缓存。为了做到这一点,是需要一些巧妙的设计的。下面是一个现代计算机系统存储读写速度量化比较:

缓存和内存的读写速度相差数百倍, 将有用的数据写入到缓存里就是成功的一半

先从CPU从内存取数据说起。给CPU一个内存地址和数据长度,它就会自动把数据加载到自己的缓存里了吗?并不是这么简单。在CPU看来,内存的数据是以4字节、8字节的”数据块”存储的。假设CPU需要一个4字节的数据,如果该数据的起始地址是4或8的倍数,那么CPU可以通过一次操作取得数据,但如果数据从地址0x1开始呢?如下图:

如果是这样的话,CPU需要做很多额外的工作,才能从内存中取得该数据。第一步,读取addr 0-3的数据;第二步,将该数据向左移动1位,第三步,读取addr 4-7的数据,第四步,将该数据向右移动3位,第五步,将两个移位后的数据合并成目标数据,如下图:

出于性能考虑,第二种情况是要尽量避免的。这也就是所谓的”内存按4字节对齐”。虽然更小字节的内存对齐可以带来一些空间上面的压缩,但在我们的场景下并没有带来任何边际效益。

对于已经加载到缓存中的数据,也不是就此可以高枕无忧。CPU的缓存并不是以字节为单位,而是以一个Cache Line为单位。Intel的CPU Cache Line通常是64字节。在CPU从内存中读取一个数据的时候,从这个数据开始的64字节的内容都会读取到缓存中。

这在多线程环境下都会带来影响,如果两个线程分别操作的两个数据相隔在64字节以内,比如队列结构体的入队和出队指针,那么线程1在更新了入队指针之后,为保持数据的一致性,会导致拷贝了相同Cache Line,只操作出队指针的线程2的缓存失效。线程2只能重新从主内存读取出队指针。这样即便两个线程在数据操作方面不存在竞争,但还是会互相影响,极大地提高Cache miss的概率,这种现象称为False sharing。

一个简单的方法是在两个指针之间添加Cache padding,即添加一个Cache Line长度的无用数据。这样两个指针就会出现在两个不同的Cache Line之中,分别为两个线程所用。因为前面提到的cache和内存的巨大的速度差异,用一组简单的测试数据可以说明False sharing带来的影响:

这个测试是,每个线程都在操作一个int数据,做简单的自加从0至10M。在数据中可以看出,在8个线程的情况下,不发生False Sharing的执行效率(绿线)是发生False Sharing(红线)的一百倍以上。

利用Cache Line的特性,也可以将某一个线程需要一起操作的数据安排到一起,进一步降低Cache Miss。当程序里某些结构体比较大的时候,也可以考虑把它分割成几个较小的结构体,存在不同的Cache Line里面,也可以降低Cache Miss。

尽可能让有用的数据留在Cache里优化性能的一个手段。对CPU来说,它的另外一个工作就是执行指令。CPU并不是简单的按顺序执行程序的指令,为了提高效率,它采用的是流水线的方式。即在执行当前指令的同时,获取下一条指令。这样下一个指令周期就可以直接执行下一条指令而不必再先去获取。

如果程序一直按顺序执行,那么CPU的流水线就会一直保持满负荷工作状态。但在程序中不可避免的会遇到转跳的情况,就是常见的那些if..else..语句。当前面的判断指令还没有执行完的时候,CPU的下一条指令是取if后的还是else后的?如果取错,那么就需要在执行完判断指令后清空整条流水线,重新加载第一个指令,拖慢整个程序的运行。

如果我们可以给CPU一些“指导”,告诉它是if后面的指令执行的概率大,还是else后面的指令执行的概率大,那么它就可以在流水线里预先获取概率大的指令,从而尽可能地避免清空流水线对性能的影响,这就是被称为“分支预测”的技术。

用一个简单的例子说明一下分支预测带来的性能提升。

两组数据,各包含100K个整数,一组随机排列,另外一组升序排列。要做的处理很简单,遍历全部数据,将所有大于128的整数相加求和。简单表示一下: for data in array; if data > 128; sum+=data;

在执行判断的时候,因为第一组数据完全随机,所以无法预测是否大于128,流水线有一定概率被清空。而第二组数据可以预测在128之后的数据全部大于128,之前的全部小于。执行的指令都是一样的,但因为流水线的问题,运行的效率相差6倍。详细的测试代码和结果可以参看这里:http://stackoverflow.com/questions/11227809/why-is-it-faster-to-process-a-sorted-array-than-an-unsorted-array

昨天我看到Facebook新开源的高性能压缩算法Zstandard的介绍,里面也提到利用减少分支的方法提升效率,它给出了一个while循环的例子。除此之外,一些简单的if判断可以用位操作的方式代替。比如返回两个数中较大的数,除了if(x>y) return x; else return y;之外还可以max  = x ^ ((x ^ y) & -(x < y)); 这样就完全不会有分支的问题,代价就是程序的可读性下降一些。其他的更多位操作的技巧可以参看:https://graphics.stanford.edu/~seander/bithacks.html

目前的感觉是软件性能调优必须得向硬件的方向上去靠(除了之前说的,还有NUMA等很多需要考虑的东西),或者优化Linux的内核(bypass socket/fast socket/huge page等等),单纯的优化算法(除了特别适用于场景的)能起到的效果比较有限。关于CPU的内容还有很多,限于篇幅这里就不再一一介绍,分享一篇比较不错的文章,有兴趣的朋友可以自行深入:http://igoro.com/archive/gallery-of-processor-cache-effects/

在采用了内存对齐,Cache padding,分支预测等技术之后,测试了一下Microflow的Cache Miss rate,看一下执行最集中的函数:

这是从消息队列里读取数据的函数,相当于所有数据包的入口。指令获取1219K次,Miss 4次,读数据578K次,Miss 11次, 写数据187K次,Miss 0。

总体来看,Cache Miss主要发生在Kernel提供的函数里面。。比如memset/memcpy等等。。所以还是有提升空间的。。。现在因为时间有限,暂时不写自己的wrapper函数,现在的方法就是实现内存池,只在初始化的时候调用这些函数,尽量减少调用次数,还是有一些效果的。。。

在介绍完关于硬件的内容之后,软件本身也有很多可以优化的内容,这个展开说可以说一天。。。在这里推荐一本书:Computer Systems: A Programmer's Perspective,里面就是在教各种如何写高效的代码。虽然在某些领域的深度并不够,但胜在覆盖面较广。感兴趣的朋友可以从网上下来看看。我在这里主要介绍一下Microflow里无锁链表和哈希的实现。

首先想说明的是,锁本身并不是降低多线程程序性能的原因,对锁的集中争夺才是。另外即便是号称可以实现无锁的”原子操作”也有它本身的cost,并不仅仅是CPU执行一个指令那么简单。在这里并不想深入太多细节,总之我的经验就是,无锁并不一定快于有锁,完全看具体应用的场景和需求。但在SDN控制器中,集中管控的网络资源信息一定是各个线程争抢的主要对象。所以实现无锁的数据结构也就有了很大的现实意义。

现代很多程序为了提高效率都采用了内存池的设计。即在启动的时候向内核申请一大块内存,当程序需要内存储存数据的时候,在用户空间分配一小块内存即可,而不必每次都去麻烦内核。Microflow也不例外,这样做有很多好处,但用户必须对分配的内存进行管理,最常见的就是将具有关联数据的小内存块用指针”连”起来,这也就是无锁链表的工作。

链表主要的意义其实就是告诉你下一个元素在哪里,这样只需要抓住链表的”头”,就可以把整条链拎出来。比如局域网里的交换机数据可以组成一条链表,一条网络路径上的所有交换机可以组成一条链表,或是同一台交换机上的端口数据可以组成一条链表,等等。

所以对链表来说,最关键的就是正确指向下一块内存的地址。多线程的场景下,有可能多个线程都想去修改这个地址,就会产生竞争,一旦改错,后面的数据就永远丢失了。

一个办法就是用到被称为”Compare-and-swap”(CAS)的原子操作。该操作的作用是,读取一块内存的值,并将它与某个值相比较,如果相同,就将这片内存的值替换为一个新值,如果不同,则维持原样。所谓原子操作,就是当某线程在执行该操作的时候,CPU保证该操作不会被任何其他的线程打断,无锁就是靠此实现。

如上图所示,两个CPU都想去修改同一块内存中的值,CPU1想要将56改为57,在图示的情况下可以成功,而CPU2想要将55改为56,因为和现在内存上的值不相等(说明已经有其他线程更改过了),所以不会成功。对CPU2来说,需要重新读取一下该内存的值,然后再执行一次CAS操作。

如果将56想象成链表的next指针,那么就可以利用CAS实现无锁操作。简单描述一下插入节点的操作:

首先新建节点(20),然后找到它要插入的位置,将它的next指针指向节点(30)

然后对节点10的next指针执行CAS操作,如果该指与操作前获取到的next指针相同,则将它更新为节点20的地址。如果不同,说明有别的线程已经更改了next的值,则重新执行以上的操作,直至成功。如此可以完成链表的无锁插入。

节点的删除也是同样。但删除的时候存在一个问题:

当我想要删除节点10,我只需要将头节点(H)的next指针指向节点10的next节点(30)即可,可以用CAS操作实现。

但如果此时有另外一个线程在如上图的位置插入了节点20,那么最终的结果便是,头结点还是指向了节点30,直接越过了节点20,即节点20的插入并没有成功。

解决的方法是为每一个链表节点结构增加了一个标志位。当要删除某个节点的时候,先将该标志位置1,表示它已在逻辑上被删除。而在插入的时候首先检查前序节点的标志位是不是1,如果是1就重新查找一遍前序节点。这样便可以避免以上的情况。

还是想强调一遍的是,无锁并不一定快于有锁,有锁也有很多种类,互斥锁,自旋锁等等,它们的特性也各不相同,锁的粒度等等也都可以调整,还是需要结合实际的需求来决定采取哪种方式。

至于哈希表,就直接利用了无锁链表。每一个哈希桶都是一条这样的链表。遇到碰撞的数据直接在链表的头结点之后插入即可。这样也就实现了无锁哈希表。

OK,关于性能优化的技术就简要介绍到这里。下面看一些控制器性能测试结果。Microflow运行的服务器CPU Intel E5-2609 v2 @ 2.50GHz 4核 /16GB 1600Mhz/Ubuntu 12.04,测试工具是OFsuite,跑在另外一台服务器上。

首先测一下单socket针对包含有ARP报文的Packet_in消息,控制器回复Packet_out消息(广播APR)的吞吐和时延:

在单socket 100K pps的情况下,Microflow的最大时延是0.6ms,平均也就0.3ms左右。再来看一下拓扑发现的情况,500个交换机组成linear的拓扑,全部发现时间600多ms:

这里需要说一下的是,为什么不采用Cbench测试。Cbench首先是将700多个Packet_in数据包全部包入一个TCP的payload,组成一个最大长度的IP报文,然后通过loopback接口(默认MTU:65536)发给localhost控制器,然后看测试结果。这样基本上没有任何TCP和每一个数据包的Linux内核空间到用户空间的拷贝的开销,可以提升测试结果,但在现实中并没有这种场景存在。而OFsuite是将可选数量的Packet_in封装在单独的TCP里面,通过以太接口恒速发给另外一台服务器,这里使用的是每一个TCP单独封装一个Packet_in,最好地模拟了现实的网络场景。

OFsuite还能测很多,流表下发速率链路建立时间什么的,不过还是等到Microflow实现了这些功能再说吧。。。

最后看一下Microflow的资源占用情况:

在初始化全部内存池,没有处理数据包的情况下,物理内存、虚拟内存的占用情况,CPU占用率4%(轮询数据队列所致)。在处理单socket 100K pps级别的数据请求的时候,各个CPU核心的占用情况如下:

按照程序里CPU亲和性的设置,CORE 1是处理Epoll I/O的核心,CORE 2和3是处理事件的核心(这里只开了两个处理线程,程序里可以配置再开几个)。每个占用率在30%左右。看来单socket 100Kpps还远不是Microflow的极限,但后面受限于Linux本身(TCP window size/recv buffer size等),没有再提速测试。。。毕竟是工作时间在公司的服务器上。。

由于其轻量级,高性能的特性,Microflow未来可能在SDN+IoT,智能家庭,工业互联网、车联网等嵌入式设备为主流的领域找到用武之地,当然有人愿意在数据中心部署也欢迎 XD

目前开发的进度还算可以,眼下需要完成的是拓扑计算,流表下发和统计搜集的功能,这样至少可以先建立端到端的路径,同时做好与WEB UI的交互,实现underlay资源的实时可视化。接下来我计划重点开发一下集群功能,不打算应用目前主流的开源集群架构,而是仿照FPS游戏的同步机制自己实现,主要还是对开放了源代码的Quake 3这款游戏有比较深的感情 :p

当然也不一定就是这样了,本来就是为了填补一下业余生活,也许下面我会重点美化一下WEB界面,以后改行做前端了也说不定 :D 不过这个项目我肯定是会继续完善下去的,虽然可能从始至终都是我一个人的自娱自乐,但我也不想去提什么”功不唐捐”这一类的陈词滥调,我只是想证明,冲动并不仅仅是魔鬼,“一时的冲动”也不一定就只能“酿成大错”,反而它恰恰应该是被我们珍视的东西,因为我知道,它会带我们去到我们要去的地方,也许所有的启程,都是一次蓄谋已久的心血来潮。

关于Microflow就介绍这些,谢谢大家!补充一下源码地址:Http://github.com/PanZhangg/Microflow

--------------------------------------------------------------------------
SDN实战团微信群由Brocade中国区CTO张宇峰领衔组织创立,携手SDN Lab以及海内外SDN/NFV/云计算产学研生态系统相关领域实战技术牛,每周都会组织定向的技术及业界动态分享,欢迎感兴趣的同学加微信:eigenswing,进群参与,您有想听的话题可以给我们留言。


  • 本站原创文章仅代表作者观点,不代表SDNLAB立场。所有原创内容版权均属SDNLAB,欢迎大家转发分享。但未经授权,严禁任何媒体(平面媒体、网络媒体、自媒体等)以及微信公众号复制、转载、摘编或以其他方式进行使用,转载须注明来自 SDNLAB并附上本文链接。 本站中所有编译类文章仅用于学习和交流目的,编译工作遵照 CC 协议,如果有侵犯到您权益的地方,请及时联系我们。
  • 本文链接https://www.sdnlab.com/17799.html
分享到:
相关文章
条评论

登录后才可以评论

SDNLAB君 发表于16-09-08
3