【问题实例】
1).2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
有点像鸽巢原理，整数个数为2^32,也就是，我们可以将这2^32个数，划分为2^8个区域(比如用单个文件代表一个区域)，然后将数据分离到不同的区域，然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。 当然这个题也可以用我们前面讲过的BitMap方法解决，正所谓条条大道通罗马~~~ 2).5亿个int找它们的中位数。
这个例子比上面那个更明显。首先我们将int划分为2^16个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
实际上，如果不是int是int64，我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域，然后确定区域的第几 大数，在将该区域分成2^20个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有2^20，就可以直接利用direct addr table进行统计了。 3).现在有一个0-30000的随机数生成器。请根据这个随机数生成器，设计一个抽奖范围是0-350000彩票中奖号码列表，其中要包含20000个中奖号码。 这个题刚好和上面两个思想相反，一个0到3万的随机数生成器要生成一个0到35万的随机数。那么我们完全可以将0-35万的区间分成35/3=12个区间，然后每个区间的长度都小于等于3万，这样我们就可以用题目给的随机数生成器来生成了，然后再加上该区间的基数。那么要每个区间生成多少个随机数呢？计算公式就是：区间长度*随机数密度，在本题目中就是30000*（20000/350000）。最后要注意一点，该题目是有隐含条件的：彩票，这意味着你生成的随机数里面不能有重复，这也是我为什么用双层桶划分思想的另外一个原因
好几个地方看到这个 Facebook - Needle in a Haystack: Efficient Storage of Billions of Photos，是 Facebook 的 Jason Sobel 做的一个 PPT，揭示了不少比较有参考价值的信息。【也别错过我过去的这篇Facebook 的PHP性能与扩展性】
图片规模
作为世界上最大的 SNS 站点之一，Facebook 图片有多少? 65 亿张原始图片，每张图片存为 4-5 个不同尺寸，这样总计图片文件有 300 亿左右，总容量
540T，天! 峰值的时候每秒钟请求 47.5 万个图片 (当然多数通过 CDN) ，每周上传 1 亿张图片。
图片存储
前一段时间说 Facebook 服务器超过 10000 台，现在打开不止了吧，Facebook 融到的大把银子都用来买硬件了。图片是存储在 Netapp NAS上的，采用 NFS 方式。
图片写入
尽管这么大的量，似乎图片写入并不是问题。如上图，是直接通过 NFS 写的。
图片读取
CDN 和 Cachr 承担了大部分访问压力。尽管 Netapp 设备不便宜，但基本上不承担多大的访问压力，否则吃不消。CDN 针对 Profile 图象的命中率有 99.8%，普通图片也有 92% 的命中率。命中丢失的部分采由 Netapp 承担。
图中的 Cachr 这个组件，应该是用来消息通知(基于调整过的 evhttp的嘛)，Memcached 作为后端存储。Web 图片服务器是 Lighttpd，用于 FHC (文件处理 Cache)，后端也是 Memcached。Facebook 的 Memcached 服务器数量差不多世界上最大了，人家连 MYSQL 服务器还有两千台呢。
Haystacks --大海捞针
这么大的数据量如何进行索引? 如何快速定位文件? 这是通过 Haystacks 来做到的。Haystacks 是用户层抽象机制，简单的说就是把图片元数据的进行有效的存储管理。传统的方式可能是通过 DB 来做，Facebook 是通过文件系统来完成的。通过 GET / POST 进行读/写操作，应该说，这倒也是个比较有趣的思路，如果感兴趣的话，看一下 GET / POST 请求的方法或许能给我们点启发。
总体来看，Facebook 的图片处理还是采用成本偏高的方法来做的。技术含量貌似并不大。不清楚是否对图片作 Tweak，比如不影响图片质量的情况下减小图片尺寸。 --EOF--