大数据的Follow up问题怎么答？

楼主看面经或者自己面试经常遇到Follow up一般都是说数据很大怎么办。
举个例子：
岛屿个数这个题，最后一般都会问，如果岛屿matrix太大不能一下子load进内存怎么办？一般的回答都是切割，分块处理。但是再进一步问细节，切块以后边界怎么处理然后就没有然后了。
大家对于这种大数据问题有什么好的建议吗？有什么学习的资料没有。谢谢。祝大家都有好的offer。

yexiaojiaycc 发表于 2018-11-5 11:04
哦哦，那就比如这个岛屿题，一般就dfs flood，那切块了以后还怎么flood呢？边界怎么处理呢？谢谢

首先不妨设matrix的大小是M * N，M、N是很大的数字比如2^20。

然后将matrix分块，设每个block的大小是a * b（比如说a = b = 2^10，每个matrix cell记1 byte，那么每个block占用内存就是1MB)，那么总共分出ceil(M / a) * ceil(N / b)个block。

现在考虑用dfs flood的方法，可以有两种设计思路：
(1) 类似于传统DB的Buffer Pool方法
(2) 类似于Map Reduce的方法

这两种不好说哪个性能更好，要看workload characteristics

这里说一下Buffer Pool方法，首先注意到每个block大小是1MB，虽然不能同时load所有的block（有一百万个）到内存，但是假定我们有4GB净可用内存，那么可以同时load 4096个block。

那么我们维持一个大小为4096个block的buffer pool，使用某种eviction policy（例如clock算法）—— 这里所说的buffer pool可以理解为LRU cache那样的东西， 不过LeetCode上的LRU cache缺少reference counter只是玩具算法题。

然后，略微改写一下原有的dfs flood算法。在原来的算法中，我们访问一个matrix cell可能直接是matrix[row][col]这种写法，现在要wrap成两个函数调用：
(1) getMatrixCell(long row, long col)
(2) setMatrixCell(long row, long col, byte value)

这两个函数首先从buffer pool中取出对应row / col的block，然后做相应的get / set操作。注意到如果buffer pool满了，又需要从磁盘上取新的block，那么buffer pool自己会evict掉一些最近没有被访问的block并且将其更新的内容（所谓dirty page）写回磁盘，从而腾出内存空间。

理论上，用buffer pool方法，pool的容量只要能容纳2个block即可，但其性能会非常差 —— 因为会不断地读写磁盘。而如果有4096个block容量，并且岛屿不长得特别狭长的话（所谓workload characteristics，这一假定其实是比较符合现实情况的），那么性能其实会相当不错。

最后，buffer pool方法属于shared-memory架构，适用于单机场景（也就是传统DB），其单机性能是强于map reduce的一套东西的（可能可以快一个数量级），但是不适用于分布式场景。如果要支持分布式的话，要设计shared-nothing的算法，就和原来的dfs flood长得不太像了。

边界处理就case by case了，所以这个本身才是考点...

foryousee 发表于 2018-11-5 11:00
边界处理就case by case了，所以这个本身才是考点...

哦哦，那就比如这个岛屿个数问题。一般用dfs 灌水法。大数据切块以后还怎么灌水呢?边界怎么处理呀？谢谢。

foryousee 发表于 2018-11-5 11:00
边界处理就case by case了，所以这个本身才是考点...

哦哦，那就比如这个岛屿题，一般就dfs flood，那切块了以后还怎么flood呢？边界怎么处理呢？谢谢

好问题，我也想知道

magicsets 发表于 2018-11-5 12:39
首先不妨设matrix的大小是M * N，M、N是很大的数字比如2^20。

然后将matrix分块，设每个block的大小是 ...

大神牛逼！！谢谢解答！！其他一些大数据问题解法是不是也都是切块，然后数据处理啊？

yexiaojiaycc 发表于 2018-11-5 15:01
大神牛逼！！谢谢解答！！其他一些大数据问题解法是不是也都是切块，然后数据处理啊？

“大数据问题要切块”就和“做软件要写代码”一样，可以这么说，但是基本没有信息量就是.. 不过总的说来两大根本套路的确就是切块（partition）和复制（replication）

然后"大数据问题”本身也分很多场景，比如找岛屿这道题目属于analytical场景，偏computing（query processing）；而对应的还有transactional场景，比如说阿里巴巴双十一峰值下大量订单应该怎么处理。不同的场景虽然都会涉及到切块，但是细节可能很不一样。

就切块来说也有很多切法，比如表数据的横切竖切（horizontal / vertical），有key情况下根据hash还是range切，等等。

还有一个重要问题是数据的存储布局（storage layout），就是数据在磁盘/SSD上是怎么存储。因为磁盘/SSD都是块设备，性能特性与内存的随机访问特性不同。我们常见的“数据结构”都是基于内存的，并不适用于磁盘访问，所以切块方法的设计要与storage layout相搭配，或者反向操作改变storage layout来适应切块方法。

比如matrix这个问题，常见的存储布局就是行优先（row-major order），一行一行的数据连续存在磁盘上。而
问题本身的特性决定了分割成一个一个方形的block更好一些，那么为了最佳性能第一步就要洗一下存储布局（大数据的shuffle操作），将各个block的数据各自放在一起。

magicsets 发表于 2018-11-6 06:15
“大数据问题要切块”就和“做软件要写代码”一样，可以这么说，但是基本没有信息量就是.. 不过总的说来 ...

哦哦好的好的，谢谢大神啦！