第 9 页的文章列表

ubuntu服务器部署ipv6访问

整个部署过程分为: 1.启用服务器的ipv6支持 2.申请ipv6通道 3.开启nginx的ipv6地址监听

1.ubuntu上开启ipv6支持,需要修改几个地方

1.开启ipv6支持,/etc/sysctl.conf 确保有以下设置:

net.ipv6.conf.all.disable_ipv6 = 0
net.ipv6.conf.default.disable_ipv6 = 0
net.ipv6.conf.lo.disable_ipv6 = 0

设置完毕后使用sysctl -p使设置生效 2.设置服务器的ipv6 dns服务器,/etc/network/interfaces 添加以下设置:

dns-nameserver 2001:4860:4860::8888
dns-nameserver 2001:4860:4860::8844

设置完毕后使用sudo resolvconf -u使设置生效 这样能够保证服务器在连接ipv6地址时有合适的dns服务器 测试:ping6 ipv6.google.com 如果能够ping通则表示已经设置成功

2.申请ipv6通道

因为我的服务器是没有分配ipv6地址的,所以需要去http://tunnelbroker.net申请ipv6的通道。 1.注册账号 2.邮箱激活 3.登录 4.create regular tunnel 5.输入你的服务器的ipv4地址,创建通道 6.在example configurations处选择操作系统,获取配置 7.在 /etc/network/interfaces中拷贝6中的配置 8.sudo resolvconf -u使配置生效 9.通过ifconfig查看是否设置成功,如果出现了ipv6的地址则表示成功

3.开启nginx的ipv6地址监听

在所有的站点配置文件中加上:

listen [::]:80
listen [::]:443

分别监听80端口和443端口(如果有https) 重启nginx即可。 通过http://ipv6-test.com/validate.php测试域名能否在ipv6下访问成功。如果是阿里云,那么有可能在IPv6 DNS server这一项上失败。因为阿里云的DNS服务器没有IPv6 DNS server。这种情况下,如果用户只有ipv6的环境,则会因为无法访问DNS服务器而失败

分类:linux标签:#linux #ipv6

ubuntu下使用GDB调试segment fault错误

注意:下面的使用仅在ubuntu实验过。 1.打开ubuntu的core dump,这样程序出错后会生成corefile以供我们分析

echo '/tmp/corefile/core.%e.%p.%t' | sudo tee /proc/sys/kernel/core_pattern
ulimit -c unlimited

然后创建/tmp/corefile文件夹

mkdir /tmp/corefile/

2.运行程序,如果出现段错误(核心已转储),则说明corefile已经生成了。检查/tmp/corefile下是否有新生成的错误文件。 如果没有,执行cat /proc/sys/kernel/core_pattern,检查/tmp/corefile/core.%e.%p.%t是否写入了 3.使用gdb调试错误

分类:linux

tcpdump分析php curl

所用工具

  • tcpdump:linux下分析网络的一个好用的终端工具
  • psysh:php的一个终端执行工具,可以很方便的在终端执行php代码
  • curl:php的curl库

tcpdump报文中Flags代表报文类型: S (SYN), F (FIN), P (PUSH), R (RST), U (URG), W (ECN CWR), E (ECN-Echo) or ‘.’ (ACK), or ‘none’ if no flags are set.

分析背景

最近在了解swoole,因为公司的技术栈是php,所以之前用的java那一套在普通的php开发上完全用不了。为了让php有更好的性能,更广泛的使用场景,找了找相关资料,了解到swoole这个库。决定使用之后,项目中有个地方需要使用到http连接池,所以需要使用curl,但是curl虽然强大,但是参数实在是太多了,里面的实现细节也只能查看c的源代码才知道。所以只能曲线救国,通过tcpdump了解curl在http请求上的工作机制 tcpdump的使用方法是:

案例分析

案例一

只执行一次exec,等待一段时间,强制关闭终端进程

<?php
$context = curl_init();
curl_setopt($context,CURLOPT_URL,"http://www.izuqun.com");
curl_exec($context);

整个过程的报文如下

    `192.168.1.107.44664 > 116.62.25.128.http`: Flags [S], cksum 0x4bdf (correct), seq 3687066847, win 29200, options [mss 1460,sackOK,TS val 5931640 ecr 0,nop,wscale 7], length 0
16:28:54.014280 IP (tos 0x20, ttl 52, id 0, offset 0, flags [DF], proto TCP (6), length 60)

    `116.62.25.128.http > 192.168.1.107.44664`: Flags [S.], cksum 0xbcb5 (correct), seq 4174849842, ack 3687066848, win 28960, options [mss 1460,sackOK,TS val 3844377305 ecr 5931640,nop,wscale 7], length 0
16:28:54.014304 IP (tos 0x0, ttl 64, id 44712, offset 0, flags [DF], proto TCP (6), length 52)

    `192.168.1.107.44664 > 116.62.25.128.http`: Flags [.], cksum 0x5bba (correct), ack 1, win 229, options [nop,nop,TS val 5931643 ecr 3844377305], length 0
16:28:54.014334 IP (tos 0x0, ttl 64, id 44713, offset 0, flags [DF], proto TCP (6), length 105)

    `192.168.1.107.44664 > 116.62.25.128.http`: Flags [P.], cksum 0xee60 (correct), seq 1:54, ack 1, win 229, options [nop,nop,TS val 5931643 ecr 3844377305], length 53: HTTP, length: 53
        GET / HTTP/1.1
        Host: www.izuqun.com
        Accept: *\* 
16:28:54.023036 IP (tos 0x20, ttl 52, id 44520, offset 0, flags [DF], proto TCP (6), length 52)

    `116.62.25.128.http > 192.168.1.107.44664`: Flags [.], cksum 0x5b85 (correct), ack 54, win 227, options [nop,nop,TS val 3844377307 ecr 5931643], length 0
16:28:54.023061 IP (tos 0x20, ttl 52, id 44521, offset 0, flags [DF], proto TCP (6), length 314)
    `116.62.25.128.http > 192.168.1.107.44664`: Flags [P.], cksum 0xba4d (correct), seq 1:263, ack 54, win 227, options [nop,nop,TS val 3844377307 ecr 5931643], length 262: HTTP, length: 262
        HTTP/1.1 200 OK
        Server: nginx/1.12.2
        Date: Mon, 11 Dec 2017 08:28:54 GMT
        Content-Type: text/html
        Content-Length: 1243
        Last-Modified: Mon, 11 Dec 2017 02:35:33 GMT
        Connection: keep-alive
        Vary: Accept-Encoding
        ETag: "5a2deef5-4db"
        Accept-Ranges: bytes
16:28:54.023076 IP (tos 0x0, ttl 64, id 44714, offset 0, flags [DF], proto TCP (6), length 52)

    `192.168.1.107.44664 > 116.62.25.128.http`: Flags [.], cksum 0x5a73 (correct), ack 263, win 237, options [nop,nop,TS val 5931645 ecr 3844377307], length 0
16:28:54.024214 IP (tos 0x20, ttl 52, id 44522, offset 0, flags [DF], proto TCP (6), length 1295)

    `116.62.25.128.http > 192.168.1.107.44664`: Flags [P.], cksum 0x870b (correct), seq 263:1506, ack 54, win 227, options [nop,nop,TS val 3844377307 ecr 5931643], length 1243: HTTP
16:28:54.024236 IP (tos 0x0, ttl 64, id 44715, offset 0, flags [DF], proto TCP (6), length 52)

    `192.168.1.107.44664 > 116.62.25.128.http`: Flags [.], cksum 0x5585 (correct), ack 1506, win 256, options [nop,nop,TS val 5931645 ecr 3844377307], length 0

13报文:tcp的三次握手, 45报文:curl发起的get请求、服务器的ack回应 6~9报文:服务器对get请求的返回、我的机器的内核的ack,因为报文长度是超出了最大的限制,所以分成两次发送 稍等一会儿,又有新的报文

    `116.62.25.128.http > 192.168.1.107.44664`: Flags [F.], cksum 0x161d (correct), seq 1506, ack 54, win 227, options [nop,nop,TS val 3844393567 ecr 5931645], length 0
16:29:59.097967 IP (tos 0x0, ttl 64, id 44716, offset 0, flags [DF], proto TCP (6), length 52)
    `192.168.1.107.44664 > 116.62.25.128.http`: Flags [.], cksum 0xd672 (correct), ack 1507, win 256, options [nop,nop,TS val 5947914 ecr 3844393567], length 0

这是服务器发起的tcp连接关闭的报文,我的机器响应了,但是没有主动再次发送Fin 主动关闭psysh进程,出现大量报文

    192.168.1.107.44664 > 116.62.25.128.http: Flags [F.], cksum 0x8765 (correct), seq 54, ack 1507, win 256, options [nop,nop,TS val 5968150 ecr 3844393567], length 0
16:31:20.253999 IP (tos 0x0, ttl 64, id 44718, offset 0, flags [DF], proto TCP (6), length 52)
    192.168.1.107.44664 > 116.62.25.128.http: Flags [F.], cksum 0x8730 (correct), seq 54, ack 1507, win 256, options [nop,nop,TS val 5968203 ecr 3844393567], length 0
16:31:20.465940 IP (tos 0x0, ttl 64, id 44719, offset 0, flags [DF], proto TCP (6), length 52)
    192.168.1.107.44664 > 116.62.25.128.http: Flags [F.], cksum 0x86fb (correct), seq 54, ack 1507, win 256, options [nop,nop,TS val 5968256 ecr 3844393567], length 0
16:31:20.890008 IP (tos 0x0, ttl 64, id 44720, offset 0, flags [DF], proto TCP (6), length 52)
    192.168.1.107.44664 > 116.62.25.128.http: Flags [F.], cksum 0x8691 (correct), seq 54, ack 1507, win 256, options [nop,nop,TS val 5968362 ecr 3844393567], length 0
16:31:21.737935 IP (tos 0x0, ttl 64, id 44721, offset 0, flags [DF], proto TCP (6), length 52)
    192.168.1.107.44664 > 116.62.25.128.http: Flags [F.], cksum 0x85bd (correct), seq 54, ack 1507, win 256, options [nop,nop,TS val 5968574 ecr 3844393567], length 0
16:31:23.437992 IP (tos 0x0, ttl 64, id 44722, offset 0, flags [DF], proto TCP (6), length 52)
    192.168.1.107.44664 > 116.62.25.128.http: Flags [F.], cksum 0x8414 (correct), seq 54, ack 1507, win 256, options [nop,nop,TS val 5968999 ecr 3844393567], length 0
16:31:26.833967 IP (tos 0x0, ttl 64, id 44723, offset 0, flags [DF], proto TCP (6), length 52)
    192.168.1.107.44664 > 116.62.25.128.http: Flags [F.], cksum 0x80c3 (correct), seq 54, ack 1507, win 256, options [nop,nop,TS val 5969848 ecr 3844393567], length 0
16:31:33.633977 IP (tos 0x0, ttl 64, id 44724, offset 0, flags [DF], proto TCP (6), length 52)
    192.168.1.107.44664 > 116.62.25.128.http: Flags [F.], cksum 0x7a1f (correct), seq 54, ack 1507, win 256, options [nop,nop,TS val 5971548 ecr 3844393567], length 0
