netstat -s统计输出的所有字段详细解释

今天工作上碰到一个问题需要知道udp的丢包数据。实际上我不相信能简单地得到udp的丢包精确数据。理由是,网卡负载太高时有些包连网卡都没收到,根本不可能来得及汇报给内核。另外,如果是路由器把udp丢了,那udp的目的端机器当然更不可能感知到有丢包了。

这时,同事说netstat -us (–statistic)可以看到udp的丢包。这里的u选项指的是只展示udp相关的统计,s选项自然表示的是统计了。如果不用u选项,则出显示所有统计数据。下面是我的机器上的输出。

Ip:
    203440255187 total packets received
    0 forwarded
    0 incoming packets discarded
    201612429535 incoming packets delivered
    1064529177 requests sent out
    15 fragments dropped after timeout
    3058122492 reassemblies required
    1230296840 packets reassembled ok
    15 packet reassembles failed
Icmp:
    14869220 ICMP messages received
    3965512 input ICMP message failed.
    ICMP input histogram:
        destination unreachable: 6054246
        timeout in transit: 687
        echo requests: 8570532
        echo replies: 243755
    12913011 ICMP messages sent
    0 ICMP messages failed
    ICMP output histogram:
        destination unreachable: 4097869
        time exceeded: 5
        echo request: 244605
        echo replies: 8570532
IcmpMsg:
        InType0: 243755
        InType3: 6054246
        InType8: 8570532
        InType11: 687
        OutType0: 8570532
        OutType3: 4097869
        OutType8: 244605
        OutType11: 5
Tcp:
    111681768 active connections openings
    4186820 passive connection openings
    24951865 failed connection attempts
    55064041 connection resets received
    275 connections established
    1033901799 segments received
    1776166765 segments send out
    12156205 segments retransmited
    6705 bad segments received.
    106348033 resets sent
Udp:
    198894689917 packets received
    472986510 packets to unknown port received.
    1146976531 packet receive errors
    116750744 packets sent
    110301286 receive buffer errors
    0 send buffer errors
UdpLite:
TcpExt:
    423 invalid SYN cookies received
    693 packets pruned from receive queue because of socket buffer overrun
    19 packets pruned from receive queue
    11309370 TCP sockets finished time wait in fast timer
    106 packets rejects in established connections because of timestamp
    10210477 delayed acks sent
    20811 delayed acks further delayed because of locked socket
    Quick ack mode was activated 8856 times
    17118697 packets directly queued to recvmsg prequeue.
    301717551 bytes directly in process context from backlog
    152118951904 bytes directly received in process context from prequeue
    104771733 packet headers predicted
    15179703 packets header predicted and directly queued to user
    218747377 acknowledgments not containing data payload received
    102637644 predicted acknowledgments
    7293 times recovered from packet loss by selective acknowledgements
    Detected reordering 40 times using FACK
    Detected reordering 27 times using SACK
    Detected reordering 1088 times using time stamp
    476 congestion windows fully recovered without slow start
    5287 congestion windows partially recovered using Hoe heuristic
    236 congestion windows recovered without slow start by DSACK
    151673 congestion windows recovered without slow start after partial ack
    1 timeouts after reno fast retransmit
    4 timeouts after SACK recovery
    10540 timeouts in loss state
    7232 fast retransmits
    649 forward retransmits
    1871 retransmits in slow start
    11612658 other TCP timeouts
    TCPLossProbes: 93185
    TCPLossProbeRecovery: 14667
    2431 packets collapsed in receive queue due to low socket buffer
    8814 DSACKs sent for old packets
    3350 DSACKs received
    1 DSACKs for out of order packets received
    90851 connections reset due to unexpected data
    214 connections reset due to early user close
    352 connections aborted due to timeout
    TCPDSACKIgnoredNoUndo: 1571
    TCPSpuriousRTOs: 7
    TCPSackShifted: 94
    TCPSackMerged: 131
    TCPSackShiftFallback: 21183
    TCPTimeWaitOverflow: 1876775
    TCPRcvCoalesce: 15711184
    TCPOFOQueue: 3194
    TCPChallengeACK: 2337394
    TCPSYNChallenge: 13608
    TCPSpuriousRtxHostQueues: 1982796
IpExt:
    InBcastPkts: 46443933
    InOctets: 44312451521655
    OutOctets: 1915626725817
    InBcastOctets: 6827280595

喂,要是转载文章。麻烦贴一下出处 ykyi.net 采集爬虫把链接也抓走

这里面确实有两个疑似表示udp的丢包数的数据:

Udp:
    1146976531 packet receive errors
    110301286 receive buffer errors

于是,当然首先是看linux man page。结果netstat的man手册里居然没有这些字段的介绍。
跟住,问google。没想到,答案就是netstat -s的输出并没有准确的文档(pooly documented)。
这里有个贴子问了相同的问题 https://www.reddit.com/r/linux/comments/706wsa/detailed_explanation_of_all_netstat_statistics/
简单地说,回贴人告诉他,“别用netstat,而是用nstat和ip tools”“这是个不可能的任务,除非看完成吨源代码”。
blablabla …
事实上,看了google到的一些贴子后,还是大概知道了真相。

    1146976531 packet receive errors

这一句对应关于UDP的一个RFC标准的文档 中定义的字段 udpInErrors。

“The number of received UDP datagrams that could not be
delivered for reasons other than the lack of an application
at the destination port.”
udpInErrors表示操作系统收到的不能被投递的UDP包,不能投递的原因除了没有应用程序开启了对应的端口。

而这一行

    110301286 receive buffer errors

