基于Redis实现范围查询的IP库缓存设计方案 _Redis

来源于公众号JAVA艺术，
作者wujiuye

我先说下结果。我现在还不敢放线上去测，这是本地测的数据，我4g内存的电脑本地开redis，一次都没写完过全部数据，都是写一半后不是redis挂就是测试程序挂。可以肯定的是总记录数是以千万为单位的。O(log(n千万/range)）的时间复杂度，本地测的结果我并不满意，7ms的时间，太久了。这个数量级的数据，就算内存缓存也很花时间，因为并不是简单的key-value，涉及到范围查找。

文章插图

文章插图

使用Sorted Set实现范围查找

最近系统需要更新IP库，IP库存储的是IP所属的国家和城市信息，广告主投放广告会有区域限制，所以需要根据点击广告的终端ip，获取位置信息，并判断是否满足广告投放区域的要求。

最头疼的是，IP信息库是按区间存储的，拿到一个ip得要知道它所属的范围才能知道它对应哪条记录。它的表结构是这样的：
Ip_from，ip_to，ccountry_code，country，regin，city
Ip起始段，Ip结束段，国家编码，国家，区域（比如中国的省），城市

文章插图

而Ip_from和ip_to是一个数值，将ip通过公式转化后的数值。
a.b.c.d

A*(256*256*256)+b*(256*256)+c*(256)+d

为了效率，程序中的转换可以写为

a*(1<<24)+b*(1<<16)+c*(1<<8)+d

在此之前我都没注意以前是怎么实现查找的，以前是用内存缓存实现，但以前的数据比较少，而查找的方式用的递归，先不说递归查找算法的缺陷。而新的ip库数据量很大，本地debug直接OOM，没有足够的内存撑起这么大的ip库。

如果说，一个csv文件的大小是1g多，那么读取到jvm中，就需要4g甚至更高的内存，因为一个对象占的内存是比一行逗号隔开的字符串耗更大的内存。要实现查找算法，创建对应的数据结构，这些也会占用很大的内存。

综上所述，我们考虑用redis来缓存，当然，也可以用mongodb，如果是用mongodb缓存，那就简单了。既然要用Redis，那么就不得不面对，Redis如何实现范围查询，还要支持高并发。这算是一道难题了。

插入一段内容，关于如果使用Sorted Set实现范围查找，就是sql中的大于等于and小于等于。（下面是我参考的一篇博客，我觉得他的实现有些鸡肋，完全可以用一条：
zadd myset 1015 1011-1015-v1 替代两条记录）。
服务端对于客户端不同的版本区间会做些不同的配置，那么客户端一个版本过来怎么快速的定位是属于哪个版本区间呢？可以利用Sorted Sets的zrangebyscore命令。
zadd myset 1011 v1_start
zadd myset 1015 v1_end

zadd myset 1018 v2_start
zadd myset 1023 v2_end

如上我们像myset里插入了4条数据，代表的意思是版本区间v1是从1011-1015版本，版本区间v2是从1018-1023版本。

https://www.cnblogs.com/zhanjindong/p/3549994.html

那么我现在如何判断1014版本属于哪个区间呢，使用zrangebyscore如下操作：
zrangebyscore myset 1014 +inf LIMIT 0 1
1)v1_end

返回v1_end说明1014属于版本区间1，上面的这个命令的意思是在myset中查找第一个score值大于等于1014的member，如果我们查找一个不在区间内的版本，比如1016:
zrangebyscore myset 1014 +inf LIMIT 0 1
1)v2_start

https://www.cnblogs.com/zhanjindong/p/3549994.html

首先，我想到的是利用Redis的有序集合Sorted Set，存储每条记录的ip区间，或者叫ip范围。ip_to列作为有序集合的score 。如：
zadd ip-country-city-locations-range 3756871679 3756871424~3756871679
这样就可以查询一个ip对应的score落在哪个区间，找出符合条件的第一个区间。如：

(1)将ip转为number，假设得到的值为：3756871650(2)使用zrangebyscore命令获取所在区间zrangebyscore ip-country-city-locations-range 3756871650 +inf 0 1因为3756871650比3756871424~3756871679区间的end值3756871679小于等于，所以匹配到这条记录。但拿到这条记录后并不能说明3756871650在这个区间内，所以还要比较