Friday, April 1, 2016

System Design Misc Part 2



https://segmentfault.com/a/1190000006025876
设计题的三个要点:
1.组件分解
2.并行计算
3.利用缓存

1. Spell Checker

场景:

给一个word,假设这是一个拼错的英文单词,我们应返回一个list of word,list里的words都是word可能的正确拼写。

分析:

有两个概念要clarify:
1.对于“拼错"这个概念,什么叫"拼错",什么叫"拼对",都是相对的,我们可以假设一本词典,这里面所有的单词都是拼对的,其他的都是拼错的。还有一个延伸就是,如果这个词”拼对“了,程序还check不check呢?
2.给一个word,我们先生成一堆和他很像的词,这些词可能拼对也可能拼错,我们把拼对的返回,问题在于,这里的”像“怎么界定?这里我们假设 - “像”,表示所有和word的edit distance(Levenshtein distance) exactly为2的单词们。

数据结构:

把词典预处理成一个map,key是所有的字典单词,value无所谓。我们只想快速的知道这个word是不是词典(拼对)的,对这个单词的其他性质并不关心。

核心算法:

给一个word,生成所有与这个word的edit distance(只substitute,不add也不remove)为2的所有string来,挨个去查hashmap。查出来的这些按照某种rank algorithm排序选出最高的10条。
至于这个排序算法,请看本题的后续部分。

复杂度:

对于一个request_spell_check(String word), 假设字母有m(英语的话就是26)个,单词长n(一般来讲1~15)
时间O(m^2 * n^2),因为设定edit distance为2,改装一个word的可能性有n(n-1)(m-1)^2/2种,假设改写一种是一条java语句(一次循环),那么改写一个interesting(长度为11)大约需要循环次数为:34375,假设1s内一台电脑可以运行10^8条java语句,那么每个request的耗时大约是0.3ms,1ms这个级别,是可以接受的。
空间O(1),通过上面的查找,查找的结果可能会非常大,我们只要返回一个ranked list of suggestions就好了,比如rank最高的十条。

后续:

关于排序算法,输入是一个list of word,这些word都在词典里,是拼对的词,现在要从里面找出10条最可能是答案的词,明显是一个没有标准答案的问题,所以要根据情况分析trade-off:
  1. Typing errors model,我们的排序就要根据键盘的layout来判断了;
  2. Phonetic modeling,情景:我想打一个词,只会读,不会写,比如kat打出了cat。解决方法是,把输入的单词按phonemes划分,每段按发音进行替换。
  3. History of refinements,搜集用户打错的数据 - 用户经常会打一个词,然后删了,打了另一个词,然后request请求,这两个词第一个词就是潜在的错误拼写,第二个是正确拼写。
  4. Stemming,通过把["computers", "computer", "compute", "computing"]提取为"compute",当我们拿到一个word时,对他stemming,然后把stemming结果的列表返回。

2. Stemming Problem

场景:

Stemming是搜索引擎normalize环节的一个技术,中文叫做词干提取,顾名思义,即把["computers", "computer", "compute", "computing"]提取为"compute"。Stemming既用在query string上,也用在document的存储中。前者可以延伸语义,比如查compute的时候很可能对computer感兴趣或者你想查的根本就是computer。后者可以大大降低搜索引擎索引的存储大小,也可以提高搜索效率。

分析:

Stemming明显是一个没有标准答案的问题,基本上是在trade-off,根据情景解决问题。而且这个题目太大,这里只是简述。
本质上Stemming就是根据某种规则(rule)重写(rewrite)。
  • 重写,基本都是focus在后缀(suffix)上,改后缀(wolves -> wolf),删后缀(cars -> car)。
  • 规则,这些规则干的事儿就是,先找到哪儿到哪儿是后缀(应该有个后缀表什么的),然后把这个后缀transform一下(应该也有个转换表什么的)。
一个有效的实现方法是根据这些规则建立一个Finite State Machine - 有限状态机。

后续:

越sophisticated的system会有更多的exceptions,即考虑更多地特殊情况,比如Chinese -> China这种。
Porter stemmer,作者Martin Porter,目前是公认最好的英语stemming algorithm。
其他的方法有:stochastic methods, n-gram based approaches.

