新闻资讯  快讯  焦点  财经  政策  社会
互 联 网   电商  金融  数据  计算  技巧
生活百科  科技  职场  健康  法律  汽车
手机百科  知识  软件  修理  测评  微信
软件技术  应用  系统  图像  视频  经验
硬件技术  知识  技术  测评  选购  维修
网络技术  硬件  软件  设置  安全  技术
程序开发  语言  移动  数据  开源  百科
安全防护  资讯  黑客  木马  病毒  移动
站长技术  搜索  SEO  推广  媒体  移动
财经百科  股票  知识  理财  财务  金融
教育考试  育儿  小学  高考  考研  留学
您当前的位置:首页 > IT百科 > 数据库 > Redis

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

时间:2019-12-02 11:40:19  来源:  作者:

来源于公众号JAVA艺术 ,

作者wujiuye


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

 

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

 

 

 

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

 

 

 

使用Sorted Set实现范围查找

 

 

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

 

最头疼的是,IP信息库是按区间存储的,拿到一个ip得要知道它所属的范围才能知道它对应哪条记录。它的表结构是这样的:

Ip_from,ip_to,ccountry_code,country,regin,city

Ip起始段,Ip结束段,国家编码,国家,区域(比如中国的省),城市

基于Redis实现范围查询的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在这个区间内,所以还要比较


3756871424<=3756871650<=3756871679

 

因为会存在这种情况,该区间与前一个区间并不是连续的,比如。

(1)3756870911=>3756870656~3756870911
(2)3756871679=>3756871424~3756871679

 

明显,这两个区间之间存在断层。但可以肯定的是,如果不落在区间(2)中,也不会落在区间(1)。所以不满足就可以直接返回null了。

 

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

 

Ip库用hash类型存储,field取ip_from或者ip_from&ip_to,value当然就是存完整的一行记录了。最后就可以根据拿到的区间信息获取到对应记录的field,使用hget命令就能获取到最终的一行ip信息记录。

hget ip-country-city-locations 3756871424

这并不难实现,但是,耗时却非常严重,可以看下官方文档介绍的Sorted Set的zrangebyscore的时间复杂度。IP库保守估计百万条记录,如果就这样上线,百分百又是服务雪崩。

 

改进思路:区间+Sorted Set

 

由于Sorted Set有序集合的查询时间复杂度是O(log(n)+m),其中n是总记录数,m是此次查询获取的记录数,在limit 0 1的情况下是O(log(n)),所以一个有序集合的元素个数越多,它的查询时间耗时越长。对于一般的应用场景,如排行榜,都是只有极少数的几百条记录。而如果用于ip库的区间查询实现,记录上百万条,而且还是用于高并发场景,不把服务搞垮才怪了。

 

既然我们要用Sorted Set,但又不能让集合的元素过大,那么我们可以分n/m个区间存储啊。假设有一百万条记录,每个Sorted Set存储1000条,那就用1000个Sorted Set集合来存储。hash的查询时间复杂度是接近O(1)的,增加1000个key在分槽位的分布式集群下根本不算什么。

 

按照上面的思路改进后,获取一个ip的国家城市信息就变成如下步骤:

1、根据ip计算出一个number值

比如:3756871650

2、根据区间大小(这一步的区间指的是每个Sorted Set的最大大小),计算出该number所在的集合的key


比如:ip-country-city-locations-range-375

3、根据这个key,去Sorted Set查询number所属的区间。

比如:zrangebyscore ip-country-city-locations-range 3756871650 +inf 0 1

 

5、拿到区间信息后,从区间信息获取ip范围位置信息的 field(hash类型存储)

比如查询结果区间信息为:3756871424~3756871679拿到field就是:3756871424

 

6、根据key和field拿到目标记录。

hget ip-country-city-locations 3756871424

 

编码实现

 

我将实现封装成一个组件,目的是对外提供更简单的使用方式,封装复杂的实现逻辑,同时,内部的改动对使用者无感知。通过SPI+分层设计,利用静态代理模式等,使得组件具有极强的扩展性,如果某天想改成使用mongodb或者内存缓存,只需要实现几个接口就可以了。

 

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

 

 

