常见分布式应用系统设计图解(五):Proximity 系统

今天是介绍 Proximity 系统,我不知道怎么翻译恰当,就保留英文原文。虽说词义上说的只是 “相似度”,但多数说的是 “地理” 上的相似度。因此,这一类系统多为基于地理上的邻近程度来提供服务的,核心功能就是要找到某人、物或地点地理位置附近的其它人、物或地点。比如像打车系统 Uber、滴滴的叫车功能,比如像大众点评、Yelp 或者百度地图、Google Map 中寻找附近餐馆的功能,或者是 “ 附近的人” 之类基于地理信息的 app 上的小功能。

从读写的角度看,基本上这类功能都要存储位置信息,基于位置的 “寻找” 是很核心的需求,因此读往往比较重。但是写的话差异就比较大了,像有一些应用,比如打车系统,需要司机和

[……]阅读全文

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

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

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

  • 这个功能可以说不是搜索系统的核心功能,而且要求响应一定要非常迅速,考虑到无法避免的网络延迟,我们希望服务端的处理越快越好。响应数据不用非常准确,但是延迟响应肯定是一个糟糕的结果。所以我们希望服务端的处理的数据尽量都在内存中,几乎不需要怎么读取磁盘,整个过程也要保持简洁。
  • 用户侧的浏览器方
[……]阅读全文

系统设计中的快速估算技巧

拿到一堆数据,去做架构也好,设计也好,可行性分析也好,工程上需要的是严谨。但是也有很多场景,比如即时的问题争辩和讨论,我们往往需要的是快速、直接的估算,这样的数据显然不需要非常精确,甚至可以说它一定会非常粗略,我们的目标往往只停留在 “量级” 的级别,但是我们依然可以对方案有一个具体的、量化的认知,这比像 “海量”、“高吞吐”、“低延迟” 这类感性的、描述性的表述还是要清晰和有力得多。

举个经典的例子,已知 Twitter 2020 年大约有 2000 亿(200 billion)的推文(tweets)发推服务的吞吐量(TPS, transaction per second)是多少,网络带宽要占用

[……]阅读全文

常见分布式应用系统设计图解(三):Top K 系统

“ Top K 系统 ” 是非常常见的一种子系统,基本上,就是从全量巨大的统计数据中,筛选出数值最大的 K 个来并按序展示。这样的筛选可以是全时间内的,也可以是最近某一段时间内的;可以是全分类的,也可以是某个特定分类的。

具体来说,像 Twitter 的 Trending Topic,微博热搜,视频网站的点击排行,下载排行(可以是日榜、月榜、总榜)等等。这样的系统,在统计数据非常大(heavy hitters)的时候,其中的挑战性在于两个:

  1. 无法简单地在单台机器的内存中进行目标 id -> count 计数的简单映射,因为数据量太大,内存放不下。
  2. 无法用实时的方式高效地显示出动态变化的 Top
[……]阅读全文

常见分布式应用系统设计图解(二):Feed 流系统

今天记录 Feed 流系统的设计学习笔记,Feed 流常见系统包括 Twitter、微博、Instagram 和抖音等等,它们的特点是,每个用户都是内容创作者,每个用户也都是内容消费者,每个用户看到的内容都是不同的,它取决于用户所关注的用户列表,再结合时间线(有时还包括优先级)将这些用户的最新 feed 聚合,并以流的方式展示出来。

  • Feed 流系统中,有两种常见的模式,一种是 push,一种是 pull。基本上,对于用户的 “被关注用户”(粉丝)可能远大于 “关注用户” 的系统,比如 Twitter,pull model 是必选,push 是可选;反之,特别是对于一些用户关系要求必须双向的,比如朋友圈,往往不
[……]阅读全文

常见分布式应用系统设计图解(一):即时消息系统

在自己学习各种各样软件系统,特别是分布式系统的过程中,我做了一些笔记,有许多常见的、经典的系统,是非常值得学习和总结的。它们数量不算多,但具有典型意义,可能这样的系统也就十几个。

我在回顾这些笔记的时候发现,有时候一张简单的图,包含最核心的几个设计,就可以很大程度地帮助理解和记忆。所以我想把这些笔记和图解的结合通过文章的形式发出来,预计每篇文章都很短,基本上一张图,加上一点说明性的文字。

Disclaimer:这些都来自我自己的阅读和理解,肯定有着相当的改变和简化,因此它并不代表任何系统实际的样子。

今天是第一篇,即时消息系统,但是基本上好多即时通讯软件都属于这一类,比如微信

[……]阅读全文

几个系统设计问题的解决思路

曾经写过一些系统设计方面的思考(比如这个这个),但是最近准备面试,又接触了更多系统设计方面的问题。这里我想简单记录一些典型系统设计问题的思路。通过学习常见的系统,在心中形成一些问题解决的套路,以在思考和分析新问题的时候提供一些既定思路。很抱歉时间关系写得很简略,主要是提示一些思路和方向。

设计 Tweeter
两种常见模型的 trade off:

  • Pull on demand: merge x timelines
  • Push on change: async, read once to get them

缓存的设计,cache through

设计 Web crawl[……]阅读全文

系统设计的典型分层和涉及的知识点

作为系统设计学习的一部分,不久前在梳理面试中典型的系统设计问题,发现大部分都可谓有套路可寻。我把思路梳理了一下,简单整理到下面这张图表里面:

System Design Layers

对于其中的内容,稍微补充几句:

  • 系统设计需要经验的积累,但也确确实实有章可循。问的问题考察的类型很集中,比如同步、异步,消息 push 和 pull,根据实际问题设计存储的数据结构,对于 scalability、availability 的认识等等。最喜欢被问到的问题,我在 《系统设计典型问题的思考》这里列了几个。
  • pull on demand 和 push on change 是消息系统里两种极其典型的消息传播方式,基本上设计 twitte

[……]阅读全文

系统设计典型问题的思考

CAP系统设计方面的问题问题是非常考验经验和思维过程的,而且和常见的算法问题、语言基础问题不同,涉及的面很广,还没有比较一致的判别标准。但无论如何,还是可以归纳一些常见的思路和典型问题的线索。

首先,反复沟通和澄清系统需求。只有把需求澄清清楚了,才可以开始思考并落到纸面上。但是需求的沟通应该是持续和循序渐进的,问题很难从一开始就思考全面。最重要的条目包括:

  • use cases,通常问题只需要 2~3 个 use cases 需要考虑,其他的部分会晚些考虑,或者不考虑。这样就可以简化问题。
  • 用户数量(用户可以是下游系统或者人)、数据数量,澄清这个事实无疑非常重要,对系统设计的决策有重大意义。
  • 请求模型,

[……]阅读全文

留心那些潜在的系统设计问题

500在系统设计阶段考虑全面很难,有许多人倾向于把整个设计分成若干阶段,在迭代中完成整个设计,这本身是非常好的,但是,就如同 “先做出来,以后再优化” 这样的经典谎言一样,本身并无错,只是许多程序员都不习惯于真正的迭代设计和迭代优化。举例来说,有一个日益复杂的类,每个人都修改一点点,一直到最后都没有人愿意去做重构,大家的心态都是一样的:“我只修改了一点点,为什么要我去动那么大的刀,于我没有任何好处”。我不在这里谈论这一问题的解决办法,我倒是想说,在开始阶段考虑清楚问题在多数情况下还是很有好处的,设计考虑得越是清楚,在后续阶段代码可以承受越多的变更而不腐朽。

再做系统设计的时候,我们常常会这样说:“一般

[……]阅读全文

back to top