s*********e
发帖数: 36 | 1 今天面了湾区一家小公司，做针对出版商的software的。 问的问题除了针对我的背景
外，主要集中
在data structure, database design。快结束时候问的一道题发散出新问题，让我想
了之后
尽快发信给他。一个open question在这里求大家帮忙啦！
题目：
问：做一个search engine, 每次搜索到的url肯定会有大量重复。怎么解决?
答：用hash table做 blahblah
问: 为了实现这个search engine, 你的设备是联在一起的100台电脑，它们可以同时工
作。可能
整个工作过程的某个时段这台机器得到的url set跟另一台机器得到的url set不一样，
我们又不希
望重复劳动。怎么办？
答：这100台机器不是联机了吗，把url的hash table存在global 的file system里，每
台机
器都对这个global的hash table操作
问：如果不允许存在global的file system里呢？每台机器可以send information给其
他机
器，可以接收information，但不能专门reque |
K******g
发帖数: 1870 | 2 这些题目到底是什么意思？search engine搜到了URL，我们把重复的URL去掉，仅保留
唯一的URL在一个hash table里，是不是这样的？
【在 s*********e 的大作中提到】
: 今天面了湾区一家小公司，做针对出版商的software的。 问的问题除了针对我的背景
: 外，主要集中
: 在data structure, database design。快结束时候问的一道题发散出新问题，让我想
: 了之后
: 尽快发信给他。一个open question在这里求大家帮忙啦！
: 题目：
: 问：做一个search engine, 每次搜索到的url肯定会有大量重复。怎么解决?
: 答：用hash table做 blahblah
: 问: 为了实现这个search engine, 你的设备是联在一起的100台电脑，它们可以同时工
: 作。可能
|
s*********e
发帖数: 36 | 3 是的。同一个url只能保存一次
【在 K******g 的大作中提到】
: 这些题目到底是什么意思？search engine搜到了URL，我们把重复的URL去掉，仅保留
: 唯一的URL在一个hash table里，是不是这样的？
|
K******g
发帖数: 1870 | 4 每台机器有两个hashtable，一个hashtable是已经和其它机器同步了的，不重复的。另
一个hashtable是没有和其他机器同步，只是local 唯一的URL。每台机器定个timer，
周期的给其他99台机器broadcast自己的第二个hashtable，等收到其他机器的回复同步
后，就把两个hashtable合并，清空第二个hashtable(这个周期可以很长，比如2个小时一次，或者一天一次）。另外其它的99台机器，每收到同
步信息，就删掉第二个hashtable里重复的URL。
【在 s*********e 的大作中提到】
: 今天面了湾区一家小公司，做针对出版商的software的。 问的问题除了针对我的背景
: 外，主要集中
: 在data structure, database design。快结束时候问的一道题发散出新问题，让我想
: 了之后
: 尽快发信给他。一个open question在这里求大家帮忙啦！
: 题目：
: 问：做一个search engine, 每次搜索到的url肯定会有大量重复。怎么解决?
: 答：用hash table做 blahblah
: 问: 为了实现这个search engine, 你的设备是联在一起的100台电脑，它们可以同时工
: 作。可能
|
K******g
发帖数: 1870 | 5 其实我有个问题不明白，为什么搜索到的URL重复的话，那些机器就是“重复劳动”呢
？反正已经搜到了，哪怕你再删掉它，也已经重复了啊。请问这个怎么解释？
【在 s*********e 的大作中提到】
: 今天面了湾区一家小公司，做针对出版商的software的。 问的问题除了针对我的背景
: 外，主要集中
: 在data structure, database design。快结束时候问的一道题发散出新问题，让我想
: 了之后
: 尽快发信给他。一个open question在这里求大家帮忙啦！
: 题目：
: 问：做一个search engine, 每次搜索到的url肯定会有大量重复。怎么解决?
: 答：用hash table做 blahblah
: 问: 为了实现这个search engine, 你的设备是联在一起的100台电脑，它们可以同时工
: 作。可能
|
s*********e
发帖数: 36 | 6 非常非常感谢！ 跟我晚上想得差不多。
我的方法的不同之处：
因为search engine （比如google）要求实时search，一次query得到一个特定数目的
URL条目
（比如说1000条）就够了。一旦hash table的size达到了，search就停止了。所以这个
timer的
time slot非常短。
我的方法是一台机器一个hashtable和一个buffer。 buffer装一个短暂time slot里本
机得到的
unique的URLs（相当与你的local 不同步 hashtable）。其他的一模一样
时一次，或
者一天一次）。另外其它的99台机器，每收到同
【在 K******g 的大作中提到】
: 每台机器有两个hashtable，一个hashtable是已经和其它机器同步了的，不重复的。另
: 一个hashtable是没有和其他机器同步，只是local 唯一的URL。每台机器定个timer，
: 周期的给其他99台机器broadcast自己的第二个hashtable，等收到其他机器的回复同步
: 后，就把两个hashtable合并，清空第二个hashtable(这个周期可以很长，比如2个小时一次，或者一天一次）。另外其它的99台机器，每收到同
: 步信息，就删掉第二个hashtable里重复的URL。
|
s*********e
发帖数: 36 | 7 原话exactly怎么说的我不记得了，大概意思就是避免每台机器独立工作。
【在 K******g 的大作中提到】
: 其实我有个问题不明白，为什么搜索到的URL重复的话，那些机器就是“重复劳动”呢
: ？反正已经搜到了，哪怕你再删掉它，也已经重复了啊。请问这个怎么解释？
|
y****n
发帖数: 579 | 8 题目的意思是所有100台机子都做url搜索，要求去除重复的url同时不能用global的hashtable？
答：每台机子都储存同样的hash函数，能将url string均匀映射到100台机子中的任意一台，再在被映射的机子上本地查询是否重复。
【在 s*********e 的大作中提到】
: 今天面了湾区一家小公司，做针对出版商的software的。 问的问题除了针对我的背景
: 外，主要集中
: 在data structure, database design。快结束时候问的一道题发散出新问题，让我想
: 了之后
: 尽快发信给他。一个open question在这里求大家帮忙啦！
: 题目：
: 问：做一个search engine, 每次搜索到的url肯定会有大量重复。怎么解决?
: 答：用hash table做 blahblah
: 问: 为了实现这个search engine, 你的设备是联在一起的100台电脑，它们可以同时工
: 作。可能
|
f**********w
发帖数: 93 | 9
check Yale Sparse matrix storage, there may be better way to do it.
If on parallel machine, you can partition the matrix into smaller ones.
【在 s*********e 的大作中提到】
: 今天面了湾区一家小公司，做针对出版商的software的。 问的问题除了针对我的背景
: 外，主要集中
: 在data structure, database design。快结束时候问的一道题发散出新问题，让我想
: 了之后
: 尽快发信给他。一个open question在这里求大家帮忙啦！
: 题目：
: 问：做一个search engine, 每次搜索到的url肯定会有大量重复。怎么解决?
: 答：用hash table做 blahblah
: 问: 为了实现这个search engine, 你的设备是联在一起的100台电脑，它们可以同时工
: 作。可能
|
s*********e
发帖数: 36 | 10 是的
hashtable？
意一台，再在
被映射的机子上本地查询是否重复。
【在 y****n 的大作中提到】
: 题目的意思是所有100台机子都做url搜索，要求去除重复的url同时不能用global的hashtable？
: 答：每台机子都储存同样的hash函数，能将url string均匀映射到100台机子中的任意一台，再在被映射的机子上本地查询是否重复。
|
|
|
s*********e
发帖数: 36 | 11 昨天发了回答之后，今天又收到后续问题了：
大概是说：
1：如果机器数目不断上升，这种broadcast来使各个机器的hash table同步的方法不
scalable. 并且You also do not handle the real case that machines go up and
down, taken offline（是说机器掉线了么？） or more machines are brought
online.
2： broadcast的过程中，丢包的情况不可避免，那样就会出现各个机器上的hash
table不同步
问题越问越多了都，真是头疼。。。大家有什么看法么？ |
f*******r
发帖数: 1086 | 12 这个问题感觉似乎可以用mapreduce的方式解决吧:
可以让多台电脑同时开始crawling URLs，
然后每个URL利用hashing原理得到一个hashing value，
把这个hashing value % (记录hashingtable的pc数目)
就是取余，这样可以保证一个hashing value会映射
到同一台机器上，这样似乎就可以了？
我不是很确定，只是之前做过类似的题目，楼主看看
是否合理？
【在 s*********e 的大作中提到】
: 今天面了湾区一家小公司，做针对出版商的software的。 问的问题除了针对我的背景
: 外，主要集中
: 在data structure, database design。快结束时候问的一道题发散出新问题，让我想
: 了之后
: 尽快发信给他。一个open question在这里求大家帮忙啦！
: 题目：
: 问：做一个search engine, 每次搜索到的url肯定会有大量重复。怎么解决?
: 答：用hash table做 blahblah
: 问: 为了实现这个search engine, 你的设备是联在一起的100台电脑，它们可以同时工
: 作。可能
|
s*********e
发帖数: 36 | 13 谢谢！我觉得很有道理。这样就是每台机器不保持各自的synchronized hashtable，而
是各自保存
一部分， 查询的时候可以指定到特定机器。 这个思路应该比各自保存同步hash table好
【在 f*******r 的大作中提到】
: 这个问题感觉似乎可以用mapreduce的方式解决吧:
: 可以让多台电脑同时开始crawling URLs，
: 然后每个URL利用hashing原理得到一个hashing value，
: 把这个hashing value % (记录hashingtable的pc数目)
: 就是取余，这样可以保证一个hashing value会映射
: 到同一台机器上，这样似乎就可以了？
: 我不是很确定，只是之前做过类似的题目，楼主看看
: 是否合理？
|
s*********e
发帖数: 36 | 14 这是一位网友的回答，我觉得很好就贴出来分享了，用consistent hash来做。
寄信人: duduhao (dudu)
标 题: Re: 在线紧急求助一道system design面试题，面经内附
发信站: 未名空间 (Wed Jun 23 01:16:45 2010)
来 源: 24.17.
Hi Shiningfree
Just saw your post. I can help you on this
Your answer is workable, but it is not optimized, so the hiring manager
follow up with you today. I will give you some of my ideas, hope it is
helpful to you.
There is a kind of data structure called consistent hashing, you can google
or wiki it. it is the critical data structure can be
【在 s*********e 的大作中提到】
: 今天面了湾区一家小公司，做针对出版商的software的。 问的问题除了针对我的背景
: 外，主要集中
: 在data structure, database design。快结束时候问的一道题发散出新问题，让我想
: 了之后
: 尽快发信给他。一个open question在这里求大家帮忙啦！
: 题目：
: 问：做一个search engine, 每次搜索到的url肯定会有大量重复。怎么解决?
: 答：用hash table做 blahblah
: 问: 为了实现这个search engine, 你的设备是联在一起的100台电脑，它们可以同时工
: 作。可能
|
s*********e
发帖数: 36 | 15 恶补了两天学了不少东西。觉得这几个概念/知识点值得学习：
distributed hash table: 分布式系统里的hashtable
http://en.wikipedia.org/wiki/Distributed_hash_table#Keyspace_partitioning
consistent hashing：增加或删除hash表中的entry时，如何减小remapping的条目数量
。（注意这里的删除不是指清空某个entry里的对应值，而是指把整个entry删掉，这样
常常导致排在这个entry后面的所有entry都需要remapping，如果是传统的连续
hashtable的话）
http://en.wikipedia.org/wiki/Consistent_hashing
关于reducemap，基本原理及要点是 将数据交给不同的机器去处理，数据划分，结果归
约。这道题里的 把hash table存在分布式系统的不同的机器上，理论上可以算
reducemap的一种吗？ |
