一段IP查找函数的优化及其它

发表于

intro1：对一段解析17monipdb/ipip.net ip库 函数的 15倍-70倍-300倍 性能优化
intro2: 一个sql count 语句的优化

声明：

  1. 本文代码均为本人所写或可在网上搜索的到的开源代码，遵循开源协议。
  2. 文中引用代码不涉及所就职公司代码，即便有也是本人从开源代码获取，或做了混淆处理。

    起因：

    先看一段某系统中的的IP查询的代码：
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    public class IpParse {
        private static int offset;
        private static int[] index = new int[256];
        private static ByteBuffer dataBuffer;
        private static ByteBuffer indexBuffer;
        ...
        private static ReentrantLock lock = new ReentrantLock();
        public static Area find(String ip) {
            int ip_prefix_value = new Integer(ip.substring(0, ip.indexOf(".")));
            long ip2long_value = ip2long(ip);
            int start = index[ip_prefix_value];
            int max_comp_len = offset - 1028;
            long index_offset = -1;
            int index_length = -1;
            byte b = 0;
            for (start = start * 8 + 1024; start < max_comp_len; start += 8) {
                if (int2long(indexBuffer.getInt(start)) >= ip2long_value) {
                    index_offset = bytesToLong(b, indexBuffer.get(start + 6), indexBuffer.get(start + 5),
                            indexBuffer.get(start + 4));
                    index_length = 0xFF & indexBuffer.get(start + 7);
                    break;
                }
            }
            byte[] areaBytes;
            lock.lock();
            try {
                dataBuffer.position(offset + (int) index_offset - 1024);
                areaBytes = new byte[index_length];
                dataBuffer.get(areaBytes, 0, index_length);
            } finally {
                lock.unlock();
            }
            return new Area(new String(areaBytes).split("\t", -1));
        }
        private static void load() {
            // 读取 ip 库到 dataBuffer
            // dataBuffer 读取并设置 indexBuffer
            ...
        }
    ...
    }

不知道读者看到这段代码是否有所忆，笔者第一眼看到这段代码时，就想起很久前还在用php解析17monipdb的IP库代码，解析部分代码，尤其是256个数组、ip2long等几个ip处理函数，看起来和网上代码的完全一样，只不过这里是参考了c#实现。
17monipdb曾是一个开放的优质的ip库，后来似乎属ipip.net这家公司所有(非官方信息，网上资料较少，从百度结果/代码/数据格式推测)，并另起一收费版ip库。在这之前，更为大家使用的是QQ IP数据库，也叫纯真IP数据库，它最为熟知的是一个叫做 qqwry.dat 的二进制文件。笔者曾在实习的第一家公司时，就是用 C 语言解析 qqwry.dat 的文件，根据IP获取省市信息，至今还依稀记得它分为头信息/数据段/索引段，从索引段读取索引/偏移信息并对数据段建立索引后方可使用，17monipdb/ipip.net也是这个原理，这里看17monip数据格式。

言归正传

当笔者被告知这段代码性能能达到300万/s的查询次时，其实是怀疑的，毕竟有一个大且不可优化的锁lock了查询函数的大部分，事实上性能确实未达到20万/s(下文会附上数据)。
如何优化呢？
先看关键部分，lock.lock()， 这个lock其实是一个ReentrantLock，也就是相当于synchronize，一个完全的悲观锁，虽然java(似乎是1.6以后，对ReentrantLock做了比synchronize好一点的优化),也就是说，这里多线程访问其实是线性的。
为什么这里要lock呢，可以优化吗？
这里用lock是因为涉及的ByteBuffer几个操作不是线程安全的，其实上文 indexBuffer 也同样非 Thread-safe的，只是这里的操作相当于不可变量(immutable)，所以不加锁(lock)也未产生并发问题。正是因为有ByteBuffer的非线程安全操作，所以这里不会采用优化锁的思路去优化，因为首先想到的是ByteBuffer替换为byte数组，这样所有offset/偏移都是方法局部变量，无所谓并发了，企图用ByteBuffer这个所谓的零拷贝技术实在是大材小用/滥用/金玉其外，实际上，七牛就有个byte数组的实现，ip17mon-java，正如其自称“IP 17mon java version, 比官方的速度快很多，支持监视文件改动自动加载”，下文会对其做个benchmark/或对其做个指正，并对比下和笔者B Tree实现的哪个更快。

