xiaoxiaoling

将博客搬至CSDN

ET和LT:   
   LT一般用在单线程。
   ET和EPOLLONESHOT配合用在多线程共享一个epoll环境下，EPOLLONESHOT标记触发过的事件从epoll中移除，下次必须重新注册，用来防止多线程同时取到同一个socket的事件产生冲突。

epoll_wait 第三个参数 取事件数量：
   单线程模型当然尽可能一次多取一些效率高，多线程为了防止一个线程把所有事件取完其他线程饥饿，ACE实现是只取1个。

错误处理：
   EAGIN | EINTR | EWOULDBLOCK 重试。
   EPOLLERR | EPOLLHUP | EPOLLRDHUP 断开连接。

惊群：
   默认系统都会有这问题，据说新系统有修复不过还是处理一下比较好，一般解决方案是同时只有一个线程等待accept，可以单独线程accept，将连接在分给其他工作线程。nginx是多进程模型，使用了基于共享内存的互斥锁，使得同时只有一个工作进程的epoll含有accept的socket，通过这种方式实现连接数上的负载均衡（连接数少的工作进程得到accept锁的概率高）。

   为了避免大数据量io时，et模式下只处理一个fd,其他fd被饿死的情况发生。linux建议可以在fd联系到的结构（一般都会自己封装一个包含fd和读写缓冲的结构体）中增加ready位，然后epoll_wait触发事件之后仅将其置位为ready模式，然后在下边轮询ready fd列表。

epoll实现：  
   epoll内部用了一个红黑树记录添加的socket，用了一个双向链表接收内核触发的事件。

   注册的事件挂载在红黑树中(红黑树的插入时间效率是logN，其中n为树的高度)。

   挂载的事件会与设备(网卡)驱动建立回调关系，也就是说，当相应的事件发生时会调用这个回调方法。这个回调方法在内核中叫ep_poll_callback,它会将发生的事件添加到rdlist双链表中。

   使用mmap映射内存，减少内核态和用户态的不同内存地址空间拷贝开销。每次注册新的事件到epoll中时，会把fd拷贝进内核，通过内核于用户空间mmap同一块内存保证了只会拷贝一次。（返回的时候不需要拷贝，select要）

   执行epoll_ctl时，除了把socket放到红黑树上，还会给内核中断处理程序注册一个回调函数，告诉内核，如果这个句柄的中断到了，就把它放到准备就绪list链表里。所以，当一个socket上有数据到了，内核在把网卡上的数据copy到内核中后就把socket插入到准备就绪链表里了。链表又是通过mmap映射的空间，所以在传递给用户程序的时候不需要复制（这也是为什么比select效率高的原因，epoll_wait返回的只是就绪队列，不需要轮询 不需要复制完成的事件列表，select，poll实现需要自己不断轮询所有fd集合，直到设备就绪）。

   epoll_wait最后会检查socket，如果是 LT，并且这些socket上确实有未处理的事件时，又把该句柄放回到刚刚清空的准备就绪链表了（LT比ET低效的原因）。

 

可见，如果没有大量的空闲，无效连接，epoll效率不比select高。

测试数据（仅是刚接触go的时候好奇做的参考意义的测试）：  

   同样的环境，echo服务器测并发io，单线程epoll qps:45000左右，每连接/协程 go： 50000多，多线程epoll（开6个epoll，每个epoll开8线程，一共48线程）：qps 70000多。

 

慢启动：一开始指数级的增加拥塞窗口，到一个门阀值后变成线性的， 之后每次超时都把门阀值降低到原来一半（并且rto翻倍，TCP超时计算是RTOx2，这样连续丢三次包就变成RTOx8了，十分恐怖），拥塞窗口设置为1重新开始慢启动（指数级增加）。一切都是为了让路由器有时间处理积压的缓冲。（所以不适用于频繁断开连接的移动网络，这也是为什么以前的下载工具开多条tcp传输速度更快的原因）。

Nagle算法：第一次（此时没有等待ack确认，空闲连接）发送小包成功，第二次继续发送 ：哪怕发送窗口，拥塞窗口都很大，之前的包没有ack确认依旧不让发直到收到之前的 ack确认。

shutdown和close的区别:

