h******e
发帖数: 52 | 1 Given a fleet of computers, write software such that each computer prints
the sum of every computer's unique value. Given API, receive(int computer#),
send(int val, int computer#), int getMyValue(), int getNumberOfComputers().
All calls are blocking. | x*******9
发帖数: 138 | 2 需求分析：
1. 根本需求：计算所有机器unique value的和
2. 特性：所有API是同步的 -> 大量请求会导致性能问题
3. 分布式系统 -> 负载均衡
4. 同时读写可以导致短时的数据不一致
解决方案：
1. 计算所有机器unique value的和
对于N台机器，我们将其分为sqrt(N)组，组内每一个元素都维护着本组机器值的和。每
次更新时，更新本组内所有机器。
这样读写的时间复杂度为O(sqrt(N))
2. 所有API是同步的，要尽量减少读写次数避免性能问题
同上
3. 分布式系统的负载均衡
对于整个系统，我们不可能只向一台机器发请求，所以load balancing是必须要考虑的。
我们可以选择每组中的任一台进行请求，把负载随机分到组只任一一台机器上。
4. 读写不一致
使用data versioning，对于每次修改记录一个时间戳，每次查询要根据同一组时间戳
来计算。这样可以保持数据的最终一致性。 | g*******d
发帖数: 495 | 3 我感觉有点像MPI的编程问题。
比如说先把请求发送到所有机器，然后要把N台机器的value进行加和。
#0负责收集#0和#1的value，#2负责#2和#3的，。。。
二进制：#xxxx0收集#xxxx0和#xxxx1上的数据
下一轮
#0负责收集#0和#2上的sum，#4负责收集#4和#6上的sum，。。。
二进制：#xxx00收集#xxx00和xxx10上的数据
。。。
直到最后一轮#0收集到所有的sum，然后返回
（补充一句，开始时发送请求到所有机器的过程是上面过程的逆过程） |
|
