針對IP地址信息的數(shù)據(jù)結(jié)構(gòu)

1. 需求

需求來源：指標(biāo)平臺

由于公司的人員變動，最近接手了elfin這個基礎(chǔ)數(shù)據(jù)應(yīng)用柠横，交接后發(fā)現(xiàn)IP地理位置數(shù)據(jù)的更新邏輯一直存在缺陷，該缺陷造成指標(biāo)平臺和大數(shù)據(jù)平臺所用的數(shù)據(jù)中存在大量的重復(fù)數(shù)據(jù)和老舊數(shù)據(jù)：本應(yīng)為580W條的IP地理位置數(shù)據(jù)實際在數(shù)據(jù)庫中存儲了約830W條篇恒。這些老舊數(shù)據(jù)很可能對大數(shù)據(jù)分析和指標(biāo)分析的準(zhǔn)確性造成影響媒咳。

鑒于大數(shù)據(jù)平臺和指標(biāo)平臺的調(diào)用鏈路復(fù)雜，具體影響無法估計，決定盡快修復(fù)該缺陷并重寫數(shù)據(jù)蜜徽，以確保數(shù)據(jù)的準(zhǔn)確性祝懂。IP地理位置數(shù)據(jù)中以IP段為索引，由于IP端存在增加拘鞋、刪除砚蓬、拆分、合并等多種更新情況掐禁，十分難以判斷怜械。在數(shù)據(jù)提供方IPIP的建議下我和產(chǎn)品經(jīng)理決定將IP地理位置數(shù)據(jù)改為全量更新。

在與指標(biāo)平臺溝通時傅事，了解到全量更新IP數(shù)據(jù)會極大的影響指標(biāo)平臺的性能。為保證數(shù)據(jù)的準(zhǔn)確性和指標(biāo)平臺的性能峡扩，經(jīng)過多次溝通確立了IP地理位置信息批量查詢的需求：

elfin對外提供ip地址數(shù)據(jù)的批量查詢功能：單次請求200條IP數(shù)據(jù)蹭越，集群 2000TPS 時 p99 達(dá)到 10ms 以下。

2. 失敗的嘗試

新增dubbo接口教届，提供批量ip數(shù)據(jù)的查詢功能响鹃，做壓測！案训！壓測結(jié)果很差买置，TPS和rt遠(yuǎn)遠(yuǎn)無法達(dá)到預(yù)期。

image.png

- 優(yōu)化嘗試

開多線程：4核4線程强霎，提升了約 30%的性能忿项。
優(yōu)化查詢算法：從遍歷部分?jǐn)?shù)據(jù)改成二分查找，性能提升不明顯城舞。

- 反思失敗

經(jīng)歷過幾次失敗的嘗試之后轩触，我意識到常規(guī)的優(yōu)化方式很可能難以顯著提高查詢性能，需要深入分析數(shù)據(jù)和算法家夺，找出性能瓶頸脱柱。

現(xiàn)有的datax格式數(shù)據(jù)是一個黑盒，IPIP方面也不愿意透露具體的數(shù)據(jù)編碼方式拉馋，只是大致知道其查詢方法是通過二進(jìn)制按位位移的方式有選擇的遍歷數(shù)據(jù)榨为，難以進(jìn)一步優(yōu)化其查詢方法。

3. 具體實現(xiàn)

- 解決思路

我決定徹底更換數(shù)據(jù)結(jié)構(gòu)和算法煌茴，拋棄IPIP提供的datax數(shù)據(jù)随闺，采取“空間換時間”的方式，使用未經(jīng)壓縮的包含全量IP地理位置信息的txtx格式數(shù)據(jù)景馁。

原始數(shù)據(jù)的特點

IPv4.txtx包含了所有的的IPv4地址板壮，從0.0.0.0到255.255.255.255都有
該數(shù)據(jù)按照IP段的段起始順序排列
所有數(shù)據(jù)的IP段無縫銜接，即前一個IP段的段結(jié)束+1=當(dāng)前IP段的段起始
每條數(shù)據(jù)為 15字節(jié)(IP段起始)+15字節(jié)(IP段結(jié)束)+281(地理位置數(shù)據(jù))
數(shù)據(jù)的主要索引為 IP段的段起始合住，次要的唯一數(shù)據(jù)為 IP段的段結(jié)束绰精。

- 批量查詢請求的特點

由于查詢時入?yún)闊o規(guī)律的IP地址列表撒璧，批量IP地址查詢可以轉(zhuǎn)化為多次單條IP地址查詢，針對單條IP地址的查詢做優(yōu)化笨使。

由于IP數(shù)據(jù)是范圍匹配不是精確匹配卿樱，無法使用諸如HashMap的結(jié)構(gòu)，為保障查詢效率使用TreeMap硫椰，key為IP段的段起始繁调，value存儲全量的IP地理位置信息，核心的查詢方法為：find floor entry靶草。

- 優(yōu)化數(shù)據(jù)結(jié)構(gòu)

在初步構(gòu)建完Demo后我遇到了一個問題：由于IPv4.txtx數(shù)據(jù)本身有近600M而且在不斷增加蹄胰，在未來1-2年內(nèi)可能增加到1G，將所有數(shù)據(jù)全放到一個TreeMap中會導(dǎo)致該TreeMap極大奕翔，每日數(shù)據(jù)更新時會造成多次長時間的FGC裕寨，極為影響系統(tǒng)性能。

