月度归档:2017年01月

PHP使用共享内存

 

概述

共享内存指在多处理器的计算机系统中,可以被不同中CPU访问的大容量内存。是众多进程间通信(IPC)方式中最快的一种,无需进行数据拷贝等操作,即可在各个进程之间共享数据。

PHP同样也提供了对共享内存操作的可能性,通过shmop扩展实现。

应用

结合一个实际使用的场景,PHP daemon多进程从上游获取用户ID,需要与指定数据集去重,用户ID大约为12位的数字。要求是不能多去重(即不能存在误伤的判断),但是也不能少去重。

考虑到多进程处理时,需要考虑如何实现便捷,快速的进行判断用户ID已存在于数据集之中。在数据结构上可以使用的几种方法有:

  • Bitmap
  • Hash
  • Array

下面分别说明三者的优缺点:

Bitmap

Bitmap(位图,以下不加区分的使用)的特点在于数据密度大时(即已排序的情况下,相邻数字间隔不大),是极为节省内存用量的数据结构。无论数字多大,在内存中只通过1 Bit进行表示。假设用1 Byte的空间进行数字的表示,数据集为[1,3,4,5,7],则这一组数据的位图可以表示为:

即便数字相当巨大,在已知最小值的情况下,同样通过同样大小的空间也可表示,如数据集为[100000001,100000003,100000004,100000005,100000007],同样也可以用同样一个位图进行表示,因为所有数字的都可以认为相对于100000000进行了偏移操作。

Bitmap操作起来速度与便利性也相当令人满意,只需要根据数字大小,找到对应的位,判断当前位的0/1值即可,位运算操作的速度之快无需多言。

然而,Bitmap的最大问题在于,如果存储的是数值的顺序信息,那么整个Bitmap的数据才是最有效的。即,如果已经数字本身是有序的,如从1开始,一直到10000,或者是有办法迅速的知道位置是1的数字的具体字面值,那么存储的位会更加的高效。

在存储用户ID这一个场景时,Bitmap不一定适用,因为用户ID可能会长于10位,如果把用户ID当成数字来看,同时考虑到可能存在的一些业务形态(6,8之类的靓号逻辑,4之类的避讳逻辑),可能得到的Bitmap就相当的“稀疏”(0过多,1过少),造成的结果就是内存的有效使用率降低。假设用户ID最大值是9999999999,仅仅在10位数的用户ID的情况下,为了包含所有的数字,需要开辟约1192.09MB大小的内存空间,当然实际应用中很可能会比这个要小,通过找到偏移值(获取比较集的最大最小值,确定偏移值,减少无用0的内存占用)、数据分块(比如前5位相同的比率大,把数字前5位作为一个集合,只生成后5位的Bitmap提高表示有效程度)等方式,但是又会引入一些其他的问题,或者效果不佳(比较集合中存在1和9999999999两个用户ID)或者是难于管理(前5位有上万种组合

)。

如果在可以接受误伤的情况下,有一个更优的方案,即布隆过滤器(Bloom filter),这是通过Bitmap可以完成的,综合速度和存储压力都较优方案。

Hash

Hash(哈希表)的特点在于快,理论上来说,Hash的查询和写入时间复杂度都是O(1)

编程语言如果提供了Hash的数据结构,那么应用数据结构就成为了一个看起来不错选择了。

实际实现中,Hash存在的第一个可能存在的问题是Hash冲突的解决,如果用开放地址法(Open addressing)进行解决,可能的问题在于冲突之后查询下一个可用地址的次数过多,而用链表(Separate chaining)解决,则会存在退化的情况(所有值都hash到一个链表中)。不过这些问题一般来说都应该是在应用过程中由编程语言关心的。

这次应用限定了编程语言为PHP,那么从PHP的实现上来看看应用Hash是否可行。

PHP里的数组就提供了Hash的功能,PHP数组的便利程度无需多言,在去重这一个场景上,完全可以通过用户ID作为key,写入布尔值作为value,通过isset()方法快速的进行去重操作。

速度上我们可能不再担忧了,但是内存占用上呢?

目前PHP的最新版本为PHP 7.1.0,常规编译安装后,通过如下脚本获取0~1000000在数组中的内存占用情况:

运行结果为:

仅仅1000000的7位字符串作为hash key的数据集,就需要耗费超过341MB的内存。可是即便是作为文本文件,这些数据集在通过换行符号分隔的情况下,完全加载到内存只需要大约8MB的内存使用。是什么造成了如此大的差距呢?

