分布式算法原理

1. 分布式计算怎么出现的

分布式计算可以分为以下几类：

传统的C/S模型。如HTTP/FTP/SMTP/POP/DBMS等服务器。客户端向服务器发送请求，服务器处理请求，并把结果返回给客户端。客户端处于主动，服务器处于被动。这种调用是显式的，远程调用就是远程调用，本地调用就是本地调用，每个细节你都要清楚，一点都含糊不得。

集群技术。近年来PC机的计算能力飞速发展，而服务器的计算能力，远远跟不上客户端的要求。这种多对一的关系本来就不公平，人们已经认识到靠提高单台服务器的计算能力，永远满足性能上的要求。一种称集群的技术出现了，它把多台服务器连接起来，当成一台服务器来用。这种技术的好处就是，不但对客户来说是透明的，对服务器软件来说也是透明的，软件不用做任何修改就可以在集群上运行。集群技术的应用范围也仅限于此，只能提高同一个软件的计算能力，而对于多个不同的软件协同工作无能为力。

通用型分布式计算环境。如CORBA/DCOM/ RMI/ DBUS等，这些技术(规范)差不多都有具有网络透明性，被调用的方法可能在另外一个进程中，也可能在另外一台机器上。调用者基本上不用关心是本地调用还是远程调用。当然正是这种透明性，造成了分布式计算的滥用，分布式计算用起来方便，大家以为它免费的。实际上，分布式计算的代价是可观的，据说跨进程的调用，速度可能会降低一个数量级，跨机器的调用，速度可能降低两个数量级。一些专家都建议减少使用分布式计算，即使要使用，也要使用粗粒度的调用，以减少调用的次数。

还其一些混合形式(SOAP?)，这里不再多说。我们主要介绍第三种分布式模型，这类分布式模型即适用于企业级应用，也适用于桌面应用。有的专注于企业级应用（如CORBA），有的专注于桌面环境（如DBUS）。它们的实现原理都差不多，基本上都基于传统的RPC或者仿RPC实现的，下面介绍一下它们的基本原理。

我们先看一下分布式的最简模型：

在传统的方法中，调用一个对象的函数很简单：创建这个对象，然后调用它的函数就行了。而在分布式的环境中，对象在另外一个进程中，完全在不同的地址空间里，要调用它的函数可能有点困难了。

看看传统的C/S模型的请求方式，客户端把参数通过网络发给服务器，服务器根据参数要求完成相应的服务，然后把结果返回给客户端，客户端拿到结果了，一次请求算完成。由此看来，调用远程对象似乎并不难，问题在于这种方式不是网络透明的，每一个细节你都要自己处理，非常复杂。

要简化软件的设计，当然是网络操作透明化，调用者和实现者都无需关心网络操作。要做到这一点，我们可以按下列方法：

在客户端要引入一个代理(Proxy)对象。它全权代理实际对象，调用者甚至都不知道它是一个代理，可以像调用本地对象一样调用这个对象。当调用者调用Proxy的函数时，Proxy并不做实际的操作，而是把这些参数打包成一个网络数据包，并把这个数据包通过网络发送给服务器。

在服务器引入一个桩(Stub)对象，Stub收到Proxy发送的数据包之后，把数据包解开，重新组织为参数列表，并用这些参数就调用实际对象的函数。实际对象执行相关操作，把结果返回给Stub，Stub再把结果打包成一个网络数据包，并把这个数据包通过网络发送给客户端的Proxy。

Proxy收到结果数据包后，把数据包解开为返回值，返回给调用者。至此，整个操作完成了。怎么样，简化吧。

Proxy隐藏了客户端的网络操作，Stub隐藏了服务器端的网络操作，这就实现了网络透明化。你也许会说，根本没有简化，只是把网络操作隔离开了，仍然要去实现Proxy和Stub两个对象，一样的麻烦。

没错。不过仔细研究一下Proxy和Stub的功能，我们会发现，对于不同对象，这些操作都差不多，无非就是打包和解包而已，单调重复。单调重复的东西必然有规律可循，有规律可循就可以用代码产生器自动产生代码。

