http连接池的选择连接算法

发表于 更新于 分类于 阅读次数： 本文字数： 13k 阅读时长 ≈ 12 分钟

在上一篇实现 HTTP 长连接中，研究了整体实现的方案

初步实现并上线后，相对于原先的短链接用法，整个链路的耗时下降了50%，还是挺有成就感的

在这一篇中着重讨论其中选择连接算法，单独写这一篇是因为在揣摩golang的连接池实现中发现了不符合预期的问题

golang版本如下：

1
2
~ go version
go version go1.21.0 linux/amd64

问题一：go实现不完全符合LRU淘汰规则

在上一篇讨论配置项的时候，得出了空闲连接数量字段是刚需的结论，golang和nginx都进行了实现

回顾一下上篇博文内容，go发起请求使用的Client会使用同一个默认Transport，idleConn管理了所有域名的连接池

下面代码片段的注释来自go源码，每个请求总会使用MRU的方式选取池中连接（越久没有使用的空闲连接越不可信赖）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
type Transport struct {
    ...//忽略本文无关
    
    idleConn     map[connectMethodKey][]*persistConn // most recently used at end
    
    ...//忽略本文无关
}

func (t *Transport) queueForIdleConn(w *wantConn) (delivered bool) {
    ...//忽略本文无关
    // Look for most recently-used idle connection.
    if list, ok := t.idleConn[w.key]; ok {
    }
    ...//忽略本文无关
}

对应的，池满了以后在淘汰连接的时候，就应该使用LRU算法淘汰

golang有两个相关配置：

  • 每个连接池的上限MaxIdleConnsPerHost（限制idleConn的某个key），默认值为2

  • 总的上限MaxIdleConns（限制整个idleConn），默认值为100

但是对这两个配置的处理却不完全一致

这两个逻辑都在transport.go的func (t *Transport) tryPutIdleConn(pconn *persistConn)中

  • MaxIdleConnsPerHost的限制超出以后，直接返回errTooManyIdleHost，这会在putOrCloseIdleConn直接关闭连接而不是复用

    显然，这里没有进行LRU淘汰，反而进行了MRU的淘汰

  • MaxIdleConns则包含了完整的LRU逻辑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
//下面会用到这个函数，在存在配置项的时候，使用配置项，否则使用默认值
func (t *Transport) maxIdleConnsPerHost() int {
    if v := t.MaxIdleConnsPerHost; v != 0 {
        return v
    }
    return DefaultMaxIdleConnsPerHost //默认为2
}

func (t *Transport) tryPutIdleConn(pconn *persistConn) {
    ...//忽略本文无关
    
    //pconn是要放回的连接指针
    //key用于定位pconn属于哪个连接池
    idles := t.idleConn[key]
    if len(idles) >= t.maxIdleConnsPerHost() {
        return errTooManyIdleHost //大于当前连接池的限制，返回错误
    }
    
    ...//忽略本文无关
    
    t.idleConn[key] = append(idles, pconn) //将当前连接加入空闲连接池
    t.idleLRU.add(pconn) //同时加入全局LRU统计中
    if t.MaxIdleConns != 0 && t.idleLRU.len() > t.MaxIdleConns { //全局的LRU统计数量 > 全部连接池的上限，那么需要淘汰
        oldest := t.idleLRU.removeOldest() //找到全局最长时间没有访问过的连接
        oldest.close(errTooManyIdle) //关闭该连接
        t.removeIdleConnLocked(oldest) //从t.idleConn[oldest.key]中删除这个连接，释放内存
    }
    
    ...//忽略本文无关
}

func (t *Transport) putOrCloseIdleConn(pconn *persistConn) {
       //一旦要放回的连接返回错误，那么直接关闭
    if err := t.tryPutIdleConn(pconn); err != nil {
        pconn.close(err)
    }
}

nginx实现

空闲连接数量字段在 nginx 中为 upstream 的 keepalive 配置，默认不开启

1
2
3
Syntax:    keepalive connections;
Default:    —
Context:    upstream

例如

1
2
3
4
upstream test_backend {
    server x.x.x.x:12345;
    keepalive 32;
}

The connections parameter sets the maximum number of idle keepalive connections to upstream servers that are preserved in the cache of each worker process. When this number is exceeded, the least recently used connections are closed.

connections参数设置了每个工作进程缓存中保留到上游服务器的空闲keepalive连接的最大数量。当超过这个数量时，使用LRU淘汰连接。

It should be particularly noted that the keepalive directive does not limit the total number of connections to upstream servers that an nginx worker process can open. The connections parameter should be set to a number small enough to let upstream servers process new incoming connections as well.