从PHP的源码来看(源码目录下的Zend/zend_types.h),PHP数组通过HashTable这一个struct实现:

数据的实际存储部分即Bucket,对内存占用影响起到决定性作用的也正是Bucket这个数据结构,Bucket的定义为:

Bucket中包含zvalzend_ulong,以及zend_string三种数据结构,下面分别来看看这几个数据结构。

zval

zval的定义如下:

zval中又包含zend_vlaue,那么通过zend_value的定义:

可以看出zend_value作为一个union至少要占用8个字节(最大的内存占用来自于当中包含的zend_long,在Zend/zend_long.h中被定义为typedef int64_t zend_long;),所以,作为一个struct,zval会占用sizeof(value)+sizeof(u1)+sizeof(u2)=8+4+4=16 Bytes。

zend_ulong

Zend/zend_long.h中被定义为typedef int64_t zend_ulong;,所以会占用8 Bytes。

zend_string

来看zend_string的定义:

其中zend_refcounted_h的定义为:

可以看到zend_refcounted_h的空间占用为sizeof(refcount)+sizeof(u)=4+4=8 Bytes。

size_t这里需要注意,因为在64位OS上编译,这里会占用8 Bytes。

结构成员val用于存储key的值,由于key都是7位长的字符串,所以这里会占用7 Bytes。

所以,在这里,空间占用为8+8+8+7=31 Bytes。

综上,直接统计数据结构的大小已经能明显看到PHP提供Hash是相当占用内存的,出于这个方面的考虑,基本可以认定Hash不适合当前的应用场景。

Array

可能有人会说,Array算是什么办法,但是对于特定情况,Array确实可以使用。

比如C语言的数组,是在内存中的一片连续空间,也就是说,实际上内存的占用就是数据个数乘以单个数据需要占用的空间。从这个角度来看,是没有太多的内存浪费的。

当然PHP的数组不能这么看,因为PHP的数组仍然有太多的冗余信息。

数组的“缺点”在于查找的耗时。线性查找的耗时几乎让人无法接受,那么如果数据可以是有序的,通过二分查找耗时将会大大降低。

1M的数据,只需要通过至多10次查找即可判断对应的值是否存在。

Bitmap/Hash/Array?

从数据特点和存储用量来考虑,同时考虑到查询速度,Array在这个场景下胜出。

存储

PHP可以使用共享内存,作为最简单的IPC方式,并且使用方式相当简单,PHP的shmop扩展中提供了对共享内存的操作能力。

创建/打开

共享内存在PHP的创建和打开工作是通过shmop_open方法实现的。定义如下:

PHP的共享内存的创建实际上是通过shmget这一系统调用实现的,参见shmop扩展源码:

shmget返回的值是一个类似文件描述符的存在,因为它并不是一个真正的文件描述符,所以我们实际上的操作依据仅仅上是一个全局唯一的数字,用来表示共享内存。同时通过shmat系统调用将共享内存映射到当前进程的地址虚拟空间之中。

共享内存打开方法中的第一个参数指定的key,是标识这一共享内存片段的依据,需要全局唯一,一个方法就是通过一个确实存在的文件,利用ftok系统调用,生成一个全局唯一的key。文件名不是决定key值的决定因素,决定因素是文件的inode号。

关闭

关闭的实现的是通过shmdt系统调用完成的。在扩展的MINIT阶段,通过zend_register_list_destructors_ex方法注册了资源析构方法为rsclean,对共享内存的的ID看做是资源(Resource)。

在调用这一方法时,通过资源删除APIzend_list_close调用注册的rsclean方法完成对资源的释放。

rsclean的实现如下:

对共享内存ID进行了shmdt操作,同时释放了的申请共享内存操作结构体。

删除

这一个方法中,是shmctl系统调用的表现的时候了。删除一段共享内存只需要将系统调用中的第二个参数设定为IPC_RMID即可。

当然,删除共享内存也可以通过Linux中的ipcrm命令完成,如ipcrm的man中提到的,如果知到key(即创建/打开部分提到的共享内存全局唯一的标识)则使用-M参数,知道ID则使用-m参数。

读取的方法则是通过共享内存ID以及开始位置以及读取的长度获得一个字符串。

从实现上来看,以下几种情况会返回false并打印WARNING日志:

  • 起始值小于0或者大于共享内存的容量
  • 读取的字节数小于0
  • 起始值大于INT_MAX与读取字节数只差
  • 起始值与读取字节数之和大于共享内存大小

实现上来说,实际上是通过memcpy将字符串的值复制到共享内存的指定位置。

参考