题外话：为什么这里要lock呢，其实可能还有一个考虑，就是实现者可能想实现动态更新IP库信息(包括文件改动全量更新/部分更新)。
如果全量更新，其实可以有其他lockless的方式优化，就是将IP库信息设置为volatile/autorefference的，更新的时候加锁或CAS方式(这也是下文代码采用方式)，find函数可以采用经典的Doug Lee在JUC包采用的方法local变量保存引用。
如果部分更新，那么不建议这么做，因为要修改索引段数据，索引段本身是个数组，大部分改动不会只是追加的方式，那样不比全量更新改动更少。

但有没有其他更好的或更高性能的实现呢？

我想做的通用一点，且其格式扩展起来方便，或者性能高。
因为是对查找性能要求高，所以首先想到了 BTree，看起来像数据库，实际上，一些数据库实现就有线程安全的BTree可借鉴，这样动态更新很方便。
我们知道Mysql数据库索引的innodb实现就是BTree，比如2000万(好像是)数据通常会用一个三层BTree即可满足，1-4次io就能定位数据，前文几个解析17monipdb的本质上也是个一层的BTree，一层有256个索引分段定位ip位于哪个“段”(类似Mysql的页)，之后就是从该页中进行二分查找，找到该ip所属的条目，该条目携带的信息即是其ip库地址信息。
这里只不过是一层，为了减少内存的花费。
需要先明确的一点，查询时，都会把ip通过移位转化为一个对应的long数值，然后通过long找到对应ip段。
其次，我想做的更通用一点，因为通过第三方渠道获取的IP信息可能只是一行文本数据，不是17monipdb那样的结构化的二进制数据, 且方便其他扩展。
综上，笔者决定采用 B+ Tree和地址数组 的数据结构保存IP库信息(BTree保存IP段->对应地址信息在地址数组下标)。
公司的IP数据也是文本方式提供，而国外就有个免费的基于文本的IP库 Maxmind geoip，它也是logstash官方ip插件在用/ELK等支持的IP库，我们配置logstash ip/地址功能时就是用这个免费IP库。该IP库主要分为两个文件 城市信息和IP段-城市id文件，下载下来后，IP段-城市id文件可能几百MB，加载会耗时，所以需要剔除部分信息。笔者简化后，城市信息/BTree实际占用内存约60MB，而17monipdb在20-30MB左右。

OceanBase/Hsqldb都有java版实现的B+Tree，但改起来麻烦，所以笔者直接用 维基百科上的B+Tree代码。
代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
/**
 * @author https://en.wikibooks.org/wiki/Algorithm_Implementation/Trees/B%2B_tree
 */
