Monday, November 30, 2015

程序员编程艺术第三十六~三十七章、搜索智能提示suggestion,附近点搜索




第三十六章、搜索关键词智能提示suggestion

题目详情:百度搜索框中,输入“北京”,搜索框下面会以北京为前缀,展示“北京爱情故事”、“北京公交”、“北京医院”等等搜索词,输入“结构之”,会提示“结构之法”,“结构之法 算法之道”等搜索词。
请问,如何设计此系统,使得空间和时间复杂度尽量低。
题目分析:本题来源于去年2012年百度的一套实习生笔试题中的系统设计题(为尊重愿题,本章主要使用百度搜索引擎展开论述,而不是google等其它搜索引擎,但原理不会差太多。然脱离本题,平时搜的时候,鼓励用...),题目比较开放,考察的目的在于看应聘者解决问题的思路是否清晰明确,其次便是看能考虑到多少细节。
    我去年整理此题的时候,曾简单解析过,提出的方法是:
  • 直接上Trie树Trie树的介绍见:从Trie树(字典树)谈到后缀树」 +  TOP Khashmap+堆,hashmap+堆 统计出如10个近似的热词,也就是说,只存与关键词近似的比如10个热词
    方法就是这样子的:Trie树+TOP K算法,但在实际中,真的只要Trie树 + TOP K算法就够了么,有什么需要考虑的细节?OK,请看下文娓娓道来。

解法一、Trie树 + TOP K

 步骤一、trie树存储前缀后缀

   若看过博客内这篇介绍Trie树和后缀树的文章http://blog.csdn.net/v_july_v/article/details/6897097的话,应该就能对trie树有个大致的了解,为示本文完整性,引用下原文内容,如下:
1.1、什么是Trie树
    Trie树,即字典树,又称单词查找树或键树,是一种树形结构,是一种哈希树的变种。典型应用是用于统计和排序大量的字符串(但不仅限于字符串),所以经常被搜索引擎系统用于文本词频统计。它的优点是:最大限度地减少无谓的字符串比较,查询效率比哈希表高。
    Trie的核心思想是空间换时间。利用字符串的公共前缀来降低查询时间的开销以达到提高效率的目的。
它有3个基本性质:

  1. 根节点不包含字符,除根节点外每一个节点都只包含一个字符。
  2. 从根节点到某一节点,路径上经过的字符连接起来,为该节点对应的字符串。
  3. 每个节点的所有子节点包含的字符都不相同。

1.2、树的构建

举个在网上流传颇广的例子,如下:
    题目:给你100000个长度不超过10的单词。对于每一个单词,我们要判断他出没出现过,如果出现了,求第一次出现在第几个位置。
    分析:这题当然可以用hash来解决,但是本文重点介绍的是trie树,因为在某些方面它的用途更大。比如说对于某一个单词,我们要询问它的前缀是否出现过。这样hash就不好搞了,而用trie还是很简单。
    现在回到例子中,如果我们用最傻的方法,对于每一个单词,我们都要去查找它前面的单词中是否有它。那么这个算法的复杂度就是O(n^2)。显然对于100000的范围难以接受。现在我们换个思路想。假设我要查询的单词是abcd,那么在他前面的单词中,以b,c,d,f之类开头的我显然不必考虑。而只要找以a开头的中是否存在abcd就可以了。同样的,在以a开头中的单词中,我们只要考虑以b作为第二个字母的,一次次缩小范围和提高针对性,这样一个树的模型就渐渐清晰了。
    好比假设有b,abc,abd,bcd,abcd,efg,hii 这6个单词,我们构建的树就是如下图这样的:
  当时第一次看到这幅图的时候,便立马感到此树之不凡构造了。单单从上幅图便可窥知一二,好比大海搜人,立马就能确定东南西北中的到底哪个方位,如此迅速缩小查找的范围和提高查找的针对性,不失为一创举。
    ok,如上图所示,对于每一个节点,从根遍历到他的过程就是一个单词,如果这个节点被标记为色,就表示这个单词存在,否则不存在。
    那么,对于一个单词,我只要顺着他从根走到对应的节点,再看这个节点是否被标记为红色就可以知道它是否出现过了。把这个节点标记为红色,就相当于插入了这个单词。
    借用上面的图,当用户输入前缀a的时候,搜索框可能会展示以a为前缀的“abcd”,“abd”等关键词,再当用户输入前缀b的时候,搜索框下面可能会提示以b为前缀的“bcd”等关键词,如此,实现搜索引擎智能提示suggestion的第一个步骤便清晰了,即用trie树存储大量字符串,当前缀固定时,存储相对来说比较热的后缀。那又如何统计热词呢?请看下文步骤二、TOP K算法统计热词。

 步骤二、TOP K算法统计热词

    当每个搜索引擎输入一个前缀时,下面它只会展示0~10个候选词,但若是碰到那种候选词很多的时候,如何取舍,哪些展示在前面,哪些展示在后面?这就是一个搜索热度的问题。
    如本题描述所说,在去年的这个时候,当我在搜索框内搜索“北京”时,它下面会提示以“北京”为前缀的诸如“北京爱情故事”,“北京公交”,“北京医院”,且“ 北京爱情故事”展示在第一个:
    为何输入“北京”,会首先提示“北京爱情故事”呢?因为去年的这个时候,正是《北京爱情故事》这部电视剧上映正火的时候(其上映日期为2012年1月8日,火了至少一年),那个时候大家都一个劲的搜索这部电视剧的相关信息,当10个人中输入“北京”后,其中有8个人会继续敲入“爱情故事”(连起来就是“北京爱情故事”)的时候,搜索引擎对此当然不会无动于衷。
    也就是说,搜索引擎知道了这个时间段,大家都在疯狂查找北京爱情故事,故当用户输入以“北京”为前缀的时候,搜索引擎猜测用户有80%的机率是要查找“北京爱情故事”,故把“北京爱情故事”在下面提示出来,并放在第一个位置上。
    但为何今年这个时候再次搜索“北京”的时候,它展示出来的词不同了呢?
    
    原因在于随着时间变化,人们对《北京爱情故事》这部电视剧的关注度逐渐下降,与此同时,又出现了新的热词,或新的电影,故现在虽然同样是输入“北京”,后面提示的词也相应跟着起了变化。那解决这个问题的办法是什么呢?如开头所说:定期分析某段时间内的人们搜索的关键词,统计出搜索次数比较多的热词,继而当用户输入某个前缀时,优先展示热词。
    故说白了,这个问题的第二个步骤便是统计热词,我们把统计热词的方法称为TOP K算法,此算法的应用场景便是此文http://blog.csdn.net/v_july_v/article/details/7382693中的第2个问题,再次原文引用:
寻找热门查询,300万个查询字符串中统计最热门的10个查询
    原题:搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来,每个查询串的长度为1-255字节。假设目前有一千万个记录(这些查询串的重复度比较高,虽然总数是1千万,但如果除去重复后,不超过3百万个。一个查询串的重复度越高,说明查询它的用户越多,也就是越热门),请你统计最热门的10个查询串,要求使用的内存不能超过1G。
    解答:由上面第1题,我们知道,数据大则划为小的,如一亿个Ip求Top 10,可先%1000将ip分到1000个小文件中去,并保证一种ip只出现在一个文件中,再对每个小文件中的ip进行hashmap计数统计并按数量排序,最后归并或者最小堆依次处理每个小文件的top10以得到最后的结果。
    但如果数据规模本身就比较小,能一次性装入内存呢?比如这第2题,虽然有一千万个Query,但是由于重复度比较高,因此事实上只有300万的Query,每个Query255Byte,因此我们可以考虑把他们都放进内存中去(300万个字符串假设没有重复,都是最大长度,那么最多占用内存3M*1K/4=0.75G。所以可以将所有字符串都存放在内存中进行处理),而现在只是需要一个合适的数据结构,在这里,HashTable绝对是我们优先的选择。
    所以我们放弃分而治之/hash映射的步骤,直接上hash统计,然后排序。So,针对此类典型的TOP K问题,采取的对策往往是:hashmap + 堆。如下所示:
  1. hashmap统计:先对这批海量数据预处理。具体方法是:维护一个Key为Query字串,Value为该Query出现次数的HashTable,即hash_map(Query,Value),每次读取一个Query,如果该字串不在Table中,那么加入该字串,并且将Value值设为1;如果该字串在Table中,那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内用Hash表完成了统计;
  2. 排序:第二步、借助堆这个数据结构,找出Top K,时间复杂度为N‘logK。即借助堆结构,我们可以在log量级的时间内查找和调整/移动。因此,维护一个K(该题目中是10)大小的小根堆,然后遍历300万的Query,分别和根元素进行对比。所以,我们最终的时间复杂度是:O(N) + N' * O(logK),(N为1000万,N’为300万)。
    别忘了这篇文章中所述的堆排序思路:‘维护k个元素的最小堆,即用容量为k的最小堆存储最先遍历到的k个数,并假设它们即是最大的k个数,建堆费时O(k),并调整堆(费时O(logk))后,有k1>k2>...kmin(kmin设为小顶堆中最小元素)。继续遍历数列,每次遍历一个元素x,与堆顶元素比较,若x>kmin,则更新堆(x入堆,用时logk),否则不更新堆。这样下来,总费时O(k*logk+(n-k)*logk)=O(n*logk)。此方法得益于在堆中,查找等各项操作时间复杂度均为logk。’--第三章续、Top K算法问题的实现
    当然,你也可以采用trie树,关键字域存该查询串出现的次数,没有出现为0。最后用10个元素的最小推来对出现频率进行排序。
    相信,如此,也就不难理解开头所提出的方法了:Trie树+  TOP K「hashmap+堆,hashmap+堆 统计出如10个近似的热词,也就是说,只存与关键词近似的比如10个热词」。
    而且你以后就可以告诉你身边的伙伴们,为何输入“结构之”,会提示出来一堆以“结构之”为前缀的词了:
    
    方法貌似成型了,但有哪些需要注意的细节呢?如@江申_Johnson所说:“实际工作里,比如当前缀很短的时候,候选词很多的时候,查询和排序性能可能有问题,也许可以加一层索引trie(这层索引可以只索引频率高于某一个阈值的词,很短的时候查这个就可以了。数量不够的话再去查索引了全部词的trie树);而且有时候不能根据query频率来排,而要引导用户输入信息量更全面的query,或者或不仅仅是前缀匹配这么简单。”

扩展阅读

    除了上文提到的trie树,三叉树或许也是一个不错的解决方案:http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/。此外,StackOverflow上也有两个讨论帖子,大家可以看看:①http://stackoverflow.com/questions/2901831/algorithm-for-autocomplete,②http://stackoverflow.com/questions/1783652/what-is-the-best-autocomplete-suggest-algorithm-datastructure-c-c

第三十七章、附近地点搜索

题目详情:找一个点集中与给定点距离最近的点,同时,给定的二维点集都是固定的,查询可能有很多次,时间复杂度O(n)无法接受,请设计数据结构和相应的算法。
题目分析:此题是去年微软的三面题,类似于一朋友@陈利人 出的这题:附近地点搜索,就是搜索用户附近有哪些地点。随着GPS和带有GPS功能的移动设备的普及,附近地点搜索也变得炙手可热。在庞大的地理数据库中搜索地点,索引是很重要的。但是,我们的需求是搜索附近地点,例如,坐标(39.91, 116.37)附近500米内有什么餐馆,那么让你来设计,该怎么做?

解法一、R树二维搜索

    假定只允许你初中数学知识,那么你可能建一个X-Y坐标系,即以坐标(39.91, 116.37)为圆心,以500的长度为半径,画一个园,然后一个一个坐标点的去查找。此法看似可行,但复杂度可想而知,即便你自以为聪明的说把整个平面划分为四个象限,一个一个象限的查找,此举虽然优化程度不够,但也说明你一步步想到点子上去了。
    即不一个一个坐标点的查找,而是一个一个区域的查找,相对来说,其平均查找速度和效率会显著提升。如此,便自然而然的想到了有没有一种一次查找定位于一个区域的数据结构呢?
    若看过博客内之前介绍R树的这篇文章http://blog.csdn.net/v_JULY_v/article/details/6530142#t2 的读者立马便能意识到,R树就是解决这个区域查找继而不断缩小规模的问题。特直接引用原文:

R树的数据结构

    R树是B树在高维空间的扩展,是一棵平衡树。每个R树的叶子结点包含了多个指向不同数据的指针,这些数据可以是存放在硬盘中的,也可以是存在内存中。根据R树的这种数据结构,当我们需要进行一个高维空间查询时,我们只需要遍历少数几个叶子结点所包含的指针,查看这些指针指向的数据是否满足要求即可。这种方式使我们不必遍历所有数据即可获得答案,效率显著提高。下图1是R树的一个简单实例:
    我们在上面说过,R树运用了空间分割的理念,这种理念是如何实现的呢?R树采用了一种称为MBR(Minimal Bounding Rectangle)的方法,在此我把它译作“最小边界矩形”。从叶子结点开始用矩形(rectangle)将空间框起来,结点越往上,框住的空间就越大,以此对空间进行分割。有点不懂?没关系,继续往下看。在这里我还想提一下,R树中的R应该代表的是Rectangle(此处参考wikipedia上关于R树的介绍),而不是大多数国内教材中所说的Region(很多书把R树称为区域树,这是有误的)。我们就拿二维空间来举例。下图是Guttman论文中的一幅图:
 
    我来详细解释一下这张图。
  1. 先来看图(b),首先我们假设所有数据都是二维空间下的点,图中仅仅标志了R8区域中的数据,也就是那个shape of data object。别把那一块不规则图形看成一个数据,我们把它看作是多个数据围成的一个区域。为了实现R树结构,我们用一个最小边界矩形恰好框住这个不规则区域,这样,我们就构造出了一个区域:R8。R8的特点很明显,就是正正好好框住所有在此区域中的数据。
  2. 其他实线包围住的区域,如R9,R10,R12等都是同样的道理。这样一来,我们一共得到了12个最最基本的最小矩形。这些矩形都将被存储在子结点中。
  3. 下一步操作就是进行高一层次的处理。我们发现R8,R9,R10三个矩形距离最为靠近,因此就可以用一个更大的矩形R3恰好框住这3个矩形。
  4. 同样道理,R15,R16被R6恰好框住,R11,R12被R4恰好框住,等等。所有最基本的最小边界矩形被框入更大的矩形中之后,再次迭代,用更大的框去框住这些矩形。
    我想大家都应该理解这个数据结构的特征了。用地图的例子来解释,就是所有的数据都是餐厅所对应的地点,先把相邻的餐厅划分到同一块区域,划分好所有餐厅之后,再把邻近的区域划分到更大的区域,划分完毕后再次进行更高层次的划分,直到划分到只剩下两个最大的区域为止。要查找的时候就方便了。
    下面就可以把这些大大小小的矩形存入我们的R树中去了。根结点存放的是两个最大的矩形,这两个最大的矩形框住了所有的剩余的矩形,当然也就框住了所有的数据。下一层的结点存放了次大的矩形,这些矩形缩小了范围。每个叶子结点都是存放的最小的矩形,这些矩形中可能包含有n个数据。
地图查找的实例
    讲完了基本的数据结构,我们来讲个实例,如何查询特定的数据。又以餐厅为例,假设我要查询广州市天河区天河城附近一公里的所有餐厅地址怎么办?
  1. 打开地图(也就是整个R树),先选择国内还是国外(也就是根结点);
  2. 然后选择华南地区(对应第一层结点),选择广州市(对应第二层结点),
  3. 再选择天河区(对应第三层结点);
  4. 最后选择天河城所在的那个区域(对应叶子结点,存放有最小矩形);
    遍历所有在此区域内的结点,看是否满足我们的要求即可。怎么样,其实R树的查找规则跟查地图很像吧?对应下图:
        
一棵R树满足如下的性质:
  1. 除非它是根结点之外,所有叶子结点包含有m至M个记录索引(条目)。作为根结点的叶子结点所具有的记录个数可以少于m。通常,m=M/2。
  2. 对于所有在叶子中存储的记录(条目),I是最小的可以在空间中完全覆盖这些记录所代表的点的矩形(注意:此处所说的“矩形”是可以扩展到高维空间的)。
  3. 每一个非叶子结点拥有m至M个孩子结点,除非它是根结点。
  4. 对于在非叶子结点上的每一个条目,i是最小的可以在空间上完全覆盖这些条目所代表的店的矩形(同性质2)。
  5. 所有叶子结点都位于同一层,因此R树为平衡树。

叶子结点的结构

先来探究一下叶子结点的结构。叶子结点所保存的数据形式为:(I, tuple-identifier)。
      其中,tuple-identifier表示的是一个存放于数据库中的tuple,也就是一条记录,它是n维的。I是一个n维空间的矩形,并可以恰好框住这个叶子结点中所有记录代表的n维空间中的点。I=(I0,I1,…,In-1)。其结构如下图所示:
    下图描述的就是在二维空间中的叶子结点所要存储的信息。
 
    在这张图中,I所代表的就是图中的矩形,其范围是a<=I0<=b,c<=I1<=d。有两个tuple-identifier,在图中即表示为那两个点。这种形式完全可以推广到高维空间。大家简单想想三维空间中的样子就可以了。这样,叶子结点的结构就介绍完了。

非叶子结点

      非叶子结点的结构其实与叶子结点非常类似。想象一下B树就知道了,B树的叶子结点存放的是真实存在的数据,而非叶子结点存放的是这些数据的“边界”,或者说也算是一种索引(有疑问的读者可以回顾一下上述第一节中讲解B树的部分)。
      同样道理,R树的非叶子结点存放的数据结构为:(I, child-pointer)。
      其中,child-pointer是指向孩子结点的指针,I是覆盖所有孩子结点对应矩形的矩形。这边有点拗口,但我想不是很难懂?给张图:
 
    D,E,F,G为孩子结点所对应的矩形。A为能够覆盖这些矩形的更大的矩形。这个A就是这个非叶子结点所对应的矩形。这时候你应该悟到了吧?无论是叶子结点还是非叶子结点,它们都对应着一个矩形。树形结构上层的结点所对应的矩形能够完全覆盖它的孩子结点所对应的矩形。根结点也唯一对应一个矩形,而这个矩形是可以覆盖所有我们拥有的数据信息在空间中代表的点的。
    我个人感觉这张图画的不那么精确,应该是矩形A要恰好覆盖D,E,F,G,而不应该再留出这么多没用的空间了。但为尊重原图的绘制者,特不作修改。
    但R树有些什么问题呢?如@宋枭_CD所说:“单纯用R树来作索引,搜索附近的地点,可能会遍历树的很多个分支。而且当全国的地图或者全省的地图时候,树的叶节点数目很多,树的深度也会是一个问题。一般会把地理位置上附近的节点(二维地图中点线面)预处理成page(大小为4K的倍数),在这些page上建立R树的索引。”

解法二、GeoHash算法索引地理位置信息

    我在微博上跟一些朋友讨论这个附近点搜索的问题时,除了谈到R树,有几个朋友都指出GeoHash算法可以解决,故才了解了下GeoHash算法,此文http://blog.nosqlfan.com/html/1811.html 清晰阐述了MongoDB借助GeoHash算法实现地理位置索引的原理,特引用其内容加以说明,如下:
支持地理位置索引是MongoDB的一大亮点,这也是全球最流行的LBS服务foursquare 选择MongoDB的原因之一。我们知道,通常的数据库索引结构是B+ Tree,如何将地理位置转化为可建立B+Tree的形式。首先假设我们将需要索引的整个地图分成16×16的方格,如下图(左下角为坐标0,0 右上角为坐标16,16):
    单纯的[x,y]的数据是无法建立索引的,所以MongoDB在建立索引的时候,会根据相应字段的坐标计算一个可以用来做索引的hash值,这个值叫做geohash,下面我们以地图上坐标为[4,6]的点(图中红叉位置)为例。我们第一步将整个地图分成等大小的四块,如下图:
    划分成四块后我们可以定义这四块的值,如下(左下为00,左上为01,右下为10,右上为11):
    
    这样[4,6]点的geohash值目前为 00然后再将四个小块每一块进行切割,如下:
    这时[4,6]点位于右上区域,右上的值为11,这样[4,6]点的geohash值变为:0011继续往下做两次切分:
    最终得到[4,6]点的geohash值为:00110100
    这样我们用这个值来做索引,则地图上点相近的点就可以转化成有相同前缀的geohash值了。
    我们可以看到,这个geohash值的精确度是与划分地图的次数成正比的,上例对地图划分了四次。而MongoDB默认是进行26次划分,这个值在建立索引时是可控的。具体建立二维地理位置索引的命令如下:
db.map.ensureIndex({point : "2d"}, {min : 0, max : 16, bits : 4})
    其中的bits参数就是划分几次,默认为26次。 
    读者点评@yuotulck:首先多谢博主的文章,不过如果是新手(例如我)看到geohash那里可能会有误解:是否相邻可以靠前缀来比较?其实这是错的,例如边界那一块的相邻区域编码的前缀从第一个就不一样了,也就是说在geohash里相近的点hash值不一定相近。
    上面的知识点了解自:http://www.cnblogs.com/step1/archive/2009/04/22/1441689.html,而geohash的进一步用法在这里可以了解到:
http://tech.idv2.com/2011/07/05/geohash-intro/
    本章完。

参考链接及推荐阅读

  1. 2012年九月十月笔试面试八十题:http://blog.csdn.net/v_july_v/article/details/7974418
  2. 从Trie树(字典树)谈到后缀树:http://blog.csdn.net/v_july_v/article/details/6897097
  3. 教你如何迅速秒杀掉:99%的海量数据处理面试题:http://blog.csdn.net/v_july_v/article/details/7382693
  4. 从B树、B+树、B*树谈到R树:http://blog.csdn.net/v_july_v/article/details/6530142
  5. 图解 MongoDB 地理位置索引的实现原理:http://blog.nosqlfan.com/html/1811.html
  6. 《Hbase实战》第8章、在HBase上查询地理信息系统;

CDN(Content Delivery Network)



https://cloud.google.com/cdn/docs/best-practices
Using versioned URLs to update content
Versioning content serves a different version of the same content, effectively removing it by showing users new content before the cache entry expires. Because versioning is free and easy to use, we recommend you use versioning as the default approach for updating cacheable content. To version content, add a parameter to the URL, such as a version number. There are various ways to include parameters in URLs, such as:
  • Add a query string: file.ext?v=100
  • Alter the file name: file.1.0.0.ext or file_v100.ext
  • Alter the file path: /v100/file.ext
When you add the parameter, you change the name of the file and the URL. This change forces the cache to ignore any existing cache entry.
https://www.fastly.com/blog/leveraging-your-cdn-cache-uncacheable-content
Event-driven content looks like dynamic content, but it really isn’t. What sets event-driven content apart from dynamic content is that it’s actually static, but for unpredictable periods of time. This means that you can’t determine cacheability lifetime in advance. 
1. Lack of a good invalidation framework
Many businesses have an extreme fear of serving stale content to their users. Imagine a media site that publishes a news article, caches it in the network, realizes that the reporter got a fact wrong, and then has no way to retract the article until it expires from the cache.

2. Lack of visibility
Another challenge that often prevents website owners from caching event-driven content is that putting that content on a CDN will make them lose some visibility into site traffic. Many analytics and stats mechanisms are based on collecting logs of user visits on an origin infrastructure. Putting these types of objects on a traditional CDN means that you won’t see the hits or log the visits, causing you to lose valuable insight into how your users interact with your applications
https://www.smashingmagazine.com/2018/02/dynamic-website-static-content-cdn/
Routing the request through a CDN makes dynamic content become static since the CDN will return the cached version of that content (requested under a specific URL). Whenever the webserver has a fresher version of that content, it needs to tell the CDN to serve the most up-to-date version. There are two ways to handle this situation:
  1. Purging the object from the CDN cache so that it will fetch the content again for that URL;
  2. Adding a versioning parameter to the URL in order to serve a different version of the object under a different URL whenever the content changes.
When making a dynamic website in which content is constantly changing and needs to immediately reflect those changes, then the first solution is not adequate. Why? Well, for the following reasons:
  • We cannot guarantee that the object will be effectively purged from all the different layers in between the webserver and the client browser. For instance, the user may have a version cached either locally or behind a corporate caching proxy;
  • Because CDN edges are located worldwide, it usually takes a few seconds for all locations to purge their objects.
In addition, programmatically purging objects from a CDN depends on the APIs made available by the CDN providers, such as Cloudflare or AWS CloudFront. If we want to have absolute control that the application will work regardless of the infrastructure where it runs, then purging the object is not recommended.

The value of the thumbprint is always changing, reflecting the activity of users on the website. For this reason, the application in the client must be able to access the latest thumbprint value, which will be added as a parameter to all requests. In order to always get the latest thumbprint, a process in the background must always get this value from the server, either every x amount of time (which can also be routed through the CDN, caching the latest thumbprint value for all clients after the first one) or through WebSockets.
https://blogs.akamai.com/2015/10/dynamic-page-caching-beyond-static-content.html
https://www.keycdn.com/blog/cdn-dynamic-content/

http://highscalability.com/blog/2017/12/11/netflix-what-happens-when-you-press-play.html

https://github.com/donnemartin/system-design-primer
A content delivery network (CDN) is a globally distributed network of proxy servers, serving content from locations closer to the user. Generally, static files such as HTML/CSS/JS, photos, and videos are served from CDN, although some CDNs such as Amazon's CloudFront support dynamic content. The site's DNS resolution will tell clients which server to contact.
Serving content from CDNs can significantly improve performance in two ways:
  • Users receive content at data centers close to them
  • Your servers do not have to serve requests that the CDN fulfills

Pull CDNs