像DCOM和CORBA等也确实是这样做的，先用IDL语言描述出对象的接口，然后用IDL编译器自动产生Proxy和Stub代码，整个过程完全不需要开发人员操心。

打包和解包的专业术语叫做marshal和unmarshal，中文常用翻译为列集和散集。不过这两个词太专业了，翻译成中文之后更加让人不知所云。我想还是用打包和解包两个词更通俗一点。

在以上模型中，调用对象的方法，确实做到了网络透明化。读者可以会问，我要访问对象的属性怎么办呢？对象的属性就是变量，变量就一块内存区域，内存区域在不同的进程里完全是独立的，这看起来确实是一个问题。还记得很多关于软件设计书籍里面讲过的吗：不要暴露对象属性，调用者若要访问对象的属性，通过get/set方法去访问。这样不行了吗，对属性的访问转换为对对象方法的调用。

OK，调用对象的方法和访问对象的属性都解决了。还有重要的一点，如何创建对象呢。因为实际的对象并不固定在某台机器上，它的位置可能是动态的。甚至Proxy本身也不知道Stub运行在哪里。如果要让调用者来指定，创建对象的过程仍未达到网络透明化。通常的做法是引入一个第三方中介，这个第三方中介是固定的，可以通过一定的方法找到它。第三方中介负责在客户端的Proxy和服务器的Stub之间穿针引线。第三方中介通常有两种：一种是只负责帮客户端找到服务器，之后客户端与服务器直接通信。另外一种就是不但负责找到服务器，而且负责转发所有的请求。

以上的模型仍然不完整，因为现实中的对象并不是一直处理于被动的地位。而是在一定的条件下，会主动触发一些事件，并把这些事件上报给调用者。也就是说这是一个双向的动作，单纯的C/S模型无法满足要求，而要采用P2P的方式。原先的客户端同时作为一个服务器存，接受来自己服务器的请求。像COM里就是这样做的，客户端要注册对象的事件，就要实现一个IDispatch接口，给对象反过来调用。

自己实现时还要考虑以下几点：

l 传输抽象层。分布可能是跨进程也可能是跨机器。在不同的情况下，采用不同的通信方式，性能会有所不同。做一个传输抽象层，在不同的情况下，可选用不同的传输方式，是一种好的设计。

l 文本还是二进制。把数据打包成文本还是二进制？打包成文本的好处是，可移植性好，由于人也可以看懂，调试方便。坏处是速度稍慢，打包后的数据大小会明显变大。采用二进制的好处是，速度快，打包后的数据大小与打包前相差不大。坏处是不易调试，可移植性较差。

l 字节顺序和字节对齐。若采用二进制方式传输，可移植性是个问题。因为不同的机器上，字节顺序和字节对齐的方式都有些差异，在数据包中要加入这些说明，以提高可移植性。

2. 分布式系统范式是什么如何系统学习分布式计算

