系统设计笔记

系统设计学习笔记。祝我好运。

考点

Communication
Working Solution
Walk through your solution and provide reasoning
Trade-offs and optimizations

基础知识讲解

分布式系统的主要特性

Scalability

系统/服务是否能够evolve并handle增长的需求。随着系统自身规模增加，scalability通常下降，因为机器之间的物理距离、网速限制，或者任务本身就无法被分配到不同机器上执行。
- horizaontal scaling: 用更多的机器，更加动态和灵活一些。
- vertical scaling: 在机器上堆更好更多更快的硬件cpu/ram/storage，通常涉及downtime以及升级的极限。

Reliability

系统在一定时间内宕机的概率。一个reliable的系统能够正常地完成任务而不会因为自身软/硬件的failure甚至人为的fault而宕机。
reliable的分布式系统通常涉及redundancy，避免single point of failure.

Availability

系统在一定时间内正常工作的概率，downtime越少、越不频繁就越available。可以理解为「较低要求的reliablity」.
如果系统reliable, 就是available的；但反过来，系统available，不一定reliable。

Efficiency

Latency(response time): 从接受到请求到第一次返回数据需要多久
Throughput(bandwidith): 单位时间内能够发送多少

Serviceability/Managebility

衡量系统的维修/维护的容易程度和所需时间。
需要考虑如果出问题了是否容易诊断(log的重要性)，部署升级或修改的方便程度，能否自动恢复（针对间歇性宕机），是否有合适的monitor&alert机.

Load Balancing

负载均衡处在client和server之间，负责接受网络请求并分配到后端cluster，提高responsivenes和availability.
如果想尽可能充分使用LB，可以考虑在client、WebServer、ApplicationServer、DBServer之间各加一层LB. 为了防止LB本身成为single point of failure，可以考虑对LB本身加上redundancy。
除了提升availability、更高效，LB还可以提供机器学习的功能，类似于流量预判从而适当地scale等等。
LB在确认server能正常响应后，就会通过某种算法将request导向server
- Least connection: 根据active connection，选最少的那个
- Least Response Time: 根据响应时间，选最快的
- Least Bandwidth: 选择负载最轻的
- Round Robin: 轮流。或者根据机器本身的处理能力赋予权重，根据权重来RR.
- IP Hash: 将client的IP映射成hash再选择对应的server。
TCP版LB v.s. HTTP版LB
- TCP LB速度快，只负责转发，不检查内容
- HTTP LB可以实现复杂的逻辑，例如根据传输数据内容决定向哪个特定server转发

Caching

Locality of reference: 缓存的思想是「最近请求过的数据很可能会再次被请求」. 通常尽可能设置在接近client的layer，这样就可以尽可能减少后续牵涉的layer了。
Content Distribution Network: CDN是大量静态数据static media的缓存，通常当请求达到一定规模时才会用CDN。如果系统尚且比较小但确实有一些反复被请求的静态数据，可以将这部分直接存到一个subdomain例如static.blah.com，用轻量级的http服务器例如Nginx快速返回这部分数据。
cache invalidation: 当数据改变时，缓存也需要相应地标记为失效，这样访问时才不会有inconsistency.
- write-through cache: 数据会同时存入DB和cache，这样可以保证完全一致且数据不会丢，但要写入两个地方才返回，速度比较慢。
- write-around cache: 数据只存入DB，访问到cache会是一个miss，再去DB取最新的数据，速度更慢。
- write-back cache: 数据只存入cache，隔一段时间或在某种条件下才会写入DB，速度最快，但也有丢失数据的风险。
cache eviction: 缓存容量有限，就需要排掉一些数据
- FIFO: 按存入的时间顺序，旧的先出去
- LIFO: 按存入的时间顺序，新的先出去
- LRU: 按hit的时间顺序，远古hit的先出去
- MRU: 按hit的时间顺序，最近hit的先出去
- LFU: 按hit的频率顺序，最少hit的先出去
- Random Replacement: 随机出去

Database

Best Practices