这一行对应 nstat -a -z (下文会再提到nstat)输出中的 UdpRcvbufErrors 字段。我没有找到RFC关于UdpRcvbufErrors字段的定义。
IBM官网上有个网页简单介绍了UdpRcvbufErrors: Number of UDP buffer receive errors. (UDP的缓冲收到错误的次数)。
再结合这篇文章: 为何udp会被丢弃Why do UDP packets get dropped。我非常有信心的认为 UdpRcvbufErrors 表示的是操作系统的内核tcp栈给udp socket分配的缓冲出错(缓冲满)的次数。至于网卡自己的缓冲,和操作系统的缓冲是两回事。网卡的缓冲出错不会被计入这个计数。udp经过的路由的丢包数当然只能够查看对应的路由器的统计数据了。

另外,因为netstat已经被废弃,不建议使用。而是用 nstat 和 ss 这两个新命令代替。
nstat的输出相当于netstat -s的输出。但nstat会输出比netstat -s更多的字段信息,且绝大多数字段名对应到RFC标准中用的字段名。

可任意转载本文,但需要注明出处!!!谢谢

Why do UDP packets get dropped: https://jvns.ca/blog/2016/08/24/find-out-where-youre-dropping-packets/
1: https://tools.ietf.org/html/rfc4113
2: https://www.ibm.com/support/knowledgecenter/STXNRM_3.13.4/coss.doc/deviceapi_response_2.html

Linux系统级/进程级最多打开文件数,FD文件描述符数

如何增加Linux系统最大文件打开数目呢?

查看系统最大可打开文件数

以下命令查看操作系统级最多可打开文件数,fd数目

$ cat /proc/sys/fs/file-max

我用ubuntu 16输出:

573738

怎么调整系统最大可打开文件数

# sysctl -w fs.file-max=1000000

需要用root用户执行以上命令,设最大为一百万。
但在命令行上修改了这个配置,会在下一次操作系统重启后重置为以前的值。要一劳永逸的改变系统最大打开文件数,需要修改 /etc/sysctl.conf 文件。

fs.file-max = 1000000

在/etc/sysctl.conf文件中增加上述一行。

ulimit命令查看/调整进程级最大文件打开数

$ ulimit -Sn
1024

这个命令查看一个ulimit的软极限值(soft limit),本用户起的进程的最大文件打开数的限制。我的ubuntu 16显示进程最多开1024个fd。如果要提高每个进程可同时打开的文件数,需要更改这个值。

$ ulimit -Sn 2048
bash: ulimit: open files: cannot modify limit: Invalid argument

但我想把每个进程可同时打开的文件数增加到以前的两倍时,报错了。这是因为,软极限值(soft limit)不能够越过(Hard Limit)。我看了一下Hard limit,也是1024

$ ulimit -Hn
1024

那没办法罗,需要以root用户登录更改Hard Limit。

怎么修改普通用户的硬极限hard Limit

用root账户登录后,编辑 /etc/security/limits.conf文件,假如普通用户名是kamuszhou。

kamuszhou hard nofile 10000
kamuszhou soft nofile 5000

以上配置修改kamuszhou普通用户的最多打开文件数的hard limit为10000,soft limit为5000。
对于ubuntu 16,如果使用图形桌面,还需要修改 /etc/systemd/system.conf 和 /etc/systemd/user.conf。
加上这么一行:

DefaultLimitNOFILE=10000

如何定制一个python的logging Handler

gevent貌似和logging冲害,如何定制一个日志File Handler

上个月用python的gevent协程库写了一个tcp服务。日志库使用python标准日志库logging。一个月后,发现一个偶发的bug。这个bug发生时,用python的标准日志库自带的FileHandler写的日志会发往socket占用的文件描述符fd。结果就是,客户端收到了本要打印到磁盘上的日志。花了不少时间定位排查这个bug,仍然没有结果。我开始怀疑是gevent协程库和python的标准日志库logging有冲突。协程库会错误的把logging打开的文件描述符fd关闭并分配给新创建的socket,于是日志就打印到socket占用的fd了。

后来,写了一个检测脚本用来监控这个情况发生的概率。该脚本每分钟会检查进程占用的所有fd,一但发现用来打印本地日志的文件fd不见了,就重启服务进程。核心代码如下:

lsof -p $pid | grep -q ${log_file_name}
if [ $? != 0 ]
then
    # 报警代码 ...
fi

发现bug发生的频率大概是一个星期一次。但这毕竟根本上解决不了问题啊,又找不到bug的原因,怎么办?

那就自定义一个File Handler吧!

决定自定义一个File Handler,这个File Handler工作在另外一个单独的进程,这样无论如何日志用的fd都不会跟主进程的各种socket用的fd冲突了吧。
代码如下,主要用到的技术进程通讯和用python的__getattribute__魔法把截获类实例的方法调用。这样,只需要把旧的代码中的File Handler(我用了TimedRotatingFileHandler)换成自定义的Handler Class,所有其他旧代码都无需改动。

#!/usr/bin/env python3

'''
created by kamuszhou*AT*tencent.com, zausiu*AT*gmail.com http://ykyi.net
Nov 20, 2018
'''

import logging
import logging.handlers
from functools import partial
from multiprocessing import Process, Queue


