performance improvement for jedis cluster info cache

[chenshi5012]

@yangbodong22011 @sazzad16

i notice that our cache for slots pool slotsnode use hashmap.
https://github.com/redis/jedis/blob/master/src/main/java/redis/clients/jedis/JedisClusterInfoCache.java#:~:text=public%20class%20JedisClusterInfoCache%20%7B,slotNodes%20%3D%20new%20HashMap%3C%3E()%3B

since slots numbers 16384, so the size of slots /slotNodes should be 16384;

for exampe : redis cluster got 3 nodes:
// M: 641995fea69ee31d24fbcfec741046255c551f71 127.0.0.1:7379
// slots:[0-5460] (5461 slots) master
// M: acab2c371826441e0927e2389785b5a213564d15 127.0.0.1:7380
// slots:[5461-10922] (5462 slots) master
// M: d72cddef3553ec6ee70b81fabb3b0179cb8b9ccc 127.0.0.1:7381
// slots:[10923-16383] (5461 slots) master

the structure for slotNodes size will be 16384, mapping ship like :
{0=127.0.0.1:7379, 1=127.0.0.1:7379, 2=127.0.0.1:7379, 3=127.0.0.1:7379 ........ 16382=127.0.0.1:7381, 16383=127.0.0.1:7381}

since all slots present as number, so [0, 1,2,3,4,5.....5460] , can be mapduce to [0~5460] , after mapreduce
the structure for slotNodes size will be 3
{0=127.0.0.1:7379, 5461=127.0.0.1:7380, 10923=127.0.0.1:7381}

mappingship switch to
{
05460:127.0.0.1:7379,
546110922:127.0.0.1:7380,
10923~16383:127.0.0.1:7381,
}
: seems better. In theory, there is an improvement in performance。

i mapreduce to 3 keys, use treemap(lowerkey, talMap.firstKey) . but compare with hashmap： Search efficiency

but， In practice Very strange， Completely wrong ！！！！

hashmap（16384keys）seemsbetter than treemap（>3keys）.lowerkey for treemap use tree structure. (slower than hashmap structure)

is there any best Practices?

[chenshi5012]

`package cluster;

import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.TreeMap;

public class TestMap {

private static int[] slotsStart;

public static void main(String[] args) {

// M: 641995fea69ee31d24fbcfec741046255c551f71 127.0.0.1:7379
// slots:[0-5460] (5461 slots) master
// M: acab2c371826441e0927e2389785b5a213564d15 127.0.0.1:7380
// slots:[5461-10922] (5462 slots) master
// M: d72cddef3553ec6ee70b81fabb3b0179cb8b9ccc 127.0.0.1:7381
// slots:[10923-16383] (5461 slots) master
// pipelines.tailMap(slot).firstKey()
// private final Map<Integer, HostAndPort> slotNodes = new HashMap<>();

    TreeMap<Integer, String> treeMap = new TreeMap<>();
    HashMap<Integer, String> hashMap2 = new HashMap<>();
    for (int i = 0; i < 16384; i++) {
        if (i <= 5460) {
            treeMap.put(i, "0-5460");
            hashMap2.put(i, "0-5460");
        } else if (i >= 5461 && i <= 10922) {
            treeMap.put(i, "5461-10922");
            hashMap2.put(i, "5461-10922");
        } else if (i >= 10923 && i <= 10927) {
            treeMap.put(i, "5461-10922");
            hashMap2.put(i, "5461-10922");
        } else if (i >= 10928) {
            treeMap.put(i, "10923-16383");
            hashMap2.put(i, "10923-16383");
        }
    }

    mapReduceBySlot(treeMap);

    for (int i = 0; i < 16384; i++) {
        if (!hashMap2.get(i).equals(treeMap.get(treeMap.tailMap(i).firstKey()))) {
            System.out.println("wrong:" + i + ":" + treeMap.get(treeMap.tailMap(i).firstKey()));
        }
    }


    long start = System.currentTimeMillis();
    for (int j = 0; j < 10000; j++) {
        for (int i = 0; i < 16384; i++) {
            hashMap2.get(i);
        }
    }
    long start2 = System.currentTimeMillis();
    for (int j = 0; j < 10000; j++) {
        for (int i = 0; i < 16384; i++) {
            treeMap.get(treeMap.tailMap(i).firstKey());
        }
    }
    long start3 = System.currentTimeMillis();

    System.out.println("hashmap: {size:" + hashMap2.size() + ",use:" + (start2 - start) + "} vs treemap: {size:" + treeMap.size() + ",use:" + (start3 - start2) + "}");

}


private static void mapReduceBySlot(TreeMap<Integer, ?> treeMap) {
    Iterator<? extends Map.Entry<Integer, ?>> iterator = treeMap.entrySet().iterator();
    while (iterator.hasNext()) {
        Map.Entry<Integer, ?> temp = iterator.next();
        Integer lowerKey = treeMap.higherKey(temp.getKey());
        if (lowerKey != null && temp.getValue().equals(treeMap.get(lowerKey))) {
            iterator.remove();
        }
    }
}

}`

[chenshi5012]

hashmap: {size:16384,use:812} vs treemap: {size:3,use:2593}

[chenshi5012]

@yangbodong22011 @sazzad16 compare with hashmap, treemap aslo arrays.
arrays show with good performance。 #3373

[sazzad16]

@chenshi5012 Could you provide any numbers?

[chenshi5012]

@chenshi5012 Could you provide any numbers?

hashmap: {size:16384,use:812} vs treemap: {size:3,use:2593}

The addressing time of the array is infinitely close to 0 . so we abandon treemap or hashmap. just select arrays. please check
#3373

[chenshi5012]

@chenshi5012 Could you provide any numbers?

and i check the sturture about treemap, it use Red-Black tree, so the search performed slower than hashmap .

[chenshi5012]

@sazzad16 since arrays took 0 seconds . i make same measured data： Reduce 7s for every 10w pieces of data

10w records, use pipelined (arrays cache) to get/set, reduce:7344ms
20w records, use pipelined (arrays cache) to get/set, reduce:14379ms
30w records, use pipelined (arrays cache) to get/set, reduce:21443ms
40w records, use pipelined (arrays cache) to get/set, reduce:28814ms
50w records, use pipelined (arrays cache) to get/set, reduce:36094ms
60w records, use pipelined (arrays cache) to get/set, reduce:43600ms
70w records, use pipelined (arrays cache) to get/set, reduce:50881ms
80w records, use pipelined (arrays cache) to get/set, reduce:58155ms
90w records, use pipelined (arrays cache) to get/set, reduce:65542ms
100w records, use pipelined (arrays cache) to get/set, reduce:73172ms

This optimization is included in #3373 ， please take a code review , and i wonder this could be merge in next stable 4.x version . thanks. ^_^

[sazzad16]

@chenshi5012 Thank you for the numbers.

1. What does w mean? E.g. 10w.
2. You summarize as reduce:; is it time reduced from using HashMap to using array?

[chenshi5012]

@chenshi5012 Thank you for the numbers.

1. What does w mean? E.g. 10w.
2. You summarize as reduce:; is it time reduced from using HashMap to using array?

1. 10w means “100,000”, w means "10K" , 10w (in chinese, sorry for me poor english ) means 100K. ^_^
2. yes， use arrays will reduce the slots/slotNodes retrieval time.

[yangbodong22011]

PR has been merged, closed by #3373