原理的角度出发,map reduce其实就是二分查找的一个逆过程,不过因为计算节点有限,所以map和reduce前都预先有一个分区的步骤.
二分查找要求数据是排序好的,所以Map Reduce之间会有一个shuffle的过程对Map的结果排序. Reduce的输入是排好序的.
MR分而治之的策略和数据库行业中另一种数据库 Massively Parallel Processor 即大规模并行处理数据库(典型代表 AWS Redshift 和 Teradata 以及微软的 Azure SQL Data Warehouse)有什么区别呢?
MPP的思路简单粗暴,把数据分块,交给不同节点储存, 查询的时候各块的节点有独立的计算资源分别处理,然后汇总到一个leader node(又叫control node),具体的优化和传统的关系型数据库很相似,涉及到了索引,统计信息等概念. MPP有shared everything /Disk / Nothing之别.
在实际应用中的确MPP有更高的效率,所以对于结构化的大数据, MPP至今仍是首选.
MR 或者 Spark胜过MPP的地方在于非结构化的数据处理上, 比如大量日志文件或者大量tweet。
或者在一些复杂的算法应用上MR或Spark的可编程性显得更加灵活. Hadoop复杂的ecosystem对于复杂情况有着更好的应对,而对于结构化的大数据,要是出一些纯统计数字的报表的话, Hadoop有点虎落平阳被犬欺的感觉。
一些大公司的架构也是MPP和Hadoop两者兼具的。既有用MPP处理传统的BI报表业务,又有使用Hadoop做一些深入分析的应用。未来MPP和hadoop能否融合起来,是一个值得观察的发展方向。
Shared Everything:一般是针对单个主机，完全透明共享CPU/MEMORY/IO，并行处理能力是最差的，典型的代表SQLServer
Shared Disk：各个处理单元使用自己的私有 CPU和Memory，共享磁盘系统。典型的代表Oracle Rac，它是数据共享，可通过增加节点来提高并行处理的能力，扩展能力较好。其类似于SMP（对称多处理）模式，但是当存储器接口达到饱和的时候，增加节点并不能获得更高的性能 。
Shared Nothing：各个处理单元都有自己私有的CPU/内存/硬盘等，不存在共享资源，类似于MPP（大规模并行处理）模式，各处理单元之间通过协议通信，并行处理和扩展能力更好。典型代表DB2 DPF和hadoop ，各节点相互独立，各自处理自己的数据，处理后的结果可能向上层汇总或在节点间流转。
我们常说的 Sharding 其实就是Share Nothing架构，它是把某个表从物理存储上被水平分割，并分配给多台服务器（或多个实例），每台服务器可以独立工作，具备共同的schema，比如MySQL Proxy和Google的各种架构，只需增加服务器数就可以增加处理能力和容量。
首先MPP 必须消除手工切分数据的工作量。这是MySQL 在互联网应用中的主要局限性。
另外MPP 的切分必须在任何时候都是平均的，不然某些节点处理的时间就明显多于另外一些节点。
对于工作负载是不是要平均分布有同种和异种之分，同种就是所有节点在数据装载的时候都同时转载，异种就是可以指定部分节点专门用来装载数据（逻辑上的不 是物理上） ， 而其他所有节点用来负责查询。 Aster Data 和Greenplum 都属于这种。
两者之间并没有明显的优势科研，同种的工作负载情况下，需要软件提供商保证所有节点的负载是平衡的。 而异种的工作负载可以在你觉得数据装载很慢的情况下手工指定更多节点装载数据。区别其实就是自动化和手工控制，看个人喜好而已。
另外一个问题是查询如何被初始化的。 比如要查询销售最好的10件商品，每个节点都要先计算出自己的最好的10件商品，然后向上汇总，汇总的过程，肯定有些节点做的工作比其他节点要多。
上面只是一个简单的单表查询，如果是两个表的连接查询，可能还会涉及到节点之间计算的中间过程如何传递的问题。 是将大表和小表都平均分布，然后节点计算的时候将得到的结果汇总（可能要两次汇总），还是将大表平均分布，小表的数据传输给每个节点，这样汇总就只需要一 次。 （其中一个特例可以参考后面给出的Oracle Partition Wise Join）。
两种执行计划很难说谁好谁坏，数据量的大小可能会产生不同的影响。
有些特定的厂商专门对这种执行计划做过了优化的，比如EMC Greenplum 和 HP Vertica。
这其中涉及到很多取舍问题，比如数据分布模式，数据重新分布的成本，中间交换数据的网卡速度，储存介质读写的速度和数据量大小（计算过程一般都会用临时表 储存中间过程）。
Hadoop与MPP的区别：
1.底层数据库：
MPP跑的是SQL,而Hadoop底层处理是MapReduce程序。
2.扩展程度
MPP虽然是宣称可以横向扩展Scale OUT，但是这种扩展一般是扩展到100左右，而Hadoop一般可以扩展1000+。
这是因为什么呢？其实可以从CAP理论上来找原因。
在理论计算机科学中，CAP定理（CAP theorem），又被称作布鲁尔定理（Brewer's theorem），它指出对于一个分布式计算系统来说，不可能同时满足以下三点：
一致性（Consistency)：
同一个数据在集群中的所有节点，同一时刻是否都是同样的值。
可用性（Availability）：
集群中一部分节点故障后，集群整体是否还能处理客户端的更新请求。
分区容忍性（Partition tolerance）：
是否允许数据的分区，分区的意思是指是否允许集群中的节点之间无法通信。
因为MPP始终还是DB,一定要考虑到C(Consistency),其次考虑A(Availability),最后才在可能的情况下尽量做好P(Partition-tolerance)。而Hadoop就是为了并行处理和存储设计的，所以数据都是以文件存储，所以有限考虑的是P,然后是A,最后再考虑C.所以后者的可靠型当然好于前者。
以下几个方面制约了MPP数据库的扩展：
1.高可用：MPP DB是通过Hash计算来确定数据行所在的物理机器（而Hadoop不需要此操作），对存储位置的不透明导致MPP的高可用很难办。
2.并行任务：数据是按照Hash来切分的，但是任务没有。每个任务，无论大小都要到每个节点上走一圈。
3.文件系统：数据切分了，但是文件数没有变少，每个表在节点上一定有一个到多个文件。同时节点数越多，存储的表越多，导致每个文件系统有上万甚至十万多个文件。
4.网络瓶颈：MPP强调对等的网络，点对点的连接也消耗了大量的网络宽带，限制了网络上的线性扩展（想象以下一台机器要给1000台机器发送信息）。等多的节点并没有提供更高的宽带，反而导致每个组节点间平均宽带降低。
5.其他关系数据库的枷锁：比如锁，日志，权限，管理节点瓶颈等均限制了MPP规模的扩大。
Hadoop和MPP的应用场景
MPP数据库有对SQL的完整兼容和一些事务的处理能力，对于用户来说，在实际的使用场景中，如果数据扩展需求不是特别大，需要的处理节点不多，数据都是结构化的数据，习惯使用传统的RDBMS的很多特性的场景，可以考虑MPP,例如Greenplum/Gbase等。
如果有很多非结构化数据，或者数据量巨大，有需要扩展到成百上千个数据节点需求的，这个时候Hadoop是更好的选择。