16:31:47.218007 IP (tos 0x0, ttl 64, id 44725, offset 0, flags [DF], proto TCP (6), length 52)
    192.168.1.107.44664 > 116.62.25.128.http: Flags [F.], cksum 0x6cdb (correct), seq 54, ack 1507, win 256, options [nop,nop,TS val 5974944 ecr 3844393567], length 0
16:32:14.417998 IP (tos 0x0, ttl 64, id 44726, offset 0, flags [DF], proto TCP (6), length 52)
    192.168.1.107.44664 > 116.62.25.128.http: Flags [F.], cksum 0x524b (correct), seq 54, ack 1507, win 256, options [nop,nop,TS val 5981744 ecr 3844393567], length 0

这些报文都是我的机器主动发送的关闭报文,但是服务器也不再响应

案例二

完整的使用curl_init和curl_close,显式关闭连接

<?php
$context = curl_init();
curl_setopt($context,CURLOPT_URL,"http://www.izuqun.com");
curl_exec($context);
curl_close($context);

报文如下

    192.168.1.107.44684 > 116.62.25.128.http: Flags [S], cksum 0x469f (correct), seq 2378041097, win 29200, options [mss 1460,sackOK,TS val 6028159 ecr 0,nop,wscale 7], length 0
16:35:20.090006 IP (tos 0x20, ttl 52, id 0, offset 0, flags [DF], proto TCP (6), length 60)
    116.62.25.128.http > 192.168.1.107.44684: Flags [S.], cksum 0xd6a7 (correct), seq 3548165201, ack 2378041098, win 28960, options [mss 1460,sackOK,TS val 3844473825 ecr 6028159,nop,wscale 7], length 0
16:35:20.090050 IP (tos 0x0, ttl 64, id 64631, offset 0, flags [DF], proto TCP (6), length 52)
    192.168.1.107.44684 > 116.62.25.128.http: Flags [.], cksum 0x75ac (correct), ack 1, win 229, options [nop,nop,TS val 6028162 ecr 3844473825], length 0
16:35:20.090105 IP (tos 0x0, ttl 64, id 64632, offset 0, flags [DF], proto TCP (6), length 105)
    192.168.1.107.44684 > 116.62.25.128.http: Flags [P.], cksum 0x0853 (correct), seq 1:54, ack 1, win 229, options [nop,nop,TS val 6028162 ecr 3844473825], length 53: HTTP, length: 53
        GET / HTTP/1.1
        Host: www.izuqun.com
        Accept: */*

16:35:20.099626 IP (tos 0x20, ttl 52, id 47030, offset 0, flags [DF], proto TCP (6), length 52)
    116.62.25.128.http > 192.168.1.107.44684: Flags [.], cksum 0x7576 (correct), ack 54, win 227, options [nop,nop,TS val 3844473828 ecr 6028162], length 0
16:35:20.099655 IP (tos 0x20, ttl 52, id 47031, offset 0, flags [DF], proto TCP (6), length 314)
    116.62.25.128.http > 192.168.1.107.44684: Flags [P.], cksum 0xda41 (correct), seq 1:263, ack 54, win 227, options [nop,nop,TS val 3844473828 ecr 6028162], length 262: HTTP, length: 262
        HTTP/1.1 200 OK
        Server: nginx/1.12.2
        Date: Mon, 11 Dec 2017 08:35:20 GMT
        Content-Type: text/html
        Content-Length: 1243
        Last-Modified: Mon, 11 Dec 2017 02:35:33 GMT
        Connection: keep-alive
        Vary: Accept-Encoding
        ETag: "5a2deef5-4db"
        Accept-Ranges: bytes

16:35:20.099670 IP (tos 0x0, ttl 64, id 64633, offset 0, flags [DF], proto TCP (6), length 52)
    192.168.1.107.44684 > 116.62.25.128.http: Flags [.], cksum 0x7464 (correct), ack 263, win 237, options [nop,nop,TS val 6028164 ecr 3844473828], length 0
16:35:20.099680 IP (tos 0x20, ttl 52, id 47032, offset 0, flags [DF], proto TCP (6), length 1295)
    116.62.25.128.http > 192.168.1.107.44684: Flags [P.], cksum 0xa0fc (correct), seq 263:1506, ack 54, win 227, options [nop,nop,TS val 3844473828 ecr 6028162], length 1243: HTTP
16:35:20.099686 IP (tos 0x0, ttl 64, id 64634, offset 0, flags [DF], proto TCP (6), length 52)
    192.168.1.107.44684 > 116.62.25.128.http: Flags [.], cksum 0x6f76 (correct), ack 1506, win 256, options [nop,nop,TS val 6028164 ecr 3844473828], length 0

这边的报文一开始和案例一完全一致,但是在我使用curl_close()显式关闭curl后,并没有发送任何关闭tcp连接的报文。查了一下资料,在php7.0中,如果$context任何有全局引用,即使使用curl_close()显式关闭,也不会关闭连接。

案例3

完整的使用curl_init和curl_close,显式关闭连接,并且多次执行exec

16:38:26.590098 IP (tos 0x0, ttl 64, id 18826, offset 0, flags [DF], proto TCP (6), length 60)
    192.168.1.107.44714 > 116.62.25.128.http: Flags [S], cksum 0x520f (correct), seq 3672832041, win 29200, options [mss 1460,sackOK,TS val 6074787 ecr 0,nop,wscale 7], length 0
16:38:26.604823 IP (tos 0x20, ttl 52, id 0, offset 0, flags [DF], proto TCP (6), length 60)
    116.62.25.128.http > 192.168.1.107.44714: Flags [S.], cksum 0xf795 (correct), seq 3884635295, ack 3672832042, win 28960, options [mss 1460,sackOK,TS val 3844520454 ecr 6074787,nop,wscale 7], length 0
16:38:26.604870 IP (tos 0x0, ttl 64, id 18827, offset 0, flags [DF], proto TCP (6), length 52)
    192.168.1.107.44714 > 116.62.25.128.http: Flags [.], cksum 0x969a (correct), ack 1, win 229, options [nop,nop,TS val 6074790 ecr 3844520454], length 0
16:38:26.604904 IP (tos 0x0, ttl 64, id 18828, offset 0, flags [DF], proto TCP (6), length 105)
    192.168.1.107.44714 > 116.62.25.128.http: Flags [P.], cksum 0x2941 (correct), seq 1:54, ack 1, win 229, options [nop,nop,TS val 6074790 ecr 3844520454], length 53: HTTP, length: 53
        GET / HTTP/1.1
        Host: www.izuqun.com
        Accept: */*

16:38:26.616651 IP (tos 0x20, ttl 52, id 28329, offset 0, flags [DF], proto TCP (6), length 52)
    116.62.25.128.http > 192.168.1.107.44714: Flags [.], cksum 0x9664 (correct), ack 54, win 227, options [nop,nop,TS val 3844520457 ecr 6074790], length 0
16:38:26.616674 IP (tos 0x20, ttl 52, id 28330, offset 0, flags [DF], proto TCP (6), length 314)
    116.62.25.128.http > 192.168.1.107.44714: Flags [P.], cksum 0xf829 (correct), seq 1:263, ack 54, win 227, options [nop,nop,TS val 3844520457 ecr 6074790], length 262: HTTP, length: 262
        HTTP/1.1 200 OK
        Server: nginx/1.12.2
        Date: Mon, 11 Dec 2017 08:38:26 GMT
        Content-Type: text/html
        Content-Length: 1243
        Last-Modified: Mon, 11 Dec 2017 02:35:33 GMT
        Connection: keep-alive
        Vary: Accept-Encoding
        ETag: "5a2deef5-4db"
        Accept-Ranges: bytes

16:38:26.616687 IP (tos 0x0, ttl 64, id 18829, offset 0, flags [DF], proto TCP (6), length 52)
    192.168.1.107.44714 > 116.62.25.128.http: Flags [.], cksum 0x9551 (correct), ack 263, win 237, options [nop,nop,TS val 6074793 ecr 3844520457], length 0
16:38:26.616701 IP (tos 0x20, ttl 52, id 28331, offset 0, flags [DF], proto TCP (6), length 1295)
    116.62.25.128.http > 192.168.1.107.44714: Flags [P.], cksum 0xc1ea (correct), seq 263:1506, ack 54, win 227, options [nop,nop,TS val 3844520457 ecr 6074790], length 1243: HTTP
16:38:26.616708 IP (tos 0x0, ttl 64, id 18830, offset 0, flags [DF], proto TCP (6), length 52)
    192.168.1.107.44714 > 116.62.25.128.http: Flags [.], cksum 0x9063 (correct), ack 1506, win 256, options [nop,nop,TS val 6074793 ecr 3844520457], length 0