class MySpecialHandler(logging.StreamHandler):
    def __init__(self, *args, **kargs):
        self._q = Queue()
        self._p = Process(target=MySpecialHandler.__run, args=(self._q,))
        self._p.start()
        self._q.put(('__init__', args, kargs))

    def join(self):
        self._p.join()

    def __run(q):
        handler = None
        while True:
            # op, params = q.get()
            method, args, kwargs = q.get()
            if method == '__init__':
                handler = logging.handlers.TimedRotatingFileHandler(*args, **kwargs)
            else:  # 主进程的日志调用实际上被转到这里
                getattr(handler, method)(*args, **kwargs)

    def __proxy(self, name, *args, **kwargs):
        # 把调用的方法名和方法参数通过Queue传到专门的日志进程。
        self._q.put((name, args, kwargs))
        fun = logging.StreamHandler.__getattribute__(self, name)
        # print('call method: ', name, args, kwargs)
        # 如果是setLevel函数,再调用一次父类的方法
        if name in {'setLevel'}:
            return fun(*args, **kwargs)

    def __getattribute__(self, name):
        '''
        Hook大法!截获所有方法
        '''
        attr = logging.StreamHandler.__getattribute__(self, name)
        if hasattr(attr, '__call__') and name not in {'join', 'emit'}:
            return partial(MySpecialHandler.__proxy, self, name)
        else:
            return attr


if __name__ == '__main__':
    handler = MySpecialHandler('/data/tmp/ttt.log', when='D', interval=1, backupCount=90)
    handler.setLevel(logging.DEBUG)
    formatter = logging.Formatter('%(asctime)s: %(levelname)s %(message)s')
    handler.setFormatter(formatter)
    logger = logging.getLogger(__name__)
    logger.propagate = False  # Don't propagate the logging to ROOT
    logger.setLevel(logging.DEBUG)
    logger.addHandler(handler)
    logger.debug('debug testtttttttt')
    logger.info('info testtttttttttt')
    logger.warn('warn testtttttttttt')
    logger.error('error testtttttttt')
    logger.critical('critical testttttt')
    handler.join()

这里自定义的日志进程类只是一个很粗糙的实现,一但跑起来,只能手动杀进程。反正我的使用场景是一个服务。所以,我也懒得加‘优雅的退出代码’。

另外,这里创建自定义日志Handler的父类是StreamHandler,它还有一个重要的函数是emit。如果想定制这么一个Handler,把日志发给kafka而不需要起进程。则子类需要重写父类的emit方法。比如:

    def emit(self, record):
        msg = self.format(record)  # 日志会以record的形式传入该函数,用format把它格式化
        self.kafka_broker.send(msg, self.topic)

伯努利(Binomial)分布和伯努利试验的区别,负伯努利分布及几何分布,超几何分布

我又重新把概率,统计书拿起来了。这次是真的,要把机器学习(统计学习)学好。显然,学好机器学习并不是一件容易的事情。需要要扎实的数学基础。好在我的数学储备还勉强可以,但远算不上“基础扎实”。所以,我有了一个长期远景规划,重新开始学习吧!

今天看了伯努力分布,负伯努利分布,超几何分布,几何分布这几个知识点。下面我一边写回顾今天学到的,一边写文章。

伯努利分布和伯努利试验的区别

伯努利试验(Binomial Experiment)指的仅仅是”一次试验”,或者成功,或者失败。伯奴利分布是一个常用分布,这是完全不同的两个概念。
每次伯努利试验的成功概率记为p,又把重复很多次伯努利试验称为伯努利过程(Binomial Process)。一个重复了n次伯努利试验的伯努利过程中,成功的试验次数记为X,这个X则是伯努利随机变量。X的概率分布被称为伯努利分布。
伯努利分布:

$$b(x;n,p) = {n \choose x} p^k (1-p)^{ n-k}$$

其中,n表示试验次数,p表示每次独立试验成功的概率,x表示成功次数。

什么是负伯努利分布(Negative Binomial Distribution)

伯努利分布和负伯努利分布的大多数设定都是一样的,都不断重复伯努利试验,要么成功要么失败。
不同点是:伯努利分布的随机变量X,表示的是在前n次伯努利试验中成功了x次;而负伯努利的随机变量x,表示的是要达成k次成功试验,需要试验x次(即第x次试验成功,前x-1次试验成功了k-1次)。伯努利分布限定了试验次数记为n,负伯努利限定了成功次数记为k。
负伯努利分布:

$$b^*(x;k, p) = {{x-1} \choose {k-1}}p^kq^x-k$$

几何分布和超几何分布

再以伯努利分布为讨论的基础,仅更改一处,即把伯努利过程中的放回抽样(with replacement)改成不放回抽样(without replacement),即可得到超几何分布。
以负伯努利分布为讨论的基础,仅更改一处,即k设为1,表示成功一次。即不断重复伯努利试验,直到第一次成功就结束,得到了几何分布。

伯努利分布,负伯努利分布的命名

  • 为什么叫伯努利分布
    因为伯努利展开式$$(q+p)^n$$的n+1个项对应伯努利分布取各个值时的情况。
  • 为什么叫负伯努利分布
    因为展开式$$p^k(1-p)^(-k)$$中的每个项对应$$b^*(x;k,p)$$取x=k, k+1, k+2, …时的情况。

安装MathJax-LaTeX插件,让wordpress显示数学公式

安装MathJax-LaTeX插件,让wordpress显示数学公式

最近看统计学,涉及很多数学公式。于是,想找到一款wordpress的插件可以显示数学公司。

当然,于是就找到了 MathJax-LaTex这个插件。虽然插件名字中有LaTex,但实际上不仅仅可以用LaTex语法描述数学公式,亦可用AsciiMath,以及MathML。
本以为像其它所有wordpress插件一样,安装很简单,很容易就能上手使用。没想到还是花了一些时间。