Pull CDNs grab new content from your server when the first user requests the content. You leave the content on your server and rewrite URLs to point to the CDN. This results in a slower request until the content is cached on the CDN.
time-to-live (TTL) determines how long content is cached. Pull CDNs minimize storage space on the CDN, but can create redundant traffic if files expire and are pulled before they have actually changed.
Sites with heavy traffic work well with pull CDNs, as traffic is spread out more evenly with only recently-requested content remaining on the CDN.

Disadvantage(s): CDN

  • CDN costs could be significant depending on traffic, although this should be weighed with additional costs you would incur not using a CDN.
  • Content might be stale if it is updated before the TTL expires it.
  • CDNs require changing URLs for static content to point to the CDN.
https://en.wikipedia.org/wiki/Content_delivery_network
CDN nodes are usually deployed in multiple locations, often over multiple backbones. Benefits include reducing bandwidth costs, improving page load times, or increasing global availability of content.
points of presence (PoPs)

Requests for content are typically algorithmically directed to nodes that are optimal in some way. When optimizing for performance, locations that are best for serving content to the user may be chosen. This may be measured by choosing locations that are the fewest hops, the least number of network seconds away from the requesting client, or the highest availability in terms of server performance (both current and historical), so as to optimize delivery across local networks. 
Most CDN providers will provide their services over a varying, defined, set of PoPs, depending on the geographic coverage desired, such as United States, International or Global, Asia-Pacific, etc. These sets of PoPs can be called "edges", "edge nodes" or "edge networks" as they would be the closest edge of CDN assets to the end user.

The Internet was designed according to the end-to-end principle.[8] This principle keeps the core network relatively simple and moves the intelligence as much as possible to the network end-points: the hosts and clients. As a result, the core network is specialized, simplified, and optimized to only forward data packets.
Content Delivery Networks augment the end-to-end transport network by distributing on it a variety of intelligent applications employing techniques designed to optimize content delivery. The resulting tightly integrated overlay uses web caching, server-load balancing, request routing, and content services

http://serverfault.com/questions/67484/what-is-an-edge-server-router-device
It's usually a caching proxy server, located near the user accessing the data, used to improve bandwidth and latency to far away users while lessening the load on central servers.

An edge server, in a system administration context, is any server that resides on the "edge" between two networks, typically a private network and the Internet. Edge servers can serve different purposes depending on the context of the functionality in question.
Some examples:
  • Security Context: usually a firewall, router or similar device
  • Application Context: a web load balancing server
  • Mail Context: some kind of hub server that forwards mail on to internal servers
Usually an edge server has some kind of gateway responsibility for the internal/private network.
https://www.incapsula.com/cdn-guide/what-is-cdn-how-it-works.html
To minimize the distance between the visitors and your website's server, a CDN stores a cached version of its content in multiple geographical locations (a.k.a., points of presence, or PoPs). Each PoP contains a number of caching servers responsible for content delivery to visitors within its proximity.
In essence, CDN puts your content in many places at once, providing superior coverage to your users.
- See more at: https://www.incapsula.com/cdn-guide/what-is-cdn-how-it-works.html#sthash.t86FXg9r.dpuf
http://chuansong.me/n/1597409

http://www.51know.info/system_performance/cdn/cdn.html
在不同地域的用户访问网站的响应速度存在差异,为了提高用户访问的响应速度、优化现有Internet中信息的流动,需要在用户和服务器间加入中间层CDN. 使用户能以最快的速度,从最接近用户的地方获得所需的信息,彻底解决网络拥塞,提高响应速度,是目前大型网站使用的流行的应用方案.

1. CDN 概述

  • CDN的全称是Content Delivery Network,即内容分发网络。其目的是通过在现有的Internet中增加一层新的CACHE(缓存)层,将网站的内容发布到最接近用户的网络"边缘"的节点,使用户可以就近取得所需的内容,提高用户访问网站的响应速度。从技术上全面解决由于网络带宽小、用户访问量大、网点分布不均等原因,提高用户访问网站的响应速度。
    cdn_overview.gif
  • Cache层的技术,消除数据峰值访问造成的结点设备阻塞。Cache服务器具有缓存功能,所以大部分网页对象(Web page object),如html, htm, php等页面文件,gif,tif,png,bmp等图片文件,以及其他格式的文件,在有效期(TTL)内,对于重复的访问,不必从原始网站重新传送文件实体, 只需通过简单的认证(Freshness Validation)- 传送几十字节的Header,即可将本地的副本直接传送给访问者。由于缓存服务器通常部署在靠近用户端,所以能获得近似局域网的响应速度,并有效减少广域带宽的消耗。不仅能提高响应速度,节约带宽,对于加速Web服务器,有效减轻源服务器的负载是非常有效的。
  • 根据加速对象不同,分为 客户端加速 和 服务器加速
    • 客户端加速 : Cache部署在网络出口处,把常访问的内容缓存在本地,提高响应速度和节约带宽;
    • 服务器加速 : Cache部署在服务器前端,作为Web服务器的代理缓存机,提高Web服务器的性能,加速访问速度 
      如果多台Cache加速服务器且分布在不同地域,需要通过有效地机制管理Cache网络,引导用户就近访问(比如通过DNS引导用户),全局负载均衡流量,这是CDN内容传输网络的基本思想.
  • CDN对网络的优化作用主要体现在如下几个方面  - 解决服务器端的“第一公里”问题  - 缓解甚至消除了不同运营商之间互联的瓶颈造成的影响  - 减轻了各省的出口带宽压力  - 缓解了骨干网的压力  - 优化了网上热点内容的分布

2. CDN 的工作原理

2.1. 传统访问过程(未加速缓存服务)

我们先看传统的未加缓存服务的访问过程,以便了解CDN缓存访问方式与未加缓存访问方式的差别:
normal.png
由上图可见,用户访问未使用CDN缓存网站的过程为:
  1. 用户输入访问的域名,操作系统向 LocalDns 查询域名的ip地址.
  2. LocalDns向 ROOT DNS 查询域名的授权服务器(这里假设LocalDns缓存过期)
  3. ROOT DNS将域名授权dns记录回应给 LocalDns
  4. LocalDns得到域名的授权dns记录后,继续向域名授权dns查询域名的ip地址
  5. 域名授权dns 查询域名记录后,回应给 LocalDns
  6. LocalDns 将得到的域名ip地址,回应给 用户端
  7. 用户得到域名ip地址后,访问站点服务器
  8. 站点服务器应答请求,将内容返回给客户端.

2.2. CDN访问过程(使用缓存服务)