所有的表都需要有primary/unique key/necessary index. 相应地，在DAO中query时用到的where clause都用到相应的key/index。
在DAO中query时只取需要用到的数据，尽可能避免SELECT *传回row中所有的东西.
及时删除不需要的key/index，否则写入会花时间在不必要的索引上。
显式地指明字符集，防止在插入时有特殊字符，导致代码中读取时于存入的值不一致/乱码。
read-only和read-write的权限指向的数据库可能也有性能差异，query/report等操作都应指向RO终端。
需要考虑数据量：比如每达到若干百GB之后需要对历史数据进行存档，或者考虑将数据表进行partition以保证读取的效率。
数据转移的job尽可能分段、间隔地进行，而不是一口气全部migrate/backfill/bulkload/delete，防止job中途崩了。

Data Partitioning

数据拆分的思想是到达某个scale界限的时候，水平地增加机器要比升级成更6的机器更便宜和可行。

Partitioning Methods

Horizontal(Data Sharding): 将不同的record row按照某种规则存入不同的table中。例如range based partitioning就是根据某个column的值的范围拆分，存入相应的表中。但这个range如果设的不好就会造成unbalanced的问题。
Vertical: 将不同的column存入不同的表中，其实就是利用DB本身JOIN的特性，实现很方便且对系统影响并不大。但当数据进一步增加时，每个表中的行数可能就需要进一步拆分了。
Directory Based: 构建一个lookup的中间层，每次查数据时先经过lookup找到对应的DB server，再去实际的地方取数据。这样的好处是将DB access的代码从实际的系统中抽象出来，将来需要改变partition scheme的时候就不需要动系统本身了。

Partitioning Criteria

Key/Hash based partitioning: 对数据entity的关键属性hash后得到一个partition编号，再根据这个编号找到服务器存取数据。由于hash函数是按照当前服务器总数定的，如果想加更多就需要downtime了。解决方法是使用consitent hashing. consistent hashing思想是利用一个hash环，对数据和缓存机器都进行hash，每个数据都存在顺时针距离最近的机器上。这样当机器增加/减少时只有环上特定段的数据需要重新分配的新的机器上，对于其他数据没有影响。
List partitioning: 每一个partition维护一个list of values，如果数据包含这个value就存入相应的partition，但效率不高。
Round-robin partitioning: 轮流，i-th tuple直接存入i % n个partition。
Composite partitioning: 结合上面几种，例如先用个简单的list、在内部再用hash based。其实consistent hashing也可以当作是一种结合式分区。

Problems of Partitioning

Joins and Denormalization: 如果table都在一个机器上，使用join操作非常正常。但是分散之后还想同时对多个table进行join就不那么feasibile了。解决方法是对数据库进行denormalize，（normalize指的是各个表之间存储的数据尽可能不重复）这样之前执行过的join操作就可以在单个table上完成了，有点类似于数据备份，但这样也就需要处理数据不一致的问题了。
Referential integrity: 类似于cross-partition query不可行，保证data integrity constraints如foreign keys之类的也很困难，在RDBMS不支持跨服务器的reference的情况下就需要在application level维护一些保证引用正确性的代码了。
Rebalancing: 当请求集中在某些服务器时可能就需要考虑调整划分规则了，通常就涉及增加新的partition或在现有的partition内部进行rebalancing。使用directory based的操作可以避免downtime，但也增加了系统的复杂性和引入了single point-of-failure（中央查询都这样）。

Hot Partition

对于一些热门的资源，可能短时间内所有request都会指向同一个partition，造成hot / overload partition持续写入.
解决方法
- 在简单的hash(uuid)基础上加入event_time信息，这样当前这个interval内会全部涌入一个partiton、下一个interval就会去别的partition，平均来看就spread out了。
- split hot partiton into two new partitons，类似于consistent hashing.
- explicitly allocate dedicated partitions，手动将经常被访问的partition分散开来。

Indexes

index本质上就是一个指出数据存储位置的额外的table，easily searchable by relavant information.
数据量大的时候，为table建立index可以大大改善查找（retrieve）速度。尤其是在huge dataset中查找relatively small payload的时候，因为通过遍历查找实在太慢。此外数据可能被分散到不同的physical devices上，通过index也可以快速找到存储的位置。
相反地，index本身可能日益增长，从而降低数据的增改删（CUD）过程，因此需要避免假如不必要的index，而且对于write heavy的数据表也需要考虑是否真的需要加index。

Redundancy & Replication

Redundancy: 作为备份或者提升系统性能时，将数据存放到多个机器上，当一个机器宕机不至于影响整体。
Replication: 更进一步，在多个机器之间需要同步数据保证一致性。通常在DBMS中比较关注，通常是master-slave的形式。

