从 0 实现一个延迟代理服务

需求背景：

后台业务逻辑类服务，其实现通常都会依赖其他外部服务，比如存储，或者其他的逻辑server。

有一类比较典型的问题：假设主调方A是同步处理模型，有一个关键路径是访问B服务。当被调服务B延迟很高时，主调方A的进程会挂起等待，导致后来的A请求也无法及时处理，从而影响整个A服务的处理能力。甚至出现A服务不可用。当然，比较理想的是B出现过载或者故障时，A的服务能力能够降到和B同等的服务能力，而非不可用。

因此，部门会定期进行容灾演习，也期望能够验证到各个服务的"最差服务能力"。即验证被调出现较高延迟或者过载的时候，主调的服务能力是否符合预期。要想做这种演习，其核心技术点是模拟"被调服务出现延迟"。以前类似场景是直接使用tc系列工具，但是由于操作麻烦，以及需要内核支持，实际使用范围非常有限。

目标：

实现一个通用的毫秒级的延迟代理服务，该代理服务用于模拟各种有延迟的被调服务。

1、支持各种应用层协议的接入，无需修改后台代码。

2、高性能。因为该服务就是用于压测其他服务的，不能自己先垮掉

为什么不使用spp？

spp是腾讯SNG内部广泛使用的后台服务器框架，封装了网络数据收发、监控等。

使用spp开发一个服务器程序，不需要使用者关注网络相关的编程，只需按照其接口规范开发插件(linux动态库,需实现spp_handle_input/spp_handle_process等接口)，然后挂到spp框架上即可运行。

spp框架通过回调插件内的spp_handle_input接口来检查数据包是否接收完整；当数据包接收完整后，框架会回调spp_handle_process对数据包进行处理。

spp是基于数据包的处理模型，proxy处理请求时第一步就是断包，即调用spp_handle_input来检查当前收包是否完整。

断包的规则是与应用层协议相关的，比如SSO协议的断包规则和单行文本协议的断包规则显然不一样。但是本程序的目的，是实现一个通用的延迟代理服务，即支持不同的应用层协议。如果使用spp基于请求包的服务模型，则每次接入新的应用层协议时都需要修改代码。不符合需求。

可能有同学会想到一个变通的方法:让spp_handle_input直接返回当前长度。事实上，当请求包转给真正的被调后，还是无法解决收包时机的问题，以及同一连接上的多个请求被转发后，收包时序的问题。

这里采用的解决方案，是实现一个基于连接的代理服务，而非基于请求包的。

代理服务使用端口来区分不同的转发规则。对于每一个接受的tcp连接，代理服务创建一个指向目标服务的连接，将前者透传到后者。回包时也是一样，按照连接对应关系反向透传即可。

这样代理服务可以做到并不关注tcp上的数据协议，完全透传即可。

不使用spp其实还有一个原因，spp的proxy/woker的模型，其实并不是适合特别高性能的服务。在worker足够轻量的时候，单线程的proxy可能成为系统的瓶颈，无法发挥出多CPU的优势。

高性能

提到高性能，作为有情怀的程序员，通常会想到

• 尽量无锁
• 尽量无拷贝
• 尽量无多余的系统调用
• 内存分配要足够快

。。。

本服务在实现过程中会尽力以这些作为目标，比如使用了一些如下的小技巧：

使用SO_REUSEPORT选项(linux3.9以上支持)来将负载均衡到各CPU，也避免使用消息队列(带来拷贝和锁开销)

使用指针操作，内存管理会麻烦一些，但避免拷贝。

使用accept4等函数，一步设置异步socket; 创建socket的函数也可以同时设置异步，减少系统调用。

使用close关闭句柄，不需要从epoll中删除句柄了(close时会自动从epoll中清理掉)。避免多余的系统调用。

获取系统时间足够快，64位机器上已经不是问题。

在运行时strace，没有一个多余的调用

连接管理

对于每个tcp连接，程序会维护一些属性，比如活跃时间等，是一个较大的结构体。因此，需要维护一个映射关系，能够根据句柄查找连接属性。可以使用map或者hashmap来实现。

但是最简单的还是，直接使用数组。这里的fddtable是在启动时分配的数组。