复旦大学计算机专业全国排第6左右，所以要靠它的研究生是有难度的 计算机专业方向及其代码 081201计算机系统结构 01计算机网络与分布式系统 02嵌入式系统及应用 03分布式系统的监测与性能分析 04并行处理 081202计算机软件与理论 01数据库与知识库 02软件工程 03Web数据处理 04计算机支持的协同工作 05计算机生物信息处理 06数据挖掘与数据仓库 07电子商务 08网络协议与分布式软件 09密码与信息安全 10算法与程序理论 11人工智能与认知科学 12信息安全与信息编码 13量子信息与计算 14服务计算 081203计算机应用技术 01大规模中文文本处理 02多媒体信息处理与检索 03计算机图形图像处理 04网络与信息工程 05计算机控制与智能系统 06模式识别与人工智能 07信息安全、网络安全 08宽带网络应用技术 初试科目： ①101政治理论②201英语③301数学一④879数据结构与操作系统 复试的笔试要考很多科目. 1. 离散数学 2. 计算机原理 3. 概率论与数理统计 4. 软件工程 5. 计算机体系结构 6. 数据库引论 7. 编译 8. 数据通信与计算机网络 9. 算法设计与分析 10. 计算机图形学 08年起，初试计算机专业课实行全国统考。 复试这10门都要考的， 08年复旦计算机复试笔试回忆题 面试很怪异今年，牛人什么时候都不怕。普通平民还是以专业知识为出发点吧，下面给出8门课的复习思路。 1.离散。离散我的复习思路是代数系统，正规子群的证明，图论，欧拉和哈密顿图，范式 ，推导。这都是大概的章节名称，要求掌握的，结果考了正规子群，命中。 2.原理。寻址，数的计算，补码，反码，移码，原码，还有就是浮点数的乘法。在这些课 的复习中肯定会有加速比的概念，看一遍就非常明白了。我没学过原理，就复习了这些， 这是在赌博，结果算是命中了。 3.概率。不解释，考研怎么复习这个就怎么复习。 4.软工。大方向着手，譬如瀑布模型，重点在测试，白盒，黑盒，还有耦合和内聚，今年 考耦合，明年考内聚。Yes！命中。 5.体系结构。我只看了cpi的计算方法，还有mips的计算方法，流水线的东西，以及流水线 的三个相关。别的东西都是操作系统上的，考好了初试这个就没问题。命中一半。不算命 中。 6.数据库。Sql语言，关系演算，模式内模式外模式，2个映像，2个独立性，还有就是无损 连接，这个最好网络一下，网上有关于怎么证明是无损连接的。命中一半。 7.网络。香农奈奎斯特公式，还有就是数通方面的计算利用率的，不只是停等，滑动窗口 的利用率也要会算，7层协议，TCP IP了解，掌握IP地址的概念，还有就是局域网的组建， 这个都是本科学过的东西，很多专业都学过，相信大家都不会陌生，总之，命中。 8.算法。NP方面的各种问题。我就看这么多。动态规划一点没看，因此未命中。 总结下来大概就50分命中的，对于我这个10门科有7门没有学过的人来说，相当相当牛了

3. 《分布式实时计算框架原理及实践案例》pdf下载在线阅读全文，求百度网盘云资源

《分布式实时计算框架原理及实践案例》网络网盘pdf最新全集下载:
链接: https://pan..com/s/1mRd2oGCC97YKNMTjSpr37Q

4. 分布式存储中，怎样使用paxos算法保证数据的一致性

在分布式系统中，我们经常遇到多数据副本保持一致的问题，在我们所能找到的资料中该问题讲的很笼统，模模糊糊的，把多个问题或分类糅合在一起，难以理解。在思考和翻阅资料后，通俗地把一致性的问题可分解为2个问题：
1、任何一次修改保证数据一致性。
2、多次数据修改的一致性。
在弱一致性的算法，不要求每次修改的内容在修改后多副本的内容是一致的，对问题1的解决比较宽松，更多解决问题2，该类算法追求每次修改的高度并发性，减少多副本之间修改的关联性，以获得更好的并发性能。例如最终一致性，无所谓每次用户修改后的多副本的一致性及格过，只要求在单调的时间方向上，数据最终保持一致，如此获得了修改极大的并发性能。
在强一致性的算法中，强调单次修改后结果的一致，需要保证了对问题1和问题2要求的实现，牺牲了并发性能。本文是讨论对解决问题1实现算法，这些算法往往在强一致性要求的应用中使用。
解决问题1的方法，通常有两阶段提交算法、采用分布式锁服务和采用乐观锁原理实现的同步方式,下面分别介绍这几种算法的实现原理。

两阶段提交算法