特别需要注意的是，keepalive指令不限制nginx工作进程可以打开到上游服务器的总连接数。connections参数应设置为一个足够小的数值，以便让上游服务器处理新的进入连接。

好在我对nginx还算熟悉，我来看下nginx的具体实现

相关逻辑在src/http/modules/ngx_http_upstream_keepalive_module.c中

先看下数据结构：

max_cached，cache和free需重点关注

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
typedef struct {
    ngx_uint_t                         max_cached;  // 配置项：最大keepalive连接个数，keepalive 32的话，这个值就是32
    ngx_uint_t                         requests;    // 配置项：定义了每个连接最多可以发起多少次请求，超过该值，连接将被关闭（和今天的主题无关）
    ngx_msec_t                         time;        // 配置项：定义了每个连接的生命周期，超过这个时间期限，连接将不再被保留（和今天的主题无关）
    ngx_msec_t                         timeout;     // 配置项：定义了在接受响应的过程中，等待返回的最长时间。如果超过这个时间，连接会被关闭（和今天的主题无关）

    ngx_queue_t                        cache;       // 辅助数据结构：保存空闲连接队列
    ngx_queue_t                        free;        // 辅助数据结构：保存剩余可用的空闲连接队列元素
    // 初始时cache.size = 0, free.size = max_cached，后续free.size + cache.size = max_cached

    ngx_http_upstream_init_pt          original_init_upstream; //定义了原始upstream的初始化函数，和upstream的负载均衡配置有关（和今天的主题无关）
    ngx_http_upstream_init_peer_pt     original_init_peer;     //upstream中每个server都是一个peer，这里定义了peer的初始化函数，和upstream的负载均衡配置有关（和今天的主题无关）

} ngx_http_upstream_keepalive_srv_conf_t;

typedef struct {
    ... //忽略
    ngx_http_upstream_keepalive_srv_conf_t  *conf;   //上面的配置项

    ngx_http_upstream_t               *upstream;

} ngx_http_upstream_keepalive_peer_data_t;

typedef struct {
    ... //忽略
    
    ngx_queue_t                        queue;         //conf->cache和cache->free队列存储的实际元素
    ngx_connection_t                  *connection;    //连接数据

    socklen_t                          socklen;       //tcp socket数据
    ngx_sockaddr_t                     sockaddr;     //tcp socket数据
 
} ngx_http_upstream_keepalive_cache_t;

初始化逻辑，可以发现放回队列中的元素是由free预先初始化好的，初始情况free.size = max_cached

1
2
3
4
5
6
7
8
9
10
11
12
static ngx_int_t ngx_http_upstream_init_keepalive(ngx_conf_t *cf, ngx_http_upstream_srv_conf_t *us) {
    ... //省略
    //分配内存，初始化max_cached个可以复用连接的位置，并且加入free
    cached = ngx_pcalloc(cf->pool, sizeof(ngx_http_upstream_keepalive_cache_t) * kcf->max_cached);
    ngx_queue_init(&kcf->cache);
    ngx_queue_init(&kcf->free);
 
    for (i = 0; i < kcf->max_cached; i++) {
        ngx_queue_insert_head(&kcf->free, &cached[i].queue);
        cached[i].conf = kcf;
    }
}

选取连接的逻辑如下，选出后，free.size就会增加1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
static ngx_int_t ngx_http_upstream_get_keepalive_peer(ngx_peer_connection_t *pc, void *data) {
    ngx_http_upstream_keepalive_peer_data_t  *kp = data;       //连接池数据，可以通过它获取到配置项conf
    ngx_queue_t          *q;                                   //从kp->conf中的cache或者free队列中取出的元素
    ngx_http_upstream_keepalive_cache_t      *item;            //队列实际存储的元素，从q转换而来
    
    cache = &kp->conf->cache;
    
    //从cache队列的第一个元素开始遍历，找可用连接
    for (q = ngx_queue_head(cache); q != ngx_queue_sentinel(cache); q = ngx_queue_next(q)) {
        item = ngx_queue_data(q, ngx_http_upstream_keepalive_cache_t, queue);
        //ngx_queue_data宏根据ngx_http_upstream_keepalive_cache_t中queue的偏移量，反向偏移
        //得到ngx_http_upstream_keepalive_cache_t的起始位置
        c = item->connection;
        if (ngx_memn2cmp((u_char *) &item->sockaddr, (u_char *) pc->sockaddr, item->socklen, pc->socklen) == 0) {
            // 找到可用的链接，从cache队列中删除，将q放进free队列（表示当前keepalive可保存的长连接数量+1）
            ngx_queue_remove(q);
            ngx_queue_insert_head(&kp->conf->free, q);
            goto found;
        }
    }
    return NGX_OK;
 
found:
    // 找到一个可以复用的TCP连接  直接返回NGX_DONE
    pc->connection = c;
    return NGX_DONE;
}

