一同攻克系统设计与构架

謝謝分享!

Designing typeahead search or autocomplete

Requirements

• realtime / low-latency typeahead and autocomplete service for social networks, like Linkedin or Facebook
• search social profiles with prefixes
• newly added account appear instantly in the scope of the search
• not for “query autocomplete” (like the Google search-box dropdown), but for displaying actual search results, including
  
  • generic typeahead: network-agnostic results from a global ranking scheme like popularity.
  • network typeahead: results from user’s 1st and 2nd-degree network connections, and People You May Know scores.
    

Architecture

Multi-layer architecture

• browser cache
• web tier
• result aggregator
• various typeahead backend
  

Result Aggregator

The abstraction of this problem is to find documents by prefixes and terms in a very large number of elements. The solution leverages these four major data structures:

• InvertedIndex<prefixes or terms, documents>: given any prefix, find all the document ids that contain the prefix.
• for each document, prepare a BloomFilter<prefixes or terms>: with user typing more, we can quickly filter out documents that do not contain the latest prefixes or terms, by check with their bloom filters.
• ForwardIndex<documents, prefixes or terms>: previous bloom filter may return false positives, and now we query the actual documents to reject them.
• scorer(document):relevance: Each partition return all of its true hits and scores. And then we aggregate and rank.
  

Performance

• generic typeahead: latency <= 1 ms within a cluster
• network typeahead (very-large dataset over 1st and 2nd degree network): latency <= 15 ms
• aggregator: latency <= 25 ms
  

If you find this article helpful


follow me on Github :)



star the repo


find more interesting articles on puncsky.com

谢谢分享！

构架入门

什么是构架构架是软件系统的形状。拿建筑物来举例子：

• 范式 paradigm 是砖块
• 设计原则是房间
• 组件是建筑
  

他们共同服务于一个特定的目的，就像医院治疗病人，学校教育学生一样。
我们为什么需要架构？行为 vs. 结构

每一个软件系统提供两个不同的价值给利益相关者：行为与结构。软件开发者必须确保这两项价值都要高

==由于其工作的需要，软件架构师更多地聚焦于系统的结构而不是特性和功能。==
终极目标——==减少每加一个新特性所需要耗费的人力成本==

架构服务于软件系统的整个生命周期，使其易于理解，开发，测试，部署和操作。 其目标是最小化每个业务用例的人力资源成本。

O’Reilly 出版的《软件架构》一书很好地介绍了这样五种基本的构架。
1.分层架构

分层架构是被广泛采用，也是被开发者所熟知的一种架构。因此，它也是应用层面上事实上的标准。如果你不知道应该使用什么架构，用分层架构就是不错的选择。

示例

• TCP/IP模式：应用层 > 运输层 > 网际层 > 网络接口层
• Facebook TAO网络层 > 缓存层(follower + leader) > 数据库层
  

优缺点：

• 优点
  
  • 易于使用
  • 职责划分
  • 可测试性
    
• 缺点
  
  • 庞大而僵化
    
    • 想要对架构进行调整、扩展或者更新就必须要改变所有层，十分棘手
      

2.事件驱动架构

任何一个状态的改变都会向系统发出一个事件。系统组件之间的通信都是经由事件完成的。

一个简化的架构包含中介(mdiator)，事件队列(event queue)和通道(channel)。下图所示即为简化的事件驱动架构：

示例

• QT：信号(signals)和槽(slots)
• 支付基础设施：由于银行网关通常有较高的延迟，因此银行的架构中采用了异步技术
  

3.微核架构(aka Plug-in Architecture)

软件的功能被分散到一个核心和多个插件中。核心仅仅含有最基本的功能。各个插件之间互相独立并实现共享借口以实现不同的目标。

示例

• Visual Studio Code 和 Eclipse
• MINIX 操作系统
  

4.微服务架构

大型系统被解离成众多微服务，每一个都是单独部署的单位，他们之间通过RPCs进行通信。

示例

• Uber: 详情查看 designing Uber
• Smartly
  

5.基于空间的架构“基于空间的架构”这一名称来源于“元组空间”，“元组空间“有”分布式共享空间“的含义。基于空间的架构中没有数据库或同步数据库访问，因此该架构没有数据库的瓶颈问题。所有处理单元共享内存中应用数据副本。这些处理单元都可以很弹性地启动和关闭。

示例：详见 Wikipedia

• 主要被使用Java的架构所采用：例如：JavaSpaces
  

在 Github 上编辑此文章

如果这篇文章对你有帮助

请在 Github 上 Follow 我 ：）

Concurrency Models