public class BPlusTree<V> {
    private Node<V> root;
    private final int M_LEAF;
    private final int N_INNER;
    public BPlusTree(int n) {
        this(n, n);
    }
    public BPlusTree(int m, int n) {
        M_LEAF = m;
        N_INNER = n;
        root = new LeafNode();
    }
    public void insert(long key, V value) {
        Split<V> result = root.insert(key, value);
        if (result != null) {
            InnerNode _root = new InnerNode();
            _root.num = 1;
            _root.keys[0] = result.key;
            _root.children[0] = result.left;
            _root.children[1] = result.right;
            root = _root;
        }
    }
    public V find(long key) {
        Node<V> node = root;
        while (node instanceof BPlusTree.InnerNode) {
            InnerNode inner = (InnerNode) node;
            int idx = inner.getLoc(key);
            node = inner.children[idx];
        }
        LeafNode leaf = (LeafNode) node;
        int idx = leaf.getLoc(key);
        if (idx < leaf.num && leaf.keys[idx]==key) {
            return leaf.values[idx];
        } else {
            return null;
        }
    }
    public V findMinGTE(long key) {
        Node<V> node = root;
        while (node instanceof BPlusTree.InnerNode) {
            InnerNode inner = (InnerNode) node;
            int idx = inner.getLoc(key);
            node = inner.children[idx];
        }
        LeafNode leaf = (LeafNode) node;
        int idx = leaf.getLoc(key);
        if (idx < leaf.num && leaf.keys[idx] == key) {
            return leaf.values[idx];
        } else {
            if (idx < leaf.num) {
                return find(leaf.keys[idx]);
            } else {
                return find(leaf.keys[idx]);
            }
        }
    }
    public static abstract class Node<T> {
        protected int num;
        protected long[] keys;
        abstract public int getLoc(long key);
        abstract public Split<T> insert(long key, T value);
    }
    class LeafNode extends Node<V> {
        @SuppressWarnings("unchecked")
        final V[] values = (V[]) new Object[M_LEAF];
        {
            keys = new long[M_LEAF];
        }
        public int getLoc(long key) {
            for (int i = 0; i < num; i++) {
                if (keys[i] - key >= 0) {
                    return i;
                }
            }
            return num;
        }
        public Split<V> insert(long key, V value) {
            int i = getLoc(key);
            if (this.num == M_LEAF) {
                int mid = (M_LEAF + 1) / 2;
                int sNum = this.num - mid;
                LeafNode sibling = new LeafNode();
                sibling.num = sNum;
                System.arraycopy(this.keys, mid, sibling.keys, 0, sNum);
                System.arraycopy(this.values, mid, sibling.values, 0, sNum);
                this.num = mid;
                if (i < mid) {
                    this.insertNonfull(key, value, i);
                } else {
                    sibling.insertNonfull(key, value, i - mid);
                }
                Split<V> result = new Split<V>(sibling.keys[0],this, sibling);
                return result;
            } else {
                this.insertNonfull(key, value, i);
                return null;
            }
        }
        private void insertNonfull(long key, V value, int idx) {
            if (idx < num && keys[idx] == key) {
                values[idx] = value;
            } else {
                System.arraycopy(keys, idx, keys, idx + 1, num - idx);
                System.arraycopy(values, idx, values, idx + 1, num - idx);
                keys[idx] = key;
                values[idx] = value;
                num++;
            }
        }
    }
    class InnerNode extends Node<V> {
        @SuppressWarnings("unchecked")
        final Node<V>[] children = new Node[N_INNER + 1];
        {
            keys = new long[N_INNER];
        }
        public int getLoc(long key) {
            for (int i = 0; i < num; i++) {
                if (keys[i] - key > 0) {
                    return i;
                }
            }
            return num;
        }
        public Split<V> insert(long key, V value) {
            if (this.num == N_INNER) {
                int mid = (N_INNER + 1) >> 1;
                int sNum = this.num - mid;
                InnerNode sibling = new InnerNode();
                sibling.num = sNum;
                System.arraycopy(this.keys, mid, sibling.keys, 0, sNum);
                System.arraycopy(this.children, mid, sibling.children, 0, sNum + 1);
                this.num = mid - 1;
                Split<V> result = new Split<V>(this.keys[mid - 1], this, sibling);
                if (key - result.key < 0) {
                    this.insertNonfull(key, value);
                } else {
                    sibling.insertNonfull(key, value);
                }
                return result;
            } else {
                this.insertNonfull(key, value);
                return null;
            }
        }
        private void insertNonfull(long key, V value) {
            int idx = getLoc(key);
            Split<V> result = children[idx].insert(key, value);
            if (result != null) {
                if (idx == num) {
                    keys[idx] = result.key;
                    children[idx] = result.left;
                    children[idx + 1] = result.right;
                    num++;
                } else {
                    System.arraycopy(keys, idx, keys, idx + 1, num - idx);
                    System.arraycopy(children, idx, children, idx + 1, num - idx + 1);
                    children[idx] = result.left;
                    children[idx + 1] = result.right;
                    keys[idx] = result.key;
                    num++;
                }
            }
        }
    }
    public static class Split<T> {
        public final long key;
        public final Node<T> left;
        public final Node<T> right;
        public Split(long k, Node<T> l, Node<T> r) {
            key = k;
            left = l;
            right = r;
        }
    }
}
public class IPMaxV2{
    private volatile BPlusTree<Integer> bTree;
    private volatile CityInfo[] cityInfoArray;
   