SQL & NoSQL

SQL: relational DB将数据存在行和列中，每一行是一个entity，每一列包含所有entity的某个属性。例如MySQL, Postgres, MariaDB.
NoSQL: 大致有如下常见类型
- Key-Value Stores: 用一组键值对来存储信息，常见的有Redis, Voldemort和Dynamo.
- Document Databases: 数据存放在「document」中，group成「collections」。每个document可以有不同的结构，自由度很高。常见的有MongoDB和CouchDB.
- Wide-Column Databases: 强调列的一种数据库，column families是行的container。在操作时不需要预先知道所有的列，行也不需要包括相同的列，比较适合用在分析大数据上。常见的有Cassandra和HBase.
- Graph Databases: 用图的形式存储数据，每个entity是一个节点，连线表示数据之间的关系。常见的有Neo4J和InfiniteGraph.
SQL与NoSQL的区别：
| Aspect | SQL | NoSQL |
| :——-: | :——-: | :———-: |
| Storage | 用行和列来存储 | 有各种存储形式，如Key-value, document, graph和columnar |
| Schema | fixed. 在插入数据前必须确定列，每一行的每一列都必须有值(包括NULL);
允许之后更改schema，但需要改动整个DB且涉及downtime | dynamic. 可以自由地增减「column」on the fly |
| Querying | 使用结构化查询语言(structured query language) | 查询关注的是a collection of documents(UnQL) |
| Scalability | vertically scalable，涉及硬件升级 | horizontally scalable，对单机硬件要求不高 |
| Reliablity or ACID Compliancy
Atomicity, Consistency, Isolation, Durability | 绝大多数relational DB都是ACID compliant | NoSQL牺牲了ACID换取performance&scalability |
何时选择SQL/NoSQL
- 选择SQL的情形
  - 需要保证ACID compliance，尤其是commerce/financial data，数据integrity、transaction非常重要。
  - 数据本身就structured and unchanging，数据增长不迅猛，就不必要支持variety的数据类型和大流量了。
- 选择NoSQL的情形
  - 存储大量没有特定结构/类型的数据，无需提前定好类型，之后存入数据也没有类型的限制。
  - 充分利用云计算和云存储，可以水平扩展提升速度，使得database不是系统的瓶颈。
  - 快速开发，不需要提前知道很多数据的确定细节，先打造出系统之后也可以在不涉及downtime的情况下往里塞各种类型的数据。

CAP Theorem

一个分布式系统只可能在以下几个特性中三选二。

Consistency: 所有节点的数据在同一时间是一致的。通过在保证update完成之前阻止read请求实现。
Availability: 所有请求都会得到回应，success/failure都算是回应。通过replicate数据到不同服务器实现。
Partition Tolerance: 系统能在节点之间信息丢失或部分失败的情况下继续工作。通过在节点和网络的各种组合中充分replicate实现。

Consistent Hashing

分布式哈希表(DHT)在分布式系统中器关键作用，它可以快速确定数据存储在cluster中的哪个节点上。

传统哈希：例如直接膜服务器个数，这样一旦增减节点所有的映射都会被破坏，而且数据并不是均匀分布的，而是可能集中到部分节点上。
一致哈希：同样是哈希，当增减节点时节点minimize the reorganization，因此非常适合scalable cache system. 实现细节如下：
1. 对一个list of servers，将他们映射成一定范围内的整数，放到一个环上，每个server就是环上的一个节点。
2. 对数据的映射则需要
  1. 将key映射成整数，定位到环上
  2. 顺时针找到第一个server，数据就放在这上面
3. 增加节点时，它所分隔的顺时针前续数据都需要放置到它上面，而不影响后续以及其他节点的数据
4. 删除节点时，将数据释放到顺时针的下一个节点即可，不影响其他节点的数据
虚拟节点：由于增减server时只能分担某个节点的负载，需要利用虚拟节点来实现负载均衡。虚拟节点就是将物理机器虚拟为一组节点(replicas)放到环上，每个cache与多个portions of ring联系起来了。存取数据时，映射到环上再找虚拟节点，就能定位到物理机器了。在增减物理机器时，也需要进行虚拟化，理想情况下新加入的虚拟节点就可以均衡地分担原有机器的负载了。

