Skip to content

四火的唠叨

一个纯正程序员的啰嗦

Menu
  • 所有文章
  • About Me
  • 关于四火
  • 旅行映像
  • 独立游戏
  • 资源链接
Menu

常见分布式应用系统设计图解(四):输入建议系统

Posted on 09/12/202008/14/2022 by 四火

输入建议系统,指的就是 “typeahead”,比如 Google 搜索,输入一个单词的前几个字母,后面最常用的几个搜索词会被联想出来。有时,它也需要具备一定程度的字符拼写错误自动更正能力。

比如上面这张截图,我输入了 “goog”,在输入框的下方列出了最常见的几个以 goog 开头的搜索短语。

  • 这个功能可以说不是搜索系统的核心功能,而且要求响应一定要非常迅速,考虑到无法避免的网络延迟,我们希望服务端的处理越快越好。响应数据不用非常准确,但是延迟响应肯定是一个糟糕的结果。所以我们希望服务端的处理的数据尽量都在内存中,几乎不需要怎么读取磁盘,整个过程也要保持简洁。
  • 用户侧的浏览器方面,有这么几件事情比较重要:缓存之前的提示数据;
    • 数据不一定只从服务端返回,浏览器也有本地的历史查询记录(比如 Cookie),提示列表可以是二者的并集;
    • 用户打开页面或者选中焦点框就要开始建立连接,从而在输入后节省连接建立时间;
    • 用户每输入一个字符,不要马上去询问服务器,而是等 100 毫秒,没有接着敲字符再发起请求;
    • 由于无法预料响应到达后是否输入串已经发生了变化,因此响应到达后要比较当前用户输入串是否是查询串,只有二者一致才要显示返回结果。
  • 为了尽量减少延迟,又考虑到一致性要求不高,CDN 是一个很好的选择。新生成的 Trie 树被推送到离用户较近的节点去。
  • 再来看服务端,大致分为三个步骤。
  • 第一个步骤是图中上面一行,用户的搜索数据或搜索日志,被异步系统处理并计数,写入右侧的数据库中,这个数据库可以考虑选用列数据库(比如 HBase),以提高批量处理的效率,主键可以是一个按序的时间段,以便后续处理。不需要统计全部搜索数据——可以是一个采样以降低数据规模,提高效率;也可以设置一个阈值,如果搜索次数低于阈值就忽略。
  • 第二个步骤是图中第二行靠右侧的部分,每隔一定时间,根据统计数据生成 Trie 树,并持久化到版本化的文件中。为什么用 Trie?因为对于输入建议这种需求,基本就是一种 “前缀查询”,经过压缩的 Trie 树查询的效率很高(其实 HashMap 也可以,但是对于 key,也就是输入前缀的空间占用非常浪费)。
  • 第三部分,考虑到树比较巨大,可以分布在若干个节点上,它的更新异步进行,即整棵树构筑完毕以后整体替换,而不是操纵正在被使用的单个节点。
  • 具体哪一些节点来负责树的哪一部分,这是一个策略问题,它由 Routing Manager 来决定,但是目标是尽量让请求均匀地分摊。比如前缀为 a~bc 的去集群 Partial Trie A,前缀为 bd~d 的去集群 Partial Trie B……这部分可以结合 Zookeeper 来实现。
  • 请求到来的时候,先到达 Typeahead Gateway,而具体请求分发的策略要根据 Routing Manager 来定,这个策略不需要每次都现询问,而可以本地缓存,定期更新。

这是《常见分布式系统设计图解》系列文章中的一篇,如果你感兴趣,请参阅汇总(目录)寻找你其它感兴趣的内容。

文章未经特殊标明皆为本人原创,未经许可不得用于任何商业用途,转载请保持完整性并注明来源链接 《四火的唠叨》

×Scan to share with WeChat

你可能也喜欢看:

  1. 常见分布式应用系统设计图解(七):爬虫搜索系统
  2. 常见分布式应用系统设计图解(九):协同编辑系统
  3. 常见分布式应用系统设计图解(十二):证券交易系统
  4. 常见分布式应用系统设计图解(三):Top K 系统
  5. 常见分布式应用系统设计图解(十):电商秒杀系统

Leave a Reply Cancel reply

Your email address will not be published. Required fields are marked *

订阅·联系

