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多。

tcp是提高带宽利用率的协议，每次发送倾向mss大小，同时不能大于对端指定的大小（发送窗口），tcp只考虑了网络中路由器缓冲区耗尽情况（也是tcp的限制）所以有拥塞窗口和慢启动：为了防止网络拥塞（自律的协议）每次发送的不能大于对方指定的（发送窗口）和自己给自己限制的（拥塞窗口）。


    

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

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

shutdown和close的区别:

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

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，动态扩大桶的数量来减少最后一维遍历的次数.

字典结构

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。

最近听朋友说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。