CDN网络是在用户和服务器之间增加Cache层,主要是通过接管DNS实现,将用户的请求引导到Cache上获得源服务器的数据
下面让我们看看访问使用CDN缓存后的网站的过程:
cdn.png
通过上图,我们可以了解到,使用了CDN缓存后的网站的访问过程变为:
  1. 用户输入访问的域名,操作系统向 LocalDns 查询域名的ip地址.
  2. LocalDns向 ROOT DNS 查询域名的授权服务器(这里假设LocalDns缓存过期)
  3. ROOT DNS将域名授权dns记录回应给 LocalDns
  4. LocalDns得到域名的授权dns记录后,继续向域名授权dns查询域名的ip地址
  5. 域名授权dns 查询域名记录后(一般是CNAME),回应给 LocalDns
  6. LocalDns 得到域名记录后,向智能调度DNS查询域名的ip地址
  7. 智能调度DNS 根据一定的算法和策略(比如静态拓扑,容量等),将最适合的CDN节点ip地址回应给 LocalDns
  8. LocalDns 将得到的域名ip地址,回应给 用户端
  9. 用户得到域名ip地址后,访问站点服务器
  10. CDN节点服务器应答请求,将内容返回给客户端.(缓存服务器一方面在本地进行保存,以备以后使用,二方面把获取的数据返回给客户端,完成数据服务过程)
通过以上的分析我们可以得到,为了实现对普通用户透明(使用缓存后用户客户端无需进行任何设置)访问,需要使用DNS(域名解析)来引导用户来访问Cache服务器,以实现透明的加速服务. 由于用户访问网站的第一步就是 域名解析 ,所以通过修改dns来引导用户访问是最简单有效的方式.

2.3. CDN网络的组成要素

对于普通的Internet用户,每个CDN节点就相当于一个放置在它周围的网站服务器.
通过对dns的接管,用户的请求被透明地指向离他最近的节点,节点中CDN服务器会像网站的原始服务器一样,响应用户的请求.
由于它离用户更近,因而响应时间必然更快.
从上面图中 虚线圈起来的那块,就是CDN层,这层是位于 用户端 和 站点服务器之间.
  • 智能调度DNS(比如f5的3DNS)
    智能调度DNS是CDN服务中的关键系统.当用户访问加入CDN服务的网站时,域名解析请求将最终由 智能调度DNS 负责处理.
    它通过一组预先定义好的策略,将当时最接近用户的节点地址提供给用户,使用户可以得到快速的服务.
    同时它需要与分布在各地的CDN节点保持通信,跟踪各节点的健康状态,容量等,确保将用户的请求分配到就近可用的节点上.
  • 缓存功能服务
    • 负载均衡设备(如lvs,F5的BIG/IP)
    • 内容Cache服务器(如squid)
    • 共享存储(根据缓存数据量多少决定是否需要)

3. CDN 智能调度Dns 实例分析

  • 分析img.alibaba.com域名
    在系统中,执行dig命令,输出如下:
      #dig img.alibaba.com       
      
      ; 部分省略
      
      ;; QUESTION SECTION:
      ;img.alibaba.com.  IN A
      
      ;; ANSWER SECTION:
      img.alibaba.com. 600 IN CNAME img.alibaba.com.edgesuite.net.
      img.alibaba.com.edgesuite.net. 7191 IN CNAME img.alibaba.com.georedirector.akadns.net.
      img.alibaba.com.georedirector.akadns.net. 3592 IN CNAME a1366.g.akamai.net.
      a1366.g.akamai.net. 12 IN A 204.203.18.145
      a1366.g.akamai.net. 12 IN A 204.203.18.160
      
      ; 部分省略
    
    从上面查询结果可以看出 img.alibaba.com. CNAME img.alibaba.com.edgesuite.net. 后面的CNAME是由 Akamai(CDN服务商) 去跳转到 智能调度器上的.
  • 分析www.discovery.com域名
    在系统中,继续执行dig命令,输出如下:
      #dig www.discovery.com
      
      ; 部分省略
      
      ;; QUESTION SECTION:
      ;www.discovery.com.  IN A
      
      ;; ANSWER SECTION:
      www.discovery.com. 1077 IN CNAME www.discovery.com.edgesuite.net.
      www.discovery.com.edgesuite.net. 21477 IN CNAME a212.g.akamai.net.
      a212.g.akamai.net. 20 IN A 204.203.18.154
      a212.g.akamai.net. 20 IN A 204.203.18.147
      
      ; 部分省略
    
    从上面查询结果可以看出 www.discovery.com. IN CNAME www.discovery.com.edgesuite.net. 后面的CNAME是由 Akamai(CDN服务商) 去跳转到 智能调度器上的.
    总结:一般来说,网站需要使用到CDN服务时,一般都是将需要加速访问的域名 CNAME到 CDN服务商的域名上.
    缓存服务和调度功能都是由服务商来完成.

4. CDN的 智能调度Dns 简化实现

4.1. 调度策略说明

在用户请求解析域名的时候,智能DNS判断用户的LocalDns的IP,然后跟DNS服务器内部的IP表范围匹配一下,看看用户是电信还是网通用户,然后给用户返回对应的IP地址
这里使用的是静态拓扑的方法,只是判断LocalDns的IP.要想使用更复杂的调度算法可以考虑商业产品,如F5的3DNS.

4.2. 假设CDN节点规划

在这里我们将使用 BIND 的View功能来实现运营商的区分,假设我们在每个运营商的机房都放有一个CDN节点,列表如下:
域名运营商(view)服务地址
www.cdntest.com网通(CNC)192.168.0.1
www.cdntest.com电信(TELECOM)192.168.0.2
www.cdntest.com教育网(EDU)192.168.0.3
www.cdntest.com默认(ANY)192.168.0.4