四火,啰嗦的程序员一枚,现居西雅图

Amazon Google Groovy Hadoop Haskell Java JavaScript LeetCode Oracle Spark 互联网 亚马逊 前端 华为 历史 同步 团队 图解笔记 基础设施 工作 工作流 工具 工程师 应用系统 异步 微博 思考 技术 数据库 曼联 测试 生活 眼界 程序员 管理 系统设计 缓存 编程范型 美股 英语 西雅图 设计 问题 面向对象 面试

分类

  • Algorithm and Data Structure (30)
  • Concurrency and Asynchronization (6)
  • System Architecture and Design (43)
  • Distributed System (18)
  • Tools Frameworks and Libs (13)
  • Storage and Data Access (8)
  • Front-end Development (33)
  • Programming Languages and Paradigms (55)
  • Testing and Quality Assurance (4)
  • Network and Communication (6)
  • Authentication and Authorization (6)
  • Automation and Operation Excellence (13)
  • Machine Learning and Artificial Intelligence (6)
  • Product Design (7)
  • Hiring and Interviews (14)
  • Project and Team Management (14)
  • Engineering Culture (17)
  • Critical Thinking (25)
  • Career Growth (57)
  • Life Experience and Thoughts (45)

推荐文章

  • 聊一聊分布式系统中的时间
  • 谈谈分布式锁
  • 常见分布式系统设计图解(汇总)
  • 系统设计中的快速估算技巧
  • 从链表存在环的问题说起
  • 技术面试中,什么样的问题才是好问题?
  • 从物理时钟到逻辑时钟
  • 近期面试观摩的一些思考
  • RSA 背后的算法
  • 谈谈 Ops(汇总 + 最终篇):工具和实践
  • 不要让业务牵着鼻子走
  • 倔强的程序员
  • 谈谈微信的信息流
  • 评审的艺术——谈谈现实中的代码评审
  • Blog 安全问题小记
  • 求第 K 个数的问题
  • 一些前端框架的比较(下)——Ember.js 和 React
  • 一些前端框架的比较(上)——GWT、AngularJS 和 Backbone.js
  • 工作流系统的设计
  • Spark 的性能调优
  • “残酷” 的事实
  • 七年工作,几个故事
  • 从 Java 和 JavaScript 来学习 Haskell 和 Groovy(汇总)
  • 一道随机数题目的求解
  • 层次
  • Dynamo 的实现技术和去中心化
  • 也谈谈全栈工程师
  • 多重继承的演变
  • 编程范型:工具的选择
  • GWT 初体验
  • java.util.concurrent 并发包诸类概览
  • 从 DCL 的对象安全发布谈起
  • 不同团队的困惑
  • 不适合 Hadoop 解决的问题
  • 留心那些潜在的系统设计问题
  • 再谈大楼扔鸡蛋的问题
  • 几种华丽无比的开发方式
  • 我眼中的工程师文化
  • 观点的碰撞
  • 谈谈盗版软件问题
  • 对几个软件开发传统观点的质疑和反驳
  • MVC 框架的映射和解耦
  • 编程的未来
  • DAO 的演进
  • 致那些自嘲码农的苦逼程序员
  • Java 多线程发展简史
  • 珍爱生命,远离微博
  • 网站性能优化的三重境界
  • OSCache 框架源码解析
  • “ 你不适合做程序员”
  • 画圆画方的故事

近期评论

  • Ticket: TRANSACTION 1.922915 BTC. Go to withdrawal >> https://yandex.com/poll/enter/BXidu5Ewa8hnAFoFznqSi9?hs=20bd550f65c6e03103876b28cabc4da6& on 倔强的程序员
  • panshenlian.com on 初涉 ML Workflow 系统:Kubeflow Pipelines、Flyte 和 Metaflow
  • panzhixiang on 关于近期求职的近况和思考
  • Anonymous on 闲聊投资:亲自体验和护城河
  • 四火 on 关于近期求职的近况和思考
  • YC on 关于近期求职的近况和思考
  • mafulong on 常见分布式基础设施系统设计图解(四):分布式工作流系统
  • 四火 on 常见分布式基础设施系统设计图解(八):分布式键值存储系统
  • Anonymous on 我裸辞了
  • https://umlcn.com on 资源链接
© 2025 四火的唠叨 | Powered by Minimalist Blog WordPress Theme