MathJax-LaTex插件依赖MathJax这个javascript开源工程。原因貌似是MathJax默认用的CDN在大陆被墙了,还是因为浏览器的同源策略被浏览器禁了??我懒得重现排查真正原因了。总之,我用MathJax-LaTex默认配置没有成功,于是我自己手动下载并安装到自己的服务器,运行OK。

  1. 首先到 https://github.com/mathjax/MathJax 下载源代码。熟悉git的同学可以用git下载,亦可用右边的 Clone or Dowload 按钮下载zip包。
  2. 把zip包上传到自己的服务器,找一个目录解压缩。
  3. 打开MathJax-LaTex的配置web页面,如下图如示,去掉Use MathJax CDN Service 的勾,不要用MathJax自己的CDN;然后,在Custom MathJax location选项中填上自己的路径。假如刚才zip包MathJax解压缩到的目录是/tools,那么就填上 /tools/MathJax-2.7.5/MathJax.js
    MathJax-LaTex-Conf
  4. 然后创建一篇新博文,现在可以录入数学公式啦。装逼必备!比如下面的伯努利分布的公式:

$$b(x;n,p) = {n \choose x} p^k (1-p)^{ n-x}$$

要输入上述方程式,在文章开头输入[mathJax] ,这个标志让MathJax-LaTex插件加载显示数学公式相关的javascript代码。然后敲两个美元号 $$,敲入公式 b(x;n,p) = {n \choose k} p^k (1-p)^{ n-k},再敲入两个美元号结尾。即用双美元号$$把公式围起来。亦可用[latex][/latex]这对标签把公式围起来。这对标签这里的公式描述用了 asciiMath语法. n choose k即一个组合。在网上搜索相关语法参考。

在这个页面可以看到更多用MathJax显示的数学公式的例子,用浏览器的查看源代码功能(ctrl-u)查看使用的语法:
使用LaTex语法: http://ykyi.net/zausiu/MathJax-2.7.5/test/sample.html
使用AsciiMath语法: http://ykyi.net/zausiu/MathJax-2.7.5/test/sample-asciimath.html
使用MathML语法:http://ykyi.net/zausiu/MathJax-2.7.5/test/sample-mml.html

C/C++用万恶的libcurl透过HTTPS发POST+JSON请求

相比python, nodejs这样的脚本开发语言已有非常好用的RESTful开发库,很多C/C++程序在调用RESTful接口时,还在使用非常难使用的libcurl纯C接口。下面是用libcurl透过HTTPS发POST请求的代码代段,http body是json字符串:

    #include <curl/curl.h>

    CURL* curl;
    struct curl_slist* headers;
    curl = curl_easy_init();
    headers_ = curl_slist_append(headers, "Content-Type: application/json");
    curl_easy_setopt(curl, CURLOPT_HTTPHEADER, headers);
    curl_easy_setopt(curl, CURLOPT_SSLCERTTYPE, "PEM");
    curl_easy_setopt(curl, CURLOPT_SSLCERT, cert_file_path.c_str());
    curl_easy_setopt(curl, CURLOPT_SSLKEYTYPE, "PEM");
    curl_easy_setopt(curl, CURLOPT_SSLKEY, key_file_path.c_str());
    curl_easy_setopt(curl, CURLOPT_CAINFO, ca_file_path.c_str());
    curl_easy_setopt(curl, CURLOPT_SSL_VERIFYPEER, 1L);
    curl_easy_setopt(curl, CURLOPT_POSTFIELDSIZE, -1L);

    // jv_text存了json字符串
    curl_easy_setopt(curl_, CURLOPT_POSTFIELDS, jv_text.c_str());
    curl_easy_setopt(curl_, CURLOPT_URL, path.c_str());

    CURLcode res = curl_easy_perform(curl_);
    if (res != CURLE_OK)   // 没有成功
    {
        LG_ERR("curl_easy_perform() failed: %s", curl_easy_strerror(res));
    }
    else  // 成功了
    {
    }
    curl_easy_cleanup(curl);

openssl签发证书肘后备急方(cheatsheet)

生成一对新的RSA非对称密钥,2048bits长。 generate an RSA private key

openssl genrsa -out private.key 2048

从私钥中提出公钥。 extract the public key

openssl rsa -in mykey.pem -pubout > my_pubkey.pub

创建自签名证书。create a self-singned certificate

openssl req -config openssl.conf -x509 -sha256 -days 3650 -newkey rsa:4096 -keyout ca.key -out ca.crt

签署CSR。sign the CSR

openssl ca -config openssl.conf -days 375 -notext -in test.csr -out test.crt

检验签书。verify the certificate

openssl verify -CAfile ca.crt test.crt

生成一个CSR。Generate a new private key and CSR(Certificate Signing Request)

openssl req -config openssl.conf -out CSR.csr -nodes -new -newkey rsa:2048 -nodes -keyout private.key

查看一个证书。show the certificate

openssl x509 -noout -text -in test.crt

PEM格式的证书转换为pfx格式的证书

openssl pkcs12 -inkey bob_key.pem -in bob_cert.cert -export -out bob_pfx.pfx

We can extract the private key form a PFX to a PEM file with this command:

openssl pkcs12 -in filename.pfx -nocerts -out key.pem

Exporting the certificate only:

openssl pkcs12 -in filename.pfx -clcerts -nokeys -out cert.pem

Removing the password from the extracted private key:

openssl rsa -in key.pem -out server.key

///////////////////////// openssl.conf /////////////////////////

我用的openssl配置文件

[ ca ]
default_ca = kamus # The default ca section

[ kamus ]
dir = . # top dir
database = $dir/index.txt # index file.
new_certs_dir = $dir/newcerts # new certs dir

