1.系统设计介绍

2.系统设计七剑客

• 同步
• 网络
• 数据库
• 分布式
• 性能
• 估算
• 面向对象
• 案例
  • 社交网站信息流
  • 日志统计
  • 网络爬虫
  • 电商产品页面

1）Concurrency （并发）

• Thread vs. Process
  • 一个进程拥有独立的内存单位，而线程是共享内存的
  • 一个进程拥有一个主线程
  • 进程是系统进行独立资源调度分配的单位
  • 线程是真正的CPU分片时间
• Consumer and Producer
  • 两个线程，两个线程共同访问一个缓冲区
  • 一个线程是生产者，将数据放入缓冲区，另一个线程是消费者，消费缓冲区中的数据
  • 如何保证生产者不会再缓冲区满的时候放入数据，消费者不会再缓冲区空的时候访问缓冲区
  • Blocking Queue是一种典型的这种容器。
• Tracking:
  • Synchronized 同步方式
  • Asynchronized 异步方式

2）Network 网络模型

• The Seven Layers of OSI

  • Application Layer HTTP协议
  • Presentation Layer
  • Session Layer
  • Transport Layer TCP/UDP
  • Network Layer
  • Data Link Layer
  • Physical Layer

• Visit URL

  • What happens after you typed a URL in your browser and pressed return key?
  • 需要连接远端服务器
    • 需要服务器的IP和端口
    • 如果没有IP和端口，则需要进行寻址，访问DNS(domain naming service)服务器，通过分层可以找到相应DNS
    • DNS返回服务器的IP
    • 和远端服务器进行TCP连接，没有指定端口时，默认80端口
    • 和服务器建立HTTP会话
    • 远端服务器返回数据，浏览器解析数据，本渲染出网页。
  • 发送请求到服务器

3）Database 数据库

• Relational DB vs. KV Store
  • KV在需求简单，数据量又较大，没有太多关联关系时使用。
• Sharding vs. Clustering
  • 一般认为单表数据量控制在1000w以内，如果超过这个量，则需要进行拆表
  • 通过协调器，来均衡各个服务器的负载。内部智能动态调度。

4）Distribute System 分布式

How to scale Tiny URL service?

• Stateless frontend servers behind a load balancr 前段服务做负载均衡，Stateless 没有状态，当用户操作时，当工作做了一般，转换服务器之后，还可以继续，而不是仍然要使用原有的服务器。
• Sharded/replicated database(on shortlink code)
• Memcached to scale read traffic 通过缓存，缓解数据库读取压力
• Spread write load 可以通过先定位，再写入的方式
• Locally buffered event tracking + async flush to high-throughput message queue(kafka)
• Use a distributed unique ID generator(64-bit)

5) Performance 性能

CPU -> L1 -> L2 -> L3 -> SSD -> HD -> Network 速度越来越慢

6) Estimation 估算

How many piano tuners are there in the entire world?

• 考察思维逻辑推理
• 对估算是否有考虑

Tiny URL:How much is total storage?

• URL 的平均长度 10-1000 字节
• 假设目前已经存了一亿个
• 新增的URL大概是一天100000条（1秒增加一条）
• 一天大概需要查询一亿次，每秒1000次

7）Design Patten 设计模式

23 patterns:

• MVC
• Singleton
• Factory
• Iterator
• Decorator
• Facade

3.案例

News Feeds

• Define feed
  • 首先要定义feed的内容，可以是一个新闻的片段，应该包含内容，发布人，发布时间
• Organize
  • aggregate 同一个人发布多条信息，是否需要归类
  • dedup 如果同一条信息多人发布，能否去重
  • sort 更具发布时间，或内容的重要新（亲密度，高级用户）
  • Level 1.0
    • Database Schema：
      • User
      • Friendship
      • News
    • Get Newsfeed
      • merge news
    • Newsfeed vs. News
      • Newsfeed是一个集合，我的主页需要显示的，我的好友圈
      • News仅仅是一个新闻。
    • Why bad?
    • 100+ friends
      • 1 Query --> Get friends list
      • 1 Query --> SELECT news WHERE timestamp>xxx AND sourceid IN friend list LIMIT 1000
    • IN 非常慢
    • Sequential scan or 100+ index queries
  • Level 2.0
  • Pull vs. Push
    • Pull：Get news from each frined,merge them together.
    • Push: NewsFeed generated when news generated.
  • Level 3.0
    • Popular star
      • Flowers 13M + 人数太多
      • Async Push may cause over 30 minutes
    • Push + Pull
      • 对于明星人群，不要push news 给 flowers
      • 对于普通人，两者结合
  • Level 4.0
    • Push disadbantage:
      • Realtime
      • Storage(Duplicate)
      • Edit
    • Go back to PULL:
      • Cache user's latest news
      • Broadcast multiple request to multiple servers(Shard by userID)
      • Merge & Sort
      • Cache newsfeeds for this user with timestamp

Stats Server

How are click stats stored?

• 每次点击就会将写入数据库
• 增加中间层，再根据某种策略，将中间层写入数据库
• 设计出一个 low-latency messaging，能够缓存数据，还能够存入数据库

Cache Requirement

• 当收到request，首先在cache中寻找，如果找到则直接返回
• 如果没有找到则传入系统
• 设计cache只能存储一定量的request，如果超过，则删除最早的request。
• 查找，删除，插入 O(1)

Web Crawler

Amazon Product Page

• The product page includes information such as
  • a) product information
  • b) user information
  • c) recommended products