3. Plagiarism Detector

场景:

在一堆文章里找相似的文章对们。
这里文章我们看做String,两篇文章如果有长度为k的公共substring,就说他们是相似的。

分析:

对某个String(文章),假设这个String长度为len,那么对这个String计算len-k+1个hashcode。
举例比如:"abcdefg"这篇文章,取k=3,我们对"abc","bcd","cde","def","efg"这5个substring分别做5次hash,存到一个大大的HashTable里,key为hash的值,value为文章id以及offset。
这样当遇到collision(这里不是指发生了多对一映射,假设hashfunction很好可以一对一映射)的时候,我们就知道那两篇文章是相似的。
这里就需要一个可以incrementally更新的hash算法,这种hash方法叫rolling hash,可参见Rabin-Karp算法,Leetcode这道题 - 187. Repeated DNA Sequences
这里说一下为什么hash算法取模的size都是质数:
好的HASH函数需要把原始数据均匀地分布到HASH数组里
原始数据不大会是真正的随机的,可能有某些规律,
比如大部分是偶数,这时候如果HASH数组容量是偶数,容易使原始数据HASH后不会均匀分布。 比如 2 4 6 8 10 12这6个数,如果对
6 取余 得到 2 4 0 2 4 0 只会得到3种HASH值,冲突会很多 如果对 7 取余 得到 2 4 6 1 3 5
得到6种HASH值,没有冲突
同样地,如果数据都是3的倍数,而HASH数组容量是3的倍数,HASH后也容易有冲突 用一个质数则会减少冲突的概率
这个HashTable的size要非常大,这样不同substring映射到同一个hashcode的几率会小。
如果想要省空间,且对结果的精确度要求不高,可以不存所有的substring的hashcode,而只是存特定的hashcode,比如最后5个bit都是0的hashcode,这样我们只存所有substring的1/(2^5)即可。
上面的方法存在很多false positive,比如假设这里文章指的是html页面,所有的文章几乎在开头都会调用同样的javascript段,我们的方法就会认为这些html都是相似的。这里我们就需要在判断前,对这些文章进行预处理,把headers去掉。
上述的方法在每篇文章(String)都很长,且这些文章分布在很多servers的时候,尤其好用。mapreduce就很适合干这个事。

4. Pair Users By Attributes

场景:

在social network里,每个用户(user)有一些属性(attributes),现在我们要把属性相同的用户配对。

分析:

用户怎么表示:用户id - 32位的int
属性怎么表示:strings
怎么叫配对:每次读入一个user(有他的id和属性们),从之前未成功配对的集合里找有相同属性们的用户。

数据结构:

map。

算法:

第一个层面:brute force。
假设连续读入n个用户,对于每个读入的用户,与unpaired set里每个用户进行attributes的比对,时间复杂度为O(N^2).
第二个层面:hashtable,key存attributes组合,value存用户。
问题是怎么把一堆attributes的组合变成一个key,即这个hashfunction怎么搞?
如果属性很少,只有几个,比如只有"蓝色","绿色","红色","吉他","钢琴","提亲","爵士鼓",那完全可以用一个bit array一波带走,然后把这个bit array随便hash一下。
时间复杂度O(nm),n为用户数,m是所有distinct attribute数,对于上面的例子就是7。时间消耗就是把每个用户的attributes转化成bit array然后把bit array哈希的时间。
第三个层面:如果attribute有很多,有1亿个,且大部分的用户只有很少的几条attributes,这样上面的方法就不好用了,对于每一个用户都要看这一亿个attribute里有没有,是浪费时间的。
在这么一个sparse subsets里,更好的方法是,直接把这些attribute们concatenate成一个string,当然concatenation之前先排个序,然后对这个string使用hash function。
时间复杂度是O(NM),n是用户数,m是平均每个用户的attributes concatenation之后的长度。

5. Detect Video Copyright Infringement

场景:

故事是这样的:有一天华谊发现youku.com上有人上传了”让子弹飞高清蓝光“整部电影,这侵犯了华谊的版权,假设你是华谊的工程师,如何给定华谊的视频库,判断youku.com哪些视频是侵权的。