    public void init(String ipDbMaxPath, String ipCityPath) {
        Map<Long, Integer> cityInfoMap_r = new HashMap<>(110_000);
        cityInfoArray = new CityInfo[110_000];
        String line = null;
        Splitter splitter = Splitter.on(",");
        int i = 0;
        try (BufferedReader br = new BufferedReader(new FileReader(ipCityPath))) {
            /*String */line = br.readLine();
            while ((line = br.readLine()) != null) {
                List<String> arr = splitter.splitToList(line);
                Long id = Long.valueOf(arr.get(0));
                String continentCode = "*"; // 适配ipipnet库 大陆信息为空，配置的AP_新加坡 是机会转化为 *_新加坡
                String countryCode = arr.get(2);
                String country = countryNmaeAdjust(arr.get(3));
                String subCode = arr.get(4);
                String subName = provinceNmaeAdjust(arr.get(3), arr.get(5));
                String cityName= arr.get(6);
                cityInfoArray[i++] = new CityInfo(id, continentCode, countryCode, country, subCode, subName, cityName, arr.get(7));
                cityInfoMap_r.put(id, i);
            }
        } catch (Exception e) {
            // log.error("err line: " + line);
            // log.error("error load maxmind city info", e);
            throw new RuntimeException(e);
        }
        //TODO ip库的问题：1.地域信息都是空的情况（如：86.62.5.0/24,,,,0,1,,,,） 2.是否存在ip跳跃的情况
        long start = System.currentTimeMillis();
        BPlusTree<Integer> bTree_r = new BPlusTree<>(64, 64);
        try (BufferedReader br = new BufferedReader(new FileReader(ipDbMaxPath))) {
            line = br.readLine();
            while ((line = br.readLine()) != null) {
                String[] arr = line.split(",");
                long key = Long.valueOf(arr[0]);
                Long cityId = Long.valueOf(arr[1]);
                // check_insert(key, cityId, arr, bTree_r);
                cityId = (cityId.longValue() != 0) ? cityId:Long.valueOf(arr[1]);
                Integer idx = cityInfoMap_r.get(cityId);
                // System.err.println(line + "--" + idx);
                bTree_r.insert(key, idx);
            }
        } catch (Exception e) {
            // log.error("error load maxmind ip lib", e);
            throw new RuntimeException(e);
        }
        long readEnd = System.currentTimeMillis();
        // log.info("index ip cost: {} ms.", readEnd - start);
        bTree = bTree_r;
        cityInfoMap_r = null;
        // cityInfoArray = cityInfoMap_r;
    }
    public CityInfo find(String ip) {
        long ip_long = convIp2Long2(ip);
        BPlusTree<Integer> bTree_r = bTree;
        Integer id = bTree_r.findMinGTE(ip_long);
        if (null == id) {
            return UNKNOWAREA;
        }
        CityInfo cityInfo = cityInfoArray[id];
        if (null == cityInfo) {
            return UNKNOWAREA;
        }
        return cityInfo;
    }
    public CityInfo find(long ip) {
        long ip_long = ip;
        BPlusTree<Integer> bTree_r = bTree;
        Integer id = bTree_r.findMinGTE(ip_long);
        if (null == id) {
            return UNKNOWAREA;
        }
        CityInfo cityInfo = cityInfoArray[id];
        if (null == cityInfo) {
            return UNKNOWAREA;
        }
        return cityInfo;
    }
    public static CityInfo UNKNOWAREA = new CityInfo(0L, "*", "*", "*", "*", "*", "*", "*");
    static String setOrDefault(String xx) {
        return (null == xx || xx.length() == 0) ? "*" : xx;
    }
    public static int b2int(byte[] origBytes) {
        int value = 0;
        switch (origBytes.length) {
        case 1:
            value = (int) ((origBytes[0] & 0x0F));
            break;
        case 2:
            value = 10 * (int) (origBytes[0] & 0x0F) + (origBytes[1] & 0x0F);
            break;
        case 3:
            value = 100 * (int) (origBytes[0] & 0x0F) + 10 * (origBytes[1] & 0x0F) + (origBytes[2] & 0x0F);
            break;
        default:
            break;
        }
        // return value > 255 ? -1 : value;
        return value;
    }
    public static long convIp2Long2(String ip) {
        String[] ss = ip.split("\\.");
        if (ss.length < 4) {
            return 0;
        }
        int ip_int = (b2int(ss[0].getBytes()) << 24) | (b2int(ss[1].getBytes()) << 16) | (b2int(ss[2].getBytes()) << 8)
                | b2int(ss[3].getBytes());
        long ret_long = ip_int & 0x7fffffffL;
        if (ip_int < 0) {
            ret_long |= 0x080000000L;
        }
        return ret_long;
    }
    @Deprecated
    public static long convIp2Long(String ip) {
        String[] ss = ip.split("\\.");
        int ip_int = (Integer.parseInt(ss[0]) << 24) | (Integer.parseInt(ss[1]) << 16) | (Integer.parseInt(ss[2]) << 8)
                | Integer.parseInt(ss[3]);
        long ret_long = ip_int & 0x7fffffffL;
        if (ip_int < 0) {
            ret_long |= 0x080000000L;
        }
        return ret_long;
    }
   