我在一次內(nèi)部周會上我提出了這個問題派继，希望能得到一些解決思路宾袜。孫奇根據(jù)需求和數(shù)據(jù)特點提出了一個良好的解決思路：拆分IP段。

解決思路：

參考IP子網(wǎng)劃分和路由的規(guī)則驾窟，將IP的前兩字節(jié)拆分出來作為索引庆猫，指向一顆較小的 TreeMap。在更新過程中逐步替換就可以避免FGC绅络。同時極大的降低了TreeMap的深度月培，提升了查詢效率。

數(shù)據(jù)結(jié)構(gòu)：

二維數(shù)組+TreeMap昨稼。其中节视，二維數(shù)組為 256x256 ，分別對應(yīng)IPv4的前兩字節(jié)假栓，這樣會有65536個TreeMap寻行。每個TreeMap的key為無符號長整型的IP段起始，value存儲IP地理位置信息匾荆。

private TreeMap<Long, IpRangeEntity>[][] treeMaps;

查詢邏輯：

根據(jù)IP的前兩段找到對應(yīng)的TreeMap拌蜘，而后使用 TreeMap 自身的 findfloor 方法來找到對應(yīng)的IP段和IP地理位置信息。

 public IpRangeEntity getValue(int ipFirst, int ipSecond, Long k) {
        TreeMap<Long, IpRangeEntity> tmp = treeMaps[ipFirst][ipSecond];
        Map.Entry<Long, IpRangeEntity> result = tmp == null ? null : tmp.floorEntry(k);
        return result == null ? null : result.getValue();
    }

數(shù)據(jù)插入邏輯：

由于IPv4數(shù)據(jù)是按照IP順序存儲的牙丽，我決定逐行讀取數(shù)據(jù)简卧、解析、并存入TreeMap烤芦。當(dāng)IP段起始的前兩字節(jié)產(chǎn)生變化時举娩，說明此時的IP不屬于當(dāng)前的TreeMap，需要將當(dāng)前TreeMap存入二維數(shù)組，構(gòu)造一個新的TreeMap铜涉，并將此段數(shù)據(jù)存入新TreeMap智玻。
插入分為兩種情況：IP段不跨TreeMap和IP段跨TreeMap。
* 如果一個IP段全部從屬于同一個TreeMap芙代，只需要獲取此段IP的段起始作為key吊奢，將數(shù)據(jù)存入TreeMap即可。

    if (first == getIpPart(ipEnd, 0) && second == getIpPart(ipEnd, 1)) {
            currentMap.put(key, ipRangeEntity);
        }

如果一個IP段同時從屬于兩個或多個TreeMap纹烹，需要將此IP段拆分成多個子段页滚，分別插入到不同的TreeMap中。拆分時只修改IP段的段起始和段結(jié)尾铺呵，子段包含的地理位置信息與拆分前相同裹驰。

else {
            // 65536 = 256^2 16777216 = 256^3
            long lastEnd = Utils.ip2Long(ipRangeEntity.getIpEnd());
            long nextStart = Utils.ip2Long(ipRangeEntity.getIpStart());
            long nextEnd = Math.min(lastEnd, nextStart + 65535);

            IpRangeEntity restIpRange = new IpRangeEntity(ipRangeEntity);
            restIpRange.setIpStart(Utils.long2Ip(nextStart));
            restIpRange.setIpEnd(Utils.long2Ip(nextEnd));
            currentMap.put(nextStart, restIpRange);

            while (nextEnd <= lastEnd) {
                switchTreeMap();

                nextStart = nextEnd + 1;
                nextEnd = Math.min(lastEnd, nextStart + 65535);
                if (nextStart >= nextEnd) break;

                first = (int) (nextStart / (16777216)); // 取ip第一個字段
                second = (int) (nextStart / (65536)) % 256; // 取ip第二個字段
                currentMap = new TreeMap<>();
                restIpRange = new IpRangeEntity(ipRangeEntity);
                restIpRange.setIpStart(Utils.long2Ip(nextStart));
                restIpRange.setIpEnd(Utils.long2Ip(nextEnd));
                currentMap.put(nextStart, restIpRange);
            }
        }

- 優(yōu)化更新邏輯

系統(tǒng)發(fā)布后發(fā)現(xiàn)，線上虛擬機(jī)在更新時CPU使用過高片挂，可能導(dǎo)致查詢請求的rt增高邦马，甚至數(shù)秒內(nèi)服務(wù)不可用。為解決這一問題宴卖，需要引入分布式鎖，將集群中的各個機(jī)器的更新時間錯開邻悬，并且在更新時調(diào)整該機(jī)的負(fù)載均衡權(quán)重症昏，使得該機(jī)流量降低。

4. 總結(jié)

- 數(shù)據(jù)結(jié)構(gòu)的優(yōu)缺點

優(yōu)點：
- 10用戶并發(fā)的情況下父丰，批量查詢200條IP的地理位置信息的耗時可以控制在7ms以內(nèi)肝谭，相比原有數(shù)據(jù)結(jié)構(gòu)的162ms，查詢速度提升20多倍蛾扇。