自动完成服务器端实现

performance memory java autocomplete

2022-09-01 23:42:00

在 html 输入框中实现自动完成功能的服务器端组件的快速有效方法是什么？

我正在编写一个服务，用于在Web界面的主搜索框中自动完成用户查询，并且完成显示在ajax驱动的下拉列表中。我们运行查询的数据只是一个大型的概念表，我们的系统知道它，它与维基百科页面标题集大致匹配。对于这项服务，速度显然至关重要，因为网页的响应能力对用户体验很重要。

当前的实现只是将所有概念加载到排序集的内存中，并在用户击键时执行简单的log（n）查找。然后，尾集用于提供最接近匹配项之外的其他匹配项。此解决方案的问题在于它无法扩展。它目前运行在VM堆空间限制（我已经设置了-Xmx2g，这大约是我们可以在32位机器上推送的最多），这阻止了我们扩展概念表或添加更多功能。在具有更多内存的计算机上切换到 64 位 VM 不是立即选择。

我一直犹豫是否要开始开发基于磁盘的解决方案，因为我担心磁盘寻道时间会扼杀性能。有没有可能的解决方案可以让我更好地扩展，无论是完全在内存中还是通过一些快速的磁盘支持的实现？

编辑：

@Gandalf：对于我们的用例，重要的是自动完成是全面的，而不仅仅是对用户的额外帮助。至于我们正在完成的内容，它是概念类型对的列表。例如，可能的条目是[（“Microsoft”，“Software Company”），（“Jeff Atwood”，“Programmer”），（“StackOverflow.com”，“Website”）]。一旦用户从自动完成列表中选择一个项目，我们将使用Lucene进行完整搜索，但我不确定Lucene是否适用于自动完成本身。

@Glen：此处未使用任何数据库。当我谈论表时，我只是指数据的结构化表示。

@Jason日：我对这个问题的原始实现是使用Trie，但是由于需要大量的对象引用，因此内存膨胀实际上比排序集更糟糕。我将阅读三元搜索树，看看它是否有用。

答案 1

对于这么大的集合，我会尝试像Lucene索引这样的东西来找到你想要的术语，并设置一个计时器任务，该任务在每次击键后重置，延迟为0.5秒。这样，如果用户快速键入多个字符，则它不会每次笔画都查询索引，只有当用户暂停一秒钟时才会查询索引。可用性测试将让您知道暂停应该多长时间。

Timer findQuery = new Timer();
...
public void keyStrokeDetected(..) {
   findQuery.cancel();
   findQuery = new Timer();
   String text = widget.getEnteredText();
   final TimerTask task = new TimerTask() {
      public void run() {
         ...query Lucene Index for matches
      }
   };
   findQuery.schedule(task, 350); //350 ms delay
}

那里有一些伪代码，但这就是这个想法。此外，如果设置了查询词，则可以预先创建和优化Lucene索引。

答案 2

我有类似的要求。

我将关系数据库与单个索引良好的综合表（避免联接和视图以加快查找速度）和内存中缓存（Ehcache）一起使用来存储最常用的条目。

通过使用MRU缓存，您将能够对大多数查找进行即时响应时间，并且在访问存储在磁盘上的大表中的索引列时，可能没有什么可以击败关系数据库。

这是无法存储在客户端上的大型数据集的解决方案，并且它的工作速度非常快（在我的情况下，非缓存查找始终在0.5秒内检索）。它还具有水平可扩展性 - 您可以随时添加其他服务器和数据库服务器。

您还可以在客户端上仅使用最常用的结果进行缓存，尤其是在您已经实现它的情况下。在我的情况下，服务器端解决方案足够快，并且客户端加载时间足够慢，因此不需要保证。

附言：仅当用户暂停一定时间以避免建议重复查找时，才进行客户端查询是一个很好的解决方案。在我的客户端上，我只在输入前三个字符后查询数据库，因为小于该值会在所有实例中返回太多结果。