certificate = $dir/ca.crt # The CA cert
serial = $dir/serial # serial no file
private_key = $dir/root.key # CA private key
RANDFILE = $dir/.rand # random number file

default_days = 365 # how long to certify for
default_crl_days= 30 # how long before next CRL
default_md = sha256 # md to use

policy = policy_any # default policy
email_in_dn = no # Don't add the email into cert DN

name_opt = ca_default # Subject name display option
cert_opt = ca_default # Certificate display option
copy_extensions = none # Don't copy extensions from request

[ policy_any ]
countryName = optional
stateOrProvinceName = optional
organizationName = optional
organizationalUnitName = optional
commonName = supplied
subjectAltName = supplied
emailAddress = optional

[ req ]
default_bits = 2048
distinguished_name = req_distinguished_name
string_mask = utf8only
default_md = sha256

[ req_distinguished_name ]
countryName = Country Name(2 letter code)
stateOrProvinceName = State or Province Name
localityName = Locality Name
commonName = Common Name
subjectAltName = SubjectAltName
emailAddress = email

nginx架设HTTP服务器接受PUT方法上传文件

最近用nginx架了个http服务器,通过http上传文件。
nginx的配置如下:

        location ~ ^/wraith {
            root /data/tmp;
            dav_methods PUT;
            dav_access user:r group:r all:r;
            create_full_put_path on;

            limit_except GET {
            }
        }

如上,子目录/wraith将接受PUT方法。

$curl -XPUT --data-binary @${TAR_PATH} --noproxy '*'  http://xxx.xxx.xxx.xxx/wraith/${TAR_FILE}

如上用curl通过http上传文件到服务器的/data/tmp目录下,文件命名为${TAR_FILE}

utf8中文字符串的多模式匹配算法的优化

utf8中文字符串的多模式匹配算法的优化

信息安全部接口组 kamuszhou@tencent.com

效果

本节仅展示优化效果,对一些业务逻辑和背景未做解释,读者可直接跳至下一节。
上个月接触到了我组的一个关于在海量文本中匹配字符串业务。读源代码时发现一些问题,并针对这些问题做了优化工作,效果非常明显。

测试的硬件环境是只用一颗主频2.4G的Intel至强处理器核心。OS是tlinux2。该业务目前载入11万3千条规则。优化前后的效果如下:

|载入 | 旧算法 |旧算法简版| 新算法 | 提升效果 |
|:—:|:——:|:——–:|:——-:|:——-:|
|速度 | 26分钟 | 3分钟 | 3秒 |60倍或250倍|
|内存 | 4327M | 4327M | 不到200M| 20倍 |
* 表中的“旧算法简版”指去掉了一个繁琐的预计算步骤

|处理速度 | 旧算法 | 新算法 | 提升效果 |
|:—:|:——:|:——–:|:——-:|
|用11万3千条规则作为待检测文本|52秒|2秒|26倍|
|10倍四大名著共88M,平均每行143个汉字|59秒|10秒|近6倍|
|文字选自四大名著共87M,平均每行10个汉字|161秒|5秒|32倍|
* 用11万3千条规则作为待检测文本使得新旧算法都会密集地走到“命中逻辑”,旨在比较“命中逻辑”的性能。
* 用四大名著作为待检测文本,使得新旧算法几乎不会走到“命中逻辑”,旨在比较算法处理正常文本时的性能。而每次处理文本的长度亦可能影响到性能表现。如表所示,处理短文本(10个汉字)时,新算法的优势有所降低,可解释为旧算法为启动每一次处理消耗较大的资源,而如果处理的文本较长时,这个资源消耗分摊到每个待处理字符就相对不那么明显了。

在一台24核的M2机器上,理论估计新算法一天可以处理36,495,360M文本,36个T~

业务简述

该业务的核心问题简单地近似概括为:

有几十万甚至更多的模式(短字符串)集合P={P1, P2, …, Pn},输入一个utf8编码的字符串string,输出有哪些模式Px在string中出现。

实际问题比上面的描述稍微复杂一点点。业务需要通过找到的模式判断是否命中预定的规则。一个模式串或多个模式都可以组成规则。比如,单独的一个Px组成一条规则,多个不同的模式则会组合成一个 关系的规则(目前业务只支持与关系,支持更复杂的匹配规则是将来需要增强的地方)。比如,有下面几条规则:
1. 铁王座
2. 雪诺 & 提利昂
3. 雪诺 & 艾莉亚 & 2
4. 雪诺 & 龙母 & 床
5. 雪诺 & 夜王 & 异鬼军团 & 守夜人

下文的讨论将继续引用这个规则列表。

当输入的string中包括“铁王座”时,则命中规则1;当包括“雪诺”同时也有“提利昂”时,则命中规则2;如果需要命中规则3,string则必须同时包括三个短字符串“雪诺”,“艾莉亚”和一个单ascii字符“2″。

原算法的主要不足

