一起攻克系统设计与构架

大家好我是 《面试官教你破解系统设计题》  https://www.1point3acres.com/bbs/thread-171320-1-1.html 的作者 把 https://www.1point3acres.com/bbs/thread-557107-1-1.html 的内容搬运到这个板块下。 一亩三分地的小伙伴们有没有兴趣一起攻克系统设计与构架？ 目标是方便 1 ）做系统和 2 ）做管理都能够很方便地有相应的背景知识，更高效率和更省钱地做出健壮的和大规模的系统。当然，对你构架面试也会有帮助。 内容是旧金山湾区公司面试的真题与解答。 点此进入 >>> https://github.com/puncsky/system-design-and-architecture <<< 攻克的方法是，针对主流的互联网产品的系统构架和常用的理论，调研市面上的解决方案，择优录用，去繁就简，像是做幻灯片一样都过一遍，观其大略，不求甚解。参考链接在每一篇基本上都有具体列出。 大多数内容是英文的，欢迎中文翻译 ：） 希望集社区的力量，互通有无，一起把这件事情做到世界一流! 最后，因为我是一亩三分地的老用户，为了回馈地里，如果有新的进展，会持续首发在一亩三分地。

补充内容 (2019-10-10 03:06):
telegram group: https://t.me/system_design_and_archiecture
微信群：由于现在人数较多，需微信加 onetptp 拉你入群

Designing Airbnb or a hotel booking system Requirements for guests search rooms by locations, dates, number of rooms, and number of guests get room details (like picture, name, review, address, etc.) and prices pay and book room from inventory by date and room id checkout as a guest user is logged in already notification via Email and mobile push notification for hotel or rental administrators (suppliers/hosts) administrators (receptionist/manager/rental owner): manage room inventory and help the guest to check-in and check out housekeeper: clean up rooms routinely Architecture ComponentsInventory <> Bookings <> Users (guests and hosts) Suppliers provide their room details in the inventory. And users can search, get, and reserve rooms accordingly. After reserving the room, the user's payment will change the status of the reserved_room as well. You could check the data model in this post. How to find available rooms? by location: geo-search with spatial indexing, e.g. geo-hash or quad-tree. by room metadata: apply filters or search conditions when querying the database. by date-in and date-out and availability. Two options: option 1: for a given room_id, check all occupied_room today or later, transform the data structure to an array of occupation by days, and finally find available slots in the array. This process might be time-consuming, so we can build the availability index. option 2: for a given room_id, always create an entry for an occupied day. Then it will be easier to query unavailable slots by dates. For hotels, syncing data If it is a hotel booking system, then it will probably publish to Booking Channels like GDS, Aggregators, and Wholesalers. To sync data across those places. We can retry with idempotency to improve the success rate of the external calls and ensure no duplicate orders. provide webhook callback APIs to external vendors to update status in the internal system. Payment & Bookkeeping Data model: double-entry bookkeeping To execute the payment, since we are calling the external payment gateway, like bank or Stripe, Braintree, etc. It is crucial to keep data in-sync across different places. We need to sync data across the transaction table and external banks and vendors. Notifier for reminders / alerts The notification system is essentially a delayer scheduler (priority queue + subscriber) plus API integrations. For example, a daily cronjob will query the database for notifications to be sent out today and put them into the priority queue by date. The subscriber will get the earliest ones from the priority queue and send out if reaching the expected timestamp. Otherwise, put the task back to the queue and sleep to make the CPU idle for other work, which can be interrupted if there are new alerts added for today. If you find this article helpful, please follow me on Github.

Lyft 的营销自动化平台 Symphony
获客效率问题：广告投放如何花更少的钱用更少的人得到更高回报？具体来讲，Lyft 的广告投放要服务如下特点

• 管理基于地域的 campaign
• 数据驱动的增长：增长必须是规模化的、可测量的、可预测的
• 支撑起 Lyft 独特的增长模型，如图：
  

主要的挑战是：难以规模化管理跨地域营销中的各个环节，广告竞标、预算、素材、激励、选择受众、测试等等。下图是营销者的一天：

我们可以发现“执行”占去了大部分的时间，而更少的时间花在了更重要的“分析和决策”上。规模化意味着减少繁复的操作，让营销人员专注于分析与决策。
解决方案：自动化为了降低成本，提高做实验的效率，需要

• 预测新用户是否对产品感兴趣
• 多渠道优化，有效评估和分配预算
• 方便地管理上千个 campaigns
  

数据由 Lyft 的 Amundsen 系统做增强学习。
自动化的部分包括：

• 更新 bid 的关键词
• 关掉效果不好的素材
• 根据市场改变 referrals values
• 找到高价值的用户 segment
• 在多个 campaign 中共享策略
  

构架
技术栈：Apache Hive, Presto, ML platform, Airflow, 3rd-party APIs, UI.
具体的组成模块LTV 预测模块用户的终身价值是衡量渠道的重要标准，预算由 LTV 和我们愿意为该地区的获客付出的价格共同决定。
我们对新用户的认知有限，随着交互的增多，所提供的历史记录会更准确地预测。
一开始的特征值：

随着历史上的交互记录的积累，做出的判断就会越准确：

预算分配模块搞定了 LTV，接下来是根据价格定预算。拟合出 LTV = a * (spend)^b 形式的曲线以及周围的区间里类似参数的曲线。为了找到全局最优，需要付出一些随机性的代价。

投放模块分为两部分，一部分是调参者，一部分是执行者。调参者根据定价，设定基于渠道的具体的参数；执行者把这些参数执行到具体的渠道上。
有很多流行的投放策略，在各色的渠道中，是共通的：

总结要注意人的经验在系统中的重要性，否则会 garbage in, garbage out. 当人从繁琐的投放任务解放出来，专注于理解用户、理解渠道、理解自身要传达给受众的信息之后，就能够获得更好的投放效果——花更少的时间达到更高的 ROI。



如果这篇文章对你有帮助
在 Github 上 Follow 我 ：）

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 上 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 我

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

设计以人为本的国际化（i18n） 工程方案

敏感词太多贴不了，详情请见 github 的 repo https://github.com/puncsky/syste ... g-i18n-solutions.md