什么是云计算

云计算（cloud computing）是分布式计算的一种，指的是通过网络“云”将巨大的数据计算处理程序分解成无数个小程序，然后，通过多部服务器组成的系统进行处理和分析这些小程序得到结果并返回给用户。云计算早期，简单地说，就是简单的分布式计算，解决任务分发，并进行计算结果的合并。因而，云计算又称为网格计算。通过这项技术，可以在很短的时间内（几秒钟）完成对数以万计的数据的处理，从而达到强大的网络服务。

现阶段所说的云服务已经不单单是一种分布式计算，而是分布式计算、效用计算、负载均衡、并行计算、网络存储、热备份冗杂和虚拟化等计算机技术混合演进并跃升的结果。

Google云计算

云计算技术涉及的面很广，从存储、计算、资源的调度到权限的管理等，云计算的一个关键问题是，如何把一个非常大的计算问题，自动分解到许多计算能力不是很强大的计算机上，共同完成。Google 针对这个问题给出的解决工具是一个叫 MapReduce 的程序，其根本原理就是计算机算法上很常见的分治（Divide-and-Conquer）算法。

分治算法的原理

在计算机科学中，分治法是建基于多项分支递归的一种很重要的算法范型。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法（归并排序、快速排序)、傅立叶变换（快速傅立叶变换)。

从分治算法到MapReduce

熟悉计算机算法的读者都知道归并排序（Merge Sort）的原理。假定要对一个长度为N的数组 $a_{1},a_{2},a_{3},...,a_{N}$ 进行排序，如果采用对 $a_{i}$ ?和 $a_{j}$ ;两两比较的办法（冒泡排序),时间复杂度是 $O(N^{^{2}})$ ，不仅非常笨（慢）。而且如果数组过大（比如几千亿个元素），也无法在一台计算机上完成。

而使用分治算法，是将这个大数组分为几份，比如一分为二，对每一半分别进行排序。当这两个子数组排序完毕后，把它们从头到尾合并，得到原来数组的排序结果。对应的大小正好是原数组一半大，只需要进行1/4的比较即可。

当然，合并的过程需要一些额外的时间，但是和省下的时间相比可以忽略不计。同理，还可以对前后每一半子数组继续分解成更小的子数组。直到子数组中只有两个元素。这种做法大大缩短了整个排序的时间，由原来的 $O(N^{2})$ 简化到 $O(N\cdot logN)$ ，如果N是一百万，那么计算时间将缩短一万倍。这个排序算法在每个子任务完成后，都要进行合并，归并排序算法也因此得名。

感兴趣的读者可以去了解一下冒泡排序和归并排序算法。

以矩阵乘法为例

如果一台服务器存不下整个大数组，这件事就变得很麻烦。好了，让我们看看分治算法怎么做。首先，把矩阵A按行拆成10个小矩阵A1，A2，...，A10，每一个有N/10行。

分别计算每个小矩阵A1，A2，…，A1和B的乘积，不失一般性，以A1来说明：
?

同理，可以在第二台、第三台、……服务器上计算出其他元素。当然，矩阵B和矩阵A一样大时，一台服务器同样存不下。不过没有关系，同样可以按列切分矩阵B，使得每台服务器只存矩阵B的1/10。上述公式可以直接使用，只是这回只完成了C1的1/10。

因此，这次需要100 台服务器而不是原来的10台，于是，在单机上无法求解的大问题就被分解成小问题得以解决。

在上面的例子中，增加了服务器的数量，但是每个元素 $c_{n,m}$ 的绝对计算时间其实并没有减少（这点不像归并排序）。但是在某些应用中，增加服务器数量可以带来绝对计算时间的减少。例如，只是要得到C中某个特定元素 $c_{n,m}$ 而不是整个C矩阵，这种需求在链接分析或者日志处理中有时会遇到，假如希望通过10倍的机器能够缩短计算时间。这个需求也可以通过分治算法来实现，具体解决方法如下：
对矩阵A按行切分，对矩阵B按列切分。A1是A的前十分之一行，A2是接下来的十分之一，等等，对B也是如此。然后用同样的方法计算得到10 个中间结果 $c_{nm}^{1}$ ，...， $c_{nm}^{10}$ 。而 $c_{n,m}$ 只是这10个数字相加的结果。下面每个结果的计算量都是最后结果的十分之一。这样，我们就用10倍的计算机数量将计算时间缩短了10倍。