• sharding (partition)
• 非常好地区分sharding和replication！link
• load balancer
• master-slave replication
• consistent hashign
• bloom filter
• Kafka vs RabbitMQ
  • 两个都是消息队列，message broker
• CDN
• peak throughput

• Process
  • Step 1 - Constraints and Use Cases （5 min！）
    • Very first thing to do when faced with the problem: clarify the constraints and use case.
    • Don't panic about the correctness, write some numbers down!
    • Write on board: the use cases like
      • (Basic features)
      1. take a url => return a shorter one (shortening)
      2. take a short => return the original (redirection)
      3. (ask some more augmented features?) 
      4. customized url?
      5. analytics?
      6. automatic link expiration?
      7. UI? API?
    • Write on board, constraints. Traffic and Data
      1. scale down to seconds! Estimate the traffic and data
      2. 100M new urls per month
      3. What can be cached?? 10% from shortening and 90% from redirection
      4. how long is url?
    • 都是先算几年或者几个月有多少，然后scale到秒！
    • Ready heavy? Write heavy?
  • Step 2 - Abstract Design
    • draw sketch，不要管细节！先把基础功能实现！
    • Application service layer 和 Data Storage Layer
  • Step 3 - Understand Bottlenecks
    • Need a load balancer? Data is so huge that need to distribute the database?
    • Talk about the tradeoff!!!
    • 这一步要结合1和2，比如1中的data per sec，就可以用来估算数据库是否有效？或者如果每次都要搜遍数据库的话，会不会效率过低？Bottlenecks identified!!!
  • Step 4 - Actual Design of a Scalable System!
    • (next section)
    • whenever get challenged by interviewer about the architectural choices, acknowledge that rarely an idea is perfect, and outline the advantages and disadvantages of your choice
    • add load balancer is not only for amortize traffic, but also to deal with spiky traffic!! and shut them down when the traffic goes back to normal. 
    • Don't forget to mention we need benchmark, profiling, and load test the architecture
• Fundamentals
  • (Scalability @Harvard)
  • (Scalability for Dummies)
  • (Database sharding)
  • and don't forget about the monitor
  • sometimes there will be a flash traffic when many people want to watch/read the same thing
• Examples
  • (highscalability blog)
• Wrap-up
• Practice

Scalability @Havard

系统设计面试题思路汇总 link

• 基本可以用Google三驾马车解决：MapReduce, GFS, BigTable
• 三驾马车之前，常用架构是：database + sharding + cache
• 虚拟节点技术
  • 虚拟节点技术：该技术常用于分布式数据分片中。具体应用场景是：有一大坨数据（maybe TB级或者PB级），我们需按照某个字段（key）分片存储到几十（或者更多）台机器上，同时想尽量负载均衡且容易扩展。传统的做法是：Hash(key) mod N，这种方法最大缺点是不容易扩展，即：增加或者减少机器均会导致数据全部重分布，代价忒大。于是乎，新技术诞生了，其中一种是上面提到的DHT，现在已经被很多大型系统采用，还有一种是对“Hash(key) mod N”的改进：假设我们要将数据分不到20台机器上，传统做法是hash(key) mod 20，而改进后，N取值要远大于20，比如是20000000，然后我们采用额外一张表记录每个节点存储的key的模值，比如：node1：0~1000000；node2：1000001~2000000。。。。。。这样，当添加一个新的节点时，只需将每个节点上部分数据移动给新节点，同时修改一下这个表即可
• Q:设计一个系统，使写速度提高 -> BigTable, 并发写到一个cache里面（随机写），然后cache满了在写到磁盘（顺序写，快！）

High Scalability

• YouTube architecture
  • Most popular content is moved to CDN
• 8个重要的scalable design pattern link
• What is your scalability plan link，
  • 写的不错！是一步一步来的
• 咖啡店的比喻，不错！link

• Web crawling and indexes link
  • the crawler should be distributed
  • robots.txt
  • DNS resolution is a well-known bottleneck in web crawling
  • BFS的时候用优先队列，权值为key
• DESIGN
  • 大合集！！！
  • 分布式crawler link
  • autocomplete
    • trie
    • HMM？
    • popularity
  • 读写锁
    • read write lock, 又叫share lock和exclusive lock
    • lock()和trylock()的区别：一个是blocked一个不block
    • 这篇写得不错 link
    • 两道面试题 link link
    • 注意writer starvation
    • producer comsumer link
    • mutex和cv实现semaphore link
  • distributed kv storage (DHT B+ tree)
  • distributed lock
    • 其实还是基于Paxos
  • distributed hash 
    • 分布式哈希基本介绍 link link
    • 一致性哈希 link
      • 普通线性hash缺点就在于如果移除、添加机器，需要有大量数据迁移！
    • GFS是基于metadata的实现！看！！->单点故障->一致性哈希
• 这篇high scalability link
• how to implement online booking link
• 购物车 link
  • cookie和session的实现，以及与数据库的联系，讲得不错！