更改 ID 字符串后 Java 性能严重下降

sfc*_*cme 6 java performance hashmap data-structures

概括

我们最近在复杂的检索引擎中更改了基于字符串的 ID 架构，并观察到严重的性能下降。本质上，我们将 ID 从更改为XXX-00000001到X384840564（有关 ID 架构的详细信息，请参见下文）并遭受几乎翻倍的运行时间。选择不同的字符串哈希函数解决了这个问题，但我们仍然缺乏一个很好的解释。因此，我们的问题是：

为什么在从旧 ID 模式更改为新 ID 模式时，我们会看到如此强烈的性能下降？
为什么我们使用“父哈希”的解决方案实际上有效？

为了解决这个问题，我们在下文中提供了 (a) 有关所使用的 ID 模式和哈希函数的详细信息，(b) 一个 Java 中突出性能缺陷的最小工作示例，以及 (c) 我们的性能结果和观察结果。

（尽管描述很长，但我们已经将代码示例大量减少到 4 条性能关键行——参见清单中的第 2 阶段。）

(a) 旧的和新的 ID 模式；散列函数

我们的 ID 对象由父 ID 对象（[A-Z0-9] 中的 16 个字符的字符串）和子 ID 字符串组成。平均有 1-10 个子 ID 使用相同的父 ID 字符串。例如，旧的孩子 ID有一个三个字母的前缀、一个破折号和一个长度为 8 的零填充运行索引号XXX-00000001（总共 12 个字符；X 可以是任何字母 [AZ]）。的新的子ID具有一个字母和9个非连续的数字，例如，X384840564（共10个字符，X可以是任何字母[AZ]）。一个明显的区别是旧的孩子 ID 字符串经常重复出现（即字符串ABC-00000002出现多个不同的父 ID，因为运行索引通常以 1) 开头，而带有任意数字组合的新子 ID 通常只出现几次，甚至只出现一个父 ID。

由于 ID 对象被放入 HashSets 和 HashMaps，因此哈希函数的选择似乎至关重要。目前，系统对父 ID 使用标准字符串哈希。对于子 ID，我们习惯于对父 ID 和子 ID 的字符串哈希进行异或运算——以下称为XOR 哈希。从理论上讲，这应该很好地分配不同的孩子 ID。作为一种变体，我们尝试仅使用父 ID 的字符串哈希作为子 ID 的哈希码——以下称为父哈希。也就是说，所有共享相同父 ID 的子 ID 共享相同的哈希。理论上，父哈希可能是次优的，因为所有共享相同父 ID 的子节点最终都在同一个桶中，而 XOR 哈希应该会产生更好的数据分布。

(b) 最小工作示例

请参考以下清单（解释如下）：

package mwe;

import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Random;
import java.util.Set;

public class Main {

   private static final Random RANDOM = new Random(42);
   private static final String DIGITS = "0123456789";
   private static final String ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" + DIGITS;
   private static final int NUM_IDS = 5_000_000;
   private static final int MAX_CHILDREN = 5;
   private static final int REPETITIONS = 5;
   private static final boolean RUN_ID_OLD = true; // e.g., 8IBKMAO2T1ORICNZ__XXX-00000002
   private static final boolean RUN_ID_NEW = false; // e.g., 6TEG9R5JP1KHJN55__X580104176
   private static final boolean USE_PARENT_HASH = false;
   private static final boolean SHUFFLE_SET = false;

   private abstract static class BaseID {

      protected int hash;

      public abstract BaseID getParentID();

      @Override
      public int hashCode() {
         return this.hash;
      }

   }

   private static class ParentID extends BaseID {

      private final String id;

      public ParentID(final String id) {
         this.id = id;
         this.hash = id.hashCode();
      }

      @Override
      public BaseID getParentID() {
         return null;
      }

      @Override
      public boolean equals(final Object obj) {
         if (this == obj) {
            return true;
         }

         if (obj instanceof ParentID) {
            final ParentID o = (ParentID) obj;
            return this.id.equals(o.id);
         }
         return false;
      }