下面是README.MD的内容

 

关于数据源表的初始化

使用需要配置update启动参数:

-Dip.database.table.update=true

如:

java -Xss256k-jar -Dip.database.table.update=true xxx-1.0.0.jar

true: 首次启动就会从指定的url文件读取解析记录,插入数据表 false: 表示已经确认表存在记录了,不需要再更新。(也不会去解析文件) 默认:false

解析记录与插入表是异步的,后台开启一个线程执行。耗时根据文件大小决定,我测的是86s

配置使用表

使用了java的SPI

需要指定使用哪个文件解析器,也就对应使用哪种类型的表

配置redis操作实现类

使用了java的SPI

如果解析配置使用了

com.chestnut.ip.database.parser.RedisIP2LocationFileParser

则需要自己实现RedisOperation,并在

com.chestnut.ip.database.suppor.IP2LocationRedisOperation

文件中配置redis操作的实现类

缓存的key

如果使用redis存储数据,则key固定为

ip-country-city-locations // 存储真实记录ip-country-city-locations-range-* // 存储范围与真实记录的key的映射

其中ip-country-city-locations-range-后面的代表的分区索引



Tags:Redis   点击:()  评论:()
声明:本站部分内容来自互联网,内容观点仅代表作者本人,如有任何版权侵犯请与我们联系,我们将立即删除。
▌相关评论
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表
▌相关推荐
我先说下结果。我现在还不敢放线上去测,这是本地测的数据,我4g内存的电脑本地开redis,一次都没写完过全部数据,都是写一半后不是redis挂就是测试程序挂。可以肯定的是总记录数是以千万为单位的。O(log(n千万/range))的时间...【详细内容】
2019-12-02   Redis  点击:(0)  评论:(0)  加入收藏
慢查询,大家可能已经接触到了MySQL的慢查询。我们配置一个时间,如果查询时间超过了我们设置的时间,我们就认为这是一个慢查询. 如上图所示:Redis客户端一条命令执行分4个步骤: 发...【详细内容】
2019-11-29   Redis  点击:(7)  评论:(0)  加入收藏
ip192.168.1.111 主192.168.1.112 从192.168.1.113 从安装redis 安装依赖yum install gcc gcc-c++ -y 下载redis-4.0.11.tar.gzcd /usr/localwget http://download.redis.i...【详细内容】
2019-11-28   Redis  点击:(2)  评论:(0)  加入收藏
常用的 SQL 数据库的数据都是存在磁盘中的,虽然在数据库底层也做了对应的缓存来减少数据库的 IO 压力。 图片来自 Pexels由于数据库的缓存一般是针对查询的内容,而且粒度也...【详细内容】
2019-11-27   Redis  点击:(2)  评论:(0)  加入收藏
概念:Redis是用C语言开发的一个开源的高性能键值对数据库。特征: 数据间没有必然的联系 内部采用单线程机制进行工作 高性能 多数据类型支持字符串类型 String列表类型 List散...【详细内容】
2019-11-27   Redis  点击:(3)  评论:(0)  加入收藏
本文实例讲述了php+redis实现注册、删除、编辑、分页、登录、关注等功能。分享给大家供大家参考,具体如下:主要界面 连接redisredis.php<?php //实例化 $redis = new Redis();...【详细内容】
2019-11-26   Redis  点击:(1)  评论:(0)  加入收藏
客户端的连接的建立Redis通过在TCP端口上进行监听,或者Unix socket(如果启用)的方式来接受客户端的连接。当一个新的客户端连接被接受执行以下操作: 当Redis使用非阻塞I/O复用,...【详细内容】
2019-11-25   Redis  点击:(5)  评论:(0)  加入收藏
最近忙于业务开发、交接和游戏,加上碰上了不定时出现的犹豫期和困惑期,荒废学业了一段时间。天冷了,要重新拾起开始下阶段的学习了。之前接触到的一些数据搜索项目,涉及到请求模...【详细内容】
2019-11-22   Redis  点击:(8)  评论:(0)  加入收藏
MVC模式(Model-View-Controller)是软件工程中的一种软件架构模式,把软件系统分为三个基本部分:模型(Model)、视图(View)和控制器(Controller)。...【详细内容】
2019-11-22   Redis  点击:(13)  评论:(0)  加入收藏
一、项目介绍Rotter是禧云自主研发的跨机房Redis双向同步解决方案(下文简称为方案),具有零侵入、高吞吐量、低延时、高堆积能力等特点。当前版本支持Sentinel模式和单点模式Red...【详细内容】
2019-11-20   Redis  点击:(7)  评论:(0)  加入收藏
适合的读者:初级程序员前言虽然现在大多数后端服务都是部署在linux服务器上的,代码开发工作很多人是在windows下进行的,由于redis官方没有windows下的版本,所以大家第一次使用的...【详细内容】
2019-11-15   Redis  点击:(9)  评论:(0)  加入收藏
Redis以内存数据库而闻名。但是,某些系统将它用作消息队列管理工具。Pub/Sub 和 RPOPLPUSH 是用于实现这样一个系统的两组命令。在这篇文章中,我将分享一些关于这两个命令集的...【详细内容】
2019-11-14   Redis  点击:(6)  评论:(0)  加入收藏
压缩列表ziplist的zset内部有两种存储结构,一种是ziplist,另一种是跳跃列表skiplist。为了彻底理解zset的内部结构,我们就再来介绍一下skiplist。skiplist介绍顾名思义,skiplist...【详细内容】
2019-11-13   Redis  点击:(12)  评论:(0)  加入收藏
Jedis api 在线网址:http://tool.oschina.net/uploads/apidocs/redis/clients/jedis/Jedis.htmlredisson 官网地址:https://redisson.org/redisson git项目地址:https://githu...【详细内容】
2019-11-11   Redis  点击:(42)  评论:(0)  加入收藏
一、Redis简介Redis是一个开源的使用ANSI C语言编写的Key-Value数据库,是一种应用非常广泛的NoSQL数据库,性能极高,拥有出色的读写速度,适用性非常的广。因此也被广泛应用在中大...【详细内容】
2019-11-01   Redis  点击:(13)  评论:(0)  加入收藏
1、系统架构 2、服务器情况 服务器 1:nginx(80)、redis(6379) 服务器 2:tomcat1(8080)、tomcat2(8080) 服务器 3:mysql(3306)3、Nginx 主要配置http { ...... upstream tomcat { ip_hash;...【详细内容】
2019-10-30   Redis  点击:(15)  评论:(0)  加入收藏
redis在现在的系统中用的越来越多了,分布式锁,缓存,附近的人,排行榜,简易版的消息队列,发布订阅等。redis中有很多命令,每个命令又有很多参数,如果让我们全部记住很不现实,今天就推...【详细内容】
2019-10-30   Redis  点击:(13)  评论:(0)  加入收藏
Redis支持主从复制功能,用户可以通过执行slaveof命令或者在配置文件中设置slaveof选项来开启复制功能。例如,现在有两台服务器—127.0.0.1:6379和127.0.0.1:7000,向服务器...【详细内容】
2019-10-28   Redis  点击:(14)  评论:(0)  加入收藏
redis存储类型主要提供了5种数据结构:字符串(String)、哈希(hash)、列表(list)、集合(set)、有序集合(short set);redis底层实现的8种数据结构SDS simple synamic string:支持自...【详细内容】
2019-10-28   Redis  点击:(14)  评论:(0)  加入收藏
Redis简介1. 支持5种数据结构支持strings, hashes, lists, sets, sorted setsstring是很好的存储方式,用来做计数存储。sets用于建立索引库非常棒;2. K-V 存储 vs K-V 缓存新...【详细内容】
2019-10-25   Redis  点击:(29)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条