分析:

和第3题要干的事儿一样,但是把document换成了video。同理也可以换成audio,这里讨论video。
判断对象是video的话,就不能像document那么干了(rolling hash),原因在于即使内容相同(比如都是“让子弹飞”),但不同的视频可以压缩成不同的格式(flv,mp4,avi),有不同的分辨率(1366x768, 1024×768),不同的压缩程度。

算法:

把所有视频都转换成相同的格式(format),分辨率(resolution)和压缩度(level of compression)。注意,这么做了之后,相同内容的视频仍然不是相同的文件。但是,经过了这样的normalization之后,我们就可以开始对每个视频生成signature了。
  • 最简单的signature生成方法:对每一帧(frame)用一个bit根据一个亮度(brightness)阈值赋0或1,这个阈值是average的brightness。
  • 更好的signature生成方法:对每帧用三个bit表示R,G,B,每个bit的取值根据R,G,B的intensity阈值赋0或1。
  • 再精确一点的signature生成方法:把每一帧分成几个region,每个region求出一个R,G,B的3个bit,再把这些region contatenate起来。

后续:

以上算法是algorithmic的,还有其他的手法:
让用户来标明是否侵权(有报酬的);和以前确认了的侵权视频进行比对,看是否完全一样;看视频header的meta-information,等等。

6. Design TeX

场景:

TeX是一个排版系统,写论文,出版社全用它。好处是不依赖平台,输出是设备无关的。像JVM一样。妈妈再也不用担心Windows下编辑的书稿在Mac里凌乱了。
一旦TeX处理了你的文件,你所得到的 DVI 文件就可以被送到任何输出设备如打印机,屏幕等并且总会得到相同的结果,而这与这些输出设备的限制没有任何关系。这说明 DVI 文件中所有的元素,从页面设置到文本中字符的位置都被固定,不能更改。TeX是一个非常多才多艺的程序。它不但可以编辑论文,书籍,幻灯片,学术杂志,个人简历,还可以 编辑乐谱,化学分子图,电路图,国际象棋,中国象棋,甚至围棋棋谱,……事实上只有少量文档不适合用TeX编辑。
问,怎么设计TeX?

分析:

两方面:
  1. building blocks,即基本元素,包括字体(fonts)和符号(symbols)怎么存,怎么表示?
    • 每个基本元素(symbol和font)最简单的表示方法是用2D array,俗称bit-mapped representation.这样做的问题是,对于resolution要求比较高的设备,这样的空间消耗极大,且不说对一个font来说有不同大小,斜体,粗体之分,这都要另存一份。
    • 更好的方法是,我们可以用数学方程来定义symbols。这样我们反而可以更精细地编程生成symbol和font,甚至可以控制字体长宽比(aspect ratio),笔画粗细(stroke width),字体的倾斜度(font slant),描边粒度(serif size)。
  2. hierarchical layout,布局,即怎么把基本元素漂亮的摆放在一起
    • 我们可以把元素(component)抽象成一个矩形的box,所有的都是矩形box,矩形box组装起来成为新的矩形Box.
      举例比如:每个symbol是个box(比如@,3,A,d,-,#),line(比如:---)和paragraph都是由box组成的,section title, tables, table entries 以及 images也都是由矩形Box组成的。至于把这些box漂亮地组装起来就用到很多的算法。

后续:

其他的问题还有:enabling cross-referencing, automatically creating indices, supporting colors, and outputting PDF.

7. Design a Search Engine

场景:

给100万个documents,每个平均10KB。输入set of words,返回set of documents,其中每个document都包含这个set of words。假设所有documents可以存放在一台电脑的RAM中。

分析:

不多说,inverted indices走起。
对于每个索引(inverted index),相当于map的一个entry,key是word,value是sorted list of ['document_ID',offset],这里list是先按document_ID,后按offset排序的。
在搜索的时候,比如搜索"beatles nirvana eminem",会分别对三个words找他们的sorted list(为了方便,下面只显示document_ID):
找到了三个词对应的索引条目:
beatles: [1]->[3]->[120]->[789]->[1022]->[7881]->[9912]
nirvana: [1]->[2]->[3]->[456]
grammy : [2]->[3]->[120]
答案就是这三个list的交集,即[3]这个document,求交集的时间复杂度和三个list的长度总和成比例(proportional to the aggregate len of the sequences)。
当然我们可以做一些优化:
  1. Compression:既省空间又提高cache命中率。因为list都是排序了的,可以用增量编码法(delta compression),每个documentId可以省几个bit。
    增量编码又叫差分编码,简单地说:不存「2, 4, 6, 9, 7」,而是存「2, 2, 2, 3, -2」。单独使用用处不大,但是在序列式数值常出现时可以帮助压缩大小。
  2. Cacheing:查询语句(query)一般都是有热点的,因此可以把频率高的query答案cache起来。
  3. Frequency-based optimization:并不是List的每一个document都返回,只返回top ten就好了。所以我们可以维护两套inverted indices,一套是top ten的,常驻RAM;另一套是剩下的,常驻硬盘。只要大部分的query都访问top ten,那整个系统的throughput 和 latency都是可以接受的。
  4. Intersection order:合并的顺序对速度有很大影响,要先合并小集合。上面的例子,应先合并nirvana和grammy,然后拿合并的结果与beatles去合并,这样速度最快。
我们也可以用多级索引(multilevel index)增加准确率。对于一个高优先级的web page,可以先将其分解成paragraphs和sentences,然后把这些paragraphs和sentences拿去建索引。
这样的好处是,我们有可能在一个paragraph或者一个sentence里找到query里所有的词,这是分级之前做不到的,之前我们的粒度只能返回文档(web page),现在可以返回paragraph和sentence,精度提高。

算法:

这里涉及两个算法题:
  1. 找两个sorted list的共同元素(intersection):两个指针从头比,一大一小不要小(advance小的pointer),两个相等就添加到result,O(N+M)。
  2. find the smallest subarray covering all values(搜索的结果里会给一段话,里面highlight出这两个关键字):两个指针维护窗口,O(N)

8. Implement PageRank

场景:

设计一个可以快速计算100亿网页pagerank的系统。

分析:

PageRank的介绍:Introduction to PageRank
简单地说就是一个N(网页数)维矩阵A,其中i行j列的值表示用户从页面j转到页面i的概率。
每个网页作为一个vertex,有超链接的两个网页有一条边,整张图是一个稀疏图,最好用邻接表(adjacency list)来表示。
建表的过程一般是:下载网页(pages),提取网页的超链接。URL由于长度变化很大,所以一般将其hash。
整个算法最耗时的地方在于矩阵乘法的迭代。
邻接表用一台电脑的RAM是放不下的,我们一般有两种做法:
  1. Disk-based sorting:
https://rao.gitbooks.io/first-system-design/content/
DSR模式:
那么我们又想使用LB的功能,同时又不愿意有这样的性能下降,这时怎么办?性能的下降是由于所有的数据包都要经过LB设备。那么我们能不能让数据包不经过LB设备呢?这时,就需要让SLB另外一种应用拓扑Direct Server Reply,即DSR模式。顾名思义,DSR模式下,server的response包不会经过LB,直接发往client。而所有的client发送的request数据包,仍然经过LB设备。
使用DSR模式,看上去只有server的response不经过LB设备,只有单边的流量得到了优化。但是在一般的CS应用中,client的request往往比较简单,数据较小较少,而server的response的数据较多较大。一般server response的流量可以占到总流量的80%到90%时,使用DSR模式,可以有效的提高性能,又不损失SLB的灵活性。

https://idf-shadow.gitbooks.io/sytem-design-hanbook/content/high_level_concepts.html
def: Load Balancer (LB) - distributed requests among servers. Load balancer has the public IP addr, servers IPs (private) not exposed.
Asynchronism Queuing everything

  1. Key-value: Redis etc.
  2. Document: MongoDB etc.
  3. Column: Cassandra etc.
  4. Graph: Neo4J etc.

http://itsumomono.blogspot.com/2015/08/compare-filedata-bulk-similarity.html
1. Check same: Checksum functions are related to hash functionsfingerprintsrandomization functions, and cryptographic hash functions.

 2. Scoring similarity:
Jaccard similarity  
w-shingling
minHash 
LSH(locality sensitive hashing)

https://en.wikipedia.org/wiki/Locality-sensitive_hashing
https://en.wikipedia.org/wiki/W-shingling
k-gram/k-mer
(a,rose,is,a,rose,is,a,rose)
The set of all contiguous sequences of 4 tokens (4-grams) is
{ (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is), (a,rose,is,a), (rose,is,a,rose) } = { (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is) }
Cosine similarity
in information retrieval and text mining, each term is notionally assigned a different dimension and a document is characterised by a vector where the value of each dimension corresponds to the number of times that term appears in the document. Cosine similarity then gives a useful measure of how similar two documents are likely to be in terms of their subject matter.[
http://itsumomono.blogspot.com/2015/07/rest-post-vs-put.html
本示例介绍在Android平台下通过HTTP协议实现断点续传下载。
我们编写的是Andorid的HTTP协议多线程断点下载应用程序。直接使用单线程下载HTTP文件对我们来说是一件非常简单的事。那么,多线程断点需要什么功能?
1.多线程下载,
2.支持断点。

使用多线程的好处:使用多线程下载会提升文件下载的速度。那么多线程下载文件的过程是: 
  (1)首先获得下载文件的长度,然后设置本地文件的长度。

      HttpURLConnection.getContentLength();//获取下载文件的长度

     RandomAccessFile file = new RandomAccessFile("QQWubiSetup.exe","rwd");

       file.setLength(filesize);//设置本地文件的长度

  (2)根据文件长度和线程数计算每条线程下载的数据长度和下载位置。
      如:文件的长度为6M,线程数为3,那么,每条线程下载的数据长度为2M,每条线程开始下载的位置如下图所示。
  
   例如10M大小,使用3个线程来下载,
        线程下载的数据长度   (10%3 == 0 ? 10/3:10/3+1) ,第1,2个线程下载长度是4M,第三个线程下载长度为2M
         下载开始位置:线程id*每条线程下载的数据长度 = ?
        下载结束位置:(线程id+1)*每条线程下载的数据长度-1=?

  (3)使用HttpRange头字段指定每条线程从文件的什么位置开始下载,下载到什么位置为止,
         如:指定从文件的2M位置开始下载,下载到位置(4M-1byte)为止
           代码如下:HttpURLConnection.setRequestProperty("Range", "bytes=2097152-4194303");

  (4)保存文件,使用RandomAccessFile类指定每条线程从本地文件的什么位置开始写入数据。
RandomAccessFile threadfile = new RandomAccessFile("QQWubiSetup.exe ","rwd");
threadfile.seek(2097152);//从文件的什么位置开始写入数据

在HTTP中,PUT被定义为indempotent的方法,POST则不是,这是一个很重要的区别。
   “Methods can also have the property of "idempotence" in that (aside from error or expiration issues) the side-effects of N > 0 identical requests is the same as for a single request.”
上面的话就是说,如果一个方法重复执行多次,产生的效果是一样的,那就是idempotent的。
      举一个简单的例子,假如有一个博客系统提供一个Web API,模式是这样http://superblogging/blogs/post/{blog-name},很简单,将{blog-name}替换为我们的blog名字,往这个URI发送一个HTTP PUT或者POST请求,HTTP的body部分就是博文,这是一个很简单的REST API例子。我们应该用PUT方法还是POST方法?取决于这个REST服务的行为是否是idempotent的,假如我们发送两个http://superblogging/blogs/post/Sample请求,服务器端是什么样的行为?如果产生了两个博客帖子,那就说明这个服务不是idempotent的,因为多次使用产生了副作用了嘛;如果后一个请求把第一个请求覆盖掉了,那这个服务就是idempotent的。前一种情况,应该使用POST方法,后一种情况,应该使用PUT方法。

      也许你会觉得这个两个方法的差别没什么大不了的,用错了也不会有什么问题,但是你的服务一放到internet上,如果不遵从HTTP协议的规范,就可能给自己带来麻烦。比如,没准Google Crawler也会访问你的服务,如果让一个不是indempotent的服务可以用indempotent的方法访问,那么你服务器的状态可能就会被Crawler修改,这是不应该发生的。



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