4.3. bind view 配置

  • 以下是named.conf配置文件的部分截取,只是涉及到 View 的部分,其他细节可参考互联网.
      acl "cnc_iprange"{   //定义ip范围(网通)
      192.168.1.0/24;  
      192.168.2.0/24;
      //此处只是示例,其他省略
      };  
      
      acl "tel_iprange"{  //定义ip范围(电信)
      192.168.3.0/24;  
      192.168.4.0/24;
      //其他省略
      };
       
      acl "edu_iprange"{  //定义ip范围(教育网)
      192.168.5.0/24;  
      192.168.6.0/24;
      //其他省略
      };
       
      acl "default_iprange"{ //定义ip范围(默认)
      192.168.7.0/24;  
      192.168.8.0/24;
      //其他省略
      }; 
      
      
      view "CNC" {
       Match-clients{cnc_iprange};
       zone "." IN {
            type hint;
            file "named.root";
       };
      
       zone "localhost" IN {
            type master;
            file "localhost.zone";
            allow-update { none; };
       };
       
       zone "cdntest.com" IN {
            type master;
            file "cnc_cdntest.zone";
       };
      };
      
      view "TEL" {
       Match-clients{tel_iprange};
       zone "." IN {
            type hint;
            file "named.root";
       };
      
       zone "localhost" IN {
            type master;
            file "localhost.zone";
            allow-update { none; };
       };
       
       zone "cdntest.com" IN {
            type master;
            file "tel_cdntest.zone";
       };
      };
      
      view "EDU" {
       Match-clients{edu_iprange};
       zone "." IN {
            type hint;
            file "named.root";
       };
      
       zone "localhost" IN {
            type master;
            file "localhost.zone";
            allow-update { none; };
       };
       
       zone "cdntest.com" IN {
            type master;
            file "edu_cdntest.zone";
       };
      };
      
      view "DEFAULT" {
       Match-clients{default_iprange};
       zone "." IN {
            type hint;
            file "named.root";
       };
      
       zone "localhost" IN {
            type master;
            file "localhost.zone";
            allow-update { none; };
       };
       
       zone "cdntest.com" IN {
            type master;
            file "default_cdntest.zone";
       };
      };
    
  • zone文件的配置说明
    这4个zone配置文件(cnc_cdntest.zone,tel_cdntest.zone,edu_cdntest.zone,default_cdntest.zone)中,只有www.cndtest.com的A记录不一样,其他的都是一样.
域名zone配置文件A记录地址
www.cdntest.comcnc_cdntest.zone192.168.0.1
www.cdntest.comtel_cdntest.zone192.168.0.2
www.cdntest.comedu_cdntest.zone192.168.0.3
www.cdntest.comdefault_cdntest.zone192.168.0.4
以上只列出了 www.cdntest.com 的A记录地址,其他关于zone的语法 请参考互联网.
  • 域名解析流程简要说明
  1. 用户向 LocalDns 查询域名 www.cdntest.com
  2. LocalDns 向 授权DNS 查询www.cdntest.com
  3. 授权DNS 判断用户使用的 LocalDns的ip地址,匹配上述设置的ip范围,如果范围在网通,就将网通对应的ip地址(192.168.0.1),回应给LocalDns(其他依此类推)
  4. LocalDns 将得到的域名ip地址,回应给 用户端 (域名解析完成)
    说明:再此过程中,我们简化了主DNS 到 智能DNS 之间的CNAME过程(为了简要说明问题). 
    这里使用的是静态拓扑(根据ip范围)的方法,也称为地域化方法,只是判断LocalDns的IP.
  • 此简化方案中的存在的问题
  1. 如果用户设置错误的dns,可能会导致用户访问比原来慢(比如网通用户设置了电信的DNS)
  2. 不能判断CDN节点服务器的健康状态和容量状态,可能会把用户定向到不可用的CDN节点
  3. 由于静态拓扑方法,可能存在用户访问的CDN节点不是最优化和最快的
  4. .....可能还有其他想不到的....

5. 总结(Summary)


在建立CDN网路时,最关键的就是 智能调度DNS,这个是CND网络总协调,通过高效的调度算法,可以使用户得到最佳的访问体验.
其次就是 CND节点的管理,比如涉及到 内容的同步机制,配置文件的更新等等,都需要有一套机制来保证.
当然在大型网站中,也要考建设CDN体系的成本和回报率.

附录D 系统设计 - 编程之法:面试和算法心得



http://www.kancloud.cn/kancloud/the-art-of-programming/41626
1、搜索关键词智能提示suggestion
百度搜索框中,输入“北京”,搜索框下面会以北京为前缀,展示“北京爱情故事”、“北京公交”、“北京医院”等等搜索词,输入“结构之”,会提示“结构之法”,“结构之法 算法之道”等搜索词。 请问,如何设计此系统,使得空间和时间复杂度尽量低。
提示:此题比较开放,简单直接的方法是:用trie树存储大量字符串,当前缀固定时,存储相对来说比较热的后缀。然后用hashmap+堆,统计出如10个近似的热词,也就是说,只存与关键词近似的比如10个热词,我们把这个统计热词的方法称为TOP K算法。
当然,在实际中,还有很多细节需要考虑,有兴趣的读者可以继续参阅相关资料。
2
某服务器流量统计器,每天有1000亿的访问记录数据,包括时间、URL、IP。设计系统实现记录数据的保存、管理、查询。要求能实现以下功能:
  • 计算在某一时间段(精确到分)时间内的,某URL的所有访问量。
  • 计算在某一时间段(精确到分)时间内的,某IP的所有访问量。
3
假设某个网站每天有超过10亿次的页面访问量,出于安全考虑,网站会记录访问客户端访问的IP地址和对应的时间,如果现在已经记录了1000亿条数据,想统计一个指定时间段内的区域IP地址访问量,那么这些数据应该按照何种方式来组织,才能尽快满足上面的统计需求呢? 设计完方案后,并指出该方案的优缺点,比如在什么情况下,可能会非常慢? � 提示:用B+树来组织,非叶子节点存储(某个时间点,页面访问量),叶子节点是访问的IP地址。这个方案的优点是查询某个时间段内的IP访问量很快,但是要统计某个IP的访问次数或是上次访问时间就不得不遍历整个树的叶子节点。或者可以建立二级索引,分别是时间和地点来建立索引。
4
给你10台机器,每个机器2个CPU和2GB内存,现在已知在10亿条记录的数据库里执行一次查询需要5秒,问用什么方法能让90%的查询能在100毫秒以内返回结果。
提示:将10亿条记录排序,然后分到10个机器中,分的时候是一个记录一个记录的轮流分,确保每个机器记录大小分布差不多,每一次查询时,同时提交给10台机器,同时查询,因为记录已排序,可以采用二分法查询。
如果无排序,只能顺序查询,那就要看记录本身的概率分布,否则不可能实现。毕竟一个机器2个CPU未必能起到作用,要看这两个CPU能否并行存取内存,取决于系统架构。
5
有1000万条URL,每条URL长度为50字节,只包含主机前缀,要求实现URL提示系统,并满足以下条件:
6
例如手机朋友网有n个服务器,为了方便用户的访问会在服务器上缓存数据,因此用户每次访问的时候最好能保持同一台服务器。 已有的做法是根据ServerIPIndex[QQNUM%n]得到请求的服务器,这种方法很方便将用户分到不同的服务器上去。但是如果一台服务器死掉了,那么n就变为了n-1,那么ServerIPIndex[QQNUM%n]与ServerIPIndex[QQNUM%(n-1)]基本上都不一样了,所以大多数用户的请求都会转到其他服务器,这样会发生大量访问错误。
问: 如何改进或者换一种方法,使得:
  • 一台服务器死掉后,不会造成大面积的访问错误,
  • 原有的访问基本还是停留在同一台服务器上;
  • 尽量考虑负载均衡。