      @Override
      public String toString() {
         return this.id;
      }

   }

   private static class ChildID extends BaseID {

      private final String id;
      private final BaseID parent;

      public ChildID(final String id, final BaseID parent) {
         this.id = id;
         this.parent = parent;
         // Initialize the hash code of the child ID:
         if (USE_PARENT_HASH) {
            // Only use the parent hash (i.e., all children have the same hash).
            this.hash = parent.hashCode();
         } else {
            // XOR parent and child hash.
            this.hash = parent.hashCode() ^ id.hashCode();
         }
      }

      @Override
      public BaseID getParentID() {
         return this.parent;
      }

      @Override
      public boolean equals(final Object obj) {
         if (this == obj) {
            return true;
         }
         if (this.hash != obj.hashCode()) {
            return false;
         }

         if (obj instanceof ChildID) {
            final ChildID o = (ChildID) obj;
            final BaseID oParent = o.getParentID();
            if (this.parent == null && oParent != null) {
               return false;
            }
            if (this.parent != null && oParent == null) {
               return false;
            }
            if (this.parent == null || !this.parent.equals(oParent)) {
               return false;
            }
            return this.id.equals(o.id);
         }
         return false;
      }

      @Override
      public String toString() {
         return this.parent.toString() + "__" + this.id;
      }

   }

   public static void run(final int repetitions, final boolean useVariant2IDs) throws IOException {
      for (int i = 0; i < repetitions; i++) {
         System.gc(); // Force memory reset for the next repetition.

         // -- PHASE 1: CREATE DATA --------------------------------------------------------------------------------
         // Fill a set of several millions random IDs. Each ID is a child ID with a reference to its parent ID.
         // Each parent ID has between 1 and MAX_CHILDREN children.
         Set<BaseID> ids = new HashSet<>(NUM_IDS);
         for (int parentIDIdx = 0; parentIDIdx < NUM_IDS; parentIDIdx++) {
            // Generate parent ID: 16 random characters.
            final StringBuilder parentID = new StringBuilder();
            for (int k = 0; k < 16; k++) {
               parentID.append(ALPHABET.charAt(RANDOM.nextInt(ALPHABET.length())));
            }
            // Generate between 1 and MAX_CHILDREN child IDs.
            final int childIDCount = RANDOM.nextInt(MAX_CHILDREN) + 1;
            for (int childIDIdx = 0; childIDIdx < childIDCount; childIDIdx++) {
               final StringBuilder childID = new StringBuilder();
               if (useVariant2IDs) {
                  // Variant 2: Child ID = letter X plus 9 random digits.
                  childID.append("X");
                  for (int k = 0; k < 9; k++) {
                     childID.append(DIGITS.charAt(RANDOM.nextInt(DIGITS.length())));
                  }
               } else {
                  // Variant 1: Child ID = XXX- plus zero-padded index of length 8.
                  childID.append("XXX-").append(String.format("%08d", childIDIdx + 1));
               }
               final BaseID id = new ChildID(childID.toString(), new ParentID(parentID.toString()));
               ids.add(id);
            }
         }
         System.out.print(ids.iterator().next().toString());
         System.out.flush();
         if (SHUFFLE_SET) {
            final List<BaseID> list = new ArrayList<>(ids);
            Collections.shuffle(list);
            ids = new LinkedHashSet<>(list);
         }
         System.gc(); // Clean up temp data before starting the timer.

         // -- PHASE 2: INDEX DATA ---------------------------------------------------------------------------------
         // Iterate over the ID set and fill a map indexed by parent IDs. The map values are irrelevant here, so
         // use empty objects.
         final long timer = System.currentTimeMillis();
         final HashMap<BaseID, Object> map = new HashMap<>();
         for (final BaseID id : ids) {
            map.put(id.getParentID(), new Object());
         }
         System.out.println("\t" + (System.currentTimeMillis() - timer));

         // Ensure that map and IDs are not GC:ed before the timer stops.
         if (map.get(new ParentID("_do_not_gc")) == null) {
            map.put(new ParentID("_do_not_gc"), new Object());
         }
         ids.add(new ParentID("_do_not_gc"));
      }
   }