原算法大致有以下几个问题。

  1. 第一问题很容易注意到。原算法用共享内存存储字符串时相当“阔绰”。比如,存储“铁王座”,“雪诺”,“2”,统统需要256字节,而实际上它们的长度分别是9字节,6节字,1字节。

  2. 原算法扫描一遍输入字符串string后,如果命中了至少一个模式,将进入一个非常“朴素”的穷举阶段:把所有的规则遍历一遍,对于每条规则中的每个模式,检查是否命中。设规则条数为n,规则的平均长度是m,这是一个O(n*m)的时间复杂度。当规则数有几十万之多是,这个阶段非常耗时。

  3. 再说匹配多模式阶段的算法。原算法可以概括为“Trie Tree”和“Boyer-Moore 模式匹配算法”。Trie Tree是非常常见的组织字符串的数据结构。而Boyer-Moore算法在1977年由Robert S Boyer和Strother Moore发表[1]。简单地讲,Boyer-Moore算法预先计算两张“跳字符”的表,籍此提高匹配速度,它本身解决的问题是单模式的匹配,但面对多模式的问题时需要做一些简单的调整,而且,随着模式数的增长,当模式数目大大超过待检查字符串的长度时,所有的“跳字符”算法,包括Boyer-Moore算法将表现不佳[2]。事实上,原算法费尽心力(十分钟量级)预计算的跳字符表中的跳字符步长是1个byte。1个byte的步长让跳字符表,除了故弄玄虚的作用外,已变得毫无意义。为何计算得到1个byte的步长?因为这近20万个模式中有单个的ascii字符,单个ascii字符的长度只有一个byte。如果跳字符步长超过1byte,就有可能错过单个ascii字符模式。

新算法的改进

解决问题1

问题1是耗内存太多。这个很容易解决,不作重点阐述。新算法广泛使用C++的标准数据结构,而不是手工在共享内存上实现朴素,笨拙,易越界的数据结构。旧方式容易产生的微妙bug,用新的开发思路,很多bug在编译期就能被检查到。效果则是不仅从消耗4G内存降到200M,而且在实现各小需求时获得明显的开发效率和代码质量的提升。

解决问题2

问题2是在命中模式后确定命中哪些规则的效率问题。旧算法不管三七二十一把所有规则全遍历一遍。新算法大的思路是使用信息检索广泛使用的“倒排索引”。并辅以更多的优化。新算法将建立的数据结构简述如下:

  • 建立“模式–>规则”的倒排索引。并预先计算一个表征“当前模式命中后,它对应的规则有多大可能性被命中”的值,更专业地讲,引入了信息论中的“熵”。“熵”将决定当命中很多个模式时,先查找哪个模式对应的规则有更高的效率。下文会继续讨论“熵”的作用。

  • 对每个模式对应的规则进行分级,只有一个模式的规则入全局哈希表,只有两个模式的规则也入全局哈希表,有三个和三个以上模式的规则放在一起作为对应该模式的多模式规则集合。这么做的理由是,只有一个模式和只有两个模式的规则最容易用哈希表快速处理,而确定是否命中多模式规则需要大得多的开销。

以上文的五条规则为例详细阐述新算法的思路:

  1. 为每个模式编号: 1:铁王座 2:雪诺 3:提利昂 4:艾莉亚 5:2 6:龙母 7:床 8:夜王 9:异鬼军团 10:守夜人

  2. 建立索引(从规则映射到模式):

    • Rule1 -> set(Pattern1)
    • Rule2 -> set(Pattern2, Pattern3)
    • Rule3 -> set(Pattern2, Pattern4, Pattern5)
    • Rule4 -> set(Pattern2, Pattern6, Pattern7)
    • Rule5 -> set(Pattern2, Pattern8, Pattern9, Pattern10)
  3. 建倒排索引(从模式映射到规则)
    • Pattern1 -> 只有单模式,入单模式全局哈希表 Pattern1 -> Rule1
    • Pattern2 -> 入双模式全局哈希表 (Pattern2, Pattern3) -> Rule2; 自有多模式集合set(Rule3, Rule4, Rule5; 熵 := 3)下文讨论如何计算熵
    • Pattern3 -> 入双模式全局哈希表 (Pattern2, Pattern3) -> Rule2; 没有自有多模式集合。
    • …略…
    • Pattern6 -> 自有多模式集合set(Rule4; 熵Entropy := 1下文解释 )
    • Pattern10 -> 自有多模式集合set(Rule5; Entropy := 1 )

    下面再详细地讨论为什么引入熵,及如何计算熵:

    假如已知命中了模式“龙母”,那么将有2种可能。要么命中Rule3,要么不命中任何规则。如果已知命中了模式“雪诺”,那么将有5种可能。命中Rule2,命中Rule3,命中Rule4, 命中Rule5,和不命中任何规则。那么,如果已经发现同时有命中多个模式,其中包括“龙母”,和“雪诺”。通过查找倒排索引,能拿到潜在可能命中的所有规则。但问题是,究竟先找“龙母”的倒排,还是先找“雪诺”的倒排呢?在这个简单的例子中,我们容易凭自觉知道,得先查“龙母”的倒排效率更高,而查“雪诺”的倒排可能会尝试不可能命中的规则。在实际业务中,有部分模式对应的规则有几千个之多,但只可能命中其中一两个,这个效率是不高的。但这个问题可以用信息论解决:发生事件“已找到模式龙母”较之发生事件“已找到模式雪诺”,事件“命中规则”在前者的条件下的确定性更高,即“熵”更小。从“熵”小的开始处理。但如何计算“熵”呢?更一般地,记找到模式Px这个事件为y,记输入string命中规则这个事件为z,记命中模式Px对应的规则这个事件为x。则计算发生命中模式Px的情况下将命中规则的条件熵的公式为:
    _** H(X|Y,Z) = -∑P(x,y,z)|logP(x|y,z) x∈{y对应的模式集合}**_
    事实上,这是个简化的模型。更严谨地,如果已知命中多个模式y1,y2,y3…yn时,则条件概率应该是P(x|y1,y2,…yn,z)。不继续展开,回到上面的公式。如果有足够多的输入文本就可以求出H(X|Y),或者在运行时积累数据,慢慢迭代也可逼近准确的熵值。但如果不在乎损失效率,还能再继续简化。用模式Px对应的多模式规则集合的大小来替代H(X|Y),用它作为非常不严谨的“熵”值。集合中的规则个数越少,则优先选用这个集合中的规则作检查。仅管求得严谨地熵将获得更高的效率,但用这个极简化的版本也能取得不错的效果。不过,上述算法只适用于“一但匹配到一个规则就迅速跳出”的情况,如果要找出所有匹配规则就没必要这么做了。但下文的实例推演中还将介绍另一个优化的方法。