用过的连接放回连接池逻辑，free.size为0就说明已经不能放回连接池了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35


static void ngx_http_upstream_free_keepalive_peer(ngx_peer_connection_t *pc, void *data, ngx_uint_t state)
    ngx_http_upstream_keepalive_peer_data_t  *kp = data;       //连接池数据，可以通过它获取到配置项conf
    ngx_queue_t          *q;                                   //从kp->conf中的cache或者free队列中取出的元素
    ngx_http_upstream_keepalive_cache_t      *item;            //队列实际存储的元素，从q转换而来

    c = pc->connection;                                        //获取peer中的当前连接

    ...  //忽略，state参数等，对连接的状态进行校验

    if (ngx_queue_empty(&kp->conf->free)) {
        //free队列已经为空，当前upstream的连接数量达到上限

        q = ngx_queue_last(&kp->conf->cache);                  //取出空闲连接队列的最后一个元素
        ngx_queue_remove(q);                                   //cache队列删除该元素

        item = ngx_queue_data(q, ngx_http_upstream_keepalive_cache_t, queue);
        //ngx_queue_data宏根据ngx_http_upstream_keepalive_cache_t中queue的偏移量，反向偏移
        //得到ngx_http_upstream_keepalive_cache_t的起始位置

        ngx_http_upstream_keepalive_close(item->connection);    //关闭该连接

    } else {
        q = ngx_queue_head(&kp->conf->free);                    //取出剩余空闲连接队列中，预先创建的元素
        ngx_queue_remove(q);                                    //free队列删除该元素

        item = ngx_queue_data(q, ngx_http_upstream_keepalive_cache_t, queue);
        //ngx_queue_data宏根据ngx_http_upstream_keepalive_cache_t中queue的偏移量，反向偏移
        //得到ngx_http_upstream_keepalive_cache_t的起始位置
    }

    ngx_queue_insert_head(&kp->conf->cache, q);                 //要放进连接池的元素，插入cache队列
    item->connection = c;                                       //队列元素的connection改成peer中的当前连接
}

小结

nginx对于每个连接池，取连接总是取队列的第一个元素，放队列也是放到队列头部，符合MRU

当连接池keepalive最大空闲连接满了以后，会使用LRU淘汰掉队列的尾部元素

这个算法是符合我认知的，而golang不符合，我倾向于golang实现的时候存在疏漏

问题二：go的删除连接算法时间复杂度过高

根据上一节中给出的nginx源码分析，nginx的队列是链表实现的，所以取元素，删除，放回（满了淘汰）的三个操作都是\(O(1)\)时间复杂度的

再看下golang的实现：

1
2
3
type Transport struct {
    idleConn     map[connectMethodKey][]*persistConn // most recently used at end
}

每个连接池的数据结构实际上是个数组