Proxies

代理是在client和后端之间插入的一层（概念上的而非物理上的，它甚至可以在client自己身上），用于帮助client从后端获取resources. 在proxy上通常可以对request做筛选，logging, 变形(如加减headers、加密解密、压缩资源等). 有几种类别，比较流行的有：

Open Proxy: 公开的，毕竟维护代理需要成本，通常只允许特定的用户群访问。公开的代理又分为
- Transparent Proxy（除了proxy IP，从header里可以提取实际使用者IP）
- Anonymous Proxy（只能知道proxy IP，无法知道真正使用者的IP）
- Distorting Proxy混淆代理（只能知道proxy IP，用一个假的IP塞到header里）
- Elite proxy高匿代理（能知道IP但无法知道是否是在使用代理）。
Reverse Proxy: client访问proxy时由代理去取resources，client访问时并不知道它是proxy。通常反向代理和实际后端同处在一个内网中，可以抵御外部恶意访问，同时实现一些负载均衡。

Communication Protocols

标准HTTP网络请求通常是这几步：

client打开连接，向server请求数据
server计算response
server将数据发回给client

大致有以下几类通信方式：

Ajax Polling: client间隔性地向server请求某些数据来进行update。当没有新内容时回复是空的，就造成了很多HTTP overhead。
HTTP Long-Polling(Hanging GET): 和上面的polling类似，但server不是立刻回复，而是等待直到有update或者timeout才回复，而client在收到response的同时会立刻再发一个请求。这有可能造成request在server端堆积。
WebSockets: 在一个TCP连接中提供全双通（full duplex）的通信渠道，一旦WebSocket handshake完成，连接就建立了，client和server都可以实时任意交换数据。
Server-sent Events: client和server之间建立了一个persistent和长期的连接，当server在不断产生data或持续发送events的时候比较合适。

message format

textual（如xml, csv, json）：广泛使用，human-readable, 但数据复杂、数据size更大、scalability不如binary.
binary（如thrift, proto-buf）：compact, faster to parse，因为schema严格、用tag取代tagName，但需要share and sync schema format

performance testing

load testing: measure behavior of a system under a specific expected load, 用来确认scalable、能承受load
stress testing: test beyond the normal capacity, often to a breaking point，找到什么部分最先崩溃memory/cpu/diskIO
soak testing: test with typical load for extended period of time，找到leak in resources如memory leak

系统设计面试

积木

In-memory: Redis(p50=1ms，可以shard), memcache
Leaderless replica: DynamoDB(inf scale几千个node且perf是线性增加), Cassandra
SQL: MySQL(单机p50=10ms，还可vrtc/hrzt sharding), PostgreSQL。
Sharded SQL: ZooKeeper + MySQL
Analytics DB: Redshift, column-oriented DB
Kafka(单DC p50=5ms, 多DC p50=100+ms), Flink: 保证scalability和durability，用在dashboard和report上。

数据库/缓存/队列选择

SQL: 有严格的transaction；有rich sql query如join/group by，不过需要小心sharding时key的选择
- MySQL: 轻快。改schema时会全复制。
- Postgres: tuple不会更改，update其实是插入。alter比较好，支持的功能全面。
NoSQL: 格式本身就是key-value对儿；有规律的access pattern；需要flexible schema。DynamoDB(每行400K)
S3: big object或媒体文件。
Redis: write都单线程处理(100k QPS), read是多线程，保证serialized transaction，但durability有问题。
MessageQueue: 主要放metadata因此不能放很大的内容，size比较固定。

两种disagree

foundamentally not working: 理论上根本就不work
not the best design: 直觉这个可能不是最优解，可能是tool限制，但面试中给出working solution，good enough就好了。

解题步骤

10 min Requirement Clarification
- User/costomers
  - Who will use the system? real world customers? internal users? consumed by other serivce/pipeline?
  - How will the system be used? offline? real-time?
- Scale(read and write)大致是多大的？Daily Active Users?
  - How many read QPS?
  - How much data is qureied per request?
  - What’s the traffic pattern? any spike?
- Performance
  - What is expected write-to-read data delay?
  - What is expected p99 latency for read queries?