    static void addPrivateNetInfo(BPlusTree<Long> bTree, Map<Long, CityInfo> cityInfoMap) {
        // ipv4 国际保留地址
        String ipInfo = "16777215,1,1;184549375,1,1;1686110207,1,1;2147483647,1,1;2852061183,1,1;"
                + "2887778303,1,1;3221225727,1,1;3221225479,1,1;3221225480,1,1;3221225481,1,1;"
                + "3221225482,1,1;3221225642,1,1;3221225643,1,1;3221226239,1,1;3223307519,1,1;"
                + "3224683007,1,1;3227018239,1,1;3232301055,1,1;3232706815,1,1;3323199487,1,1;"
                + "3325256959,1,1;3405804031,1,1;4026531839,1,1;4294967295,1,1;4294967295,1,1";
        for (String ipip : ipInfo.split(";")) {
            String[] line = ipip.split(",");
            check_insert(Long.valueOf(line[0]), Long.valueOf(line[1]), line, bTree);
        }
        cityInfoMap.put(1L, new CityInfo(1L, "保留地址", "保留地址", "保留地址", "保留地址", "保留地址", "保留地址", "*"));
        cityInfoMap.put(0L, new CityInfo(0L, "未定义", "未定义", "未定义", "未定义", "未定义", "未定义", "*"));
    }
...
}
public class CityInfo {
    private long id;
    private String continentCode;
    private String countryCode;
    private String countryName;
    private String subCode;
    private String subName;
    private String cityName;
    private String timeZone;
    ...getter/setter
}

解释：

  1. 这里的find不是标准的BTree find 方法，因为存储的是IP段，所以BTree节点存的是IP界限，查询时对于查找不到返回null的[常见]会再次追溯父节点，返回大于该数值的最小(右侧最左)的节点，即 findGTE方法。
  2. 简单起见，代码中保证IP段连续/保留IP段这些没加进来，但是必须的，否则可能导致结果不准确。

