背景
产品希望新增一个针对校园ip定向投放广告的策略。即来了一个ip可以判断出是否在给定的ip范围内。
数据原型
在数据量不大的情况下，最初的原型如下：
+----+-------+------------+------------+
| id | orgid | startip | endip |
+----+-------+------------+------------+
| 1 | 100 | 1887045022 | 1887839022 |
| 5 | 101 | 3334455544 | 3334564191 |
| 6 | 101 | 3396407296 | 3396411391 |
+----+-------+------------+------------+
最核心的部分是三个：startip、endip 以及 id。其中 id 是我们要查询的结果。 基于该表的查询语句只能是
SELECT id FROM iplist WHERE startip <= {ip} AND endip >= {ip}
其中 {ip} 是要查询的 ip 地址，为了方便查询，在 php 中用 ip2long 函数把它转换为一个整数。在这个表中，startip和endip都设置为索引，并且数据量并不大，因此在并发度不高的情况下单条查询并无瓶颈。 假如说我们是在高并发且数据量大的情况下查询，查询时间以及db的压力都是需要考虑的。
数据量
此处列举下目前场景的数据：
一、mysql集群能够承受的qps为2000。该集群下除了我们的表还有诸多fufei相关的表。
二、接口预计调用日pv为4500万，uv为1600万。
同时该接口对于性能要求有比较高，在上述数据量的背景下，直接去从数据库读取存在并发压垮数据库的风险。
方案选型
如上所述，基于对高并发数据获取的可靠性以及有效性，可以确定直读数据库存在风险。因此考虑从文件、redis、memcache等这几种存储选型入手来分析确认。
一、文件存储
文件存储的数据结构即将下面的数组序列化或者json成一个字符串，写入文件。
array(
array(
'orgid'=>100,
'startip'=> 12232323232,
'endip'=> 22232323232,
),
array(
'orgid'=>100,
'startip'=> 12232323232,
'endip'=> 22232323232,
),
etc....
)
该方案的优点是简单直接、无需考虑被压垮的问题。
缺点就是增加了计算成本，每来一个ip都需要读文件字符串解析后，遍历数组判断ip是否属于对应范围。这里我们增加了读文件解析文件以及遍历数组的时间。
当然也并不是不可解决，比如说我可以把文件解析到的字符串直接cache起来，但是数组遍历的时间还在。想过自己搞一套类似二分查找的实现，比如说线段树，但是这块构造和维护成本较高，逻辑容易复杂出错，暂时就搁置该方案。
二、redis
目前我们这一套是比较典型的关系型模式，redis相对来说轻量级，用什么办法来构造底层数据存储呢？
- 将关系型数据转换为数字集合
- 该方案就是将范围内的ip全部列出来，形成一套数据集，以string或者set的方式存储起来。
- 经过统计，我们目前全部范围内的ip数量共90万个。
- 走string内存占用为80MB，查询的时间复杂度为O(1)
- 走set内存占用40MB，查询时间复杂度O(1)
- 该方案的优点就是简单粗暴，直接平铺数据，并且时间复杂度也很低，典型的以空间换时间。
- 缺点就是获取全局ip的成本较高，管理难度高，另在网上有看到说set集合超过10条性能也会下降，这个有待考证。
- 在redis中实现范围查询，利用zset的特性实现。
- zset的具体说明可以参见redis官方文档，这里只需要知道三个概念即可：key、member、score三块。
- 把startip和endip都转化为zset里的score，然后把id定义为member。这样查询就很简单了，只需要用ZREVRANGEBYSCORE和ZRANGEBYSCORE两个方法分别查询出小于ip最近score以及大于ip的最接近score。 score对应的两个ip_id是相同的，那么说明这个ip在这个地址段，如果不同的话证明这个ip地址没有被任何地址段所定义，是一个未知的ip。
- 这样的话，就可以不用去存那90万个ip，只要专注于存储ip段即可，最终内存占用92kb。和string还有set比起来有小了非常多。由于zset特性，我们的查找时间复杂度同二分查找一致，即O(log n )
- 该方案的优点是用较小的内存换取了较高的时间效率。同时可以更好支持我们数量的增加，假如ip段数据翻倍，对于zset存储来说，也就是多几百个，时间效率不会有影响，内存占用也不会激增。
- 缺点就是与set和string存储相比，时间复杂度稍高些。
三、php扩展
这块思想可以借鉴下，用的就是二分查找，查找的是文件，文件存储了全部的ip信息。 http://pecl.php.net/package/qqwry
static uint32_t search_index(const uint32_t ip,FILE *qqwry_file) {
uint32_t index_ip;
unsigned char head[8];
unsigned char index_bytes[7];
fread(head,8,1,qqwry_file);
uint32_t index_start,index_end,index_mid;
index_start = (uint32_t)LE_32(&head[0]);
index_end = (uint32_t)LE_32(&head[4]);
while (1) {
if ((index_end-index_start)==7) {
break;
}
//printf("index:%u:%u\n",index_start,index_end);
index_mid=index_end/7 - index_start/7;
if (index_mid%2==0) {
index_mid=index_mid/2;
} else {
index_mid=(index_mid+1)/2;
}
index_mid=index_start+index_mid*7;
fseek(qqwry_file,index_mid,SEEK_SET);
fread(index_bytes,7,1,qqwry_file);
index_ip=(uint32_t)LE_32(&index_bytes[0]);
if (index_ip==ip) {
break;
} else if (index_ip<ip) {
index_start=index_mid;
} else {
index_end=index_mid;
}
}
if (index_ip>ip) {
fseek(qqwry_file,index_start,SEEK_SET);
fread(index_bytes,7,1,qqwry_file);
}
return (uint32_t)LE_24(&index_bytes[4]);
}
最终实现
最终采用redis的zset实现。方案一和方案三主要是与现有整体环境结合以及后续维护成本，暂时放弃。
redis的string和set虽然时间复杂度低，但是内存占用相对多，并且不便于管理。
zset内存占用少，且时间复杂度无明显劣势，管理方便，因此最终选择zset。
public function isSchoolIp($intUserIp){
$arrInput = array(
'app' => self::REDIS_APP,
'key' => self::ORGVIP_IPLIST,
'min' => 0,
'max' => 0,
'offset' => 0,
'count' => self::IP_LIMIT,
);
// 获取小于用户ip的最接近值
$arrInput['min'] = $intUserIp;
$arrInput['max'] = 0;
$arrLessOutput = Server::call('Redis', 'ZREVRANGEBYSCORE', $arrInput);
if(empty($arrLessOutput)){
return false;
}
// 获取大于用户ip的最接近值
$arrInput['min'] = $intUserIp;
$arrInput['max'] = self::MAX_IP_NUM;
$arrMoreOutput = Server::call('Redis', 'ZRANGEBYSCORE', $arrInput);
if(empty($arrMoreOutput)){
return false;
}
$start = $arrLessOutput[self::ORGVIP_IPLIST][0];
$end = $arrMoreOutput[self::ORGVIP_IPLIST][0];
list ($startOp, $startId) = explode('_', $start);
list ($endOp, $endId) = explode('_', $end);
// 判断id是否同一个
if ($startId == $endId) {
return true;
}
return false;
}