   public static void main(final String[] args) throws IOException {
      if (RUN_ID_OLD) {
         run(REPETITIONS, false);
      }
      if (RUN_ID_NEW) {
         run(REPETITIONS, true);
      }
   }

}

Run Code Online (Sandbox Code Playgroud)

本质上，程序首先生成一个 ID 的 HashSet，然后通过它们在 HashMap 中的父 ID 对这些 ID 进行索引。详细：

在第一阶段（阶段1），生成用或者500万个父ID的，每个具有1至10个子ID的旧（例如，XXX-00000001）或新的ID的模式（例如，X384840564）和两个散列函数之一。生成的子 ID 收集在 HashSet 中。我们为每个子 ID 显式创建新的父 ID 对象以匹配原始系统的功能。对于实验，可以选择在 LinkedHashSet 中对 ID 进行改组以扭曲基于哈希的排序（参见 boolean SHUFFLE_SET）。

所述第二阶段（阶段2）模拟性能关键路径。它从 HashSet 中读取所有 ID（带有父代的子 ID），并将它们放入一个以父 ID 为键的 HashMap（即按父代聚合 ID）。

注意：实际的检索系统具有更复杂的逻辑，例如从多个集合中读取 ID 并将子 ID 合并为映射条目的值，但结果证明这些步骤中没有一个是造成所讨论的强大性能差距的原因。

其余行尝试控制 GC，以便数据结构不会过早 GC:ed。我们尝试了不同的替代方法来控制 GC，但总体上结果似乎相当稳定。

当运行程序，常量RUN_ID_OLD和RUN_ID_NEW分别激活旧的和新的ID架构，（最好只激活一次一个）。USE_PARENT_HASH在 XOR 散列 (false) 和父散列 (true) 之间切换。SHUFFLE_SET扭曲了 ID 集中的项目顺序。所有其他常量可以保持原样。

(c) 结果

这里的所有结果都基于使用 OpenJDK 11 的典型 Windows 桌面。我们还测试了 Oracle JDK 8 和一台 Linux 机器，但在所有情况下都观察到类似的效果。对于下图，我们在独立运行中测试了每个配置，而每次运行重复计时 5 次。为了避免异常值，我们报告了重复的中位数。但是请注意，重复的时间并没有太大差异。性能以毫秒为单位。

观察：

切换到新的 ID 模式时，使用 XOR 哈希会导致 HashSet 设置的性能大幅下降。这个散列函数似乎不是最理想的，但我们缺乏一个很好的解释。
无论 ID 模式如何，使用父哈希函数都会加快进程。我们推测内部 HashSet 顺序是有益的，因为生成的 HashMap 将建立相同的顺序（因为 ID.hash = ID.parent.hash）。有趣的是，如果将 HashSet 分成 50 个部分，每个部分都包含完整 HashSet 的一个随机分区，也可以观察到这种效果。这让我们感到困惑。
整个过程似乎严重依赖于第二阶段的for循环中的读取顺序（即HashSet的内部顺序）。如果我们扭曲了混洗后的 LinkHashSet 中的顺序，我们最终会陷入最坏的情况，无论 ID 模式如何。
在单独的实验中，我们也对填充HashMap时的碰撞次数进行了诊断，但在更改ID schema时并没有发现明显的差异。

谁能更清楚地解释这些结果？

更新

下图显示了非混洗运行的一些分析结果（使用 VisualVM）。缩进表示嵌套调用。所有百分比值都相对于阶段 2 时间 (100%)。

一个明显的区别似乎是 HashMap.putVal 的自我时间。树化桶没有明显的区别。

归档时间：	4 年，11 月前
查看次数：	131 次
最近记录：	4 年，11 月前