Interview Questions | Learn for Master - Part 3
  • 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...]
  • leetcode paint fence

    There is a fence with n posts, each post can be painted with one of the k colors.

    You have to paint all the posts such that no more than two adjacent fence posts have the same color.

    Return the total number of ways you can paint the fence.

    Note:
    n and k are non-negative integers.

    There are many solutions online, but the following is the easiest to understand. Thanks the author! https://discuss.leetcode.com/topic/31093/easy-to-understand-java-o-n-runtime-o-1-space

    w(n) number of ways to paint n posts

    p(n) color of the nth post

    w(n) consists of two cases:

    1.p(n) == p(n –

    [Read More...]
  • Leetcode H-Index

     

    Problem Description

    Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher’s h-index.
    According to the definition of h-index on Wikipedia: “A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each.”
    For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3,

    [Read More...]
  • Leetcode Single Number II

    Given an array of integers, every element appears three times except for one. Find that single one.

    Note:
    Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

     

     

    整体思路是:整数的32个bits,出现次数mod 3后必余0, 1, 2
    其中余1的就是答案

      int singleNumber(int A[], int n) {
          int n1=0, n2=0; // n1为mod 3余1的bits,n2为mod 3余2的bits
          for (int i=0; i<n; ++i) {
              int n0 = ~(n1|n2); // 若非余1也非余2,就是余0了
              // 若「原本就余2且bit为0」或「原本余1且bit为1」,则该bit更新后余2
              n2 = (n2&~A[i]) | (n1&A[i]);
              // 若「原本就余1且bit为0」或「原本余0且bit为1」,则该bit更新后余1
              n1 = (n1&~A[i]) | (n0&A[i]);
          }
          return n1;

    [Read More...]
  • Leetcode Longest Consecutive Sequence

    Given an unsorted array of integers, find the length of the longest consecutive elements sequence.

    For example,
    Given [100, 4, 200, 1, 3, 2],
    The longest consecutive elements sequence is [1, 2, 3, 4]. Return its length: 4.

    Your algorithm should run in O(n) complexity.

    Analysis

    We can use a hashset to record all the elements in the array. Then for each number in the array, we expand to both left and right and record the length of the expansion. 

    See the following Java code:

     

    [Read More...]
  • Leetcode Distinct Subsequences

    Given a string S and a string T, count the number of distinct subsequences of T in S.

    A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (ie, “ACE” is a subsequence of “ABCDE” while “AEC” is not).

    Here is an example:
    S = “rabbbit”, T = “rabbit”

    Return 3.

    Java solution

    Here are three solutions to solve this problem.

     

    [Read More...]
  • LeetCode Serialize and Deserialize Binary Tree (Java)

    Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

    Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

    For example, you may serialize the following tree

    as “[1,2,3,null,null,4,5]”,

    [Read More...]
  • LeetCode Patching Array

    Given a sorted positive integer array nums and an integer n, add/patch elements to the array such that any number in range [1, n]inclusive can be formed by the sum of some elements in the array. Return the minimum number of patches required.

    Example 1:
    nums = [1, 3], n = 6
    Return 1.

    Combinations of nums are [1], [3], [1,3], which form possible sums of: 1, 3, 4.
    Now if we add/patch 2 to nums, the combinations are: [1],

    [Read More...]
Page 3 of 1112345...10...Last »