- 支持用户的哪些操作？是否需要根据搜索/写入做优化？需要自己come up with一些near future的新功能，需要培养business sense.
- 后台/entity需要储存哪些类型的数据？
- 是否需要支持一些机器学习模型如推荐热搜？
- 是否有一些后台push notification的操作？
- 分清楚MVP, bonus feature.
- non-functional requirement: availability, reliability, consistency, real-time.
- Cost:
  - Should we consider the $ cost? indicates open-source.
  - Should we consider maintainence cost? indicates public cloud resource providers.///
10 min Back-of-the-envelope estimation 估算系统规模
- 系统的scale是怎样的？（单位时间内新增内容/查询次数）
- 需要多少的storage和cache？这涉及不同的DB选择
- 网络bandwidth是怎么样的？这涉及之后的traffic management和load balancing.
- >1000 QPS的时候就需要partition了。
- 单个MySQL大概不超过500GB.
10 min Architecture + Database (High-level Design)
- Stateless Service: HTTP+LB，基本就要cover前面的feature
- Stateful Service: websocket/polling，例如slack发消息、在线离线
- 3rd-party: 需要假设他们不可靠，需要retry，怎么防止重复request，
- 画一个系统关键component的图，将每个操作end-to-end都过一遍
- 标配是client - LB - ApplicationServer - DB/File Storage(pic,video).
10 min System interface definition 将系统对外开放的API写出来
- 将contract翻译成函数+参数的形式
- 确保包括了出题人所有想要的操作
10 minDefining Data Model
- 可以理解为数据库中需要存储的entity，clarify数据是如何在系统中各个component之间流动的
- guide for data partitioning and management比如storage, transportation, encryption.
10 min Detailed Design
- 将系统中关键的两三个component拎出来解释有哪些实现方式和对应的pros&cons.
- 在讨论时可以举一些场景例子解释在哪些情况下有优势，而不能解决哪些情况。缓存设在哪层会产生哪些好处/不足。根据需求是否有些小hack可以做，好处坏处是什么。
- How to sca
Identifying and Resolving bottlenecks 找出系统瓶颈并提供mitigate方案
- Single Point of Failure？
- Data Replicas保证在少量数据库崩时还能提供数据？
- Server Replicas保证在少量服务器崩时还能提供服务？
- 如何monitor并设置alert？阈值是多少？

模拟题

Design Slack

Use Case
- Functional: 这个需求太大了，可不可以分成MVP版本和后续bonus版本。
  - Direct Messsage
  - Channel Message
  - Multimedia Message
  - Link preview
  - Search history
  - Bonus: Group Membership, Notification, Highlight unread message
- Non-functional: 需要一上来就问用户数量级，例如日活200M，那平均到每秒就是/10^5左右，然后可能PEAK单独乘个5。
  - High availability
  - High reliability(没有数据丢失)
  - Consistent
  - High performance: real time
- Not covered:
  - Authentication/Authorization
  - Mobile/Web Client Side
  - Throttle: 1s upto 10msg
Constraints 分别计算QPS和data_volume
- One domain
- DAU: 10M
- Peak direct message: 10M 100条 5倍于平时 / 86400 = 50K msg/s
- 每条msg多大？100bytes
- Peak throughput: 50000 * 100 / 1000 = 100MB/s
- Storage per day: 100MB * 86400 = 10TB
- Group limit: 1000 members in a group
Architecture & Database
分成不同的microservice进行互动，每个service的特征也就基本决定了选择什么DB和cache。
- Account service: manage user info (SQL + redis/memcache)
- Friends service: may not need in slack (SQL + redis/memcache)
- Group service: manage group membership info (SQL + redis/memcache)
- Media service: process uploaded multi-media/linke info (amz S3 + Content Delivery Network加速查找媒体文件)
- Notification service: notify users for new message (Kafka topic) 这里值得提一句exactly once的notify非常复杂，需要做2-phase commit.
- Message storage service: store message (DynamoDB, infinite scale，对应的cache叫DAX) Cassandra和dynamo类似比如hinted handoff(for consistency)，但也有区别，如cassandra conflict是last-write-win.
- Message search service: message search index and lookup，每个message发完要async到这里来index一下，用elasticsearch做搜索，用lucene，用inverted index实现。
- Emoji Service: 对message的回应。存放在redis，不过缺陷是data loss.
- Channel service: 决定每个request该到哪个service去
API设计
REST或gRPC/Thrift. gRPC用的是protobuf，比thrift成熟一些。
Public API:
- 打开页面getChannels(user_id)
  - store last viewed channel
  - store visible channels: (recent DM & membership fo the group)
  - show unread msg/last msg preview: denormalized data
