编年史映射中的多重映射

16

ChronicleMap的GitHub上肯定有关于Multimaps in ChronicleMap的免责声明:

Chronicle Map不是...

...没有二级索引。

一个Multimap。使用ChronicleMap<K,Collection<V>>作为Multimap在技术上是可能的,但通常会导致问题...

不幸的是,这是我的一个用例,使用ChronicleMap的堆外存储肯定是最简单的方法。

让我试着用披萨来解释我的问题。我有100,000个不同的比萨饼。每个比萨饼都有一个ID和许多不同的配料和饼皮。我有三种访问模式:

  • 按ID给我比萨饼。
  • 给我所有具有特定配料的比萨饼。
  • 给我所有具有特定饼皮的比萨饼。
我可以使用ChronicleMap<UUID,Pizza>轻松地存储披萨。但这只是一种访问模式。我不想遍历每个披萨来查找具有匹配的配料或皮脆的披萨。因此,我想存储类似于ChronicleMap<Topping,Collection<UUID>>ChronicleMap<Crust,Collection<UUID>>的东西。

然后,如果有人要求所有配有意大利辣香肠的披萨,我会在顶部的ChronicleMap中查找匹配披萨的UUID,然后在主披萨映射中查找。

但上面引用的文档让我害怕。有人知道这种事情经常导致的“问题”可能是什么吗?即使这对我似乎有效,为什么我不应该这样做?这是否与ChronicleMap如何存储序列化对象有关,特别是集合?

一些潜在问题的额外说明:

  1. 我们以后可能会添加需要更新集合的披萨。
  2. 许多进程正在尝试执行这些操作,因此需要通过ChronicleMap共享映射,而不仅仅是基本的ConcurrentMap。
1个回答

26

如果实际数据确实像披萨一样,有配料和面皮,即只有少数不同的配料/面皮,并且成千上万的披萨都包含其中之一,我会说在这种情况下拥有适当的多重映射是过度的,你最好有 pepperoni_pizzas.datonions_pizzas.dat,...不同的可附加共享列表与UUID,您可以使用Chronicle Queue方便地从多个进程访问和更新它们。

如果有10万到100万个配料/面皮,平均只有10到100个披萨有特定的配料,那么确实应该使用多重映射。

基本上,Chronicle-Maps作为多重映射存在三种“问题”:

每次查询都会产生过多的垃圾分配

如果创建一个带有List<UUID>Set<UUID>类型值的Chronicle Map而没有指定自定义值序列化程序,则它将工作,但它将非常低效,因为它将默认使用内置的Java序列化来序列化和反序列化整个值集合,并且不会重复使用集合堆对象或单个UUID堆对象的元素。因此,每次请求ChronicleMap时都会生成大量垃圾。

解决方案 但是,如果您将值序列化程序指定为ListMarshallerSetMarshaller(或基于ListMarshallerSetMarshaller实现编写的自定义集合marshaller),以及可重复使用的UUID堆对象,它将解决此垃圾问题:

ListMarshaller<ReusableUuid> valueMarshaller = ListMarshaller.of(
     ReusableUuidReader.INSTANCE, ReusableUuidWriter.INSTANCE);
List<ReusableUuid> averageValue = Stream
    .generate(() -> ReusableUuid.random())
    .limit(averagePizzasForTopping)
    .collect(Collectors.toList());
 ChronicleMap<Topping, List<ReusableUuid>> map = ChronicleMap
     .of(Topping.class, (Class<List<ReusableUuid>>) (Class) List.class)
     .averageKey(pepperoni)
     .valueMarshaller(valueMarshaller)
     .averageValue(averageValue)
     .entries(numberOfToppings)
     .createPersistedTo(new File("toppings_to_pizza_ids.dat"));

低效的值更新和复制

当您将另一个披萨UUID附加到100个UUID列表中,并将新值插入回Chronicle Map时,Chronicle Map将重新编写整个列表,而不是将一个UUID附加到非易失性内存块的末尾。如果使用复制,则会将包含100个UUID的整个列表作为更新后的值发送到其他节点,而不仅仅是发送添加的一个UUID。

这两者(值更新和复制)都可以通过可怕的黑科技进行优化,但这需要对Chronicle Map实现有非常深入的了解,并且非常脆弱。

Chronicle-Map的内存碎片化

如果在数据存储期间计划添加新的披萨,则最初分配给条目的内存区域将变得太小,无法容纳具有更多UUID的新值,因此将重新分配内存区域(对于每个UUID列表可能会重新分配多次)。Chronicle Map的数据结构设计意味着简化的内存分配方案,在大量重新分配条目的情况下,会遭受严重的碎片化问题。

如果您在Linux上运行应用程序,并且列表中有很多UUID,请通过在ChronicleMapBuilder配置中指定.actualChunkSize()并依赖于Linux的懒惰映射内存分配功能(逐页分配,根据需要),为每个条目预先分配大量的内存(多于任何列表实际上需要的)。因此,您将最多为每个UUID列表损失4KB的内存,如果列表的大小为几KB,则这可能是可以接受的。

另一方面,如果您的列表很长(它们是UUID的列表,即小结构),并且总共只有100,000个披萨,则首先不需要使用multimap,参见本回答开头。

对于值的短列表(集合),可以通过内存超额提交和依赖于Linux的懒惰映射内存分配方式来解决问题,但仅当元素本身很大时才能起作用,因此平均总值大小为数KB。

如果可以以其他方式避免条目内存重新分配,即添加新的披萨UUID,但也删除它们,则配料到UUID列表大小围绕某个平均值浮动,而重新分配很少被触发,则碎片化也不是一个问题。

如果在Chronicle Map中插入条目后从未更新过值(或值从未更改过大小),则内存碎片化永远不是问题。

结论

在某些用例中,并且使用适当的配置,Chronicle Map可以很好地用作multimap。在其他情况下,Chronicle Map作为multimap固有地效率低下。

影响因素包括:

  • multimap中键-> List<Value> 条目的总数
  • 值的总数
  • 键大小的平均值和分布
  • 不同值大小的平均值和分布
  • 值列表大小的平均值和分布
  • 值列表在Chronicle Map生命周期中的动态(从未更新,仅附加,删除并附加。从列表开头和中间删除的成本更高。)
  • Chronicle Map是否被复制

1
这非常有帮助,可能是我在Stack Overflow上得到的最好的答案。真希望我能给你点赞两次。非常感谢! - Depressio
关于 ListMarshaller 的问题。如果我不使用 UUID,而是只使用整数(更简单),那么我是否仍需要为整数创建读/写编组器?似乎已经有一个 IntegerMarshaller,所以我可能只需执行 ListMarshaller.of(IntegerMarshaller.INSTANCE) - Depressio
@Depressio,Integer类与UUID存在相同的问题-它是不可变的,因此每次反序列化都需要创建大量对象,需要使用ListMarshaller。在整数的情况下,复制整个ListMarshaller类并将其专门用于读写原始int而不是通用元素可能更容易且更有效率。您还可以使用专门的原始容器(例如来自fastutil库)进行堆上存储,而不是通用的ArrayList。 - leventov
@Depressio应该简化为基本类型 - 而不是对象。即MutableUUID应该有两个字段:long mostSigBits,long leastSigBits(与原始UUID相同),但这些字段可重置。如果应用某些去重技术,并且String内容经常相同,也可以保留Strings不变。 - leventov
@Depressio 建立这些对象的层次结构可能非常繁琐,但是Chronicle Values有时可以提供帮助--请参见示例 - leventov
显示剩余8条评论

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文,
原文链接