close只是递减引用计数， shutdown的半关闭会影响所有的进程。

   工作上虽然和cdn没关系但是技术方向还是很多相似之处的，例如：负载均衡，缓存，分布式，路由等。
   cdn简单的说就是个复杂的大缓存，由于目标用户（包括源和端）广泛直接导致了其复杂性，遍布广节点多则需要分流负载甚至自组织，应用繁杂则需要分流路由，提速则需要缓存，稳定则需要监控调度，为了透明则需要各种映射。
   由于接入面广和网络的复杂性，不可能让客户端直接面对源，于是就有了专门接入客户端的边缘服务器/组，这些边缘服务器和后端的调度，监控，源服务器通讯。既然是缓存就涉及到数据一致性的问题，最简单的就是各接入端的边缘服务器在需要的时候到后台拉取，或者更智能的他们之间可以相互拉取，甚至后台调度提前推送。
   边缘接收到请求后首当其冲的问题就是对请求的内容 “去哪找”和“怎么去”，想要知道内容的位置，一般缓存的实现不外乎就是统一到一个目录服务器找，或者广播所有自己知道的节点问一圈，更高效的方法是将请求url哈希后直接找到目的地址，当然只要是缓存都会过期也就有TTL的概念。“怎么去”的方式多种多样，由于互联网web服务居多基于DNS的路由使用最广泛，缺点是客户端和中继点会缓存，更新需要一定时间。HTTP重定向，URL改写，也有直接在网络设备路由器上做，直接在路由表中保持路径。这些方法在cdn这个庞杂的系统中根据需要使用，例如边缘服务器为了接收到客户端的请求可以使用dns重定向，然后再用哈希或者url改写转发到后端的源。 
   现如今的网络内容有许多是动态生成的，对这些无法提前缓存的内容可以直接略过只存静态内容（分段缓存），组装的时候发送回客户端或者直接赋予边缘服务器生成动态内容的能力（边缘计算）当然这对网页的制作有规范。
   面向大众的服务都有潮汐效应，在热点时段的访问量是平时的几十上百倍（根据二八理论，80%的问题都是在20%的地方出现的，热点访问量也是大多访问小部分数据，如果能提前将热点缓存于各边缘服务器最直接有效），如果有自适应的动态调整功能整个服务会健壮很多。边缘服务器是离用户最近的，可以将每个节点看成组，组长监控负载自适应的添加删除组员（缓存服务器）以及更新dns，不允许组员跨组拉数据。当然如果客户端之间可以使用P2P相互取数据也是一个办法。   
   当前出现了基于流媒体的cdn，视频内容分发在后端以文件的形式传输（适合传输的格式更高效），到边缘服务器再以流的形式和客户端传输（不需要全部传完即可开始播放）。同时也要综合考虑时段需求，视频编码策略也很重要。

dpdk是通过许多不同的纬度来加速包处理的，其中主要包括：

 

hugepage大页内存(进程使用的是虚拟地址，一般页表(4k)能映射的虚拟地址空间有限，使用大页能减少换页次数提高cache命中，通过mmap把大页映射到用户态的虚拟地址空间有用过mmap的都知道这是实现共享内存的手段，所以dpdk还支持多进程共享内存)

 

cache预取 (每次预读当前数据相邻前后的数据)，批量操作数据，cache line对齐(通过浪费一点内存将要操作的数据对齐)

 

接管了网卡用户态驱动使用轮询而不是网卡中断

 

将网卡rx tx队列映射到用户态空间实现真正的零拷贝（传统堆栈至少也得一次拷贝，因为队列空间在内核而内核和用户态使用不同的地址空间）(传统堆栈为了支持通用性，例如ipx等其他网络，将包处理过程分了很多层次，层之间的接口标准统一数据结构就需要转换，无形中带来了巨大的成本，如osi七层模型而实用的就是tcp/ip四层模型)

 

线程绑定cpu

 

支持NUMA，不同的core属于不同的node，每个node有自己的mempool减少冲突

 

无锁环形队列(冲突发生时也是一次cas的开销)

 

dpdk通过tools/dpdk-setup.sh的脚本，通过编译、挂载内核模块， 绑定网卡（先把网卡ifconfig down），设置hugepage后就可以使用了。

 

 

