Amazon S3s密钥背后的数据结构(过滤数据结构)

为了验证我的说法,一个常规的树状图应该足以满足任何有1000000个条目的bucket,这里有一个非常简单的测试用例,它给出了一些数字(注意:这不是一个微基准,它只是为了了解这个问题的严重性)。

java.util.TreeMap 最后问他们 map.subMap(fromKey, toKey) .

public static void main(String[] args) {

    TreeMap<String, Object> map = new TreeMap<String, Object>();

    int count = 1000000;
    ArrayList<String> uuids;

    {
        System.out.print("generating ... ");
        long start = System.currentTimeMillis();
        uuids = new ArrayList<String>(count);
        for (int i = 0; i < count; i++) {
            uuids.add(UUID.randomUUID().toString());
        }
        System.out.println((System.currentTimeMillis() - start) + "ms");
    }

    {
        System.out.print("inserting .... ");
        long start = System.currentTimeMillis();

        Object o = new Object();
        for (int i = 0; i < count; i++) {
            map.put(uuids.get(i), o);
        }

        System.out.println((System.currentTimeMillis() - start) + "ms");
    }

    {
        System.out.print("querying ..... ");

        String from = "be400000-0000-0000-0000-000000000000";
        String to =   "be4fffff-ffff-ffff-ffff-ffffffffffff";

        long start = System.currentTimeMillis();

        long matches = 0;

        for (int i = 0; i < count; i++) {
            Map<String, Object> result = map.subMap(from, to);
            matches += result.size();
        }

        System.out.println((System.currentTimeMillis() - start) + "ms (" + matches/count
                + " matches)");

    }
}

下面是我的机器的一些示例输出(1000000个键,1000000个范围查询):

generating ... 6562ms
inserting .... 2933ms
querying ..... 5344ms (229 matches)

插入一个键平均需要0.003毫秒(当然在接近结束时会更多),而查询229个匹配项的子范围每次查询需要0.005毫秒。那是相当理智的表演,不是吗?

generating ...  59562ms
inserting ....  47099ms
querying ..... 444119ms (2430 matches)

插入一个键平均需要0.005毫秒,而查询一个包含2430个匹配项的子范围每次查询需要0.044毫秒。尽管查询速度慢了10倍(最后,它会遍历所有匹配项,这总是O(n)),但性能也不会太差。

由于S3是一个云服务,我认为它受到了网络的限制。因此,不需要迫切需要一个非常花哨的数据结构来获得所需的性能。尽管如此,我的测试用例中仍然缺少一些特性,最显著的是并发性和持久性。尽管如此,我认为我已经展示了一个规则的树结构对于这个用例来说已经足够了。如果你想做一些新奇的事情,可以尝试使用子树读写锁,或者用.subMap(fromKey,toKey)的替代品;