淘先锋技术网

首页 1 2 3 4 5 6 7

Design复习

 
FLAG‎ > ‎

Design复习

  • 如何秒掉99%的海量数据题！！！ http://blog.csdn.net/v_july_v/article/details/7382693
  • 十道海量数据题： http://blog.csdn.net/v_july_v/article/details/6279498
    • 总而言之就是hash function写到小文件，然后再处理，然后再归并
    • 注意
      • bloom filter
        • k个hash，映射到bit vector
        • 快速，节约，但有false positive且不能进行删除操作
      • hashing
      • bit-map
      • heap
      • external sort
      • trie
      • mapreduce
  • Quora关于系统设计题 http://www.quora.com/Job-Interviews/How-should-I-prepare-system-design-questions-for-Google-Facebook-Interview
  • 很有见地的一系列博文！！link
    • 重点看GFT三家的解剖！！！
    • “做大的艺术”也有对分布式的讨论
    • 缓存人气作者
  • 非常好的总结！！！link
  • facebook design 总结！！其实也是一个非常非常好的general总结 link
    • Memcache （不是memcached，那个开源的内存cache）
    • Scalable Web Architecture and Distributed Systems
      • 对于一个像flickr一样的网站，更重要的是requesting time而不是上传时间。所以优化只要集中在读的一侧而不是上传的一侧
  • flickr架构 link
  • Pinterest架构 link
  • 买买提上关于除了刷题的建议link
  • 看一下段地址的完全实现过程
  • 解剖Twitter http://blog.sina.com.cn/s/blog_46d0a3930100fai8.html
  • Google Calendar的实现过程
  • Google的系统设计题：http://www.mitbbs.com/article_t/JobHunting/32562595.html
    • 如果实现像facebook一样的activity broadcast.
    • 一个朋友f1更新一条信息后，他的所有朋友都要看到这条信息。
    • 条件：
    • 1. 朋友数量极大。
    • 2. 有的朋友在线，有的不在线，不在线的登陆后要能看到。
    • 3. 如果储存空间有限，如何处理。
  • 如何开发一个聊天室 http://book.mixu.net/node/ch3.html
  • Terasort link
    • 普通归并排序的瓶颈在于合并是是sequential的
    • Terasort保证mapper处理的各个块，i的所有元素都比i + 1的大，这样就可以自然的归并了

Keywords for Design

Hired in Tech - System Design link

  • 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

  • Vertical scaling
    • CPU cores, RAM, disks, etc.
    • why not a full solution? Real-world constraints...
    • Updating drive - updating IO of databases
    • RAID
  • Horizontal scaling
    • Use more cheaper hardware, multiple servers
    • problem of CONSISTENCY, SYNCHRONIZATION
    • 用load balancer回复客户端请求，即暴露一个公共IP给外部；而所有服务器都用的内部IP，客户请求都是由load balancer来分配！ 
  • Load balancing
    • Round-robin请求 to 各个服务器
    • Implement load balancer:
      • Software: HAProxy etc.
      • Hardware: 100K for decent one...
    • Use multiple load balancers to avoid single node failure at the load balancer
    • (from HiredInTech) 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. Also, when one server is down, use others (reliability)
  • Caching
    • .html - redundancy, no template, must write <header> ... lots of find and replace 
    • MySQL query cache
    • memcached 
      • memory cache, which is also a server
      • if read-heavy, then this is very efficient!
  • DB replication
    • master-slave, benefit for read-heavy websites
    • master-master, 
    • load balancer can also generate a single-node failure
    • use heat beat to detect activity
  • DB partitioning
    • different multiple servers: mit.thefacebook.com, harvard.thefacebook.com
    • A-H to server1 I-Z to server 2, etc.
  • 最后还有一段实例，很好~
    • Sync between data center?
      • load balancing on DNS level!

Scalability for Dummies link

  • part 1, replicas
  • part 2, database can become the bottleneck. Switch to NoSQL.
  • part 3, caching - in-memory caching like Redis, not file-based caching!
    • cache queries (but hard to remove)
    • cache objects, makes asynchronous processing possible
  • part 4, asynchronism
    • async 1: cache the dynamic content, pre-rendered HTML
    • async 2: (computing-intensive tasks) pass to backend, constantly check if the job is done

Database Sharding

  • 基本可以用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

公司核心技术复习

  • 必看论文
    • Google: Google File System, MapReduce, Bigtable
      • Bigtable
        • 类似于一个分布式kvs
        • key是<行，列，timestamp>
        • tablet是最小单位
    • Facebook: Cassandra
    • Amazon: Dynamo
  • 注意distributed data store
    • Non-relational, therefore quick

Google

  • 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的实现，以及与数据库的联系，讲得不错！

Facebook

  • Zuck's law
  • 这篇文章！！！！http://www.mitbbs.com/article_t/JobHunting/32741713.html
  • Hiphop compiler
Facebook Stats
Facebook Infrastructure

Facebook feeds 
  • http://readme.skplanet.com/wp-content/uploads/2012/11/0-3_Facebook1.pdf 讲得很爽
  • 系统的几个文章
    • 关于feeds的general discuss！！！！link
    • SO上的 link
    • 这里面的几个链接都非常好！！！
      • push model for people who don't have many followers
      • pull model for the other way around
Tech Talks
  • "Facebook is not about actions, but interactions"