在两阶段提交协议中，系统一般包含两类机器（或节点）：一类为协调者（coordinator），通常一个系统中只有一个；另一类为事务参与者（participants，cohorts或workers），一般包含多个，在数据存储系统中可以理解为数据副本的个数。两阶段提交协议由两个阶段组成，在正常的执行下，这两个阶段的执行过程如下所述：
阶段1：请求阶段（commit-request phase，或称表决阶段，voting phase）。
在请求阶段，协调者将通知事务参与者准备提交或取消事务，然后进入表决过程。在表决过程中，参与者将告知协调者自己的决策：同意（事务参与者本地作业执行成功）或取消（本地作业执行故障）。
阶段2：提交阶段（commit phase）。
在该阶段，协调者将基于第一个阶段的投票结果进行决策：提交或取消。当且仅当所有的参与者同意提交事务协调者才通知所有的参与者提交事务，否则协调者将通知所有的参与者取消事务。参与者在接收到协调者发来的消息后将执行响应的操作。
举个例子：A组织B、C和D三个人去爬长城：如果所有人都同意去爬长城，那么活动将举行；如果有一人不同意去爬长城，那么活动将取消。用2PC算法解决该问题的过程如下：
首先A将成为该活动的协调者，B、C和D将成为该活动的参与者。
阶段1：A发邮件给B、C和D，提出下周三去爬山，问是否同意。那么此时A需要等待B、C和D的邮件。B、C和D分别查看自己的日程安排表。B、C发现自己在当日没有活动安排，则发邮件告诉A它们同意下周三去爬长城。由于某种原因，D白天没有查看邮件。那么此时A、B和C均需要等待。到晚上的时候，D发现了A的邮件，然后查看日程安排，发现周三当天已经有别的安排，那么D回复A说活动取消吧。
阶段2：此时A收到了所有活动参与者的邮件，并且A发现D下周三不能去爬山。那么A将发邮件通知B、C和D，下周三爬长城活动取消。此时B、C回复A“太可惜了”，D回复A“不好意思”。至此该事务终止。
两阶段提交算法在分布式系统结合，可实现单用户对文件（对象）多个副本的修改，多副本数据的同步。其结合的原理如下：
1、客户端（协调者）向所有的数据副本的存储主机（参与者）发送：修改具体的文件名、偏移量、数据和长度信息，请求修改数据，该消息是1阶段的请求消息。
2、存储主机接收到请求后，备份修改前的数据以备回滚，修改文件数据后，向客户端回应修改成功的消息。 如果存储主机由于某些原因（磁盘损坏、空间不足等）不能修改数据，回应修改失败的消息。
3、客户端接收发送出去的每一个消息回应，如果存储主机全部回应都修改成功，向每存储主机发送确认修改的提交消息；如果存在存储主机回应修改失败，或者超时未回应，客户端向所有存储主机发送取消修改的提交消息。该消息是2阶段的提交消息。
4、存储主机接收到客户端的提交消息，如果是确认修改，则直接回应该提交OK消息；如果是取消修改，则将修改数据还原为修改前，然后回应取消修改OK的消息。
5、 客户端接收全部存储主机的回应，整个操作成功。
在该过程中可能存在通信失败，例如网络中断、主机宕机等诸多的原因，对于未在算法中定义的其它异常，都认为是提交失败，都需要回滚，这是该算法基于确定的通信回复实现的，在参与者的确定回复（无论是回复失败还是回复成功）之上执行逻辑处理，符合确定性的条件当然能够获得确定性的结果哲学原理。

分布式锁服务

分布式锁是对数据被外界修改持保守态度，在整个数据处理过程中将数据处于锁定状态，在用户修改数据的同时，其它用户不允许修改。
采用分布式锁服务实现数据一致性，是在操作目标之前先获取操作许可，然后再执行操作，如果其他用户同时尝试操作该目标将被阻止，直到前一个用户释放许可后，其他用户才能够操作目标。分析这个过程，如果只有一个用户操作目标，没有多个用户并发冲突，也申请了操作许可，造成了由于申请操作许可所带来的资源使用消耗，浪费网络通信和增加了延时。
采用分布式锁实现多副本内容修改的一致性问题， 选择控制内容颗粒度实现申请锁服务。例如我们要保证一个文件的多个副本修改一致， 可以对整个文件修改设置一把锁，修改时申请锁，修改这个文件的多个副本，确保多个副本修改的一致，修改完成后释放锁；也可以对文件分段，或者是文件中的单个字节设置锁， 实现更细颗粒度的锁操作，减少冲突。
常用的锁实现算法有Lamport bakery algorithm （俗称面包店算法）， 还有Paxos算法。下面对其原理做简单概述。

Lamport面包店算法