在内核模块igb加载时，会注册pci设备驱动

static struct pci_driver igbuio_pci_driver = {

.name = "igb_uio",

.id_table = NULL,

.probe = igbuio_pci_probe,

.remove = igbuio_pci_remove,

};

 

在绑定网卡时，会调用igbuio_pci_probe，使用用户态驱动uio接管网卡(中断处理、mmap映射设备内存到用户空间)

系统启动时，bios会将设备总线地址信息记录在/sys/bus/pci/devices，dpdk程序启动时会去这里扫描pci设备，根据不同类型的NIC有对应的初始化流程。在后面配置队列的时候会把用户态的队列内存地址通过硬件指令交给NIC，从而实现零拷贝。

 

如果NIC收到包，会做标记，轮询的时候通过标记取数据包

while (nb_rx < nb_pkts) {

/*

 * The order of operations here is important as the DD status

 * bit must not be read after any other descriptor fields.

 * rx_ring and rxdp are pointing to volatile data so the order

 * of accesses cannot be reordered by the compiler. If they were

 * not volatile, they could be reordered which could lead to

 * using invalid descriptor fields when read from rxd.

 */

rxdp = &rx_ring[rx_id];

staterr = rxdp->wb.upper.status_error;

if (! (staterr & rte_cpu_to_le_32(E1000_RXD_STAT_DD)))

break;

rxd = *rxdp;

发包的轮询就是轮询发包结束的硬件标志位，硬件发包完成会写回标志位，驱动发现后再释放对应的描述符和缓冲块。

 

KNI

通过创建一个虚拟网卡，将收到的包丢给协议栈

 /* 发送skb到协议栈 */

            /* Call netif interface */

            netif_receive_skb(skb);

 

POWER

在负载小的时候没有必要使用轮询模式，这时可以打开网卡中断 使用eventfd  epoll通知用户层

 

Ring

无锁环形队列的核心就是操作头尾索引，先将头尾索引赋给临时变量，再把尾索引往后跳n个位置，利用cas判断头如果还是在原来的位置就指向尾否则就重复这个过程，然后在操作中间跳过的n个元素就是安全的了，此时头尾索引应该指向同一个位置，如果不同应该是有别的线程也在操作，重复等待即可。(这里有个细节，索引是只加不减的，因为是环形队列索引又是unsigned 32bits，所以每次取数据前把索引模队列长度-1， uint32_t mask;           /**< Mask (size-1) of ring. */即可)

 

Windows下使用vmware虚拟机的时候出现EAL: Error reading from file descriptor，根据网上的说法打了patch还是不行，后来尝试挂载内核模块的时候不加载vfio模块就可以了

 

Redis是工作中很常用的，这里将比较普遍使用的结构研究了下做个备忘。

 

hash

实现和dnspod的dataset半斤八两，本质上是个二维数组，通过将key哈希作为一维的下表，第二维的数组存相同哈希的元素，查找使用遍历的方式，所以这里redis做了优化，当满足条件的时候(数组数量太大)会进行rehash，动态扩大桶的数量来减少最后一维遍历的次数.

函数名称	作用	复杂度
dictCreate	创建一个新字典	O(1)
dictResize	重新规划字典的大小	O(1)
dictExpand	扩展字典	O(1)
dictRehash	对字典进行N步渐进式Rehash	O(N)
_dictRehashStep	对字典进行1步尝试Rehash	O(N)
dictAdd	添加一个元素	O(1)
dictReplace	替换给定key的value值	O(1)
dictDelete	删除一个元素	O(N)
dictRelease	释放字典	O(1)
dictFind	查找一个元素	O(N)
dictFetchValue	通过key查找value	O(N)
dictGetRandomKey	随机返回字典中一个元素	O(1)

 

字典结构

typedef struct dict {

    // 类型特定函数

    dictType *type;

    // 私有数据

    void *privdata;

    // 哈希表

    dictht ht[2];

    // rehash 索引

    // 当 rehash 不在进行时，值为 -1

    int rehashidx; /* rehashing not in progress if rehashidx == -1 */

    // 目前正在运行的安全迭代器的数量

    int iterators; /* number of iterators currently running */

} dict;

这里哈希表有两个，一般都用ht[0]，当需要rehash的时候会创建一个比ht[0]大的 2 的 N 次方的ht[1]，然后渐进式的将数据dictEntry移过去(除了定时的rehash，在每次操作哈希表时都会_dictRehashStep)，完成后将ht[1]替换ht[0]

 

zset

zset本质就是list,只不过每个元素都有若干个指向后继span长的指针，这样简单的设计大大提高了效率，使得可以比拟平衡二叉树，查找、删除、插入等操作都可以在对数期望时间内完成，对比平衡树，跳跃表的实现要简单直观很多。

 

 

/* ZSETs use a specialized version of Skiplists */

/*

 * 跳跃表节点

 */

typedef struct zskiplistNode {

    // 成员对象

    robj *obj;

    // 分值

    double score;

    // 后退指针

    struct zskiplistNode *backward;

    // 层

    struct zskiplistLevel {

        // 前进指针

        struct zskiplistNode *forward;

        // 跨度

        unsigned int span;

    } level[];

} zskiplistNode;

 

/*

 * 跳跃表

 */

typedef struct zskiplist {

    // 表头节点和表尾节点

    struct zskiplistNode *header, *tail;

    // 表中节点的数量

    unsigned long length;

    // 表中层数最大的节点的层数

    int level;

} zskiplist;

 

/*

 * 有序集合

 */

typedef struct zset {

 

    // 字典，键为成员，值为分值

    // 用于支持 O(1) 复杂度的按成员取分值操作

    dict *dict;

    // 跳跃表，按分值排序成员

    // 用于支持平均复杂度为 O(log N) 的按分值定位成员操作

    // 以及范围操作

    zskiplist *zsl;

 

} zset;

 

虽然这种方式排序查找很快，但是修改的话就得多做些工作了

 

/* Delete an element with matching score/object from the skiplist.

 *

 * 从跳跃表 zsl 中删除包含给定节点 score 并且带有指定对象 obj 的节点。

 *

 * T_wrost = O(N^2), T_avg = O(N log N)

 */

int zslDelete(zskiplist *zsl, double score, robj *obj)

 

intset

typedef struct intset {  

uint32_t encoding; //所使用类型的长度，4\8\16  

uint32_t length; //元素个数  

int8_t contents[]; //保存元素的数组  

} intset;  

 

intset其实就是数组，有序、无重复地保存多个整数值，查找用的是二分查找 * T = O(log N)，添加的话在找到对应的数组中应该存在的位子后使用memmove向后移出空位填补(当然需要先realloc预分配空间)，同理删除也是用memmove向前移动

 

set

当使用整数时，使用intset，否则使用哈希表

 

 

其他的关于网络事件处理，epoll，回调，拆包都和正常使用差不多，关于错误处理EINTR(系统调用期间发生中断)和EAGAIN 继续重试而如果是EPOLLHUP或EPOLLERR则让io该读读该写写，有错处理就是了。

 

 

 

 

dns的递归解析过程还是挺繁琐的，要知道一个域名可能有cname、ns 而请求的cname、ns可能还有cname、ns，如果按照线性的处理每个请求那逻辑就变成毛线团了

dnspod的处理还是挺巧妙的，通过一个公共的数据集dataset将所有域名对应的a、cname、ns等类型的数据作为单独的条目存入，当有需要某个域名的信息时先去dataset找，找不到在加入qlist请求根，有专门的线程不间断的将qlist轮询dataset找（这里只要次数允许，没得到想要的结果就轮询所有qlist到dataset找虽然可以简化逻辑分离的彻底但是会是个性能瓶颈，后面有方案）当根返回以后只是简单的将记录(通常是一个域名的cname、ns或者a)存入dataset(而不是继续流程，因为根据这个返回是cname还是ns或者a处理不同逻辑复杂，而这样处理对于用到相同域名的请求还有优化作用)，剩下的工作交给那边不间断轮询的线程

 

Dnspod主要由3个run（若干个线程）组成

 

run_sentinel  监听53端口接收客户端请求，将请求放到队列中

run_fetcher   从队列中取出请求，根据qname取得最后一级cname，查看本地dataset 是否有记录，如果有则返回，没有则将该请求放入qlist中

 

run_quizzer    

1.不间断的遍历qlist，只要状态为PROCESS_QUERY且dataset中没有的就向对应的根发送请求。

2.通过epoll等待根返回，解析返回的数据加入 dataset

3.检查记录的ttl，在将记录加入dataset时还会将这些记录以红黑树的形式组织起来，取得ttl最早到期的，将其放入qlist中等待刷新，注意这里不是删除，如果收不到不返回则该记录一直存在

 

关于dataset的实现

dataset是使用哈希表实现的，本质上是个二维数组，将域名哈希成一个值，模上数组的数量作为下标，找到对应的数组接着遍历查找，根据需要可以扩大数组的数量提升性能。

 

我们的优化手段

之前提到dnspod的qlist会不间断轮询，属于主动查询，对性能有不小的影响，这里我们采取的做法是被动(类似回调的方式)，我们将请求的域名和类型分类，相同的放在一组，当dataset找不到向根发出请求后我们并不每次主动轮询，而是在等到应答后，触发该域名和类型的请求组，让他们根据自己的逻辑走下一步（一般是先找该域名的最后一级cname，根据这个cname查是否存在他的对应请求类型的记录，一般是a或者ns，如果没有，则找这个cname的ns）

 

以上可以看出dataset很重要，负载也不小，还经常需要并发访问，这里我们每次接收到根的回复后，除了将记录的答案加进dataset，还创建一个临时的dataset，只存该次回复的信息，在后面的流程会优先到这里去找，没有的再找dataset。

     摘要: 最近在研究DPDK，这是sigcomm 2014的论文，纪录在此备忘Ps:  文中关键词的概念：segment : 对应于tcp的PDU(协议传输单元)，这里应该指tcp层的包，如果一个包太大tcp负责将它拆分成多个segment（这个概念对理解后文有帮助）根据unix网络编程卷1 第8页注解2：packet是IP层传递给链路层并且由链路层打包好封装在帧中的数据（不包括帧头）而IP层的包...  阅读全文

一直想用cegui，但是没机会用，只是抽空看其代码

最近听朋友说0.7 debug下帧数提高100多，挺惊讶的，重新到久违了的官网上下了0.7.1

看了下渲染的实现(GL)

首先，添加了GeometryBuffer玩意，使得每个window保存了属于自己的顶点和纹理信息

然后在RenderingSurface中有GeometryBuffer队列，使得每个拥有AutoRenderingSurface属性的window有属于自己的队列(默认只有FrameWindow才有)

而在drawself中执行的则是先通过looknfeel，把需要渲染的信息丢到每个部件自己的GeometryBuffer里，然后把GeometryBuffer丢到RenderingSurface的队列中(一般为

FrameWindow的GeometryBuffer队列，每个面板就有自己的渲染队列了)

要知道以往都是只有一个队列的，要渲染啥直接往里塞。 。 。
这样一改就不必每个小部件有更改都要全部重新清空渲染了

再往后就是把每个窗口队列里的GeometryBuffer渲染到各自的RenderingSurface表面上，这里要注意的是并不是渲染到屏幕上而是表面上，cegui在这里使用了渲染到纹理，GL

用的是fbo实现的。

注意RenderingSurface只有两个来源，一是通过设置AutoRenderingSurface属性，另一个就是RenderingRoot了，RenderingRoot只有一个，在render中，通过第一个来源的使

用的是fbo的渲染，而第二个来源则直接渲染到屏幕了。

所有的这些执行完后就可以渲染到屏幕了，通过RenderingRoot执行，注意这里的RenderingRoot中的RenderTarget和之前的不一样，这里用的是OpenGLViewportTarget而不是

OpenGLFBOTextureTarget。

     摘要: 这个看代码里面batch相关的。[Direct3D] 实现批次渲染、硬件 T&L 的渲染器和 D3DPipeline 在是否从 D3DRender 提供顶点缓存区操作给流水线时做了一些权衡，最后决定暂时使用 IDirect3DDevice9::DrawPrimitiveUP 来渲染，因为它更容易书写，而且开销是一次顶点拷贝，流水线也不用操心对缓存的使用。 (DrawPrimitive的...  阅读全文