struct FDDATA 
{   
    int             fd; 
    uint16_t        flag; 
    uint16_t        state; 
    int             seq; 
    int             pair_fd;    

    int             type;
    uint32_t        local_ip;     //网络字节序。该字段可能用作其他意义
    uint32_t        remote_ip;    //网络字节序
    uint16_t        local_port;   //网络字节序。该字段可能用作其他意义
    uint16_t        remote_port;  //网络字节序

    uint32_t        events; 
    uint32_t        delay;
    TIMEOUT_KEY     tkey;
    union {
    struct {
        TTcpBuffer*     first;  //for tcp
        TTcpBuffer*     last;   //for tcp
    };
    TUdpBuffer*     ub;     //for udp
};

};static FDDATA* fddtable;
 #define fddptr(fd) (fddtable+(fd))

Linux上的句柄是整数值，所以这里可以使用这个技巧，直接以fd的值作为数组的索引

优点：简单，快，无生命周期问题

缺点：存在一定空间浪费

这里提到快，其实是有疑议的。

虽然使用数组来管理连接的数据结构是O(1)的，足够快。但事实上内核管理句柄是使用红黑树的，其时间复杂度为O(logN)。综合来说，时间复杂度依然是O(logN)。但是依然足够快了。

连接超时机制

作为一个7×24运行的服务，需要考虑其健壮性。考虑如下几个场景

1.某客户端连接该服务后，客户端机器掉电，或者网线断开，或者中间路由器故障。此时服务器并不知晓，会继续保持连接。

2.客户端编程使用了长连接，然后一直没有断开，也没有继续请求。此时服务器也会保持连接。

如果没有清理机制，

场景1会导致服务端的句柄数随时间增长，最终耗尽资源后宕机，不可能7×24小时持续运行。

场景2类似，如果这样的客户端太多，会占用服务端的资源，却没有真正用于提供服务

所以每一个成熟的服务器都会自带清理基因：对于长时间不活跃的连接，服务器会主动断开，以节约服务器资源。

这个问题其实是比较有趣的，可以抽象为如下的问题模型：

有N个tcp连接，

1.如果一个连接连续n秒没有收到数据，则该连接已到期。

2.如果某连接有数据到来，则从最后一次收数据开始，重新计时n秒

3.连接有可能在中途被关闭

4.随时可能有新的连接加入

简单来说，就是在一堆到期时间变化的句柄中找出已到期的句柄。

显然最直接的办法是遍历，时间复杂度O(N)。

然而，一个server可管理的句柄数可达数十万，甚至百万级，这种方法显然效率太低

方案1：O(1)级的超时机制（假设n是常量）

维护一个链表，按照到期时间对数据排序，最先到期的项都在链表头部。

如果要寻找所有已到期的句柄，只需从头部开始遍历，注意只要遇到一个未到期的句柄，就可以退出遍历了。因为由于有序性，后面的节点更不可能到期。

由于"在当前时刻刚好到期"的句柄数，相对于所有句柄数而言是一个非常小的值，所以节约了大量的遍历时间。

不过问题来了，当一个句柄收到数据时，到期时间变化了，该如何处理？

假设句柄的最后收包时间为t， 则到期时间应为t+n，由于n是常量，所以t+n的顺序其实就是t的顺序。

所以只需删除掉链表中原有节点，然后添加到链表尾端即可，时间复杂度O(1)

细心的同学会发现，其实还是有一个问题，如何根据fd找到链表中原有的项？

通常的解决方法是使用侵入式的链表(侵入式链表可以参考linux内核中链表的实现方式),可以避免这种查找以及节点拷贝等问题。很多LRU算法也使用这种实现方式。spp的proxy也使用了这种实现方式。

方案2：O(logN)级别的超时机制

从方案1可以看到，虽然实现了O(1)的查找，但是该方案有一个限制：即n必须是常量。

如果n不是常量，则"最后收包的连接一定在最后超时"这一结论不成立了，则意味着不能简单的将连接放到链表尾部。即方案1无法正常处理这种情况。

n为变量时，比较典型的实现方式是使用红黑树。而c++中使用红黑树，最简单的办法就是直接使用std::multimap

由于本服务器实现上允许使用方配置各种不同的超时时间，所以使用了红黑树的方案。