取元素：\(O(1)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
func (t *Transport) queueForIdleConn(w *wantConn) (delivered bool) {
    ...//忽略无关代码
    
    // Look for most recently-used idle connection.
    if list, ok := t.idleConn[w.key]; ok {
        stop := false
        
        for len(list) > 0 && !stop {
            ...//忽略无关代码
            t.idleLRU.remove(pconn)             //从LRU中删除
            list = list[:len(list)-1]           //取尾部元素
        }
}

删除：\(O(n)\)​

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
func (t *Transport) removeIdleConnLocked(pconn *persistConn) bool {
    ...//忽略无关代码
    
    switch len(pconns) {
    case 0:
        // Nothing
    case 1:                                              //当只有一个元素时，删除t.idleConn中整个连接池
        if pconns[0] == pconn {
            delete(t.idleConn, key)
            removed = true
        }
    default:
        for i, v := range pconns {
            if v != pconn {                              //关键来了，通过遍历确定元素位置，妥妥的O(n)
                continue
            }
            // Slide down, keeping most recently-used
            // conns at the end.
            copy(pconns[i:], pconns[i+1:])               //将该元素后面的所有元素向前移动一位，妥妥的O(n)
            t.idleConn[key] = pconns[:len(pconns)-1]
            removed = true
            break
        }
    }
}

放回（满了淘汰）：不满\(O(1)\)，满了调用删除接口\(O(n)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func (t *Transport) tryPutIdleConn(pconn *persistConn) {
    ...//忽略无关代码
    
    //pconn是要放回的连接指针
    //key用于定位pconn属于哪个连接池
    t.idleConn[key] = append(idles, pconn)
    t.idleLRU.add(pconn)
    if t.MaxIdleConns != 0 && t.idleLRU.len() > t.MaxIdleConns {
        oldest := t.idleLRU.removeOldest()
        oldest.close(errTooManyIdle)
        t.removeIdleConnLocked(oldest)
    }
    
    ...//忽略无关代码
}

这个删除连接池的算法，让我看的很不解

因为队列头部的元素是最久没有使用的，因此全局连接池达到上限，淘汰时一定先删除某个子连接池的第一个元素，这意味着每次删除都需要把所有元素移动一遍

但是考虑到数据存在cpu的局部性原理，因此对性能下结论为时过早，我写一段cpp代码验证一下算法

算法实现

nginx的算法性能显然是最好的，但是c代码封装的不太好，可维护性比较差，考虑封装一个RemovableLRU的数据结构

提供取元素，放回，删除的三个操作popBack，pushBack,remove

go的算法实现很简单，为了完整的模仿go行为，淘汰的popHead复用remove操作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
template <typename K, bool isPopHeadUseRemove = true>
class SimpleRemovableLRU {
    vector<K> vs_;
    uint limit_ = 0;
    K popHead() {
        K k = vs_.front();
        if (isPopHeadUseRemove) {
            remove(k);
            return k;
        }
        vs_.erase(vs_.begin());
        return k;
    }
public:
    void setLimit(uint limit) {
        limit_ = limit;
    }
    template <typename T>
    pair<bool, K> pushBack(T && k) {
        vs_.emplace_back(move(k));
        if (limit_ != 0 && vs_.size() > limit_) {
            return {true, popHead()};
        }
        return {false, {}};
    }
    void remove(const K &k) {
        auto iter = find(vs_.begin(), vs_.end(), k);
        vs_.erase(iter);
    }
    K popBack() {
        auto v = move(vs_.back());
        vs_.pop_back();
        return v;
    }
};

而我的实现要做到三个操作都是\(O(1)\)​复杂度

pushBack和popBack显然必须要用链表实现，而remove需要使用哈希表来实现

因此链表的元素和哈希表的元素必须相互引用各自的元素指针

graph LR;
    A["pushBack() / popBack()"] -- Use --> B[list]
    C["remove()"] -- Use --> D[unordered_map]
    E[Data element in list] -->|Reference| F[Data element in unordered_map]
    F -->|Reference| E

那么这个算法就非常简单了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
template <typename K, bool isPopHeadUseRemove = true>
class RemovableLRU {
    struct Data {
        template<typename T>
        Data(T && k) : k(std::forward<T>(k)) {}
        K k;
        typename unordered_map<K, typename list<Data>::iterator>::iterator mIter;
    };
    list<Data> datas_;
    unordered_map<K, typename list<Data>::iterator> m_;
    uint limit_ = 0;
    K popHead() {
        Data data = move(datas_.front());
        if (isPopHeadUseRemove) {
            remove(data.k);
            return data.k;
        }
        datas_.pop_front();
        m_.erase(data.mIter);
        return data.k;
    }
public:
    void setLimit(uint limit) {
        limit_ = limit;
    }
    template <typename T>
    pair<bool, K> pushBack(T && k) {
        datas_.emplace_back(std::forward<T>(k));
        typename list<Data>::iterator lIter = datas_.end(); 
        lIter--;
        auto ret = m_.insert({k, lIter});
        if (ret.second) {
            auto mIter = ret.first;
            mIter->second->mIter = mIter;
        }
        if (limit_ != 0 && datas_.size() > limit_) {
            return {true, popHead()};
        }
        return {false, {}};
    }
    template <typename T>
    void remove(T && k) {
        auto iter = m_.find(k);
        if (iter != m_.end()) {
            auto &lIter = iter->second;
            datas_.erase(lIter);
            m_.erase(iter);
        }
    }
    K popBack() {
        Data data = move(datas_.back());
        datas_.pop_back();
        m_.erase(data.mIter);
        return data.k;
    }
};

算法性能测试

完整代码见RemovableLRU.cpp

使用2000个元素进行测试，通过生成随机元素进行操作：

  • pushWithoutLimit：pushBack没到上限
  • pushWithLimit：pushBack到上限
  • remove
  • popBack
1
2
3
4
5
6
7
8
9
10
~/algorithm_test# g++ -std=c++17 -g -Wall -O2 RemovableLRU.cpp
~/algorithm_test# ./a.out 
RemovableLRU<int, true> pushWithoutLimit:                   Cost 0.332 ms
RemovableLRU<int, true> pushWithLimit:                      Cost 0.326 ms
SimpleRemovableLRU<int, true> pushWithoutLimit:             Cost 0.044 ms
SimpleRemovableLRU<int, true> pushWithLimit:                Cost 0.346 ms
RemovableLRU<int, true> remove:                             Cost 0.172 ms
SimpleRemovableLRU<int, true> remove:                       Cost 0.425 ms
RemovableLRU<int, true> popBack:                            Cost 0.118 ms
SimpleRemovableLRU<int, true> popBack:                      Cost 0.001 ms

通过改变代码中performanceElementSize = 2000;可以对不同数量的元素进行测试，制表如下

100元素 2000元素 10000元素（经典c10k） 65535元素（最差case）
RemovableLRU pushBackWithoutLimit $ O(1)$ 0.019 ms 0.332 ms 1.825 ms 14.232 ms
RemovableLRU pushBackWithLimit $ O(1)$ -（同上） -（同上） -（同上） -（同上）
RemovableLRU remove $ O(1)$ 0.012 ms 0.172 ms 1.158 ms 8.703 ms
RemovableLRU popBack $ O(1)$ 0.006 ms 0.118 ms 0.662 ms 4.915 ms
SimpleRemovableLRU pushBackWithoutLimit $ O(1)$ 0.002 ms 0.044 ms 0.277 ms 2.283 ms
SimpleRemovableLRU pushBackWithLimit $ O(n)$ 0.002 ms 0.346 ms 18.08 ms 873.601 ms
SimpleRemovableLRU remove $ O(n)$ 0.005 ms 0.425 ms 10.45 ms 506.061 ms
SimpleRemovableLRU popBack $ O(1)$ 0ms 0.001 ms 0.006 ms 0.04 ms

和我猜测的差不多，在小数量级中局部性原理的性能非常优秀

但是随着数量级的增长，2000是生产中有可能遇到的一种情况

虽然pushBackWithLimit的时间差值更明显，由于调用了remove，因此直接比较remove即可：

go的算法比起我的实现性能下降了60%左右（0.172ms -> 0.425ms）

在经典c10k的大并发场合下，性能下降了90%（1.158ms -> 10.45ms），该量级下就已经超过内网的rtt耗时了

在65536端口都被占满的最差case下，性能下降了99%（8.703ms -> 506.061ms）

总结

问题一的不完全符合LRU也许影响不大

问题二的删除操作时间复杂度过高就很致命了，删除在这个场景下有三种使用情况：

  • 淘汰（对应表中pushBackWithLimit）：因为队列头部的元素是最久没有使用的，因此全局连接池达到上限，淘汰时一定先删除某个子连接池的第一个元素，这意味着每次删除都需要把所有元素移动一遍
  • 请求超时导致的需要删除连接（对应表中remove）：在这种场合下，时间复杂度更高的算法会更耗费cpu，使超时更严重，恶性循环导致雪崩
  • 对端关闭的正常删除：这种情况相对前两种反而是小问题了

go出来这么多年也相当稳定了，也许存在我分析错误的可能性，和朋友们讨论一下看看

参考资料

从HTTP.TRANSPORT看连接池的设计

nginx upstream中长连接池的维护

net/http: Why not close the conn directly instead of put the conn into a new list?

相关文章
  • 2024-06-23
    实现HTTP长连接

    业务有个需求是为taf的HTTP客户端实现长连接

    我5年前在前公司就写过cpp的HTTP连接池版本sheep/HTTP_client实现广告项目的RTB

    当初的那个实现很粗糙，凑活用就行，但是现在的这个实现是给全公司人用的，首先摆在面前的问题就是实现HTTP长连接的哪个版本？

    个人倾向于1.1版本，对服务端要求低比较通用，最后确实选择了1.1版本，选定了版本随之而来又有这些问题：

    • 是否需要实现Pipelining

    • 是否需要解析协议上的任何控制字段

    • 需要哪些配置字段？默认值是什么？

      例如连接池的默认的空闲连接数量，这种默认设置最怕大佬问到底，为什么设为5？为什么设为10？

      有现有方案就可以直接转移仇恨：为什么golang设为x？为什么nginx设为x？

    • 以域名为粒度实现每个域名一个连接池，还是以ip为粒度

      当初是实现了一个基于ip的Client用来实现rpc框架（每个ip单连接多路复用），基于Client又封装了ClientPool给redis, HTTP, mysql用（每个ip连接池）

      现在看着不太对劲，HTTP的长连接应该以域名为粒度吧？

    • 稀疏链接问题梳理

      这个放到taf框架的博文里面去了，因为初版不打算为HTTP客户端实现太多功能