• Single-threaded - Callbacks, Promises, Observables and async/await: vanilla JS
• threading/multiprocessing, lock-based concurrency
  
  • protecting critical section vs. performance
    
• Communicating Sequential Processes (CSP)
  
  • Golang or Clojure’s core.async.
  • process/thread passes data through channels.
    
• Actor Model (AM): Elixir, Erlang, Scala
  
  • asynchronous by nature, and have location transparency that spans runtimes and machines - if you have a reference (Akka) or PID (Erlang) of an actor, you can message it via mailboxes.
  • powerful fault tolerance by organizing actors into a supervision hierarchy, and you can handle failures at its exact level of hierarchy.
    
• Software Transactional Memory (STM): Clojure, Haskell
  
  • like MVCC or pure functions: commit / abort / retry
    

设计负载均衡器
需求分析

互联网服务往往要处理来自全世界的流量，但是，一个服务器只能够同时服务有限数量的请求。因此，通常我们会有一个服务器集群来共同处理这些流量。那么问题来了，怎样才能够让这些流量均匀地分布到不同的服务器上呢？

从用户到服务器，会经过很多的节点和不同层级的负载均衡器。具体来讲，我们这次设计的需求是：

• 设计第7层的负载均衡器，位于数据中心的内部。
• 利用来自后端实时的负载信息。
• 服务每秒千万级的流量以及10 TB每秒级别的吞吐量。
  

补充：如果服务 A 依赖服务 B，那我们称 A 是 B 的下游服务，而 B 是 A 的上游服务。

挑战为什么负载均衡会很难做？答案是很难收集准确的负载分布数据。
按照数量分布 ≠ 按照负载分布最简单的做法是根据请求的数量，随机地或者循环地分布流量。然而，实际的负载并不是根据请求的数量来算的，比如有些请求很重很耗CPU，有些请求很轻量级。

为了更加准确地衡量负载，负载均衡器得保持一些本地状态 —— 比如，存当前的请求数、连接数、请求处理的延迟。基于这些状态，我们能够使用相应的负载均衡的算法 —— 最少连接、最少延迟、随机 N 取一。
最少连接：请求会被导向当前连接数最小的服务器。

最少延迟：请求会被导向最少平均反应时长且最少连接数的服务器。还可以给服务器加权重。

随机 N 取一 （N 通常是 2，所以我们也可以称之为二选一的力量）：随机的选两个服务器，取两者之中最好的，能够避免最坏的情况。
分布式的环境
在分布式的环境中，本地的负载均衡器难移了解上下游服务完整的状态，包括

• 上游服务的负载
• 上游服务可能超级大，因此很难选择一个合适的子集接入负载均衡器
• 下游服务的负载
• 不同种类的请求的具体处理时间很难预测
  

解决方案有三种方案能够准确地搜集负载的具体情况并相应地处理：

• 中心化的一个均衡器，根据情况动态地处理
• 分布式但是各个均衡器之间要共享状态
• 服务器返回请求的时候捎带上负载信息，或者是均衡器主动询问服务器
  

Dropbox 在做 Bandai 的时候选择了第三种方案，因为这很好地适应了现行的随机 N 选一的算法。

然而，与原配的随机 N 选一的算法所不同的是，不是使用本地的状态，而是选择服务器实时返回的结果。
服务器使用率：后端服务器设置了最大负载，数当前的连接，然后计算出使用率，范围是从 0.0 到 1.0.

有两个问题需要考虑：

• 处理错误: 如果 fail fast ，由于处理得很快，反而会吸引更多的流量产生更多的错误。
• 数据要衰减: 如果服务器的负载太高，没有请求会发到那里。因此，使用一个类似于反 S 曲线的衰减函数来保证老数据会被清理掉。
  

结果: 服务器接收的请求更加的均衡了

如果这篇文章对你有帮助，请在 github 上 follow 我

更多内容，请访问我的博客

請問一天平均花多少時間在這上面

puncsky 发表于 2019-10-10 20:07
Designing typeahead search or autocomplete

Requirements

autocomplete这篇怎么github上没有？想问一下哪个平台可以作为楼主的更新的single source of truth？

一剑终情 发表于 2019-10-22 03:17
autocomplete这篇怎么github上没有？想问一下哪个平台可以作为楼主的更新的single source of truth？

github 有收录的，以github 为准吧，论坛好像老帖子回复没有编辑功能

xva 发表于 2019-10-21 20:51
請問一天平均花多少時間在這上面

时间是个大问题，我自己的话有时间就做一点吧，毕竟我现在也不刷题只是凭着兴趣而不是利益来做这件事情，如果有社区的伙伴来做就最好了