- 发消息SendMessage(sender_id, receiver_id, message_type, message_text, media_id)
  - message_type 可以是DM或group
  - create_timestamp, update_timestamp, expiration_time, state会被channel service加进去
  - state可以是received/sent/notified/viewed/deleted.
- updateMessage(message_id, message)
- uploadFile(user_id, permission_group, file_description, extra_metadata): 常见的upload file都是用一个MessageQueue或workerPull处理的。当用户上传图片，服务器生成随机key，在s3上申请地址，将media连同key传输过去，复制备份，postprocesssing后服务器将media+key的URL存入user profile. 顺便讲解一下link preview, 可以是sender-side（发送方随着链接生成preview两个打包发送，不过这样可以伪造）或receipient-side（接收方只在收到链接时生成preview）或server-side（由服务器生成preview，不过也可以通过识别server进行伪造preview）。
- lookupEntity(user_id): 内部用Trie实现，快速查找，可能存在客户端。
- joinGroup(user_id, group_id)
- getDirectMessage(user_id, friend_id)
- getGroupMessages(user_id, group_id)
- CRUD for group info
- CRUD for user info
  Internal API: 内部service之间处理数据使用
- media service: processMedia(media_id): 包括replicate media, post-processing(generate preview/thumbnail), distribute to CDN（media chop成很小部分例如几秒）。
- notification service: notifyUser(user_id, sender_id, message_id, msg_preview),可以用DB或kafka，request thru message queue, async把message交到worker pool，之后会有handler来发消息（call特定API如websocket/苹果安卓的推送API），接到receipt之后可以用DB存下来，如果call了通知API返回成功了message的state才会标记成notified，如果没成功会有个background job check一下尝试重call notification endpoint.

Data Model

User table (SQL mysql单机平均p50也就5ms):

id uuid (shard key)
name string
status online/offline (websocket可以做，只要没expire就是在线)
location string
team string

Friend table (SQL):

user_id_1 uuid (shard key)
user_id_2 uuid
connected_date date
last_view_date date

Group membership table (SQL):

group_id uuid
user_id uuid (shard key)
join_date date
role admin/member
last_view_date date

Channel table (redis can handle 100k RPS):

key: user_id
value: list of jsons like: 
group/user_uuid {
  channel_name,
  unread_msg: 10,
  last_msg_preview: ok...
  timestamp: xxx
}

message storage table (dynamodb):

container_id: group_id for groupchat, sorted{userId1+userId2} for DM (partition_key)
timestamp_msg_id: (sort_key)
msg_id: uuid
sender_id: uuid
message: string
created_timestamp: timestamp
updated_timestamp: timestamp

emoji table (redis):

key: msg_id
value: list of json like
user_id {
  name,
  emoji
}

Design Web Crawler

Business/Use Case
- Functional:
- a list of domain and seed URL
- async crawl
- parse document contents and store the data. need to index the contents
- discover new urls and add to unvisited urls
- Non-functional:
- High scalability; Flexibility in Scale(因为可能一开始没法估计有多少个url，可以逐渐增加机器)
- Fault Tolerant（从任何一个部分无缝连接地重启）; Idempotent
- Schema flexible & extensible (当field变多需要能够adapt)
- Not covered:
- server side authentication
- server side throttle & rate limiting
Constraints Calc
- Empirical results driven
- DB: data size is the limitation; foresee the growth?
- server side throttling bottleneck:
- different account
- different IP across nodes
- don’t bring down the crawlee
- same node to crawl diff sites in parallel
Architecture
- scheduler: 定时重复或者ondemand来爬虫，将一些seed写入metadata. 确定需要crawl哪里后将seed插入record（重复就abort）不等crawler来执行、将progress更新进metadata，出错就从读seed开始。
- crawler: 从metadata读url，deep copy把未整理的内容存入raw data. stateless，读url，如果db中显示已经爬过了就跳过、crawl完就存入rawdata并更新state为CRAWLED.
- parser: async地读取内容，把后续url也存入metadata，这一步也要去重. 读需要parse的record然后尝试parse，如果失败就更新state为STUCK，成功就存入cleaned_data并更新为PROCESSED.
- sweeper: 监控进度，重试crawler/parser。notify the failure/unexpected schema. 需要把STUCK的都重试下，或者发notification。或者通过检测时间差看看是否长时间queue了或者一直还在crawl，也重新入queue.
  在scheduler和crawler、crawler和parser之间都是用message queue，这样是async的可以保证separate of concern.