是解决多个线程并发访问一个共享的单用户资源的互斥问题的算法。 由Leslie Lamport（英语：Leslie Lamport）发明。
Lamport把这个并发控制算法可以非常直观地类比为顾客去面包店采购。面包店只能接待一位顾客的采购。已知有n位顾客要进入面包店采购，安排他们按照次序在前台登记一个签到号码。该签到号码逐次加1。根据签到号码的由小到大的顺序依次入店购货。完成购买的顾客在前台把其签到号码归0. 如果完成购买的顾客要再次进店购买，就必须重新排队。
这个类比中的顾客就相当于线程，而入店购货就是进入临界区独占访问该共享资源。由于计算机实现的特点，存在两个线程获得相同的签到号码的情况，这是因为两个线程几乎同时申请排队的签到号码，读取已经发出去的签到号码情况，这两个线程读到的数据是完全一样的，然后各自在读到的数据上找到最大值，再加1作为自己的排队签到号码。为此，该算法规定如果两个线程的排队签到号码相等，则线程id号较小的具有优先权。
把该算法原理与分布式系统相结合，即可实现分步锁。

Paxos算法

该算法比较热门，参见WIKI，http://zh.wikipedia.org/wiki/Paxos%E7%AE%97%E6%B3%95
Paxos算法解决的问题是一个分布式系统如何就某个值(决议)达成一致。一个典型的场景是，在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点都执行相同的操作序列，那么他们最后能得到一个一致的状态。为保证每个节点执行相同的命令序列，需要在每一条指令上执行一个“一致性算法”以保证每个节点看到的指令一致。一个通用的一致性算法可以应用在许多场景中，是分布式计算中的重要问题。节点通信存在两种模型：共享内存(Shared memory)和消息传递(Messages passing)。Paxos算法就是一种基于消息传递模型的一致性算法。BigTable使用一个分布式数据锁服务Chubby，而Chubby使用Paxos算法来保证备份的一致性。

采用乐观锁原理实现的同步