举实例简述匹配方法:
1. 输入字符串 “xxxx铁王座xxxxx”
匹配到模式“铁王座”时,检查“单模式规则查询表”,发现该模式在表中,迅速命中Rule1。如果业务只需要发现一个匹配规则,此时就可以快速结束其它逻辑。

  1. 输入字符串 “xxx提利昂xxxx雪诺xxxx”
    匹配到“提利昂”时,检查“单模式规则查询表”,没有匹配。
    匹配到“雪诺”时,检查“单模式规则查询表”,没有匹配。
    把“雪诺”和“提利昂”合在一起生成一个惟一key,查“双模式规则建查询哈希表”,命中。

  2. 输入字符串 “xxxx雪诺xxxx夜王xxxx龙母xxxx异鬼军团xxxxx守夜人”
    会连续匹配到5个模式,每匹配到一个模式,按照前述1,2的方法检查单模式哈希表和双模式哈希表。一般地,命中第n次模式时,将会带来一次单模式哈希表的检查和 n-1 次双模式哈希表的检查。直到字符串扫描结束。进入处理多模式字符串的阶段。在这个阶段,已经拿到了字符串中出现的5个模式,通过查找“倒排索引表”,可以找到所有可能的多模式规则。按照预先计算好的“熵”的大小排序,取熵最小(即确定性最高)的模式对应的多模式规则开始尝试。此例中,模式“龙母”,“守夜人”,“异鬼军团”,“夜王”的熵都是1,而“雪诺”的熵是4,表示查“雪诺”对的规则将有最大的不确定性。于是,从熵小的模式开始,查“龙母”的倒排找到Rule3,发现不匹配;再查“守夜人”的倒排找到Rule5,此时发现Rule5命中。这里,就体现出来了简化“熵”的缺点,在实际应用中,如果算得严谨的熵值,会较大概率地先选择“守夜人”模式对应的多模式规则,一击即中!

  3. 输入字符串 “xxxx雪诺xxxx夜王xxxx龙母xxxx异鬼军团xxxxx”
    此例与例3类似,但结果将是不匹配任何规则。前部分步骤与例3一样,当所有“熵”是1的模式对应的多模式规则被检查发现不匹配后,再找到“雪诺”对应的所有多模式规则:Rule3,Rule4,Rule5。此时,需要检查这三个规则吗?不需要!因为不可能匹配到。这个断言可以一般性的概括为:

    已找到 n 个彼此不相同的模式,并且已经查找过 m 个模式对应的规则皆不匹配,还剩余 n -m 个模式对应的多模式规则需要被检查。这时取第 m + 1个模式对应的所有多模式规则。对于其中每个规则,取得它的size,即这条规则由多少个模式组成。如果 size > (n – m),那么,可以立即肯定这个Rule无法匹配。不用浪费时间。
    上述规律适用于“查找过m个模式对应的规则皆不匹配”的情况,如果处理前m个模式的对应规则时有q个模式的对应规则存在命中,则判断式改为 size > (n – m + q)

改进问题3

问题3是匹配算法的效率问题,是否还有可改进的空间呢?
新算法大概从四个方面提升匹配算法的效率:

  1. 前文有提到在20万之多大量模式的前提下,旧算法计算的“跳字符”步长实际是1。而我们的业务处理的字符多是utf8编码的中文,一个中文字有3个bytes,当处理中文时,显然步长可以放心地提到3bytes。一般地,utf8编码的首字节记载了当前“字”的长度[3],这个长度即可以作为“跳字符”的步长。在中文字占绝对多数的情况下,平均步长应该非常接近3,而旧算法只有1。粗略地,乐观地估计,这个改进将使得新的算法将获得接近3倍的性能提升。

  2. 业务处理的文本多是utf8编码的中文文本,而旧算法用的是通用的编码无关的算法,未对utf8中文作优化。很容易想到,如果以一个utf8字符为单位建Trie Tree比以Byte为单位建Trie Tree将获得更紧凑的内存布局,和更高效的cpu利用。既能提高速度又能节省内存。

  3. 至此,新算法将在Trie Tree的结点存一个utf8字符,大多数情况下是一个3bytes的中文字。但现代服务器的cpu是64位的,一个中文字也才占了3字节,还有5个字节没有利用上啊!这时,有点NLP经验的开发者应该马上想到Bigram了。使用Bigram“二元模型”能继续提高性能。扫描utf8字符串时,每次取一个Bigram,虽然跳节符跳字符步长仍然是一个utf8字符,但因为每次取出两个utf8字组成Bigram增加了上下文信息,匹配效率将大大增加,大量地减少了因为单个utf8字匹配到模式第一个utf8字而造成的无谓地“爬树”时间。为利用好Bigram,新算法的Trie Tree的第1层(树根记为第0层)将存一个Bigram,而其他层仍然存单个utf8字。新旧算法的Trie Tree将分别如下文的Figure 1,Figure 2所示。但引入上述Bigram的逻辑将引入一个新问题,即无法用新的Trie Tree命中单个utf8字的模式。比如Rule2中的ascii字符,数字“2”和Rule4中的中文字“床”。好在这样的单个字模式在规则中量很少,可以把找单个字模式的逻辑推迟到命中了需要单个字模式的规则时。举例说明即当发现命中了Rule4中的模式“龙母”,潜在可能命中Rule4,此时再扫描一遍原文本看有没有“床”这个模式。因为这个特殊情况在所有规则中所占比重非常低,所以执行到这个逻辑也会很少,因此这个额外的推迟逻辑不会拖累新算法的整体效率。在绝大多数情况下,引入Bigram将提高效率,可忽略引入的额外逻辑造成的负担。还有极端的只有一个utf8字的模式单独组成一个规则,这种极端情况目前没有出现,未来出现的可能性也很低,暂时不予考虑。即使出现了也能在不可避免地,至少一次遍历字符串时轻易解决。

  4. 第四点倒不是算法层面的改进,而是把旧算法中不必要的堆分配以及各种不必要的其他开销全部删掉,留下干干净净纯干活的代码。