16:38:28.241841 IP (tos 0x0, ttl 64, id 18831, offset 0, flags [DF], proto TCP (6), length 105)
    192.168.1.107.44714 > 116.62.25.128.http: Flags [P.], cksum 0x2174 (correct), seq 54:107, ack 1506, win 256, options [nop,nop,TS val 6075199 ecr 3844520457], length 53: HTTP, length: 53
        GET / HTTP/1.1
        Host: www.izuqun.com
        Accept: */*

16:38:28.253636 IP (tos 0x20, ttl 52, id 28332, offset 0, flags [DF], proto TCP (6), length 314)
    116.62.25.128.http > 192.168.1.107.44714: Flags [P.], cksum 0xeede (correct), seq 1506:1768, ack 107, win 227, options [nop,nop,TS val 3844520867 ecr 6075199], length 262: HTTP, length: 262
        HTTP/1.1 200 OK
        Server: nginx/1.12.2
        Date: Mon, 11 Dec 2017 08:38:28 GMT
        Content-Type: text/html
        Content-Length: 1243
        Last-Modified: Mon, 11 Dec 2017 02:35:33 GMT
        Connection: keep-alive
        Vary: Accept-Encoding
        ETag: "5a2deef5-4db"
        Accept-Ranges: bytes

16:38:28.253689 IP (tos 0x0, ttl 64, id 18832, offset 0, flags [DF], proto TCP (6), length 52)
    192.168.1.107.44714 > 116.62.25.128.http: Flags [.], cksum 0x8be1 (correct), ack 1768, win 276, options [nop,nop,TS val 6075202 ecr 3844520867], length 0
16:38:28.253704 IP (tos 0x20, ttl 52, id 28333, offset 0, flags [DF], proto TCP (6), length 1295)
    116.62.25.128.http > 192.168.1.107.44714: Flags [P.], cksum 0xb8a1 (correct), seq 1768:3011, ack 107, win 227, options [nop,nop,TS val 3844520867 ecr 6075199], length 1243: HTTP
16:38:28.253713 IP (tos 0x0, ttl 64, id 18833, offset 0, flags [DF], proto TCP (6), length 52)
    192.168.1.107.44714 > 116.62.25.128.http: Flags [.], cksum 0x86f3 (correct), ack 3011, win 295, options [nop,nop,TS val 6075202 ecr 3844520867], length 0

多次curl_exec()会复用之前的连接,但是curl_close()依然是不能关闭连接的。但当我使用unset($context)时,观察到了以下报文:

    192.168.1.107.49938 > 116.62.25.128.http: Flags [F.], cksum 0x8407 (correct), seq 54, ack 1506, win 256, options [nop,nop,TS val 274723 ecr 3860448314], length 0                                                                                                      
10:20:58.408173 IP (tos 0x20, ttl 52, id 25537, offset 0, flags [DF], proto TCP (6), length 52)                                      
    116.62.25.128.http > 192.168.1.107.49938: Flags [F.], cksum 0x5ca5 (correct), seq 1506, ack 55, win 227, options [nop,nop,TS val 3860458424 ecr 274723], length 0                                                                                                      
10:20:58.408218 IP (tos 0x0, ttl 64, id 34603, offset 0, flags [DF], proto TCP (6), length 52)                                       
    192.168.1.107.49938 > 116.62.25.128.http: Flags [.], cksum 0x5c85 (correct), ack 1507, win 256, options [nop,nop,TS val 274726 ecr 3860458424], length 0 

我的机器主动关闭连接发出Fin,服务器ack并发送Fin,我的机器也ack。两边顺利的完成了连接的关闭。 所以当前可以得出以下几点: 1.$context = curl_init(), $context是可以复用的,复用$context后,多次执行curl_exec()可以避免tcp的3次握手和4次断开的过程。 2.curl_close()在上面的试验中,并不能正常的关闭连接,这是因为在psysh的执行环境中,$context一直是在当前的作用域,会一直保持着变量的引用。而php7.0中,$context如果保持引用,curl_close则不会关闭连接,而unset($context)则会关闭。 3.服务器主动关闭连接后发出Fin,我的机器虽然响应了ack,但是没有主动发送Fin,这会不会导致服务器大量的fin_wait2? 第三点是很重要的,如果不解决会大量占用服务器资源。 所以再做一个实验,实验过程如下:

  • 我的机器初始化大量的curl_init(),然后不释放,等待服务器关闭。使用netstat查看服务器是否会出现大量的fin_wait2。

使用netstat -an|awk '/tcp/ {print $6}'|sort|uniq -c可以快速查看各种tcp连接状态的统计。 初始情况为:

20 CLOSE_WAIT
63 ESTABLISHED                                                                              
10 LISTEN

psysh中执行以下脚本

$contextArr = array();
for($i = 0; $i < 1000; $i++){
    $contextArr[$i] = curl_init();
    curl_setopt($contextArr[$i],CURLOPT_URL,"http://www.izuqun.com");
    curl_exec($contextArr[$i]);
}

脚本执行完后,服务器状态变化如下:

20 CLOSE_WAIT
1058 ESTABLISHED
5 FIN_WAIT2
10 LISTEN
2 TIME_WAIT
20 CLOSE_WAIT
58 ESTABLISHED
1001 FIN_WAIT2
10 LISTEN
20 CLOSE_WAIT
63 ESTABLISHED
10 LISTEN

可以看到,中间有1000个FIN_WAIT2状态,说明我们的猜想是正确的。

分类:编程相关

Swoole Server架构分析

一.简介

首页这里引用一下swoole的官方介绍:

swoole:面向生产环境的 PHP 异步网络通信引擎 使 PHP 开发人员可以编写高性能的异步并发 TCP、UDP、Unix Socket、HTTP,WebSocket 服务。Swoole 可以广泛应用于互联网、移动通信、企业软件、云计算、网络游戏、物联网(IOT)、车联网、智能家居等领域。 使用 PHP + Swoole 作为网络通信框架,可以使企业 IT 研发团队的效率大大提升,更加专注于开发创新产品。

通过上述的介绍,我们是可以得出几点信息的

  • 1.swoole可以投入生产环境
  • 2.使用php编写
  • 3.异步网络通信引擎,支持大量的网络协议,并且具有很高的网络性能

swoole server与传统的php运行模式是完全不同的,它是常驻内存的,省去了大量的php脚本的初始化。

二.swoole server的是怎么运行的

swoole进程/线程模型 这是一张官方的swoole运行时进程/线程模型。

1.Master进程

Master进程是一个多线程模型,其中包括Master线程,Reactor线程组,心跳检测线程,UDP收包线程。 以http server为例,Master线程负责监听(listen)端口,然后接受(accept)新的连接,然后将这个连接分配给一个Reactor线程,由这个Reactor线程监听此连接,一旦此连接可读时,读取数据,解析协议,然后将请求投递到worker进程中去执行。 Master进程是使用select/poll进行IO事件循环的,这是因为Master进程中的文件描述符只有几个(listenfd等),Reactor线程使用的是epoll,因为Reactor线程中会监听大量连接的可读事件,使用epoll可以支持大量的文件描述符。

2.Manager进程

Manager进程是专门用来管理Worker进程组和Task进程组的。它会Fork出指定数量的Worker进程和Task进程,并且有以下职能:

  • 子进程结束运行时,manager进程负责回收此子进程,避免成为僵尸进程。并创建新的子进程
  • 服务器关闭时,manager进程将发送信号给所有子进程,通知子进程关闭服务
  • 服务器reload时,manager进程会逐个关闭/重启子进程

3.Worker进程和Task进程

Worker进程接收Reactor线程投递过来的数据,执行php代码,然后生成数据交给Reactor线程,由Reactor线程通过tcp将数据返回给客户端。(如果是UDP,Worker进程直接将数据发送给客户端)。 Worker进程中执行的php代码和我们平时写php是一样的,它等同于php-fpm。但是众所周知,php-fpm下,php在处理异步操作时是很无力的,swoole提供的Task进程可以很好的解决这个问题。Worker进程可以将一些异步任务投递给Task进程,然后直接返回,处理其他的由Reactor线程投递过来的事件。 Task进程以完全同步阻塞的方式运行,一个Task进程在执行任务期间,是不接受从Worker进程投递的任务的,当Task进程执行完任务后,会异步地通知worker进程告诉它此任务已经完成。 所以介绍完上述的一些概念后,再引用一张官方的swoole执行流程图。 swoole运行流程图 这里需要注意,在文档上说的是:Workder进程组和Task进程组是由Manager进程Fork出来的,但是流程图上画的是在启动服务器时Fork出主进程和Worker进程组以及Tasker进程组。

三、使用swoole和传统php开发的优缺点

在说这个话题之前,需要先了解一下CGI,FASTCGI。 1.CGI CGI的全称是Common Gateway Interface,通用网关接口,它使得任何一个拥有标准输入输出的程序拥有提供web server的能力。假设我们写了一个Hello World的c++程序,这个程序接受输入{text},输出{text},Hello World。 以nginx作为接受http请求为例,nginx接受一个http请求,Fork出一个进程,将http请求带来的text参数作为输入,执行完hello world程序,将输出{text},Hello World作为输出,销毁这个Fork出来的进程,由nginx返回给客户端。 这种方式虽然简单,但是要不断的Fork进程,销毁进程。 2.FASTCGI FASTCGI,顾名思义,它是CGI的改进版,是一个常驻型的CGI服务。我们常用的php-fpm就是这种模式运行的,php-fpm负责Forl多个进程,每个进程中都运行了php的解释器。可以在终端下看一下php-fpm的进程: php-fpm进程 一个php-fpm主进程,pid是1263,Fork出了3个子进程。在nginx+php-fpm的组合中,nginx负责接受http请求,将请求封装好交给php-fpm,php-fpm将请求按照一定的规则交给一个子进程去执行,这个子进程中的php解释器加载php代码运行。也是因为这个原因,传统的php只能作为web server。 然后我们发现,nginx+php-fpm的组合和我们Reactor+Worker子进程的运行方式非常相似。 3.swoole的运行方式 这里以swoole作为http server为例(传统php几乎都是作为web服务)。 首先swoole是实现了http server的,也就是说不需要nginx作为http服务器了,当然swoole并不是为了取代nginx,实际上swoole当前实现的http server功能有限,比如说只支持Get和Post,所有往往swoole前面还要运行一个nginx来作为前端代理服务器。 其次,swoole是内存常驻的。和php-fpm的常驻服务不同,php-fpm中常驻的是php的解释器,这个解释器会重复加载php代码,初始化环境,而swoole只在启动的时候加载,这样一来,性能就自然而然的提高了。这一点可以在开发中很明显的体现出来,php-fpm下,修改的php代码会即时生效,而使用swoole则需要重启swoole的server才能使代码生效。 通过上面的一些说明,就可以很明显的得出swoole和传统php开发的优缺点了。 swoole server优点: - swoole性能更高 - 可以做为tcp,udp服务器 - 在高io高并发的服务器要求下,swoole的运行模式是完全可以胜任的 swoole server缺点: - 更难上手。这要求开发人员对于多进程的运行模式有更清晰的认识 - 更容易内存泄露。在处理全局变量,静态变量的时候一定要小心,这种不会被GC清理的变量会存在整个生命周期中,如果没有正确的处理,很容易消耗完所有的内存。而以往的php-fpm下,php代码执行完内存就会被完全释放。 - 无法做密集计算。当然这一点是php甚至是所有动态语言都存在的问题。写在这里是因为防止误导读者以为使用swoole后,php可以用来做密集计算。

分类:linux, php

png格式分析与压缩原理

1.简介

 png图片格式采用了一种很灵活的编码设计,支持多种编码方式来展示一张图片:灰度图片、索引彩色图像、真彩色图像、带α通道数据的灰度图像、带α通道数据的真彩色图像。因为png的编码方式灵活,使得其压缩的发挥空间非常大。

2.几种编码方式的说明

注意:这里的一个通道并不等同于1个字节或2个字节,因为png IDAT块的编码单位是bit而不是byte,具体一个通道占用的位数是靠bit depth来决定的

a.灰度图片

灰度图片一般是用来生成我们常见的黑白照片,bit depth可选值为1、 2、 4、 8、16,其一个像素点用一个通道来表示(0255)或(065535),因此这种图片的大小往往非常小

b.索引彩色图像

索引彩色图像很有意思,它可以和真彩色图像一样拥有表达彩色图片的能力,但是一张索引彩色图像上最多只有256种颜色,每种颜色用三个字节(RGB,0255)表示。它的bit depth可选值为1、 2、4、8,它有一个调色板区域,用来记录索引颜色的值,然后像素点数据区域用一个通道(0255)来表示调色板区域记录的颜色索引。所以对于色彩不多的图片来说,采用索引彩色来编码是很适合的。

c.真彩色图像

真彩色图像最好理解,它的bit depth为8或16,它的每个像素点都用3个字节(3个通道)来表示,分别为R(0255),G(0255),B(0255),可以表达256_256_256=16777216种颜色,或者使用6个字节(3个通道)来表示,分别为R(065535),G(065535),B(065535),可以表达65535_65535_65535种颜色。

d.带α通道数据的灰度图像

就是在灰度图片上增加了α通道,共2个通道,支持透明(0255)或者(065535),但是它的bit depth为8或16,因此这种编码方式一个像素点是2个字节或4个字节

e.带α通道数据的真彩色图像

就是在真彩色图像上增加了α通道,同四个通道,支持透明(0255)或者(065535),它的bit depth为8或16,因此这种编码方式一个像素点是4个字节或8个字节

3.png图片具体编码说明

png图片的编码一般如下:header,chunk,chunk,chunk….chunk。 header代表png图片的头,png文件头一般都是由固定的8个字节组成 89 50 4E 47 OD 0A 1A 0A 图片软件可以通过这8个字节来判断这个文件是不是png格式。 chunk代表png图片的数据块,数据块是有不同的类型的,记录了不同的信息。一张png图片可能包含多个数据块。 数据块的类型如下(关键部分高亮显示): PNG文件格式中的数据块(表1.1)

数据块符号 数据块名称 多数据块 可选否 位置限制
IHDR 文件头数据块 第一块
cHRM 基色和白色点数据块 在PLTE和IDAT之前
gAMA 图像γ数据块 在PLTE和IDAT之前
sBIT 样本有效位数据块 在PLTE和IDAT之前
PLTE 调色板数据块 在IDAT之前
bKGD 背景颜色数据块 在PLTE之后IDAT之前
hIST 图像直方图数据块 在PLTE之后IDAT之前
tRNS 图像透明数据块 在PLTE之后IDAT之前
oFFs (专用公共数据块) 在IDAT之前
pHYs 物理像素尺寸数据块 在IDAT之前
sCAL (专用公共数据块) 在IDAT之前
IDAT 图像数据块 与其他IDAT连续
tIME 图像最后修改时间数据块 无限制
tEXt 文本信息数据块 无限制
zTXt 压缩文本数据块 无限制
fRAc (专用公共数据块) 无限制
gIFg (专用公共数据块) 无限制
gIFt (专用公共数据块) 无限制
gIFx (专用公共数据块) 无限制
IEND 图像结束数据 最后一个数据块

png 文件中,每个数据块由4个部分组成 length | type(name) | data | CRC, 说明如下 length: 4 bytes, data的长度,不包括type和CRC type: 4 bytes, ASCII码([A-Z,a-z]) CRC: 4bytes CRC(cyclic redundancy check)域中的值是对Chunk Type Code域和Chunk Data域中的数据进行计算得到的。CRC具体算法定义在ISO 3309和ITU-T V.42中,其值按下面的CRC码生成多项式进行计算: x32+x26+x23+x22+x16+x12+x11+x10+x8+x7+x5+x4+x2+x+1 除了高亮的关键数据块,还有下面比较有意思的数据块 tRNS

tRNS contains transparency information. For indexed images, it stores alpha channel values for one or more palette entries. For truecolor and grayscale images, it stores a single pixel value that is to be regarded as fully transparent.

tRNS包含透明度信息, 1.在索引图片中,它可以保存一或多个调色板像素对的alpha通道值。用来指明哪些像素需要透明,透明度是多少。然后剩下的像素透明度都被默认成255,完全不透明。 2.在灰度图片中,包含单个灰度级别值,格式如下: Gray: 2 bytes, range 0 .. (2^bitdepth)-1 被指定的灰度值都会被当成是透明的,其他灰度值则完全不透明(如果bit depth小于16,则取最低有效位,其他位为0) 3.在真彩色图片中,包含单个RGB颜色值,格式如下: Red: 2 bytes, range 0 .. (2^bitdepth)-1 Green: 2 bytes, range 0 .. (2^bitdepth)-1 Blue: 2 bytes, range 0 .. (2^bitdepth)-1 被指定的颜色值都会被当成是透明的,其他颜色值则完全不透明(如果bit depth小于16,则取最低有效位,其他位为0) 在带alpha通道的图片中,tRNS是被禁止使用的。

a.IHDR数据块

IHDR数据块存储了png图像的基本信息,一个图像中只能有一个IHDR数据块,并且也是png图像的第一个数据块。共有13个字节。记录的信息如下: 表1.2

域的名称 字节数 说明
Width 4 bytes 图像宽度,以像素为单位
Height 4 bytes 图像高度,以像素为单位
Bit depth 1 byte 图像深度.索引彩色图像: 1,2,4或8 , 灰度图像: 1,2,4,8或16 真彩色图像: 8或16
ColorType 1 byte 颜色类型. [0]:灰度图像, 1,2,4,8或16 [2]:真彩色图像,8或16 [3]:索引彩色图像,1,2,4或8 [4]:带α通道数据的灰度图像,8或16 [6]:带α通道数据的真彩色图像,8或16
Compression method 1 byte 压缩方法(LZ77派生算法)
Filter method 1 byte 滤波器方法
Interlace method 1 byte 隔行扫描方法. 0:非隔行扫描 1: Adam7(由Adam M. Costello开发的7遍隔行扫描方法)

从这个表中可以得出,一张png图片最大的宽高(4294967300 × 4294967300) 这里的Bit depth一开始很难理解,引用维基百科两段话:

Pixels in PNG images are numbers that may be either indices of sample data in the palette or the sample data itself. The palette is a separate table contained in the PLTE chunk. Sample data for a single pixel consists of a tuple of between one and four numbers. Whether the pixel data represents palette indices or explicit sample values, the numbers are referred to as channels and every number in the image is encoded with an identical format. The permitted formats encode each number as an unsigned integral value using a fixed number of bits, referred to in the PNG specification as the bit depth. Notice that this is not the same as color depth, which is commonly used to refer to the total number of bits in each pixel, not each channel. The permitted bit depths are summarized in the table along with the total number of bits used for each pixel. The number of channels depends on whether the image is grayscale or color and whether it has an alpha channel. PNG allows the following combinations of channels, called the color type.

大意是:png图片的像素(Pixels)是调色板中样本数据的索引或者样本数据其本身,调色板是在PLTE数据块中的。单个像素的样本数据包含1~4个数字的元组。像素数据表示调色板索引或者明确的样本值,每个数字代表每个通道,每个数字都有唯一可识别的编码。 允许编码每个数字的格式是一个使用固定位数的unsigned整数值,在PNG中称为bit depth(位深)。位深和color depth(颜色深度)不同,颜色深度通常代表一个像素的总位数,不是每个通道的总位数。 通道数取决于这个图片是否是灰度图还是有alpha通道的色彩图 因此可以知道bit depth是一个通道的位数,bit depth在索引彩色图片和灰度图中使用,使得图片的一个像素点的大小可以小于一个字节

b.PLTE数据块(调色板数据块)

  • a.PLTE数据块在索引彩色图像中必须存在,这里记录了整张图片所有的颜色,最多为256个。这个是bit depth规定的,由表1.2可知,索引彩色图像的bit depth为1,2,4,8,共为1、4、16、256种颜色。每种颜色是3个字节(RGB),所以PLTE数据块的length肯定是3的倍数,否则就是非法的。

  • b.PLTE数据块在真彩色图像或带α通道数据的真彩色图像中是可选的

  • c.PLTE数据块在灰度图像或带α通道数据的灰度图像中是不能存在的

c.IDAT数据块

这部分的数据块存放的就是图像的一个个像素(使用压缩算法之后生成的像素),一张图像中可以存在多个IDAT数据块,这种编码方式虽然稍微增加了图像的大小,但是可以使得PNG图像以一种流的方式生成。例如在浏览器中打开一张非常大的PNG图像,如果网络很慢,我们可以看到图片是从上到下一点点打开的,这是因为即使整张图片没有加载完,仍然可以显示局部内容。 IDAT数据块是最重要的一部分,这里的数据会被隔行扫描方法(Interlace method)滤波器(filtering)压缩算法(compression)处理。这三个部分会在下面详细介绍。 并且要注意的是,IDAT数据块存储的数据并不是以字节为最小单位,在灰度图片和索引彩色图片中,一个字节可能会包含多个像素点,由bit depth指定。

d.IENT数据块

这段数据块标记PNG文件或者数据流已经结束,并且必须要放在文件的尾部。 正常情况下, png 文件的结尾为如下12个字符: 00 00 00 00 49 45 4E 44 AE 42 60 82 由于数据块结构的定义,IEND数据块的长度总是0(00 00 00 00,除非人为加入信息),数据标识总是IEND(49 45 4E 44),因此,CRC码也总是AE 42 60 82

4.隔行扫描方法

隔行扫描方法是为了图片被更先进的展示出来。在图片传输过程中,可以让图片的展示有淡入的效果。虽然平均下来稍微增加了存储的大小,但是给带来用户更快的显示效果。

  • a.这个方法取值为0时,代表像素点是从左到右顺序存储,扫描线扫描时从上到下即可。

  • b.这个方法取值为1时,被称为Adam7算法 Adam7分为7个扫描步骤,可见下图:

    5.过滤器

    过滤器中只有一种过滤方法,但是有多种过滤类型。过滤方法并不会影响数据的大小,也不会影响丢失任何信息,过滤的目的只有一个,为压缩方法提供更好压缩的数据,IDAT数据中的每一行第一个字节定义了过滤类型,过滤类型的介绍如下:

    a.过滤类型0:None

    也就是不做任何过滤

    b. 过滤类型1:Sub

    记录当前像素和左边像素的差值。左边起第一个像素是标准值,不做任何过滤

    c. 过滤类型2:Up

    记录X - B的值,即当前像素和上边像素点差值。如果当前行是第1行,则当前行数标准值,不做任何过滤。

    d.过滤类型3:Average

    记录当前像素与左边像素和上边像素的平均值的差值。

    • 如果当前行数第一行:做特殊的Sub过滤,左边起第一个像素是标准值,不做任何过滤。其他像素记录该像素与左边像素的二分之一的值的差值。
  • 如果当前行数不是第一行:左边起第一个像素记录该像素与上边像素的二分之一的值的差值,其他像素做正常的Average过滤。

    e.过滤类型4:Paeth

    记录X - Pr的值,这种过滤方式比较复杂,Pr的计算方式(伪代码)如下:

p = a + b - c
pa = abs(p - a)
pb = abs(p - b)
pc = abs(p - c)
if pa <= pb and pa <= pc then Pr = a
else if pb <= pc then Pr = b
else Pr = c
return Pr

如果当前行数第一行:做Sub过滤。 如果当前行数不是第一行:左边起第一个像素记录该像素与上边像素的差值,其他像素做正常的Peath过滤。

6.压缩算法

压缩算法当前只定义了一种,值为0,是使用一个滑动窗口的deflate/inflate压缩,这个算法可以调用zlib库来实现

7.关于压缩

对于一张图片,我们可以使用以上知识来完成一次无损压缩,以及去除所有的辅助数据块。但是很多场景下,常规的无损压缩并不能带来很高的压缩比,这个时候可以考虑使用有损压缩,大概的思路就是将总体颜色数减少到256以下(使用相近的颜色来代替),然后使用索引色彩来编码整张图片,带来很高的压缩比

实际操作验证

一级压缩图片(958.8k):/uploads/wp/2017/11/output_1.png 九级压缩图片(857.0k):/uploads/wp/2017/11/output_9.png 有损压缩图片(273.0k):/uploads/wp/2017/11/test_tiny.png 原图(1.5m):/uploads/wp/2017/11/test.png) 使用vim打开原图: 8950 4e47 0d0a 1a0a是png固定的头, 0000 000d是iHDR数据块的长度,为13,4948 4452是数据块的type,为IHDR,之后紧跟着是data, 0000 02bc是图片的宽度,0000 03a5是高度,08是Bit depth,也就是一个通道是8位,06是color type,这里表示图片是真彩色,00是压缩方法,png中目前只有一种,也就是LZ77派生的算法,00是滤波器方法,表示不使用,00是隔行扫描方法,代表不扫描。8f 1434 a4是四个字节的CRC校验码。 00 0000 01是sRGB数据块的长度(???),为1,73 5247 42是type,为sRGB,00是存储的一个字节数据,aece 1ce9是循环校验码 之后还有一个iDoT数据块,再紧接着才是IDAT数据块,下面就不分析了。 再打开9级压缩的图片 简单看一下,sRGB和iDOT数据块已经不存在了,IDAT数据块的长度发生了改变,其实就是被压缩了。这种压缩是无损的,9级压缩和1级压缩相差十几k的大小,但是压缩的越小,耗时也越长。 最后去看在tinypng上进行有损压缩的图片: 它多了一个PLTE字段,意味着这张图变成了索引彩色图片,索引彩色图片最关键的一点就是总颜色数不能超过256。如果这张图片的总颜色数没有256个,那么甚至可以说这次图片的压缩是无损的。但是一旦颜色数超过256,就需要将多个相近的颜色处理成一个颜色,也就是有损的压缩

参考

分类:工作, 图像相关

leveldb源代码阅读(四)- table cache的实现

一、前言

缓存在整个计算机体系中,占据着举足轻重的地位,往往被用于提升软件的运行速度。在计算机系统中,最典型的当属CPU高速缓存了,CPU高速缓存是介于CPU寄存器和内存之间,CPU向内存中请求数据时,会先检查CPU高速缓存中是否存在数据,如果不存在,则会将内存中的数据放入高速缓存中,再将高速缓存中的数据读入CPU。这个过程中,缓存之所以能够大大的提升系统速度,是因为程序在运行的时候对内存的访问具有局部性的特点,这种局部性我理解为程序在运行时对某一块的内存请求会非常频繁,而这一块内存在第一次请求之后就会被缓存,所以会大大提升之后的数据读取速度。所以,缓存设计的是否合理有效,在于缓存的命中率高不高。 在leveldb中,为了提升对数据的检索速度,也设计了缓存,对应的代码在db/table_cache.h和db/table_cache.cc中,这个table cache的实现主要借助于Cache类,关于Cache类,是可以用户自定义实现的,但leveldb也有一个内置的Cache的实现,文件是util/cache.cc。主要是LRU(最近最少使用)算法,原理是“如果一个数据最近被使用,那么将来被使用的概率同样也很大”。同样也实现了一个HashTable,leveldb中提供的数据显示在g++ 4.4.3下比built-in的哈希表性能稍高,大概5%左右。

二、概览

2.1 hash table数据结构

哈希表是一个很常见的结构了,存储的是key-value结构,一个key-value对常被称作entry,它最大的特点是查找快。在网上找了一张hash table的图 hash table 首先它是一个长为len的数组,每个数组中的元素都是一个链表。如图所示,john Smith和Sandra Dee都被hash到152这个地方,所以在152这个地方使用链表来存储这两个entry.查找的时候Sandra Dee的时候,先找到152这个地方,在遍历链表,直到找到key是Sandra的entry。

2.2 LRU算法

在leveldb中,LRU算法的实现是使用两个双向环形链表,一个链表(in-use)存储当前正在使用的数据,另一个链表(lru)按照访问时间先后顺序存储缓存数据,每个数据都可以在in-use和lru之间切换。当我们需要使用LRU算法来淘汰数据时,只需要在lru上淘汰排序靠后的数据即可。

2.3 分片LRU缓存

分片LRU缓存很简单,其实就是同时创建多个LRU缓存对象,然后使用hash将特定的缓存数据放置到相应的LRU缓存对象中。这个方式可以避免一个LRU缓存中存储过多的数据。

三、详细分析

3.1 Hash Table

leveldb中实现了HashTable,使用的是最经典的数组+链表的实现。通过hash值定位到数组中的某一处,然后在这一处的链表上遍历查找。 HashTable的长度是哈希算法效率的最大影响因素,如果存在较多的hash冲突,则在链表上遍历查找的时间花费会很长。所以这个长度的选择是很重要的,比如在Java中的HashMap,实现中有一个负载因子0.7,如果数组上已经有值的数量超过总长度的0.7就会对整个哈希表resize。在leveldb中,这个resize的阈值是当前所有Insert进来的元素个数超过了数组的长度length,就会进行resize。这里简单的分析一下最重要的查找和resize过程。

  • 哈希表查找过程
  // Return a pointer to slot that points to a cache entry that
  // matches key/hash.  If there is no such cache entry, return a
  // pointer to the trailing slot in the corresponding linked list.
  LRUHandle** FindPointer(const Slice& key, uint32_t hash) {
    LRUHandle** ptr = &list_[hash & (length_ - 1)];     //这里hash & (length_ - 1)会定位到小于length的位置,ptr就是hash到的位置
    while (*ptr != NULL &&
           ((*ptr)->hash != hash || key != (*ptr)->key())) {
           //hash到特定位置后,如果当前位置的hash和当前hash不一样,或者key不一样,并且指针也不为空,则继续向下找,直到找到
      ptr = &(*ptr)->next_hash;
    }
    return ptr;
  }
  • 哈希表resize的过程
   void Resize() {
    uint32_t new_length = 4;        //哈希表的长度从4开始,逐倍增长
    while (new_length < elems_) {
      new_length *= 2;
    }
    LRUHandle** new_list = new LRUHandle*[new_length];
    memset(new_list, 0, sizeof(new_list[0]) * new_length);      //申请新的哈希表的所需的空间
    uint32_t count = 0;
    for (uint32_t i = 0; i < length_; i++) {    //将旧的哈希表的数据重新计算复制到新的哈希表中
      LRUHandle* h = list_[i];
      while (h != NULL) {
        LRUHandle* next = h->next_hash;
        uint32_t hash = h->hash;
        LRUHandle** ptr = &new_list[hash & (new_length - 1)];
        h->next_hash = *ptr;
        *ptr = h;
        h = next;
        count++;
      }
    }
    assert(elems_ == count);
    delete[] list_; //删除旧的哈希表
    list_ = new_list;
    length_ = new_length;
  }
};

3.2 LRUCache的实现

这里的LRUCache的私有成员变量包括以下几个

  // Initialized before use.
  size_t capacity_;         //LRUCache的大小。

  // mutex_ protects the following state.
  mutable port::Mutex mutex_;       //互斥变量,用来同步访问
  size_t usage_;                    //LRUCache已经使用的大小

  // Dummy head of LRU list.
  // lru.prev is newest entry, lru.next is oldest entry.
  // Entries have refs==1 and in_cache==true.
  LRUHandle lru_;                   //LRU链表的头,lru.prev代表新的节点,lru.next代表旧的节点,节点的refs == 1,in_cache == true

  // Dummy head of in-use list.
  // Entries are in use by clients, and have refs >= 2 and in_cache==true.
  LRUHandle in_use_;                //正在使用的节点链表的头,refs >= 2,in_cache == true

  HandleTable table_;               //哈希表,用来在缓存中实现快速查找

LRU的构造函数,直接构造出空的环形链表

LRUCache::LRUCache()
    : usage_(0) {
  // Make empty circular linked lists.
  lru_.next = &lru_;
  lru_.prev = &lru_;
  in_use_.next = &in_use_;
  in_use_.prev = &in_use_;
}

LRU中节点的引用和解引用

//增加引用时,如果在缓存中,则移动到in_use中
void LRUCache::Ref(LRUHandle* e) {
  if (e->refs == 1 && e->in_cache) {  // If on lru_ list, move to in_use_ list.
    LRU_Remove(e);
    LRU_Append(&in_use_, e);
  }
  e->refs++;
}

//解引用时会出现两种情况。1.节点不再需要,使用deleter来删除节点 2.不再被使用,移动到缓存
void LRUCache::Unref(LRUHandle* e) {
  assert(e->refs > 0);
  e->refs--;
  if (e->refs == 0) { // Deallocate.
    assert(!e->in_cache);
    (*e->deleter)(e->key(), e->value);
    free(e);
  } else if (e->in_cache && e->refs == 1) {  // No longer in use; move to lru_ list.
    LRU_Remove(e);
    LRU_Append(&lru_, e);
  }
}

缓存的插入

Cache::Handle* LRUCache::Insert(
    const Slice& key, uint32_t hash, void* value, size_t charge,
    void (*deleter)(const Slice& key, void* value)) {
  MutexLock l(&mutex_);

  LRUHandle* e = reinterpret_cast<LRUHandle*>(
      malloc(sizeof(LRUHandle)-1 + key.size()));    //这个地方申请内存需要注意,在LRUHandle中,key_data只有1个字节,其实是整个key的开头一个字节,所以申请的空间实际上是包含整个key的
  e->value = value;
  e->deleter = deleter;
  e->charge = charge;
  e->key_length = key.size();
  e->hash = hash;
  e->in_cache = false;
  e->refs = 1;  // for the returned handle.
  memcpy(e->key_data, key.data(), key.size());

  if (capacity_ > 0) {      //如果capacity大于0,也就是需要进行缓存
    e->refs++;  // for the cache's reference.
    e->in_cache = true;
    LRU_Append(&in_use_, e);
    usage_ += charge;
    FinishErase(table_.Insert(e));
  } // else don't cache.  (Tests use capacity_==0 to turn off caching.)

    //当使用的内存大于容量时,则要移除旧的缓存,直到缓存小于指定的容量
  while (usage_ > capacity_ && lru_.next != &lru_) {
    LRUHandle* old = lru_.next;
    assert(old->refs == 1);
    bool erased = FinishErase(table_.Remove(old->key(), old->hash));
    if (!erased) {  // to avoid unused variable when compiled NDEBUG
      assert(erased);
    }
  }

  return reinterpret_cast<Cache::Handle*>(e);
}

缓存的查找

Cache::Handle* LRUCache::Lookup(const Slice& key, uint32_t hash) {
  MutexLock l(&mutex_);
  LRUHandle* e = table_.Lookup(key, hash);      //直接借用哈希表完成缓存的快速查找
  if (e != NULL) {
    Ref(e);
  }
  return reinterpret_cast<Cache::Handle*>(e);
}

3.3 分片缓存的实现(ShardedLRUCache)

分片缓存的实现其实就是借助上面的LRUCaChe,只不过同时拥有多个LRUCache,然后特定的缓存数据会被缓存到相应的LRUCache中。

static const int kNumShardBits = 4;                     //可以理解为缓存片数量的容量因子(这里是4个bits,所以共有16个缓存片)
static const int kNumShards = 1 << kNumShardBits;       //一共有多少个缓存片

//通过Shard函数可以将任意一个hash分配到16个缓存片中的任意一个)
static uint32_t Shard(uint32_t hash) {
    return hash >> (32 - kNumShardBits);
}

所有的缓存存储和读取都会通过上面的Shard函数来找到特定的缓存片,从而实现了分片缓存。

五、总结

在这个部分,400行左右的代码就实现了哈希表,LRU缓存,分片LRU缓存。了解到LRU缓存的具体实现方式,特别是LRU中Ref和UnRef的实现非常精炼,很好的解决了一个数据在LRU缓存中被引用时脱离缓存,不使用时进入LRU缓存的功能。同时将LRU缓存简单的封装,就可以实现分片LRU缓存。

分类:levelDB源码阅读标签:#leveldb #cache #lru #hash #shardedLRUCache

ubuntu上使用chrome进行手机页面调试的方案

虽然大多数时候我们都可以使用chrome的开发者工具,通过模拟手机来调试手机页面,但是对于一些特殊的动作是无法在电脑上做的,比如说手机的多点触控操作,在页面上模拟双指缩放时没法使用鼠标完成,因此需要通过手机来进行真机调试,但是调试的同时,我们希望可以看到调试信息,希望可以实时修改查看。这个时候就可以借助chrome的远程设备使用手机chrome打开页面,在电脑chrome中调试。具体的调试过程在 远程调试 Android 设备使用入门可以看到。下面只是记录ubuntu下使用该方案遇到的问题。

一.打开远程调试界面

打开chrome的控制台,点击右上角的列表按钮,找到more tool->remote device即可。

二.找不到已连接的手机

这个在windows上一般比较容易,因为基本上各种安全软件都会自动帮助用户连上,在Ubuntu下我们需要使用adb来连接手机。使用adb start-server来开启服务监听手机的连接。如果出现权限错误,可以adb kill-server,再adb start-server。只要手机上弹出连接确认框,即说明已经连上了。

三.Inspect的页面空白

这个问题困扰了我很久,因为我在windows上是没有问题的,后来查了一下,是因为chrome需要翻墙才行,在windows上我使用的是shadowsocks的pac方案,linux上则是自己建立的翻墙规则,导致有遗漏。所以如果出现Inspect页面空白,可以尝试全局翻墙

四.如果在手机上访问开发机器上的服务

这个问题有这种解决方案。 1.如果手机和电脑在同一个局域网内,可以直接访问电脑的ip地址即可。但是http服务监听的地址不能只是localhost,应该是电脑的ip地址或者0.0.0.0 2.使用远程设备的端口转发功能,设置如下图 端口转发设置 成功的界面如下 端口转发设置成功 这样,我在手机上访问localhost:4200,相当于在电脑上访问localhost:4200,在手机上访问localhost:1025,相当于在电脑上访问localhost:80。需要注意的是,端口转发的左侧输入框端口号必须大于1024,这是因为小于等于1024的端口号是被划分出来特殊使用的。

分类:前端

树的可视化以及家谱绘制的算法

一、前言

树的可视化意思就是将一颗树(数据结构的树)用图形展现出来。树的可视化有很多种用途,比如说很常见的组织结构图就是树的可视化的应用。家谱也可以算是一颗树,但是与树的可视化稍微不同的是,会有配偶这个角色,同时一个家谱可能并不是从一个根节点向下(可能存在某个家族向上追溯到某一代,之前的资料已经完全丢失了,那么这个家谱的起源应该是这一代人,而不是具体到某一个人)。

二、难点

在树的可视化过程中,难点就在于如何确定每一个节点的位置(X,Y),Y坐标相对来说是比较好确定的,可以根据它在一颗树中的第几层来确定Y的值;X的值既受到同一层其他的节点位置的影响,同时也受到其子代位置的影响。因为其子代可能会和其兄弟节点的子代交叉。所以这篇文章主要讲解的是每个点的位置的计算。 家谱的绘制和树的可视化也有前言中的一些不同之处,因为也不能完全的将树的可视化算法生搬硬套。 下面我将一步步的讲解整个树的可视化算法的过程,以及如何将这个算法应用到家谱的绘制上,并给出具体的实现代码(因为是网页上有这个需求,所以代码是js写的)。算法的主要提出者是John Q. Walker II,这里有他对这个算法的相关讲解。POSITIONING NODES FOR GENERAL TREES

三、算法介绍

图1: 示意图

1、节点属性定义

var Node = function(key,image,description){
    this.key = key;
    this.parent = null;         //父辈
    this.offspring = null;      //指向最左边的子辈
    this.leftSibling = null;    //左兄弟
    this.rightSibling = null;   //右兄弟
    this.prelim = 0;            //x坐标的预定义
    this.modifier = 0;          //调整的大小
    this.level = 0;
    this.width = 60;            //每个节点的最终宽度,如果存在配偶这个宽度是会发生改变的
    this.height = 80;           
    this.nodeWidth = 60;        //每个节点的基本宽度,不会变
    this.nodeHeight = 80;
    this.x = 0;
    this.y = 0;
    this.spouses = [];
    this.image = image||"assets/post-photo.jpg";
    this.description = description || "";
};

这里首先介绍几个重要的属性: parent,offspring,leftSibling,rightSibling:分别是当前节点的父节点指针、最左边的孩子节点的指针、左兄弟、右兄弟。以上图为例,M点的parent是N,offspring是H,leftSibling是G,rightSibling是null。 prelim:当前点的X的预定义位置。如同在难点中所说,X的位置受到很多因素的影响,所以需要多次计算。prelim只是预定义的位置,不是最终的位置。 modifier:调整值,不过这个调整值并不是说当前点的X还要调整多少,而是当前点的后代的X还要调整的大小。 level:当前点所处的层级。 width、height、nodeWidth、nodeHeight:这些参数用来表示节点的宽和高,width和nodeWidth的区别在于,nodeWidth是画出来的节点的宽度,是一个基本属性,不会改变,width则表示这个点最终会占用的宽度。在树的可视化算法中,只需要nodeWidth和nodeHeight,width和height是专门为家谱的绘制增加的。 x:当前点的X,如何确定X的大小呢?以M为例,M.X = M.prelim + N.modifier + O.modifier。 y:当前点的y,以M为例: M.y = M.level * (每层的间隔 + M.height); spouses:这个是专门为家谱的绘制准备的。表示当前点的配偶,一个点的配偶可以有多个,所以使用数组。

2、算法的大概流程

算法大概可以划分为:

  • 1.倒序遍历整颗树,初次确定每个点的prelim和modifier。
  • 2.从最底层逐级向上检查是否存在交叉,如果存在交叉则调整(这一步和我参考的算法不同,它是从上向下检查,但是我在使用中发现,如果存在子树的子树交叉的情况,那么在高层做了调整之后,这里再做一次调整就可能出现再次重叠的情况,所以改用从底层向上检查)。 (勘误:这个地方不对,应该还是从上向下遍历,这样从上方调整后,即使下方还有重叠,也可以再次检测并调整)
  • 3.最后确定根节点的位置

3、算法详细介绍

这里我们先定义几个常量:

SiblingSeparation = 4,   //兄弟节点之间的间隔
SubtreeSeparation = 6,   //子树之间的间隔
width = nodeWidth = 2   //节点的宽度

还是以图1所示的树为例,这里先做一遍倒序遍历,初步确定每一个节点的位置: A:因为A的左节点是null,所以

A.prelim = 0;
A.modifier = 0;

B:

B.prelim = 0;
B.modifier = 0;

C:因为C有左节点B,所以C要在B的基础上做向右的偏移,偏移量为B的prelim加上B的宽度加上间隔大小(这个地方的处理和John Q. Walker II的算法不同,是为了家谱的显示做的更改)。所以

C.prelim = B.prelim + B.width + SiblingSeparation = 0 + 2 + 4 = 6;
C.modifier = 0;

D:因为D是B、C的父节点,同时是A的右兄弟,所以D的位置由A确定后,为了保证D应该在B和C中间,应该对B、C做调整,但是我们并不会再回头对B、C做处理,而是计算D的modifier,以此来表示D的后代需要调整的位置。并且D.modifer应该等于D.prelim - (B.prelim + C.prelim)/2。

D.prelim = A.prelim + A.width +  SiblingSeparation= 0 + 2 + 4 = 6;
D.modifier = D.prelim - (B.prelim + C.prelim) / 2 = 6 - (0 + 6) / 2 = 3;

E:因为E没有左兄弟,所以直接通过A、D来确定位置即可

E.prelim = (A.prelim + D.prelim) / 2 = (0 + 6) / 2  = 3;
E.modifier = 0;

F:

F.prelim = E.prelim + E.width + SiblingSeparation = 3 + 2 + 4 = 9;
F.modifier = 0;

G:

G.prelim = 0;
G.modifier = 0;

H:

H.prelim = 0;
H.modifier = 0;

I:

I.prelim = H.prelim + H.width + SiblingSeparation = 0 + 2 + 4 = 6;
I.modifier = 0;

J:

J.prelim = I.prelim + I.width + SiblingSeparation = 6 + 2 + 4 = 12;
J.modifier = 0;

K:

K.prelim = J.prelim + J.width + SiblingSeparation = 12 + 2 + 4 = 18;
K.modifier = 0;

L:

L.prelim = K.prelim + k.width + SiblingSeparation = 18 + 2 + 4 = 24;
L.modifier = 0;

M:

M.prelim = G.prelim + G.width + SiblingSeparation = 6;
M.modifer = M.prelim - (H.prelim + L.prelim) / 2 = -6;

N:

N.prelim = F.prelim + F.width + SiblingSeparation = 9 + 2 + 4 = 15;
N.modifier = N.prelim - (G.prelim + M.prelim) / 2 =  12;

走到这里我们就不再向上走了,因为根节点的位置肯定是有E和N来最终确定。所以这个时候应该来调整整颗树,检查是否存在节点位置重叠的情况。检查是否重叠是一个递归,所以使用递归检查会降低很多复杂度。但是这里我们走一遍过程,并非是严格按照代码执行过程。 我们先检查最底层,也就是这颗树的第4层: 检查C和H是否有重叠(当然是最右和最左做对比了): C.X = D.modifier + E.modifier + C.prelim = 3 + 0 + 6 = 9; H.X = M.modifier + N.modifier + H.prelim = -6 + 12 + 0 = 6; 所以H在C的左边3处,显然是重叠了的。所以需要将H所在的子树全部向右移offset = SubtreeSeparation - (H.X-C.X) = 9;我们一直向上找,直到C和H的祖先是兄弟时,也就是E和N,修改N.prelim、N.modifier就代表将N和其子树全体右移。

N.prelim = N.prelim + offset = 15 + 9 = 24;
N.modifier = N.modifier + offset = 12 + 9 = 21;

这时候E和N之间距离变得更大了,但是E和F的距离与F和N的距离是不同的,为了让树显示的好看一点

F.prelim = F.prelim + offset / 2 = 9 + 9 / 2 = 13.5;

F的子树也应该调整一下(虽然这里并没有)

F.modifier = F.modifier + offset / 2 = 0 + 9 / 2 = 4.5;

我们再往上看,发现已经没有重叠的了。 这时候确定根节点O的位置

O.prelim = (E.prelim + N.prelim) / 2 = (3 + 24) / 2 = 13.5;
O.modifier = 0;

四、如何将树的可视化算法应该到家谱的绘制上。

在之前已经介绍过家谱和树的结构有稍许不同,所以我们尽量将家谱做一些处理,使其变成标准的树结构。

  • 1.配偶问题。 将某个节点的配偶不当成一个节点看待,而是这个节点的一部分,所以我们只需在有配偶的时候改变节点的width就可以了。
  • 2.不只一个根节点的问题 既然有不只一个根节点存在,那么我们就自己定义一个虚拟的节点作为根节点,将第一层所有的点的parent都指向这个根节点即可。这样就是一个非常标准的树结构了。

五、源代码

源代码放在了github上,地址为https://github.com/joyme123/candraw

分类:工作标签:#树的可视化 #族谱

leveldb源代码阅读(三)-memtable的实现

一、序言

在之前的文章中提到,leveldb所有的记录都是由一个个log文件逐渐转变来的,与存储在磁盘上的log文件对应的就是内存中的memtable。memtable和log文件存储的内容是一致的。

二、SkipList

memtable中的键值对是通过SkipList这种数据结构存储的,SkipList相对于普通的List来说,普通的List查找时间复杂度为O(n),而SkipList可以达到O(log(n)),同时,SkipList相对与红黑树,在多线程上,需要锁住的数据量更小,性能更优。 SkipList示意图 比如上图就是一个SkipList结构,如果我们需要搜索45这个点,我们首先在最高层(第二层)找到30,然后发现下一个点是57,已经大于45了,于是来到下一层(第一层)从30开始,向后找,就能找到45了,在这个过程中,我们跳过了很多个点。因此这种数据结构得名SkipList。

2.1 SkipList的基本信息

SkipList是memtable中用到的最主要的数据结构。 SkipList的线程安全特点:写操作需要外部的同步,比如信号量这种。读操作需要保证在读的时候SkipList不会被销毁。除此之外,读操作没有任何的内部锁或者同步。 SkipList的基本原则: (1)分配节点在SkipList销毁之前不会被删除。因为在代码中我们没有任何的删除节点的操作。 (2)一个节点的内容,除了next/prev指针,在这个节点被存储到SkipList之后其他数据都是不变的。只有Insert()会修改list的内容,初始化一个节点并使用release-stores去将这个节点存放到一个或多个list中需要谨慎对待。

2.2 SkipList的成员函数

SkipList中,公共的成员函数只有两个 void Insert(const Key& key); bool Contains(const Key& key) const; 顾名思义,Insert用来向SkipList中插入key,Contains用来检查SkipList中是否包含某个key。 私有的成员函数如下:

  Node* NewNode(const Key& key, int height);
  int RandomHeight();
  bool Equal(const Key& a, const Key& b) const { return (compare_(a, b) == 0); }

  // Return true if key is greater than the data stored in "n"
  bool KeyIsAfterNode(const Key& key, Node* n) const;

  // Return the earliest node that comes at or after key.
  // Return NULL if there is no such node.
  //
  // If prev is non-NULL, fills prev[level] with pointer to previous
  // node at "level" for every level in [0..max_height_-1].
  Node* FindGreaterOrEqual(const Key& key, Node** prev) const;

  // Return the latest node with a key < key.
  // Return head_ if there is no such node.
  Node* FindLessThan(const Key& key) const;

  // Return the last node in the list.
  // Return head_ if list is empty.
  Node* FindLast() const;

2.3 SkipList的节点Node实现

// Implementation details follow
template<typename Key, class Comparator>
struct SkipList<Key,Comparator>::Node {
  explicit Node(const Key& k) : key(k) { }

  Key const key;

  // Accessors/mutators for links.  Wrapped in methods so we can
  // add the appropriate barriers as necessary.
  Node* Next(int n) {
    assert(n >= 0);
    // Use an 'acquire load' so that we observe a fully initialized
    // version of the returned Node.
    return reinterpret_cast<Node*>(next_[n].Acquire_Load());
  }
  void SetNext(int n, Node* x) {
    assert(n >= 0);
    // Use a 'release store' so that anybody who reads through this
    // pointer observes a fully initialized version of the inserted node.
    next_[n].Release_Store(x);
  }

  // No-barrier variants that can be safely used in a few locations.
  Node* NoBarrier_Next(int n) {
    assert(n >= 0);
    return reinterpret_cast<Node*>(next_[n].NoBarrier_Load());
  }
  void NoBarrier_SetNext(int n, Node* x) {
    assert(n >= 0);
    next_[n].NoBarrier_Store(x);
  }

 private:
  // Array of length equal to the node height.  next_[0] is lowest level link.
  port::AtomicPointer next_[1];
};

注意到Node实现了两个版本的Next和SetNext,带有NoBarrier_的是多进程不安全的,因为在少数情况下会用到,因此做了额外的实现。另外,可以注意这里只实现了Next()方法,并没有Prev()指向上一个节点,可以知道SkipList并不是一个双向链表,但是SkipList的迭代器是支持Prev()方法的,所以这是一个值得注意的地方。 Node节点的创建是通过NewNode()方法

template<typename Key, class Comparator>
typename SkipList<Key,Comparator>::Node*
SkipList<Key,Comparator>::NewNode(const Key& key, int height) {
  char* mem = arena_->AllocateAligned(
      sizeof(Node) + sizeof(port::AtomicPointer) * (height - 1));
  return new (mem) Node(key);
}

NewNode中使用了arena来分配对齐的内存,分配的内存大小是sizeof(Node)+sizeof(port::AtomicPointer) * (height - 1)。这里可以注意到申请的空间不仅仅是一个Node的大小,还包括sizeof(port::AtomicPointer) * (height - 1),这是因为SkipList是一个多层的结构,所以如果当前Node是3层,那么就需要3个Next指针,在Node的代码中,默认只申请了一个Next指针空间,所以需要额外的多申请(height - 1)个AtomicPointer的空间。

2.4 SkipList的迭代器(Iterator)

SkipList实现了自己的迭代器,迭代器的声明如下:

class Iterator {
   public:
    // Initialize an iterator over the specified list.
    // The returned iterator is not valid.
    explicit Iterator(const SkipList* list);

    // 如果迭代器位于一个有效的节点上,就会返回true.
    bool Valid() const;

    // 返回当前位置的key.
    // REQUIRES: Valid()
    const Key& key() const;

    // 前进到下一个位置
    // REQUIRES: Valid()
    void Next();

    // 后退到上一个位置
    // REQUIRES: Valid()
    void Prev();

    // 移到第一个key >= target的entry
    void Seek(const Key& target);

    // 移到这个list的第一个entry
    // 如果list非空,迭代器的最终状态是Valid()
    void SeekToFirst();

    // 移到这个list的最后一个entry
    // 如果list非空,迭代器的最终状态是Valid()
    void SeekToLast();

   private:
    const SkipList* list_; 
    Node* node_;
    // Intentionally copyable
  };

其中Prev()的实现并不是通过prev指针,因为上文中已经介绍了Node只有next指针。Prev()是通过FindLessThan来实现,找到小于指定Node的最后一个值。这里有一个问题,为什么不使用prev指针,难道不会大大的降低时间复杂度吗?看一下FindLessThan的具体实现。

template<typename Key, class Comparator>
typename SkipList<Key,Comparator>::Node*
SkipList<Key,Comparator>::FindLessThan(const Key& key) const {
  Node* x = head_;
  int level = GetMaxHeight() - 1;
  while (true) {
    assert(x == head_ || compare_(x->key, key) < 0);
    Node* next = x->Next(level);
    if (next == NULL || compare_(next->key, key) >= 0) {
      if (level == 0) {
        return x;
      } else {
        // Switch to next list
        level--;
      }
    } else {
      x = next;
    }
  }
}

其实就是SkipList查找过程的实现。时间复杂度应该是O(log(n)).相比于prev指针的话,在空间占用上是少一点的。具体为什么这样实现还得继续往下看。 SkipList还以同样的方式实现了FindGreaterOrEqualFindLast

template<typename Key, class Comparator>
typename SkipList<Key,Comparator>::Node* SkipList<Key,Comparator>::FindGreaterOrEqual(const Key& key, Node** prev)
    const {
  Node* x = head_;
  int level = GetMaxHeight() - 1;
  while (true) {
    Node* next = x->Next(level);
    if (KeyIsAfterNode(key, next)) {
      // Keep searching in this list
      x = next;
    } else {
      if (prev != NULL) prev[level] = x;
      if (level == 0) {
        return next;
      } else {
        // Switch to next list
        level--;
      }
    }
  }
}

FindGreaterOrEqual的实现还是比较有意思的,在返回比指定key大于或等于的节点的同时,还可以选择性的将该节点的prev指针保存到Node** prev中,返回给用户。其实这也是Iterator中Prev()的实现不采用prev指针的原因,因为有了FindGreaterOrEqual这样的实现,SkipList的内部实现中根本不需要Prev()来将指针向前移动,同时又大大的节约了内存。 下面看一下SkipList的Insert的实现。

void SkipList<Key,Comparator>::Insert(const Key& key) {
  // TODO(opt): We can use a barrier-free variant of FindGreaterOrEqual()
  // here since Insert() is externally synchronized.
  Node* prev[kMaxHeight];
  Node* x = FindGreaterOrEqual(key, prev);

  // Our data structure does not allow duplicate insertion
  assert(x == NULL || !Equal(key, x->key));

  int height = RandomHeight();
  if (height > GetMaxHeight()) {
    for (int i = GetMaxHeight(); i < height; i++) {
      prev[i] = head_;
    }
    //fprintf(stderr, "Change height from %d to %d\n", max_height_, height);

    // It is ok to mutate max_height_ without any synchronization
    // with concurrent readers.  A concurrent reader that observes
    // the new value of max_height_ will see either the old value of
    // new level pointers from head_ (NULL), or a new value set in
    // the loop below.  In the former case the reader will
    // immediately drop to the next level since NULL sorts after all
    // keys.  In the latter case the reader will use the new node.
    max_height_.NoBarrier_Store(reinterpret_cast<void*>(height));
  }

  x = NewNode(key, height);
  for (int i = 0; i < height; i++) {
    // NoBarrier_SetNext() suffices since we will add a barrier when
    // we publish a pointer to "x" in prev[i].
    x->NoBarrier_SetNext(i, prev[i]->NoBarrier_Next(i));
    prev[i]->SetNext(i, x);
  }
}

首先,Insert方法中没有做任何的多线程同步,所以需要调用者在外部进行写入同步(防止多个线程同步写入)。 插入的过程是先找到需要插入的位置,然后调用RandomHeight()来随机得到当前节点的高度,之后向普通链表一样执行插入操作。 注意到这里有一个多线程读写的问题。也就是当我们改变max_height_的值的时候,并没有改变head_指针。这种情况下有两种可能,一是读到了新的max_height_,但是head_指针还没有更改,这时候指针会立刻下降到下一级,SkipList的多级只是为了提高查找速度,所以在这里并没有其他的副作用;二是正常的情况,不作讨论。

2.Memtable

Memtable的实现主要就是依赖于SkipList,分析了SKipList之后,Memtable的插入,查找操作都是SkipList的插入和查找。

  // Increase reference count.
  void Ref() { ++refs_; }

  // Drop reference count.  Delete if no more references exist.
  void Unref() {
    --refs_;
    assert(refs_ >= 0);
    if (refs_ <= 0) {
      delete this;
    }
  }

Memtable的实现使用了类似于计数器引用的机制,不过这是手动实现的,所以需要用户在使用Memtable时调用Ref()来增加引用计数,引用结束后调用Unref来减少引用计数,当引用计数为0时则销毁自己。

总结

Memtable的设计还是很让人佩服的,至少对我来说是这样。了解到了SkipList这样的数据结构,也了解到内存屏障这种多进程情况下代码执行乱序的问题,还有内存对齐的必要、内存对齐的实现。同时也了解了一些C++编写程序的独特风格(我写的C++一直像Java,反而少了一点C++的美)

分类:c++, levelDB源码阅读标签:#leveldb #memtable #skiplist

leveldb源码阅读(二)—— Varint和Arena的实现

一、Varint

Varint是在leveldb中广泛使用的一种变长的整数类型,Varint其实和unicode的实现非常相似,并且是little-endian。如果当前字节的最高位是1,则表示后面的字节也属于这个整数,如果最高位是0,则表示该整数结束了。所以,一个无符号4个字节的整型数,使用Varint可能以1,2,3,4,5个字节来表示。 比如130:

无符号整型表示起来为:00000000 00000000 00000000 10000010
使用Varint表示为:10000010 00000001             #这里注意Varint是little-endian

因为牺牲了每个字节的最高位作为标志位,所以遇到大的数可能需要5个字节。

某个无符号整型:10000001 00000001 00000001 00000001
使用Varint表示:10000001 10000010 10000100 10001000 00001000

但是平均下来,Varint是绝对会节省大量的存储空间的。 那么leveldb中Varint是如何编码和解码的呢?

char* EncodeVarint32(char* dst, uint32_t v) {
  // Operate on characters as unsigneds
  unsigned char* ptr = reinterpret_cast<unsigned char*>(dst);
  static const int B = 128; //10000000
  if (v < (1<<7)) {  v < 2^7
    *(ptr++) = v;
  } else if (v < (1<<14)) { v < 2^14
    *(ptr++) = v | B;
    *(ptr++) = v>>7;
  } else if (v < (1<<21)) { //v < 2^21
    *(ptr++) = v | B;
    *(ptr++) = (v>>7) | B;
    *(ptr++) = v>>14;
  } else if (v < (1<<28)) {
    *(ptr++) = v | B;
    *(ptr++) = (v>>7) | B;
    *(ptr++) = (v>>14) | B;
    *(ptr++) = v>>21;
  } else {
    *(ptr++) = v | B;
    *(ptr++) = (v>>7) | B;
    *(ptr++) = (v>>14) | B;
    *(ptr++) = (v>>21) | B;
    *(ptr++) = v>>28;
  }
  return reinterpret_cast<char*>(ptr);
}

上面这一段对uint32_t的变量进行Varint32编码的例子,编码的结果保存在dst里,返回的ptr是dst的最后一个字节的指针。使用if-else对1、2、3、4、5个字节的情况分别做了处理。主要就是移位和或运算符的使用。跟着代码走一遍就能理解。

const char* GetVarint32PtrFallback(const char* p,
                                   const char* limit,
                                   uint32_t* value) {
  uint32_t result = 0;
  for (uint32_t shift = 0; shift <= 28 && p < limit; shift += 7) {
    uint32_t byte = *(reinterpret_cast<const unsigned char*>(p));
    p++;
    if (byte & 128) {
      // More bytes are present
      result |= ((byte & 127) << shift);
    } else {
      result |= (byte << shift);
      *value = result;
      return reinterpret_cast<const char*>(p);
    }
  }
  return NULL;
}
inline const char* GetVarint32Ptr(const char* p,
                                  const char* limit,
                                  uint32_t* value) {
  if (p < limit) {
    uint32_t result = *(reinterpret_cast<const unsigned char*>(p));
    if ((result & 128) == 0) {
      //如果低8位是0xxxxxxx,little-endian,也就是小于128
      *value = result;    //直接赋值
      return p + 1;
    }
  }
  return GetVarint32PtrFallback(p, limit, value);
}

上面GetVarint32Ptr是解码Varint32,当值大于128时,则调用GetVarint32PtrFallback。在则调用GetVarint32PtrFallback中,利用循环一个字节一个字节的取出,最终将value指针指向结果result。

二、Arena

Arena是leveldb中管理内存分配的类。所有的内存分配都通过Arena申请,可以根据申请的内存大小使用不同的内存分配策略,也可以避免过多的内存碎片问题,并且在内存释放时统一使用Arena来释放,方便管理。 Arena类的实现并不复杂。首先看一下成员变量。

  // Allocation state
  char* alloc_ptr_;                 //指向当前块中剩余的内存起点
  size_t alloc_bytes_remaining_;    //当前块中剩余的内存

  // Array of new[] allocated memory blocks
  std::vector<char*> blocks_;       //用来保存所有new出来的char数组,释放内存时也会使用到

  // Total memory usage of the arena.
  port::AtomicPointer memory_usage_;    //通过Arena申请的内存

然后就是public的成员函数:

// Return a pointer to a newly allocated memory block of "bytes" bytes.
  char* Allocate(size_t bytes);

  // Allocate memory with the normal alignment guarantees provided by malloc
  char* AllocateAligned(size_t bytes);

  // Returns an estimate of the total memory usage of data allocated
  // by the arena.
  size_t MemoryUsage() const {
    return reinterpret_cast<uintptr_t>(memory_usage_.NoBarrier_Load());
  }

功能上很简单,Allocate用来申请指定大小的内存,AllocateAligned用来申请保证内存对齐的内存空间,MemoryUsage用来获取内存使用情况。

我对内存对齐的理解:现在假定内存对齐的最小单位是8个字节,那么如果你只申请14个字节,内存对齐会多给你分配2个字节凑成16个字节。内存对齐的好处就是访问速度的提升,在CPU一次读取8个字节的情况下。在没有内存对齐的情况下,你要读取第612个字节,就需要读取两次,第一次07个字节,通过移位取出67,再读取第815个字节,取出812。这样就需要读取两次。而如果在内存对齐的情况下,你需要读取的612个字节应该被放在8~15个字节中。只需读取一次即可。

私有的成员函数有:

char* AllocateFallback(size_t bytes);
char* AllocateNewBlock(size_t block_bytes);

这两个函数提供了具体的内存分配的实现。 具体分析这5个成员函数。 1.Allocate(size_t bytes)

inline char* Arena::Allocate(size_t bytes) {
  // The semantics of what to return are a bit messy if we allow
  // 0-byte allocations, so we disallow them here (we don't need
  // them for our internal use).
  assert(bytes > 0);
  if (bytes <= alloc_bytes_remaining_) {
    char* result = alloc_ptr_;
    alloc_ptr_ += bytes;
    alloc_bytes_remaining_ -= bytes;
    return result;
  }
  return AllocateFallback(bytes);
}

Allocate是一个内联函数。内联函数的好处在于编译时会直接在调用处展开,对于程序执行速度有一定提升,但是也会导致程序大小变大。 assert(bytes > 0);是一个断言语句,断言语句可以在编译时由编译器去除,但是在调试的时候可以帮助程序员发现问题所在。这里用来保证没有出现0个字节分配的情况。 后面的判断语句用来判断当前块的剩余空间是否够分配,如果够则分配。如果不够则交给AllocateFallback()处理。返回的是分配的空间起点。 2.AllocateAligned(size_t bytes)

char* Arena::AllocateAligned(size_t bytes) {
  const int align = (sizeof(void*) > 8) ? sizeof(void*) : 8;
  assert((align & (align-1)) == 0);   // Pointer size should be a power of 2
  size_t current_mod = reinterpret_cast<uintptr_t>(alloc_ptr_) & (align-1);
  size_t slop = (current_mod == 0 ? 0 : align - current_mod);
  size_t needed = bytes + slop;
  char* result;
  if (needed <= alloc_bytes_remaining_) {
    result = alloc_ptr_ + slop;
    alloc_ptr_ += needed;
    alloc_bytes_remaining_ -= needed;
  } else {
    // AllocateFallback always returned aligned memory
    result = AllocateFallback(bytes);
  }
  assert((reinterpret_cast<uintptr_t>(result) & (align-1)) == 0);
  return result;
}

AllocateAligned(size_t bytes)用来做内存对齐的分配。 const int align = (sizeof(void*) > 8) ? sizeof(void*) : 8;用来获取分配的最小单位,如果指针大小大于8,则取指针大小,否则使用8作为最小的对齐单位。 assert((align & (align-1)) == 0);这是一个很有意思的判断,可以保证只有2的n次方才能满足。 size_t current_mod = reinterpret_cast<uintptr_t>(alloc_ptr_) & (align-1);current_mod是余数,比如当前指针地址是15,align是8,那么余数为7,这个余数就是alloc_prt_&(align-1)的值。 size_t slop = (current_mod == 0 ? 0 : align - current_mod);因为当前指针可能不是align的整数倍,slop即代表当前指针需要偏移的大小,来保证是align的整数倍。 size_t needed = bytes + slop; needed代表需要分配的空间。 之后的判断则和Allocate()函数做法相同了。需要注意的是返回的result指针是align的整数倍,这样就能保证以最少的内存读取次数来获取想要的数据。 3.AllocateFallback(size_t bytes)

char* Arena::AllocateFallback(size_t bytes) {
  if (bytes > kBlockSize / 4) {
    //如果需要分配的bytes大于块大小的1/4,则单独在新的块中分配,以此避免浪费过多的剩下的空间(这样能保证浪费的空间小与kBlockSize / 4)
    char* result = AllocateNewBlock(bytes);
    return result;
  }

  // 重新开辟新的块空间进行分配,上一个块剩下的空间都浪费了。
  alloc_ptr_ = AllocateNewBlock(kBlockSize);
  alloc_bytes_remaining_ = kBlockSize;

  char* result = alloc_ptr_;
  alloc_ptr_ += bytes;
  alloc_bytes_remaining_ -= bytes;
  return result;
}

上面两个成员函数在当前块分配空间不足时,都将分配任务交给AllocateFallback处理。 4.AllocateNewBlock(size_t block_bytes)。

char* Arena::AllocateNewBlock(size_t block_bytes) {
  char* result = new char[block_bytes];
  blocks_.push_back(result);
  memory_usage_.NoBarrier_Store(
      reinterpret_cast<void*>(MemoryUsage() + block_bytes + sizeof(char*)));
  return result;
}

使用new char来申请一个新的块,并将块的起始指针存入blocks_中。更新memory_usage的大小。 5.MemoryUsage() ``` size_t MemoryUsage() const { return reinterpret_cast<uintptr_t>(memory_usage_.NoBarrier_Load()); } ``` 获取memory_usage_中存储的使用空间数据。

三、Memeory Barrier(内存屏障)

memory_usage_的类型是AtomicPointer,这是一个原子类型,针对不同平台有不同的实现。可以用来线程安全的存储和获取值。 AtomicPointer类实现了几个函数:

NoBarrier_Load();
NoBarrier_Store(void* v)
Acquire_Load();
Release_Store(void* v)

这里面涉及到一个Memory Barrier(内存屏障,Memory fence)的概念。 引用一个wikipedia的例子:

Processor #1: while (f 0); // Memory fence required here print x; Processor #2: x = 42; // Memory fence required here f = 1;

一个两核心的CPU按照上述例子执行。可能会出现很多种情况: 虽然我们希望的是打印“42”。但是如果核心#2存储操作乱序执行(out-of-order),就有可能f在x之前被更新了。这样打印语句就可能打印出“0”。同样的,核心#1读取操作可能也乱序执行,x就有可能在f被判断之前读取了,打印语句可能打印出一个无法预期的值。对于大多数程序来说,上面的这些情况都是不可以接受的。使用memory barrier可以避免out-of-order的问题。 简而言之就是,在多CPU共享内存空间的情况下,两条语句的执行顺序已经无法保证了。需要memory barrier来保证执行顺序的正确。 当然,单CPU是不会出现这个问题的。 现在再来解释上面的4个函数的作用。

NoBarrier_Load();           //不使用内存屏障的读取
NoBarrier_Store(void* v)    //不使用内存屏障的存储
Acquire_Load();             //使用内存屏障的读取
Release_Store(void* v)      //使用内存屏障的存储
分类:c++, levelDB源码阅读标签:#leveldb #Varint #Arena