处理键值存储中的集合（列表或集合）的最佳方法是什么？

Question

我想知道当您的存储类似于 memcached 时，从非常大的列表中添加/删除项目的有效方法是什么？ 也许有一些带有Java接口的分布式存储可以很好地处理这个问题？

有人可能会推荐兵马俑。 我知道，但这并不是我所需要的。 ;)

Answer 1

Hazelcast 1.6 将具有分布式实现 MultiMap，其中一个键可以与一组值关联。

MultiMap<String, String> multimap = Hazelcast.getMultiMap ("mymultimap");
multimap.put ("1", "a");
multimap.put ("1", "b");
multimap.put ("1", "c");
multimap.put ("2", "x");
multimap.put ("2", "y");

Collection<String> values = multimap.get("1"); //containing a,b,c

Hazelcast 是队列、主题、映射、集合、列表、锁定和执行人服务。 它非常容易使用； 只需将 hazelcast.jar 添加到类路径中并开始编码即可。 几乎不需要任何配置。

Hazelcast 在 Apache 许可下发布，并且还提供企业级支持。 代码托管于 Google 代码。

Answer 2

也许您还应该看看 Scalaris！

Answer 3

如果忽略并发问题，您可以使用键值存储对大多数数据结构进行建模。 您的要求并不完全清楚，因此我将对您的用例做出一些假设。 希望如果他们不正确，您可以概括该方法。

您可以通过拥有一个已知的根（我们称之为“node_root”）节点来轻松地在存储中创建一个链表，该节点指向 {data, prev_key, next_key} 的值元组。 prev_key 和 next_key 元素是键名称，应遵循约定“node_foo”，其中 foo 是 UUID（理想情况下您可以按顺序生成这些元素，如果不是，您可以使用其他类型的 UUID）。 这提供了对您的数据的有序访问。

现在，如果您需要 O(1) 删除某个键，则可以在结构上添加第二个索引，其中键为“data”，值“node_foo”用于右侧 foo。 然后您可以像处理内存中的链表一样执行删除操作。 完成后删除索引节点。

现在，请记住，并发修改此列表与并发修改任何共享数据结构一样糟糕。 如果您使用的是 BDB 之类的东西，您可以使用它们（出色的）事务支持来避免这种情况。 对于没有事务或并发控制的情况，您需要提供外部锁定或对单个线程的序列化访问。