API Design
- addScheduledCrawl(domainNames, cronExpression)
- startCrawling(domainNames, iteration, blacklistUrls)
DB choice
- raw data(crawl出来的)：key-value，可以用s3/dynamo/cassandra/mongoDB
- cleaned data: 需要durability和transaction所以用SQL
- metadataL SQL

Data Model

raw_data(S3):

1
2
3

id uuid,
raw_data html/json,
created_at timestamp

cleaned_data(SQL):

hash_of_url_iteration string,   （这样可以去重且不影响retry）
type scheduled/triggered,
url string,
iteration int,
extracted_field...

metadata(SQL):

// schedule table
id uuid,
cron string with crontab format,
created_by string,
created_at timestamp,
name string,
urls string,
state ON/PAUSED/OFF
// iteration_progress
schedule_id uuid,
iteration int,
started_at timestamp,
urls_found int,
stuck_count int,
crawled int,
processed int
// url_record
hash_of_url_iteration string,
url string,
iteration int,
state QUEUED/CRAWLED/PROCESSED/STUCK,
created_at timestamp,
updated_at timestamp,
notified boolean,
deleted boolean

Design ticket booking system (12306)

Business
- Functional
- search route
- route breaking
- book route ticket
- show remaining ticket
- seat reservation
- cancel any time
- Non-functional
- reliable
- performant
- race-condition: 抢座可能会出现read-modify-write conflict，通过row level 2-phase locking解决：取non-exclusive读锁，要下单时要变成exclusive的写锁，此时其他读锁都会被踢出去。这个QPS=100K. 还结合multi-version concurrency control。此外还可以考虑MySQL和Postgres的snapshot isolation，读可能会有stale数据但不会被写block、写也不会被读block。
- transactional; financial related
- Not covered
- payment
- capcha
- throttle at LB
Constraints
- QPS 1M, grow to >10M. Peak: 10M/10k trains = 1k QPS per train; 假设没那么多车次，就按10K QPS好了
- Read-Write Ratio: 假设是10:1，那就对于每个车次有100K，单个SQL的shard也是可以handle的。
Architecture
- Load Balancer
- Booking Service
- Seat Allocating Service
API Design
- searchRoute(from, to)
- bookTicket(from, to, ticketCount): 插入booking table, 返回increment_id和request_id，之后async去读对应行数看看state是否为CONFIRMED。
- getSeat(route, ): 可以做多条route的动态座位划分，
  background job来定时看看table里哪些人可以取到作为、哪些route要被重新开放预定。
  将已经发出的车次挪到history data warehouse去。
Databse Choice
因为要进行transactional的更新，所以选用SQL。
为了保证scalability，需要进行shard。
Book了之后不能data loss. Replica可以选择synchronize

Data model/schema

// booking
id auto_incre_int,
booking_uuid uuid(hash of 车次&datetime) sharding
train_num string,
start_time datetime,
user_uuid uuid（护照号、身份证也行）,
ticket_count int,
route string/uuid,
created_at timestamp,
state [EMPTY, CONFIRMED, CANCELED]
index on passenger_id, request_id, route.
primary_key on auto_incre_int, 也用来决定谁抢票赢了
// sea t allocating
id auto_incre_int,
booking_id int,
seat_num string,
created_at,
state []

URL Shortening service

需求分析
- Functional
  - 输入一个长链接，生成唯一且更短的链接。
  - 输入短链接，需要重定向到原链接
  - 如果愿意，用户可以customize生成的短链接
  - 短链接不是永久的，用户可以定义expiration
- Non-functional
  - Highly available，否则短链接都没法用了
  - Minimal latency，最短时间完成转换
  - 短链接不能guessable/predictable
- Advanced
  - Analytics friendly，方便统计redirect数据
  - 支持REST API，其他service可以call我们的service
Capacity Estimation and Constraints
- Traffic Estimates
  - 读操作（redirect from short URL）要多于写操作（create new URL），具体比例假设是100:1
  - 如果每个月需要生成500 Million的新短链接,对应到QPS就是500M / (30 * 24 * 3600) = 200; 那么每个月redirect次数是50 Billion，对应到QPS就是20K/s.
