來源于公眾號JAVA藝術 ，
作者wujiuye
我先說下結果。我現在還不敢放線上去測，這是本地測的數據，我4g內存的電腦本地開redis，一次都沒寫完過全部數據，都是寫一半后不是redis掛就是測試程序掛?？梢钥隙ǖ氖强傆涗洈凳且郧f為單位的。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在這個區間內，所以還要比較
3756871424<=3756871650<=3756871679
因為會存在這種情況，該區間與前一個區間并不是連續的，比如。
(1)3756870911=>3756870656~3756870911 (2)3756871679=>3756871424~3756871679
明顯，這兩個區間之間存在斷層。但可以肯定的是，如果不落在區間(2)中，也不會落在區間（1）。所以不滿足就可以直接返回null了。
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或者內存緩存，只需要實現幾個接口就可以了。
下面是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-后面的代表的分區索引