提示:一致性hash算法。
7
对于给定的整数集合S,求出最大的d,使得a+b+c=d。a,b,c,d互不相同,且都属于S。集合的元素个数小于等于2000个,元素的取值范围在[-2^28,2^28 - 1],假定可用内存空间为100MB,硬盘使用空间无限大,试分析时间和空间复杂度,找出最快的解决方法。
有一大批数据,百万级别的。数据项内容是:用户ID、科目ABC各自的成绩。其中用户ID为0~1000万之间,且是连续的,可以唯一标识一条记录。科目ABC成绩均在0~100之间。有两块磁盘,空间大小均为512MB,内存空间64MB。
  • 为实现快速查询某用户ID对应的各科成绩,问磁盘文件及内存该如何组织;
  • 改变题目条件,ID为0~10亿之间,且不连续。问磁盘文件及内存该如何组织;
  • 在问题2的基础上,增加一个需求。在查询各科成绩的同时,获取该用户的排名,问磁盘文件及内存该如何组织。
8
有几百亿的整数,分布的存储到几百台通过网络连接的计算机上,你能否开发出一个算法和系统,找出这几百亿数据的中值?就是在一组排序好的数据中居于中间的数。显然,一台机器是装不下所有的数据。也尽量少用网络带宽。
9
类似做一个手机键盘,上面有1到9个数字,每个数字都代表几个字母(比如1代表abc三个字母,z代表wxyz等等),现在要求设计当输入某几个数字的组合时,查找出通讯录中的人名及电话号码。
10
这是一种用户登录验证手段,例如银行登录系统,这个设备显示6位数字,每60秒变一次,再经过服务器认证,通过则允许登录。问How to design this system?
  • 系统设计思路?服务器端为何能有效认证动态密码的正确性?
  • 如果是千万量级永固,给出系统设计图示或说明,要求子功能模块划分清晰,给出关键的数据结构或数据库表结构。 考虑用户量级的影响和扩展性,用户密码的随机性等,如果设计系统以支持这几个因素.
  • 系统算法升级时,服务器端和设备端可能都要有所修改,如何设计系统,能够使得升级过程(包括可能的设备替换或重设)尽量平滑?
11
http服务器会在用户访问某一个文件的时候,记录下该文件被访问的日志,网站管理员都会去统计每天每文件被访问的次数。写一个小程序,来遍历整个日志 文件,计算出每个文件被访问的访问次数。
  • 请问这个管理员设计这个算法
  • 该网站管理员后来加入腾讯从事运维工作,在腾讯,单台http服务器不够用的,同样的内容,会分布在全国各地上百台服务器上。每台服务器上的日志数量, 都是之前的10倍之多,每天服务器的性能更好,之前他用的是单核cpu,现在用的是8核的,管理员发现在这种的海量的分布式服务器,基本没法使用了,请重新设计一个算法。
12
一在线推送服务,同时为10万个用户提供服务,对于每个用户服务从10万首歌的曲库中为他们随机选择一首,同一用户不能推送重复的,设计方案,内存尽可能小,写出数据结构与算法。
13
每个城市的IP段是固定的,新来一个IP,找出它是哪个城市的,设计一个后台系统。
14
请设计一个排队系统,能够让每个进入队伍的用户都能看到自己在队列中所处的位置和变化,队伍可能随时有人加入和退出;当有人退出影响到用户的位置排名时需要及时反馈到用户。
15
设计相应的数据结构和算法,尽量高效的统计一片英文文章(总单词数目)里出现的所有英文单词,按照在文章中首次出现的顺序打印输出该单词和它的出现次数。
16
有几百亿的整数,分布的存储到几百台通过网络连接的计算机上,你能否开发出一个算法和系统,找出这几百亿数据的中值?就是在一组排序好的数据中居于中间的数。显然,一台机器是装不下所有的数据。也尽量少用网络带宽。
17
假设已有10万个敏感词,现给你50个单词,查询这50个单词中是否有敏感词。
分析:换句话说,题目要你判断这50个单词是否存在那10万个敏感词库里,明显是字符串匹配,由于是判断多个单词不是一个,故是多模式字符串匹配问题,既是多模式字符串匹配问题,那么便有一类称之为多模式字符串匹配算法,而这类算法无非是KMP、hash、trie、AC自动机、wm等等。
那到底用哪种算法呢?这得根据题目的应用场景而定。
10万 + 50,如果允许误差的话,你可能会考虑用布隆过滤器;否则,只查一次的话,可能hash最快,但hash消耗空间大,故若考虑tire的话,可以针对这10万个敏感词建立trie树,然后对那50个单词搜索这棵10万敏感词构建的tire树,但用tire树同样耗费空间,有什么更好的办法呢?Double Array Trie么?请读者继续思考。



Labels

Review (572) System Design (334) System Design - Review (198) Java (189) Coding (75) Interview-System Design (65) Interview (63) Book Notes (59) Coding - Review (59) to-do (45) Linux (43) Knowledge (39) Interview-Java (35) Knowledge - Review (32) Database (31) Design Patterns (31) Big Data (29) Product Architecture (28) MultiThread (27) Soft Skills (27) Concurrency (26) Cracking Code Interview (26) Miscs (25) Distributed (24) OOD Design (24) Google (23) Career (22) Interview - Review (21) Java - Code (21) Operating System (21) Interview Q&A (20) System Design - Practice (20) Tips (19) Algorithm (17) Company - Facebook (17) Security (17) How to Ace Interview (16) Brain Teaser (14) Linux - Shell (14) Redis (14) Testing (14) Tools (14) Code Quality (13) Search (13) Spark (13) Spring (13) Company - LinkedIn (12) How to (12) Interview-Database (12) Interview-Operating System (12) Solr (12) Architecture Principles (11) Resource (10) Amazon (9) Cache (9) Git (9) Interview - MultiThread (9) Scalability (9) Trouble Shooting (9) Web Dev (9) Architecture Model (8) Better Programmer (8) Cassandra (8) Company - Uber (8) Java67 (8) Math (8) OO Design principles (8) SOLID (8) Design (7) Interview Corner (7) JVM (7) Java Basics (7) Kafka (7) Mac (7) Machine Learning (7) NoSQL (7) C++ (6) Chrome (6) File System (6) Highscalability (6) How to Better (6) Network (6) Restful (6) CareerCup (5) Code Review (5) Hash (5) How to Interview (5) JDK Source Code (5) JavaScript (5) Leetcode (5) Must Known (5) Python (5)

Popular Posts