下面是BenchMark数据

使用 JMH 测试的性能，2-32线程:
target_ipparse表示原来的方法，target_localtor为七牛开源的解析方法，target_maxmindv2为笔者的B Tree方法。硬件为2017年 8G i5 new Mac，JDK信息如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
# JMH version: 1.21
# VM version: JDK 1.8.0_151, Java HotSpot(TM) 64-Bit Server VM, 25.151-b12
# VM invoker: /Library/Java/JavaVirtualMachines/jdk1.8.0_151.jdk/Contents/Home/jre/bin/java
# VM options: -Dfile.encoding=UTF-8
# Warmup: 1 iterations, 10 s each
# Measurement: 3 iterations, 10 s each
# Timeout: 10 min per iteration
# Threads: 2 threads, will synchronize iterations
# Benchmark mode: Throughput, ops/time
....
# 2 线程
Benchmark                Mode  Cnt     Score      Error   Units
JMHIP.target_ipparse    thrpt    3   113.956 ±  391.000  ops/ms
JMHIP.target_localtor   thrpt    3  1846.572 ± 3566.676  ops/ms
JMHIP.target_maxmindv2  thrpt    3  1995.854 ±  125.343  ops/ms
# 4 线程
Benchmark                Mode  Cnt     Score      Error   Units
JMHIP.target_ipparse    thrpt    3   137.426 ±   18.704  ops/ms
JMHIP.target_localtor   thrpt    3  1847.472 ±  951.733  ops/ms
JMHIP.target_maxmindv2  thrpt    3  1817.778 ± 3347.274  ops/ms
# 8 线程
Benchmark                Mode  Cnt     Score     Error   Units
JMHIP.target_ipparse    thrpt    3   140.642 ±  79.715  ops/ms
JMHIP.target_localtor   thrpt    3  1888.104 ± 439.820  ops/ms
JMHIP.target_maxmindv2  thrpt    3  2040.365 ± 336.506  ops/ms
# 16 线程
Benchmark                Mode  Cnt     Score     Error   Units
JMHIP.target_ipparse    thrpt    3   139.092 ±  33.246  ops/ms
JMHIP.target_localtor   thrpt    3  1792.992 ± 396.497  ops/ms
JMHIP.target_maxmindv2  thrpt    3  2077.337 ± 278.774  ops/ms
# 32 线程
Benchmark                Mode  Cnt     Score      Error   Units
JMHIP.target_ipparse    thrpt    3   110.591 ±  128.144  ops/ms
JMHIP.target_localtor   thrpt    3  1538.003 ± 1925.825  ops/ms
JMHIP.target_maxmindv2  thrpt    3  2079.801 ±  838.722  ops/ms

JMH类:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
...
@State(Scope.Benchmark)
@BenchmarkMode(Mode.Throughput)
@OutputTimeUnit(TimeUnit.MILLISECONDS)
public class JMHIP {
    static Locator locator;
    static IpParse ipParse;
    static IPMaxV2 ipmaxv2;
    @Setup
    public void target_blank() throws IOException {
        locator = Locator.loadFromLocal("/Users/thomas/git/17monipdb.dat");
        System.out.println(locator.find("220.255.1.166"));
       
        ipmaxv2 = new IPMaxV2();
        ipmaxv2.init("/Users/thomas/git/maxmind_ip_data", "/Users/thomas/git/maxmind_city_data");
        System.out.println(ipmaxv2.find("220.255.1.166"));
        ipParse.load("/Users/thomas/git/17monipdb.dat");
        System.out.println(ipParse.find("220.255.1.166"));
    }
    // @CompilerControl(CompilerControl.Mode.INLINE)
    @Benchmark
    public void target_localtor() {
        locator.find("220.255.1.166");
    }
    @Benchmark
    public void target_maxmindv2() {
        ipmaxv2.find("220.255.1.166");
    }
    @Benchmark
    public void target_maxmindv2long() {
        ipmaxv2.find(16819199l);// 16819199 3707699622
    }
    @Benchmark
    public void target_ipparse() {
        ipParse.find("220.255.1.166");
    }
    public static void main(String[] args) throws RunnerException {
        Options opt = new OptionsBuilder().include(JMHIP.class.getSimpleName()).warmupIterations(1)
                .measurementIterations(3).threads(16).forks(1).build();
        new Runner(opt).run();
    }
}