- Storage Estimates
  - 假设每个长短链接对需要存储5年，每个存储对象大概500 bytes，则需要的存储空间为500M * 5yr * 12mo * 500bytes = 15TB
- Bandwidth Estimates
  - 写入操作QPS为200/s，incoming data大概是200/s * 500bytes = 100KB/s.
  - 读取（redirect）操作QPS为20K/s，outgoing data大概是20K/s * 500bytes = 10MB/s.
- Memory Estimates
  - 其实就是考虑缓存。80-20rule指的是20%的热门URL产生的80%的流量，那么我们需要将这20%的对象存在内存中。
  - 假设缓存每天更新，只需要存当天的20%的read requests，即20K/s * 3600s * 24hr * 500bytes * 20% = 170GB. 不过其中可能有很多重复的hit，因此实际占用的可能少于170GB。
Architecture
Jamboard linke
- Key Generating Service是一个offline预先生成短链接的service。为什么不直接hash给定的url呢？因为这个hash可能重复、而且不同用户上传相同长链接的话需要分辨，这个当然可通过append auto-inc的办法解决，但可能overflow；或者可以append user_uuid，但需要user登陆且可能重复。因此用这个KGS+memcache，从DB中不断把生成的短链接读到cache里并标记用已使用
- Cleanup Service是一个lazy删除过期链接的serivce，可以在off-peak时扫描并删除，也可以当user来读过期链接时再删除。被删除的key可以被reuse。
API
- createURL(clientKey, originalUrl, customAlias = null, userName = null, expireDate = null)
- deleteURL(clientKey, shortUrl)
DB Choice
- 选择NoSQL主要是以下考虑：
- 存储数据量很大(每个月500M rows)
- 每个row其实很小
- 除了user-url关系，没有强relationship，因此考虑nosql
- Read heavy
- Partitoning
- Range based: 直接根据短链接开头字母分，像字典一样，但可能造成不均匀分布
- Hash based: 对短链接求hash来决定存入哪个partition，用consistent hashing防止overloaded partitions.
- Cache
- memcache来存经常性被访问的短链接-长链接对儿。
- evict可以用LRU排除

Data Model + schema

URL：

shortened_url: string (primary key)
original_url: string
created_at: datetime
expire_at: datetime
user_uuid: UUID

User:

user_uuid: uuid (primary key)
name: string
email: string
created_at: datetime
last_login: datetime

Pastebin

需求分析use case
- Functional:
- 存入text，生成URL
- 根据URL访问text
- 设置过期时间或默认过期时间
- custom url
- Non-functional
- reliable，数据不丢失
- available，能根据url访问text
- 访问速度快
- url和text之间不能guessable
- Bonus/Non-goal
- DA支持，统计访问次数
- 作为第三方允许别的service通过API调用
Capacity + Constraints
- text limit: 10MB, avg 10KB
- read-write ratio: 5:1, READ-HEAVY
- write: 1MM pastes/day = 1MM/24/3600 = 12 QPS，网络bandwidth为120KB/s
- read: 5MM read/day = 58 QPS, 类似地，网络bandwidth为600KB/s
- storage volume: 1MM * 10KB = 10GB/day, 存10年就是36TB。注意这只是text本身，还需要存url作为key，总共有3.6B条记录，假设url为6个字符每个字符占用1Byte的话，需要22GB，不是一个数量级因此可以忽略。
- cache volumn: 假设20%的链接贡献了80%的流量，需要将每天 5MM * 10KB * 20%缓存下来，即10GB。
Architecture
和shorten-url非常类似
API
- addPaste(clientKey, textContent, customUrl = null, textTitle = null, userName = null, expireDate = null)
- getPaste(clientKey, accessUrl)
- deletePaste(clientKey, accessUrl)
Database Choice
- 和shorten一样，都是read-heavy, 单位object小，因此也可以考虑NoSQL
- text作为object也可以用amazon s3存放，这样之后想扩到支持图片上传也可以。

Data Model and schema
还是和shorten类似

Paste:

hash_of_url: string (primary key)
content_key: string (for look up in object storage S3)
created_at: datetime
expire_at: datetime
user_uuid: UUID