一个纯正程序员的啰嗦
这一篇记录分布式的流量控制系统。
首先，关于流量控制系统，从功能性需求上考虑，它涉及到使用怎样的规则去限制流量（基于 IP、用户 ID、地域，等等），以及，流量超出限制以后的策略是怎样的（比如返回 HTTP 429 或者带有 ratelimit 的 HTTP headers，queue，客户端 retry with exponential backoff 等等）。其中一个基本的问题是，流控在客户端做还是服务端做，通常来说，服务端是一定要的。对于存在的形式，有的流控功能可以以一个 lib 依附于 app 执行，有的则可以通过一个 service 来实现。
其次，从非功能性需求上考虑，比方说系统的可靠性，增加 lat
[……]阅读全文
这一篇是记录分布式工作流系统的。我这些年来参与了几个不同的分布式工作流系统的工作（以前从另外的角度写了一些总结放在这里），大部分是基于基础分布式工作流引擎二次开发的，但也有从头开始实现一个的。总的来说，从原理上看可以说它们的实现是大同小异，大致是基于 Amazon 的 SWF 的各种实现变体。
从功能需求上看，一个工作流系统，当然是要完成一个工作流的执行和追踪，因此，它的用户，可以定义工作流的逻辑，启动、停止工作流，并能够查询工作流的当前执行状态。但我觉得有一条需要着重强调——自治（Autonomy）能力。分布式工作流系统通常来说，要比其它常见的分布式基础设施，从用户理解的角度来说，要复杂和困难
[……]阅读全文
这篇的内容是关于分布式消息队列的，无论是在实时系统，还是在非实时系统中，它都有广泛的应用。作为一个消息队列，基本的功能需求相对好描述，简单说有两条：
非功能需求方面，这里面有几个基本的重要特性可以拿来考量，可以说这些基本都是分布式系统所共有的，但其中有几个是异步系统所更为看重的——比如说：
[……]阅读全文
从大致的非功能需求角度来说，作为一般的分布式持久化存储系统，这样三个需求从重要性依次排列：
Durability > Availability > Performance
即最重要的是，数据绝对不能丢失，其次是要一直提供服务，最后才是要保持一定的性能。当然，有了上述基础以后，我们还可以谈论任何分布式存储系统都涉及的重要特性，比如一致性。最后，作为特定的存储系统——“数据库”，我们还常常谈论一些特定的特性，比如权限管理和事务控制等等。
下面拿的是 Bigtable 来举例的，它建立在 GFS 这样的分布式文件系统上面，有一定代表性。
[……]阅读全文
继续分布式系统的设计图解，下半部分是基础设施，此篇是分布式文件系统。这里面典型就是 GFS，对应开源的版本就是 HDFS。
既然谈到分布式文件系统，我觉得需要从需求层面做一个简单的说明：
[……]阅读全文
【Updated on 9/15/2023】本来只是自己粗浅的总结，但好几位朋友说这套笔记帮助很大，甚至帮他们通过了系统设计面试并找到了工作，那我就打算置顶一段时间，让更多人看到。
这一篇是给我记录的那些常见分布式系统设计图解系列的文章做一个汇总，也提供一个访问入口。
如同我在第一篇文中说的那样，自己在学习各种各样分布式系统的过程中，做了一些笔记，也有自己的理解，把它们放到一起，用一张图选择最主要的部分来阐释，从我的角度来说，是能够帮助理解和记忆的。事实上，遇到的很多各种各样的分布式系统，绝大多数都逃不出那最常见的十几种，也就是说，逃不出这些 “套路” 和 “玩法”。这就是把它们整理成一
[……]阅读全文
文件同步分享系统包括 Dropbox、Google Drive，也包括国内的各种网盘，比如百度网盘。总的来说，这里讨论的这个系统包含这样几个基本功能：
[……]阅读全文
互联网搜索引擎都有爬虫系统，无论是 Google 还是百度。当然这里我们讨论的只是一个极其简单的版本。
对于爬到的资源，我们这里其实讨论的只是文本而已，还有图片、音频、视频这些媒体，如果我们也需要存下来，那就需要专门的媒体服务。对于媒体文件的存放，在之前的文中已经讨论过，这里就不再覆盖了。
[……]阅读全文
流媒体系统，主要是视频流媒体系统。比如 YouTube，比如 Netflix，比如爱奇艺，还有优酷。再一个许多大型的社交平台上，几乎是一定要内嵌流媒体服务的，以支持用户上传视频类型的内容。
这类系统我们需要考虑的不只有单纯视频文件的存储和传输，还有文件的编码、解码，和视频截图（比如用作 thumbnail）的生成等等基本功能。
[……]阅读全文
今天是介绍 Proximity 系统，我不知道怎么翻译恰当，就保留英文原文。虽说词义上说的只是 “相似度”，但多数说的是 “地理” 上的相似度。因此，这一类系统多为基于地理上的邻近程度来提供服务的，核心功能就是要找到某人、物或地点地理位置附近的其它人、物或地点。比如像打车系统 Uber、滴滴的叫车功能，比如像大众点评、Yelp 或者百度地图、Google Map 中寻找附近餐馆的功能，或者是 “ 附近的人” 之类基于地理信息的 app 上的小功能。
从读写的角度看，基本上这类功能都要存储位置信息，基于位置的 “寻找” 是很核心的需求，因此读往往比较重。但是写的话差异就比较大了，像有一些应用，比如打车系统，需要司机和
[……]阅读全文
输入建议系统，指的就是 “typeahead”，比如 Google 搜索，输入一个单词的前几个字母，后面最常用的几个搜索词会被联想出来。有时，它也需要具备一定程度的字符拼写错误自动更正能力。
比如上面这张截图，我输入了 “goog”，在输入框的下方列出了最常见的几个以 goog 开头的搜索短语。
[……]阅读全文
拿到一堆数据，去做架构也好，设计也好，可行性分析也好，工程上需要的是严谨。但是也有很多场景，比如即时的问题争辩和讨论，我们往往需要的是快速、直接的估算，这样的数据显然不需要非常精确，甚至可以说它一定会非常粗略，我们的目标往往只停留在 “量级” 的级别，但是我们依然可以对方案有一个具体的、量化的认知，这比像 “海量”、“高吞吐”、“低延迟” 这类感性的、描述性的表述还是要清晰和有力得多。
举个经典的例子，已知 Twitter 2020 年大约有 2000 亿（200 billion）的推文（tweets）发推服务的吞吐量（TPS, transaction per second）是多少，网络带宽要占用
[……]阅读全文
“ Top K 系统 ” 是非常常见的一种子系统，基本上，就是从全量巨大的统计数据中，筛选出数值最大的 K 个来并按序展示。这样的筛选可以是全时间内的，也可以是最近某一段时间内的；可以是全分类的，也可以是某个特定分类的。
具体来说，像 Twitter 的 Trending Topic，微博热搜，视频网站的点击排行，下载排行（可以是日榜、月榜、总榜）等等。这样的系统，在统计数据非常大（heavy hitters）的时候，其中的挑战性在于两个：
[……]阅读全文
今天记录 Feed 流系统的设计学习笔记，Feed 流常见系统包括 Twitter、微博、Instagram 和抖音等等，它们的特点是，每个用户都是内容创作者，每个用户也都是内容消费者，每个用户看到的内容都是不同的，它取决于用户所关注的用户列表，再结合时间线（有时还包括优先级）将这些用户的最新 feed 聚合，并以流的方式展示出来。
[……]阅读全文
在自己学习各种各样软件系统，特别是分布式系统的过程中，我做了一些笔记，有许多常见的、经典的系统，是非常值得学习和总结的。它们数量不算多，但具有典型意义，可能这样的系统也就十几个。
我在回顾这些笔记的时候发现，有时候一张简单的图，包含最核心的几个设计，就可以很大程度地帮助理解和记忆。所以我想把这些笔记和图解的结合通过文章的形式发出来，预计每篇文章都很短，基本上一张图，加上一点说明性的文字。
Disclaimer：这些都来自我自己的阅读和理解，肯定有着相当的改变和简化，因此它并不代表任何系统实际的样子。
今天是第一篇，即时消息系统，但是基本上好多即时通讯软件都属于这一类，比如微信
[……]阅读全文
上个月在极客时间做了一场直播，聊了聊职业生涯技术选择的话题，直播标题叫做《专精 or 博学，多少人输在了技术选择上？》。我把编辑剪好的视频贴在下面。如果对于我写的极客时间专栏 《全栈工程师修炼指南》感兴趣的话，也欢迎订阅。下面的胶片或视频如果加载比较慢，可以点击 B 站视频链接。
[expand title="胶片"][doc id=6246][/expand]
[expand title="P1 我是谁"] [/expand]
[expand title="P2 第一部分：技术路线的选择"]
[……]阅读全文
我觉得去理解数据结构的时候，需要注意到它其实包含两个层面。一个层面是高一级的，从功能、接口的角度去理解，比如说堆，有什么功用，都有怎样的 API；另一个层面是低一级的，从结构和实现的角度去理解，比如堆的实现，可以用数组实现，也可以用单独的节点对象+指针实现。上面一层相同，但是下面一层不同，功能上可能基本一致，但是性能上针对不同的应用场景就可以天差地别。
图就是另外一个典型例子，无向图也好，有向图也好，这是从功能上说的，但它们各自的实现，或者说基于的 “表示方法” 有多种。我记得在学习数据结构早期，基本上没有比较系统地去比较它们，那今天就把这一课补上。
比如上面这个有向图，四个顶点
[……]阅读全文
我用手机拍了很多照片，平时都保存在一台 Windows 台式机上，这台机器硬盘空间大，主要干两个事情，一个是我打游戏，一个就是存放多媒体数据（主要是照片，也有很多文档）。有时候我需要它提供照片服务，以方便家人使用各种媒体终端（手机、电视盒子等）阅览，有时候则需要往上面拷贝数据以作备份只用，于是我使用 Plex 折腾了一下，但是由于台式机噪音等等的关系，不适合长期开机，因此当时那个方案还是残缺的。
现在打算彻底解决这个问题。大致总结一下，以下是我的主要的几个需求：
[……]阅读全文
有这样一个经典的算法题，说是一个单向链表，它内部可能存在环，也可能不存在，用怎样的方法，可以检测出，这个链表是否存在环。下图即是这个形成环的示意，如果单向链表的尾部，指向了链表中的一个节点，而不是指向空，那就构成环了。
接着的一个问题是，怎么检测出这个链表是否有环？
看到这个问题，也许你会觉得，太简单了，但是这个问题只是一个引子。在 《求第 K 个数的问题》一文中，我从简入深，逐步展开，把这 “第 K 个数” 的一系列问题翻了个底朝天。我想关于这个链表成环问题，我也利用类似的思路，看看我是不是也能把这一个问题前前后后讲清楚。
在进一步思考怎样判断这个成环
[……]阅读全文
还记得在读书的时候，就对程序员有种坐在电脑前疯狂敲代码的刻板印象。工作以后，逐渐理解了软件工程师的工作到底是怎么样的，可是写代码，作为软件工程师最重要的本职工作，还是占据了相当比重的时间。在面试别人的时候，也经常被问到这样的问题——“平均你每天有多少时间花在写代码上？”，这个问题看似简单，却能反映出一个问题，软件工程师，能否有足够的时间专注在最本职工作——写代码上。毫无疑问，我完全理解这样的问题，并且，我也一直以来想保持着自己一个 “纯粹” 程序员的身份。我觉得我的职业通道也是一条纯粹的技术人的道路，因而写代码，是一个如同每天吃饭喝水一样的基本操作。
可是，随着职业生涯的进展，特别是近半年来 [……]阅读全文