Amazon S3s 密钥背后的数据结构（过滤数据结构）

我想实现一个类似于 Amazon S3 的查找功能的数据结构。就上下文而言，Amazon S3 将所有文件存储在平面命名空间中，但允许您通过文件名中的公共前缀查找文件组，从而复制目录树的功能，但又不那么复杂。

问题是，查找和过滤操作都是 O(1)（或者足够接近，即使在非常大的存储桶上 - S3 的磁盘等效项 - 两个操作也可能是 O(1)））。

简而言之，我正在寻找一种功能类似于哈希图的数据结构，并具有高效（至少不是 O(n)）过滤的额外好处。我能想到的最好的方法是扩展 HashMap，使其还包含一个（排序的）内容列表，并对与前缀匹配的范围进行二分搜索，然后返回该集合。这对我来说似乎很慢，但我想不出任何其他方法来做到这一点。

有谁知道亚马逊是如何做到的，或者有更好的方法来实现这种数据结构？

只是为了验证我的主张，即常规 TreeMap 应该足以满足任何包含多达 1,000,000 个条目的存储桶，这里有一个非常简单的测试用例，它给出了一些数字（注意：这并不是一个微基准测试，只是为了感受一下这个问题的严重程度）。

我使用随机生成的 UUID 来模拟按键（如果您用斜杠替换破折号，您甚至会得到一种目录结构）。之后，我将它们放入常规中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)");

    }
}

这是我的机器的一些示例输出（1,000,000 个键，1,000,000 个范围查询）：

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

插入 1 个键平均花费 0.003 毫秒（当然，接近结束时花费的时间更长），而查询包含 229 个匹配项的子范围每个查询花费 0.005 毫秒。这是相当理智的表现，不是吗？

将数量增加到 10,000,000 个键和查询后，数量如下：

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

插入 1 个键平均需要 0.005 毫秒，而查询具有 2430 个匹配项的子范围每次查询需要 0.044 毫秒。尽管查询速度慢了 10 倍（最后，它会迭代所有匹配项，且始终为 O(n)），但性能仍然还不错。

由于 S3 是一项云服务，我认为它无论如何都会受到网络的限制。因此，并不迫切需要非常奇特的数据结构来获得所需的性能。尽管如此，我的测试用例仍然缺少一些功能，最明显的是并发性和持久性。尽管如此，我认为我已经证明常规树结构足以满足此用例。如果你想做一些奇特的事情，可以尝试子树读写锁定，也许可以替代 .subMap(fromKey, toKey);