我们举个例子说明该算法的实现原理。如一个金融系统，当某个操作员读取用户的数据，并在读出的用户数据的基础上进行修改时（如更改用户帐户余额），如果采用前面的分布式锁服务机制，也就意味着整个操作过程中（从操作员读出数据、开始修改直至提交修改结果的全过程，甚至还包括操作员中途去煮咖啡的时间），数据库记录始终处于加锁状态，可以想见，如果面对几百上千个并发，这样的情况将导致怎样的后果。
乐观锁机制在一定程度上解决了这个问题。乐观锁，大多是基于数据版本（ Version）记录机制实现。何谓数据版本？即为数据增加一个版本标识，在基于数据库表的版本解决方案中，一般是通过为数据库表增加一个 “version” 字段来实现。读取出数据时，将此版本号一同读出，之后更新时，对此版本号加一。此时，将提交数据的版本数据与数据库表对应记录的当前版本信息进行比对，如果提交的数据版本号大于数据库表当前版本号，则予以更新，否则认为是过期数据。
对于上面修改用户帐户信息的例子而言，假设数据库中帐户信息表中有一个 version 字段，当前值为 1 ；而当前帐户余额字段（ balance ）为 $100 。
操作员 A 此时将其读出（version=1 ），并从其帐户余额中扣除 $50（$100-$50 ）。
在操作员 A 操作的过程中，操作员B也读入此用户信息（ version=1 ），并从其帐户余额中扣除 $20 （ $100-$20 ）。
操作员 A 完成了修改工作，将数据版本号加一（ version=2 ），连同帐户扣除后余额（ balance=$50 ），提交至数据库更新，此时由于提交数据版本大于数据库记录当前版本，数据被更新，数据库记录 version 更新为 2 。
操作员 B 完成了操作，也将版本号加一（ version=2 ）试图向数据库提交数据（ balance=$80 ），但此时比对数据库记录版本时发现，操作员 B 提交的数据版本号为 2 ，数据库记录当前版本也为 2 ，不满足 “ 提交版本必须大于记录当前版本才能执行更新 “ 的乐观锁策略，因此，操作员 B 的提交被驳回。这样，就避免了操作员 B 用基于 version=1 的旧数据修改的结果覆盖操作员A 的操作结果的可能。
乐观锁机制与分布式系统相结合上， 我整理了伪代码如下：
obj 操作的目标
vlaue 修改的值
atom_update_ver 每个目标上的版本，每次修改该值递增
set( obj, value)
{
//从每个节点上取出修改前的对象版本
get original_ver = obj.atom_update_ver from each node;
//将值赋到每个节点的obj目标
set obj = value from each node;
//条件修改每个节点的obj版本，目标版本加一
//比较和修改操作是原子操作
result = (set obj.atom_update_ver = original_ver + 1
where original_ver + 1 > obj.atom_update_ver
for each node);
if(result == ok)
return set_ok;
else
return set(obj, value);//不成功递归修改

该算法未考虑节点下线、失效等问题，在后续我将分析采用乐观锁原理实现一致性算法，解决问题2、节点失效、通信失败等问题。

5. 云计算与分布式计算有区别吗

分布式技术其实质上是一种基于网络的计算机处理技术。一个分布式系统（Distributed System）是一组逻辑和物理上互联的处理单元的集合。其实质就是对资源的系统范围的分散控制，以达到应用程序的协同执行。这种系统不要求单台计算机的功能十分强大，故能降低成本。分布式系统具有快速访问、多用户使用的优点。系统中的每台计算机可以方便快捷的访问其他内部节点的信息文件，它既可以为本地用户的特殊要求服务，也可以为网络中其他用户服务，实现不同计算机之间的通信与协同工作。

云计算（Cloud Computing）是分布式处理、并行处理、网格计算的发展，是虚拟化、效用计算、IaaS、PaaS、SaaS等概念混合跃升的结果。基本原理是将计算任务分布在云端的大量的分布式计算机上、数据也存储在云端，使得企业将有限的资源切换到需要的应用上，降低企业运行的成本。这样带来的结果是中小企业不需要购置专门的计算机系统去满足某一应用需求，只需要想云计算中心支付服务费即可获得响应服务，而云计算中心则大规模的云，以向用户提供服务。总的来说云计算具有如下的特点：超大规模云计算集群、虚拟化、高可靠性、通用性、按需服务、极其廉价。

6. 云计算操作系统和分布式操作系统有什么区别

分布式操作系统负责管理分布式处理系统资源和控制分布式程序运行。它和集中式操作系统的区别在于资源管理、进程通信和系统结构等方面。运行于分布式计算机系统上的分布式程序由若干个可以独立执行的程序模块组成,它们分布于一个分布式处理系统的多台计算机上被同时执行。它与集中式的程序设计语言相比有三个特点：分布性、通信性和稳健性。

云计算操作系统是以分布式操作系统为基础的，提供资源的网络称为“云”。其基本原理是，使计算分布在大量的分布式计算机上，而非本地计算机或远程服务器中。这样可以有效降低对客户端的要求，通过“云”网络，无论是移动设备、数码产品还是台式PC，都可以获得类似的有效服务。

7. 分布式计算是谁提出的研究到什么程度了未来有哪些可研究方向目前的发展状态如何

没有谁提出，估计是总结出来的
最早概念应该是谷歌的技术就有。比如maprece
目前原理框架进步很少，而是技术实现的优化，新框架太少，本质上是分工计算模型太少，

8. 分布式系统常用的一致性算法有哪些

有一些系统设计基础的话，给你推荐几本书吧： 《面向模式的软件架构 卷4：分布式计算的模式语言》出版社：人民邮电出版社 主要讲分布式计算系统软件的设计和实现。 偏软件方向，相对较专业。 《分布式计算（第二版）》出版社：电子工业出版社 主要介绍分布式计算的数学基础和理论，揭示设计分布式系统的底层问题（通信、协调、同步及不确定）和基本的算法概念及下界技术。 容易理解，适合自学。 《分布式系统原理与范型》出版社：清华大学出版社 全书的第一部分讨论了分布式系统的原理、概念和技术，其中包括通信、进程、命名、同步、一致性和复制、容错以及安全。第二部分给出了一些实际的分布式系统：基于对象的分布式系统、分布式文件系统、基于文档的分布式系统以及基于协作的分布式系统，介绍了一些实际系统的设计思想和实现技术。 容易理解，适合自学。