摘要

我们最近在一个复杂的检索引擎中更改了基于字符串的id模式，并观察到性能严重下降。本质上，我们把身份证从 XXX-00000001 至 X384840564 （关于id模式的详细信息，请参见下面的内容）和几乎加倍的运行时。选择不同的字符串哈希函数解决了这个问题，但我们仍然缺乏一个很好的解释。因此，我们的问题是：
为什么在从旧的id模式更改为新的id模式时会出现如此大的性能下降？
为什么我们使用“父散列”的解决方案真的有效？
为了解决这个问题，我们将在下文中提供（a）关于所使用的id模式和散列函数的详细信息，（b）一个突出性能缺陷的java最小工作示例，以及（c）我们的性能结果和观察结果。
（尽管描述很长，但我们已经将代码示例大量缩减为4行性能关键代码–请参见清单中的第2阶段。）

（a） 新旧身份模式；散列函数

我们的id对象由父id对象（在[a-z0-9]中包含16个字符的字符串）和子id字符串组成。相同的父id字符串平均由1–10个子id使用。例如，旧的子ID有一个三个字母的前缀、一个破折号和一个长度为8的零填充运行索引号， XXX-00000001 （共12字；x可以是任何字母[a-z]）。例如，新的子ID有一个字母和9个非连续数字， X384840564 （共10个字符，x可以是任意字母[a-z]）。一个明显的区别是，旧的子id字符串经常重复出现（即 ABC-00000002 与多个不同的父id一起发生，因为正在运行的索引通常以1开头），而具有任意数字组合的新子id通常只发生几次，甚至仅与单个父id一起发生。
由于id对象被放入hashset和hashmaps中，因此hash函数的选择似乎至关重要。目前，系统对父ID使用标准字符串哈希。对于子id，我们习惯于对父id和子id的字符串散列进行异或运算，从今以后称为异或散列。理论上，这应该可以很好地分配不同的子ID。作为一种变体，我们尝试只使用父id的字符串哈希作为子id的哈希代码，从今以后称为父哈希。也就是说，共享相同父id的所有子id共享相同的哈希。从理论上讲，父散列可能是次优的，因为共享相同父id的所有子散列最终都在同一个bucket中，而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);
      }
   }

}

本质上，程序首先生成一组id，然后在hashmap中按它们的父id索引这些id。具体内容：
第一阶段（第1阶段）生成500万个父ID，每个子ID使用旧ID（例如。， XXX-00000001 )或新的id模式（例如。， X384840564 )两个散列函数中的一个。生成的子id收集在hashset中。我们显式地为每个子id创建新的父id对象，以匹配原始系统的功能。为了进行实验，可以选择在linkedhashset中对ID进行洗牌，以扭曲基于哈希的排序（参见boolean） SHUFFLE_SET ).
第二阶段（第2阶段）模拟性能关键路径。它从hashset中读取所有id（子id及其父id），并将它们放入一个hashmap中，父id作为键（即按父id聚合id）。
注意：实际的检索系统有一个更复杂的逻辑，比如从多个集合中读取id，并将子id合并为map条目的值，但事实证明，这些步骤都不是造成性能差距的原因。
其余的行尝试控制gc，这样数据结构就不会过早地被gc:ed。我们尝试了不同的方法来控制gc，但是结果总体上看起来相当稳定。
运行程序时，常量 RUN_ID_OLD 以及 RUN_ID_NEW 分别激活旧的和新的id模式（最好一次只激活一个）。 USE_PARENT_HASH 在异或哈希（false）和父哈希（true）之间切换。 SHUFFLE_SET 扭曲id集中的项目顺序。所有其他常量都可以保持原样。

（c） 结果

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

观察：
当切换到新的id模式时，使用xor哈希会导致hashset设置的性能大幅下降。这个散列函数看起来不太理想，但我们缺乏一个很好的解释。
不管id模式如何，使用父哈希函数都可以加快进程。我们推测内部hashset顺序是有益的，因为生成的hashmap将建立相同的顺序（因为id.hash=id.parent.hash）。有趣的是，如果散列集被分成50个部分，每个部分都有一个完整散列集的随机分区，也可以观察到这种效果。这让我们感到困惑。
整个过程似乎严重依赖于第二阶段for循环中的读取顺序（即hashset的内部顺序）。如果我们扭曲了无序linkhashset中的顺序，那么不管id模式如何，我们最终都会陷入最坏的情况。
在另一个实验中，我们还诊断了填充hashmap时的冲突数，但在更改id模式时没有发现明显的差异。
谁能更清楚地解释这些结果？

更新

下图显示了非无序运行的一些评测结果（使用visualvm）。缩进表示嵌套调用。所有百分比值均与第2阶段计时（100%）相关。

一个明显的区别似乎是hashmap。putval的自我时间。树型水桶无明显差异。