以句柄的到期时间（微秒级时间戳）作为key，清理函数(及参数)作为value

std::multimap<int64_t,STRUCT_TIMEOUT> mmt;
static inline void remove_timeout_handler(TIMEOUT_KEY key) { mmt.erase(key); }
static inline 
TIMEOUT_KEY register_timeout_handler(int (*proc)(void*), void* param, int ms, int flag){
    STRUCT_TIMEOUT value;
    value.proc = proc;
    value.param = param;
    value.flag = flag; 
    return mmt.insert(std::make_pair(current+ms*1000,value));
}

红黑树的第一个元素是整棵树中key最小的，如果第一个元素都没有超时，则可以断定整棵树肯定不存在已超时的元素了。所以只需要循环检查第一个元素是否超时，如果已超时，则回调对应的清理函数(由红黑树的元素的value指定的），然后删除第一个元素；否则退出循环。

        int next_timeout = -1; 
        while(!mmt.empty()) { 
            if(mmt.begin()->first-current<1000) {
                int flag = mmt.begin()->second.flag;
                mmt.begin()->second.proc(mmt.begin()->second.param); 
                if(flag) mmt.erase(mmt.begin());
            } else {
                int64_t t = (mmt.begin()->first-current)/1000; 
                if(next_timeout<0||t<next_timeout) next_timeout = t; 
                   break;
            }
        }

使用红黑树来管理超时也是比较一个常用的实现方式。在linux内核的句柄管理，以及nginx中都有使用。

延迟机制与定时器

1、数据结构

如果只是为了管理连接超时，只需把int型的句柄值作为std::multimap的value也可以实现，然后在适当的时机去检查std::multimap中的句柄的超时情况即可。

但事实上，在一个异步处理的服务器程序中，有很多类似的场景，比如本服务器中涉及的tcp句柄到期清理，udp句柄到期清理，请求包延迟，以及connect超时等，其处理逻辑均不同。 但是其本质是相同的，都是在指定时间后执行一个逻辑。这种"指定时间后执行一个逻辑"可以抽象为统一的定时器，以便代码中所有地方都可以很容易的复用到这种定时机制。

实现定时器时，实际上是将value设计为STRUCT_TIMEOUT数据结构，这只是一个简单的结构体，包含了回调函数，回调参数，标识3个字段。并提供注册定时器事件、移除定时器事件的接口。

这样，tcp句柄到期清理，udp句柄到期清理，请求包延迟，connect超时这几类场景，其触发及回调的机制是相同的，只是value的值不同

"将收到的数据延迟后再转发"也只是其中一个具体场景，程序收到数据后注册一个定时器事件，被唤醒后执行回调函数(转发数据)即可。

将64位函数指针放到value中会浪费一定空间。如果红黑树有100w个元素，则需要约8M的空间用于存储函数指针。

若严格考虑内存使用效率，其实有一个简单的优化方案：用一个数组来存储回调函数列表，然后将数组的索引放到value中(代替函数指针)。

通常来说，回调函数的可选值是很少的，比如我们可以使用1个字节或者2个字节的整数索引即可标识一个回调函数。

此外flag字段其实目前只需要1位即可标识。

不过对于本服务来说，这个value的内存浪费并不是大问题，所以暂未针对value的大小做优化

2、定时器唤醒

使用红黑树实现定时器，很容易找到当前已经到期的节点。 但是还有个问题未解决：程序应该在什么时机做超时检查？即定时器唤醒时机的问题。

服务器总框架是运行在一个epoll事件循环中，当有网络事件发生(比如句柄可读可写)时epoll就会返回。如果没有事件发生，则epoll处于阻塞状态。 那程序如何知道有定时器事件到期？

很容易想到，epoll本身是可以指定毫秒级的超时时间的。在epoll最后一个参数指定的超时时间到期时，即使没有网络事件发生，epoll也会返回。 所以我们若指定epoll的超时时间，比如100ms，则可以肯定每100ms内epoll至少会返回1次，我们就有可靠的时机去检查红黑树上的超时情况。

这样做，虽然是可行的，但有个问题：epoll超时时间设置为多少是合适的？

问题1 如果该值很小，那么在没有网络事件发生的时候，epoll也会频繁返回。而且大部分情况下的检查，都会发现并没有超时事件到期。即浪费cpu做无用功。

问题2 如果该值很大，则会导致定时器的精度很低。比如若设置epoll超时时间为500ms，则对于一个10ms后即将到期的事件来说，最多可能需要等待500ms之后才被发现。

理想的情况当然是按需返回： 即epoll最好能在下次(红黑树内的)超时到期的时候返回，然后程序会检查红黑树，正好发现此事件到期。这种策略下，每一次epoll唤醒都是有效的(对比问题1)，而且到期时间是准确的(对比问题2)

事实上，很容易就做到这一点，因为下一次的到期时间就是红黑树的第一个元素的key值！

所以epoll的最后一个参数取红黑树的首节点key值与当前时间的差即可。

    while(1) {
        int next_timeout = -1; 
        while(!mmt.empty()) { 
                if(mmt.begin()->first-current<1000) {
                int flag = mmt.begin()->second.flag;
                mmt.begin()->second.proc(mmt.begin()->second.param);   
                if(flag) mmt.erase(mmt.begin());
            } else {
                int64_t t = (mmt.begin()->first-current)/1000;  
                if(next_timeout<0||t<next_timeout) next_timeout = t; 
                break;
            }
        }

        n = epoll_wait(epfd, e, 1024, next_timeout);
        。。。
    }

内存分配策略

这里面临的内存分配，其实也是一个有意思的问题。

由于该server的实现目标是可以透传任意的数据，对接入的服务没有要求，这意味着我们事先并不知道连接上数据量有多少，可能是几十个字节，也可能是几兆的文件。

那么server接收数据时应该使用多大的缓冲区？

如果缓冲区太小，在数据量非常大时，则可能需要循环很多次调用系统调用(read)，影响性能。

如果缓冲区太大，在数据量非常小时，则会浪费内存，对于几十万连接的服务来说，这个内存浪费会比较可观。

我使用了一个折中的办法，指数增长的缓冲区大小，以期望在 系统调用的次数 和 浪费的内存 间取一个平衡。

目前默认配置的缓冲区大小为512Byte，系统首先使用这么大的缓冲区去recv

如果缓冲区收满，则继续收包，但再次分配的缓冲区大小翻倍，使用1024Byte

如果缓冲区又收满，则继续收包，但再次分配的缓冲区大小再翻倍，2048Byte

。。。

    while(1) {
        ret=read(fd,tb->buffer+tb->bytes,tb->blk_size-sizeof(TTcpBuffer)-tb->bytes); 
        if(ret<0) {            
           if(errno==EAGAIN) break;  
           if(errno==EINTR) continue;
            __tb_free(tb); clean_tcp(fdd,strerror(errno)); return -2;
        } else if(ret==0) {
            __tb_free(tb); clean_tcp(fdd,strerror(errno)); return -3;
        } else {
            tb->bytes += ret;
        }

        DL_NORMAL("read. fd=%d, src=%s:%d, ret=%d", fd, NTOA_IP(tmpip0,fdd->remote_ip), NTOH_PORT(fdd->remote_port), ret);        
           if(tb->bytes==tb->blk_size-(int)sizeof(TTcpBuffer)) {            
           if(tb->bytes>=TConfig::MAX_BUFFER_SIZE) {
                 __tb_free(tb); clean_tcp(fdd,"Memory limit"); return -4; 
            }
            size_t size = tb->blk_size * 2; 
            TTcpBuffer* tb2 = (TTcpBuffer*)__tb_realloc(tb, size); 
            if(!tb2) { __tb_free(tb); clean_tcp(fdd, "Alloc memory fail"); return -5; }
            tb = tb2;
        }
    }
    。。。
  }

这种策略下，分配的缓冲区理论上最多浪费一倍(最后一次分配后只使用了很少比如才1个字节)，系统调用次数为log(total/512)也不会特别夸张。

这是一个可以接受的平衡点。

此外，对于连接数据结构的自身由于使用了预分配，并且是O(1)的效率，不涉及内存分配问题了。

对于其他的通用的内存分配，比如STL内的内存分配，目前暂未做特别处理。

由于目前都运行在64位的tlinux2.2上，其glibc的性能已经很高，所以暂未使用tcmalloc类的第三方库。