综合上述改进,如下示意图是新旧匹配算法的Trie Tree。

新算法TrieTree
Figure 1 新算法的Trie Tree

旧算法TrieTree
Figure 2 旧算法的Trie Tree

对照新旧算法的Trie Tree,看图,更容易理解为何新算法又快又省内存。
新算法的Trie Tree第一层使用Bigram,一些不会命中的普通文本几乎在树的第一层就被发现了,而旧算法每个结点只存了一个Byte的数据,但utf8中文字的第一个Byte有四个bit位是固定的,在有近二十万个模式的情况下,旧算法几乎对每个中文字都会“爬树”到至少第二层。
再举个例子,输入字符串“雪花啤酒”,因为有模式“雪诺”,当处理第一个汉字“雪”时。新算法会取Bigram”雪花”,在树的第一层即发现不可能匹配,但旧算法爬到树的第三层时会命中“雪”,至少要爬到树的第四层才能得出不匹配的结论。

未来改进

新的形势对该业务提出更高的要求,未来需要处理更复杂的匹配规则,比如酌情实现“正则式”的子集。

参考资料

[1]: Robert S. Boyer, Standford Research Institute & J Strother Moore, Xerox Palo Alto Research Center. A fast String Searching Algorithm. Communications of the ACM. 1977.
[2]: Ricardo Baeza-Yates & Berthier Ribeiro-Neto. Modern Information Retrieval, 2nd. P385, 3rd paragraph. 2011.
[3]: utf8维基百科词条 https://en.wikipedia.org/wiki/UTF-8

服务器端的tcp有大量TIME_WAIT怎么办

公司的群里讨论tcp的TIME_WAIT的问题。TIME_WAIT这个状态可是面试时经常问的知识点啊。
讨论的问题是:有一个服务器,它对外网提供服务,同时它作为客户端连接很多后端的其它服务器。这位同事连后端其它服务器时用了短tcp连接。结果出现了大量的tcp TIME_WAIT状态,吞吐量上不去,怎么办?

先说结论:
1. 如果该服务器要处理外网IP的入流量,那最好的办法应该是用tcp长链接改造它与后端服务器的连接。如果用中间件,比如上zeromq那更省心了。
2. 如果不想做改动,并且在应用层确认已经交互已经完成,则可以用shutdown()直接发RST结束tcp会话,而不走正常的4次挥手。查阅shutdown系统调用的文档获知如何发RST。
3. 如果该服务器不需要处理处网IP请求的话,那么,启用port reuse 即打开net.ipv4.tcp_tw_reuse不会有太大问题(如果处理外网请求就有问题,和NAT相关,见https://vincent.bernat.im/en/blog/2014-tcp-time-wait-state-linux),或者更好的,把/proc/sys/net/ipv4/tcp_fin_timeout改小,改成1或者2。让TIME_WAIT只保持很短的时间。

首先,需要知道一个tcp会话由 src_ip, src_port, dest_ip, dest_port 四元组确定。
我们公司的IDC环境中, 上述的服务器作为客户端再发起tcp连接联后端服务器,则 src_ip 固定了, dest_ip是后端服务器的ip, port是后端服务器监听端口。这样只有 src_port 是可变化的,但port只有16个bits还不能用well-known ports,这样就更少了。

再说,主动关闭时,tcp连接需要进入TIME_WAIT状态,保持两倍MSL时长,是为了处理两种情况:
1) 让当前这个会话的迷路包在网路中消失。这样不会干扰到新建的会话。
2) 确保主动关闭方的FIN-ACK包,如果丢失的话,还能重发。
1981年的TCP RFC上把MSL设成两分钟,https://tools.ietf.org/html/rfc793

Maximum Segment Lifetime, the time a TCP segment can exist in
the internetwork system. Arbitrarily defined to be 2 minutes.

MSL设置这么长,因为以前的网络环境差啊。不过现在因为移动互联网,比较差的网络状态也是非常常见的。但RFC允许实现方减少MSL值。事实上linux的MSL写死在代码中为1分钟并且不可在运行期配置。
如果tcp连接的双方都在性能高速稳定的内网中,这个MSL就太长了。

调试时,还发现如果port用完了,connect的时候内核代码会用自旋锁忙等检查port资源。有linux内核开发基础的开发者都知道spin_lock的时候是不会让出cpu的,于是cpu全被spin_lock吃掉了。一直要等到有port被释放。再后来又发现,如果scoket没有设定SO_REUSEADDR选项,则connect()系统调用会返回EADDRINUSE。

tcp的连接双方都是确定且长期的,用什么tcp短连接呢??改造吧~~~