针对这个结果几个有趣总结：

  1. 几轮结果，ipparse/localtor 都是8线程(4核)时性能最好，而 maxmindv2比较稳定。
  2. 老的ipparse性能其实只有15万/s不到的吞吐量，localtor比maxmindv2稍微差点，但也可达到200万/s的吞吐量

对于1，说明ipparse/localtor在更大如200线程并发时，性能其实会更差，甚至达不到10万/s，虽然对应用可能足够，但是和声称的差距还是蛮大的。
对于1，localtor似乎是无锁的，竟然也会因线程增长而减少，有点意外。另外如果仔细看 Localtor代码，可以发现其文件流/URL流都没有规范的关闭，AutoReload的那个类不够并发安全。
对于2，奇怪的是maxmindv2怎么始终不变？是不是还漏了哪里的明显的性能优化点？

更多

实际上：

  1. 是的，find(String ip) 这个方法里，convIp2Long2(ip)也耗费许多性能，如果用 find(long ip)替代，还可以有 5倍性能的提升！(一个快速把字符串ip转化为long数字的方法就是使用查表方法，毕竟只额外需一个长度为256的数组)。
    见 下文benchmark数据。
  2. 上述ip 220.255.1.166或者说3707699622，其实是一个B+ Tree首次未命中的情况，如果首次命中性能会怎样？可以再有24倍的性能提升！做到这点其实不难，可以在创建B+ Tree索引时，叶节点加一个指针指向他的下一个兄弟叶节点。
    这个是jmh数据，这也是为什么上文采用 220.255.1.166这个IP，因为它可以代表大多数差性能下的查询。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    # 16 线程   string ip -> long ip : 3707699622
    Benchmark                    Mode  Cnt     Score      Error   Units
    JMHIP.target_maxmindv2      thrpt    3  2110.476 ±  647.039  ops/ms
    JMHIP.target_maxmindv2long  thrpt    3  9010.649 ± 1973.710  ops/ms
    # 16 线程   string ip -> long ip + 命中 : 16819199
    Benchmark                    Mode  Cnt      Score       Error   Units
    JMHIP.target_maxmindv2      thrpt    3   2068.251 ±   178.626  ops/ms
    JMHIP.target_maxmindv2long  thrpt    3  46669.170 ± 28929.424  ops/ms

总结下来，使用B Tree和优化convIp2Long2可以有70倍性能提升的，这还是在ipparse 表现最好情况下，如果再优化BTree首次命中情况，就会有约300倍性能提升了。

SQL count(id)

几个月前，朋友问的一个问题，是我几年前写的系统，大概是定时刷Mysql数据库的任务，3分钟一次，数据量最近破千万了，加了功能，发现任务耗时超过了3分钟，咨询我优化下。
N年不做数据库相关的我，不再熟练sql优化了，看到代码里sql语句其实还是有种放弃的感觉，但好在看到有几条类似：
select count(*) from xxx
的统计sql,id就是各个表的主键索引，试着把它换为 count一个二级索引，即一个非空且index的列：
select count(*) from xxx where uid > 0
耗时还是能从4秒多提升到0.37秒。勉强挤进2分半了。
因为第一种要全表扫描，但是mysql innodb 的clustered index其实把主键和行数据存放在一起的[这也是为什么列存储兴起]，但二级索引(secondary index)不会包含，仅记录主键指向行记录。
对于用count(*)/count(id)统计表记录总数时，利用二级索引进行count会快些。