• Amazon 电梯设计

    楼主前段时间Amazon onsite,遇到了Amazon经典的电梯设计题目,下面是我对这个题目的总结,也是答案不是最好的,欢迎大家来补充。
    下面是我的onsite 面经:http://www.1point3acres.com/bbs/ … p;page=1#pid1956961
     
     
    我感觉对于OOP设计问题,关键要和面试官进行讨论,弄清情景situation ,who will use it,在这个situation都是有哪些对象,他们在干什么,他们之间是什么关系,然后一个对象一个对象的去分析这个对象应有的属性,和行为。多和面试官讨论,越细致越好!如果可以使用什么单例,或者factory method 来设计的话,multi threading, 就尽量的添加上这些东西。
     

    elevator:

    First ask the interviewer what kind of elevator?  there is only one elevator serving that building or multiple elevators serving the building simultaneously?
    this situation is that: there is one elevator serving the building.  there are many floors in the buliding. Maybe there are some users in different floor pressing the button simultaneously. This results in some requests to RequestProcessCenter for processing. The  RequestProcessCenter figure out the first request that need to be processed in such an algorithm that the distance between target floor and current floor is shortest.

    [Read More...]
  • [系统设计/OOD] 系統設計救星! 一天內手把手教你面試System design

    前言:常看到有人問 system design需不需要準備 new grad會不會考system design 我想給地裡的戰友們建議 當然準備面試刷題是基本中的基本 但當你刷到一定程度後 刷題投資報酬率就開始低了 這時我真心建議可以花些時間讀system design 因為你花在這個的前10-20小時投資報酬率非常高!基本的觀念有了以後可以apply到所有的問題 面試之前不管HR跟你說有沒有system design你都不怕 廢話不多說 直接進入主題
     
    我的所有資料來源都是地裡還有以下連結
    https://www.evernote.com/shard/s576/sh/7e58b450-1abe-43a8-bf82-fbf07f1db13c/049802174415b418a2e65f75b744ab72
    https://github.com/checkcheckzz/system-design-interview
    https://www.interviewbit.com/courses/system-design/
     
    這篇文章主要是把所有手上資源照priority順序加上一些自己的整理 用簡單的方式介紹怎麼Ace system design 依照priority順序分成
    明天面 下禮拜面 下個月面 跟明年面
     
    =====明天要面system design=====
     
    迷途書僮:誒jyt0532 我明天就要面試了 沒空讀那麼多你給的文章 該怎麼辦?
    jyt0532: 很好 今天幸好你遇到我 我用最少的時間讓你知道明天面試的時候大方向怎麼走
    Step1: 先問所有requirement, spec 這個系統需要提供什麼功能
    Step2: Constrains: 問他我們需要處理多少traffic, 多少data, latency重不重要 A和C選哪個
    Step3: 計算需要多少機器 要用什麼storage
    Step4: Abstract design: 先畫出大架構! 每個會出現的component都要畫出來 再看面試官希望你深入講哪個component
    Step5: Scale: 讓你的system有fault tolerance, scale成大公司的系統架構
     
    迷途書僮: 等等step2的A和C是什麼
    jyt0532: CAP的A和C 如果你明天要面試你不知道CAP是什麼 那我的建議是你今天早點休息 明天才有精神 地球是很危險的
    迷途書僮: 別這樣啦 我幫你加大米拜託給我一個最簡單最好的解釋
    jyt0532: 既然你都這麼說了 今天幸好你遇到我 把這個看完你就通透了http://ksat.me/a-plain-english-introduction-to-cap-theorem/
    迷途書僮: 喔原來是這個 那這4個step 你這樣講真的很抽象 可不可以舉個例子 我可以apply到所有system design的題目
    jyt0532: 光說不練假把戲 我帶你手把手跑一次system design process
     
    來個基本的 假設現在要design一個hash
    Step1,

    [Read More...]
  • POI-GeoHash

    POI-GeoHash

    https://dzone.com/articles/designing-spacial-index
    Geographic Information Systems (GIS) is an interesting area of exploration because it poses two significant challenges: latency at scale and modeling spatial locality.
    Let’s say you’re visiting NYC and need an Internet connection. Where’s the nearest Wi-Fi hotspot?How might an HBase application help you answer that question? What kind of design decisions go into solving that problem, and how can it be solved in a scalable way?
    You know you want fast access to a relevant subset of the data. To achieve that, let’s start with two simple and related goals:

    1. You want to store location points on disk such that points close to each other in space are close to each other on disk.
    [Read More...]
  • Facebook design interview

    这里原帖地址: http://www.mitbbs.com/article_t/JobHunting/32492515.html

    以下为转载内容

    ===========================我是分割线==================

    稍微总结一下

    1. 入门级的news feed
    http://www.quora.com/What-are-best-practices-for-building-somet
    http://www.infoq.com/presentations/Scale-at-Facebook
    http://www.infoq.com/presentations/Facebook-Software-Stack
    一般的followup question是估算需要多少server
    另外这个帖子有讨论
    http://www.mitbbs.ca/article_t/JobHunting/32463885.html
    这篇文章稍微提到要怎么approach这种题,可以稍微看看
    http://book.douban.com/reading/23757677/

    2. facebook chat,这个也算是挺常问的
    http://www.erlang-factory.com/upload/presentations/31/EugeneLet
    https://www.facebook.com/note.PHP?note_id=14218138919
    http://www.cnblogs.com/piaoger/archive/2012/08/19/2646530.html
    http://essay.utwente.nl/59204/1/scriptie_J_Schipers.pdf

    3. typeahead search/search suggestion,这个也常见
    https://www.facebook.com/video/video.php?v=432864835468
    问题在这个帖子里被讨论到,基本上每个问题,在视频里都有回答
    http://www.mitbbs.com/article_t/JobHunting/32438927.html

    4. Facebook Messaging System(有提到inbox search, which has been asked before)
    messaging system就是一个把所有chat/sms/email之类的都结合起来的一个系统
    http://www.infoq.com/presentations/HBase-at-Facebook
    http://sites.computer.org/debull/A12june/facebook.pdf
    http://www.slideshare.net/brizzzdotcom/facebook-messages-hbase/
    https://www.youtube.com/watch?v=UaGINWPK068

    5.

    [Read More...]
  • chord algorithm 分布式hash表

    出处:http://www.cnblogs.com/gnuhpc/

     

    P2P的一个常见问题是如何高效的定位节点,也就是说,一个节点怎样高效的知道在网络中的哪个节点包含它所寻找的数据,如下图:

    clip_image002

    对此,有三种比较典型的来解决这个问题。

    Napster:使用一个中心服务器接收所有的查询,服务器告知去哪下载其所需要的数据。存在的问题是中心服务器单点失效导致整个网络瘫痪。

    clip_image004

    Gnutella:使用消息洪泛(message flooding)来定位数据。一个消息被发到系统内每一个节点,直到找到其需要的数据为止。当然,使用生存时间(TTL)来限制网络内转发消息的数量。存在的问题是消息数与节点数成线性关系,导致网络负载较重。

    clip_image006

    SN型:现在大多数采用所谓超级节点(Super Node),SN保存网络中节点的索引信息,这一点和中心服务器类型一样,但是网内有多个SN,其索引信息会在这些SN中进行传播,所以整个系统的崩溃几率就会小很多。尽管如此,网络还是有崩溃的可能。

    现在的研究结果中,Chord、Pastry、CAN和Tapestry等常用于构建结构化P2P的分布式哈希表系统(Distributed Hash Table,DHT)。

    DHT的主要思想是:首先,每条文件索引被表示成一个(K, V)对,K称为关键字,可以是文件名(或文件的其他描述信息)的哈希值,V是实际存储文件的节点的IP地址(或节点的其他描述信息)。所有的文件索引条目(即所有的(K, V)对)组成一张大的文件索引哈希表,只要输入目标文件的K值,就可以从这张表中查出所有存储该文件的节点地址。然后,再将上面的大文件哈希表分割成很多局部小块,按照特定的规则把这些小块的局部哈希表分布到系统中的所有参与节点上,使得每个节点负责维护其中的一块。这样,节点查询文件时,只要把查询报文路由到相应的节点即可(该节点维护的哈希表分块中含有要查找的(K,V)对)。

    这里介绍的Chord算法就是解决网络内节点定位问题的一种P2P协议。它通过多个节点跳转找到我们所查找的资源:

    clip_image008

    我们先看看它是如何进行的,随后再总结其特点和操作特征,以及一些实现。

    1.Chord里面的基本要素

    节点ID:NID(node identifier),表示一个物理机器,m位的一个数字(m要足够大以保证不同节点的NID相同的几率小的可以忽略不计),由节点机器的IP地址通过哈希操作得到。

    资源ID;KID(key identifiers),原为键ID,其实际表示一个资源(因为Key与一个资源value哈希绑定),故在本文中统称资源ID(这样比较直观),m位的一个数字(m要足够大以保证不同资源的KID相同的几率小的可以忽略不计),由Key通过哈希操作得到。

    常哈希函数:较之一般哈希函数,节点的加入和离开对整个系统影响最小,另外还有一些优势在此不赘述。在Chord中使用SHA-1来进行常哈希计算。

    Chord环:Chord Ring,NID和KID被分配到一个大小为2^m的环上,用于资源分配(给某一个节点)和节点分布,以及资源定位(注:在这个环上的ID为0–2^m-1)。首先我们说资源分配,资源被分配到NID>=KID的节点上,这个节点成为k的后继节点,是环上从k起顺时针方向的第一个节点,记为successor(k)。而节点分布则顺时针将节点N由大到小放在这个环上。例如下边这幅图:

    clip_image010

    这是一个m=6的环,其中有10个节点,5个资源,K10的后继节点为N14,也就是说K10被分配给了N14。

    2.Chord资源定位(Key Location)

    资源定位是Chord协议的核心功能,为了便于理解,我们先介绍一个简单的资源定位方法,然后再介绍这个可伸缩的资源定位方法。

    简单方法:

    考虑如下场景:节点n寻找KID为id的资源,此时节点n首先问询是否在下一个节点上(find_successor),这要看资源k的KID是否在该节点NID和下一个节点的NID之间,若在则说明资源k被分配给了下一个节点,若不在则在下一个节点上发起同样的查询,问询下下一个点是否有该资源。如此迭代下去,用伪代码定义这个操作:

    n.find_successor(id) 
       if (id є (n;

    [Read More...]
  • Pinterest的Feed架构与算法

    Pinterest的Feed架构与算法
    Monday, Nov 30th, 2015 by Tim

    Pinterest首页的Feed消息流,最早是按照用户的关注对象的Pin(类似微博)聚合后按时间进行排序(自然序,类似朋友圈),后来版本的feed系统放弃了自然序,而是根据一定规则及算法来设计,内部称之为Smart feed,其算法及架构根据其公开资料整理如下,值得业界做信息流产品的技术架构师参考。

    Pinterest每个用户的首页feed都是个性化内容。Pinterest系统大约1/3流量都指向feed页面,因此它是整个系统最关键的页面之一。当工程师开发新版Smart Feed时,如何达到99.99%可用性也是衡量项目是否成功的指标之一。

    Pinterest smart feed的主要算法及规则如下

    • 不同来发表来源的Pin按照不同的频次聚合。
    • 将Pin按照算法及权重有选择的去除(或延迟加载),质量较低的发表来源不必每次显示全部,系统可以有选择的决定哪些立即出现,哪些延迟显示。Pin的质量都是从当前接收用户的角度来衡量。
    • Pin排序的逻辑是最好的优先,而不是最新的优先。一些发表来源的Pin可能最新的优先,但另外一些发表来源的可能新的Pin优先级低。

    Pinterest Feed如图所示主要由以下几部分构成,最左边是数据来源,最右边是用户看到的Pinterest瀑布流。中间的三个服务介绍如下。
    pinterest-1

    Feed worker

    Feed worker职责:接收新的pin并根据接收的用户的不同赋予pin权重并保存。同一个Pin,不同的接收用户有不同的权重打分。
    新的pin主要有三个来源:关注用户,相关内容,关注关系的感兴趣内容。Worker会给每个来源的pin打分之后插入到一个pool里面,每个Pool是针对单个用户的优先队列(Priority Queue,即优先级高的内容先出)。
    由于Feed Worker按照接收用户的维度存储,因此所有的pin进入worker时候已经按照关注关系进行分发(即行内通常说的Feed推模式)。

    Feed content generator

    Feed content generator负责返回用户上次访问后新的pin。Content Generator可以返回前n条或者全部新的pin,用户获取过(即浏览过)的pin会从pool中删除。Content Generator可以将多个发表源的pin按照一定规则重新排列,但是不能改变原来的Priority Queue返回的优先顺序。即队列中高优先级的会被优先取出。

    Smart feed service

    物化视图用于保存用户上次feed列表的快照。此服务不需要对feed的重新排序,它将上次返回给用户的pin按照当时的顺序完整保存,由于它属于用户已阅读过的历史列表,读写较少,因此它可以提供更好的可用性。另外由于可以限制历史列表的长度,存储空间可控,因此可以更低成本来增加从库来提高访问的可用性。

    Feed依赖content generator来提供新的Pin,如果content generator不可用,服务可以优雅的降级,用户仍然可以获取历史的列表,返回物化存储的结果。

    Pinterest通过以上3个不同的服务,实现了对feed返回内容灵活的控制,每个服务都有自己明确的职责,达到了每个用户都具备个性化返回内容的目标。

    Feed存储

    Pinterest的feed存储需要解决以下几个需求:

    • 写入新发表的feed,由于Pinterest采用的是推模式,这个场景需要面临需要高的写入QPS,但用户能容忍一定的写入延迟。
    • 获取首页的物化feed列表,相对与写入的QPS要小很多,但是用户对请求的延迟容忍度低。
    • 删除feed。

    可以采用简单的设计方法,比如将所有的feed写入到一个存储,可以简单实现访问、更新及删除功能。在Pinterest当前的访问规模有上百T的数据以及每秒百万访问操作。经过综合评估,选择使用HBase来实现了上述需求,Pinterest业务场景需要提供非常高的读写及更新操作,HBase同时提供较高的读写及更新访问性能。

    用户发表一个新的Pin时,将Pin分发给他所有的粉丝,他的粉丝可能被shard到所有的HBase region上,因此一个分发操作可能要访问到多个region,并锁定每个region的WAL日志,然后进行更新再解锁。每次的write/delete/update操作锁定WAL非常低效,而且很快成为系统的瓶颈。更好的方法是将HBase的操作批量进行,并且可以加大HBase的吞吐能力,但另外一方面增加了访问的时延latency,如果是面向用户请求的操作,访问时延增大是不能接受的。

    为了满足不同的需求,Pinterest设计使用了双HBase集群的方法,将数据在不同的阶段写入到不同的HBase集群的方法,请参考图示。
    pinterest-3
    Zen是一个在HBase基础上提供图(Graph)存储的服务。
    SmartFeed Worker将用户发表的内容分发后通过Zen保存在HBase中,异步处理任务通过PinLater服务来调用。
    SmartFeed ContentGenerator负责返回最新的Pin,并进行评分及排序。
    当用户刷新请求自己首页的feed时,SmartFeed服务从Content Generator和物化存储的HBase归并数据返回给用户,如果生成服务请求超时,则系统仍然可以返回物化存储的数据给用户。在后台,SmartFeed将物化存储的数据从左边的存储删除。
    在实际的场景中,物化存储HBase的数据远远要比发表池的数据要少,这样请求的速度会非常快。

    Feed的高可用

    使用上述设计后,系统的可用性相当于物化存储HBase的可用性。HBase集群目前存在GC卡顿的风险,还有单点故障region迁移等问题,因此使用单一的HBase集群,可用性很难保证99.99%以上。

    为了解决这个问题,在另外一个EC2可用区启用一个备用集群,任何写入到主集群的数据将会在数百毫秒内同步到另外一个集群上。当主集群不可用时,可以从备用集群返回用户请求的数据。通过上述设计,整个系统的可用性达到99.99%以上(不包括写)。

    pinterest-2

    参考资料

    http://pingineering.tumblr.com/post/105293275179/building-a-scalable-and-available-home-feed
    https://engineering.pinterest.com/blog/building-scalable-and-available-home-feed

    from: http://timyang.net/architecture/pinterest-feed/

    [Read More...]
  • System Design面试

    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.
    [Read More...]
  • Random ID Generator

    Random ID Generator

    From: http://blog.gainlo.co/index.php/2016/06/07/random-id-generator/

    Let’s continue our system design interview questions discussion. If you are new to this series, you can check our previous posts. Basically, each week we are going to pick several interesting interview questions and provide in-depth analysis.

    It’s worth to note that the post is not about giving you something like a standard answer. Instead, we focus more on analyzing the problem and how to come up with reasonable approaches. This is even more true for system design interviews because the question can be extremely open-ended.

    [Read More...]
  • Design a Cache System

    Design a Cache System

    from: http://blog.gainlo.co/index.php/2016/04/19/design-facebook-chat-function/

    Similar to our previous posts, we would like to select system design interview questions that are popular and practical so that not only can you get ideas about how to analyze problems in an interview, but learn something interesting at the same time.

    If you have no idea about system design interviews, I’d recommend you read this tutorial first. In this post, we are addressing the problem – how to design a cache system. Topics covered by this post include:

    • LRU cache
    • Eviction policy,
    [Read More...]
  • Design Facebook Chat Function

    Design Facebook Chat Function

    http://blog.gainlo.co/index.php/2016/04/19/design-facebook-chat-function/

    One of the most interesting parts of preparing system design interview is that you can get to know a lot of details about how existing systems are built.

    To make the weekly post more helpful, I’d like to cover a wide range of topics. We’ve been talking about stuff like recommendation, ranking a lot in the past few weeks, this time I want to cover something different.

    Question

    It starts with a very simple question – how to design Facebook chat function?

    With great news like Facebook buys Whatsapp for $19B and Facebook messenger gets really popular recently,

    [Read More...]
Page 1 of 212