分布式
分布式的特点
各种计算机之间的差别以及计算机之间的通信方式的差别对用户来说是隐藏的；用户和应用程序无论在何时何地都能够以一种一致和统一的方式与分布式系统进行交互。（用户眼里只有一台机器）
P2P的问题及解决方式
问题
如何高效的定位节点，也就是说，一个节点怎样高效的知道在网络中的哪个节点包含它所寻找的数据。
DHT
- 每条文件索引被表示成一个(K, V)对
- K称为关键字，可以是文件名（或文件的其他描述信息）的哈希值
- V是实际存储文件的节点的IP地址（或节点的其他描述信息）
- 所有的文件索引条目(即所有的（K, V）对)组成一张大的文件索引哈希表，只要输入目标文件的K值，就可以从这张表中查出所有存储该文件的节点地址。
- 再将上面的大文件哈希表分割成很多局部小块，按照特定的规则把这些小块的局部哈希表分布到系统中的所有参与节点上，使得每个节点负责维护其中的一块。
- 这样，节点查询文件时，只要把查询报文路由到相应的节点即可
Chord算法
解决网络内节点定位问题，通过多个节点跳转找到我们所查找的资源。
节点ID
NID（node identifier），表示一个物理机器；
资源ID
KID（key identifiers），原为键ID，其实际表示一个资源；
Chord环
Chord Ring，NID和KID被分配到一个大小为2^m的环上，用于资源分配（给某一个节点）和节点分布，以及资源定位。
资源分配
资源被分配到NID>=KID的节点上，这个节点成为k的后继节点，是环上从k起顺时针方向的第一个节点，记为successor(k)。而节点分布则顺时针将节点N由大到小放在这个环上。
例：
现在N26节点要加入系统，首先它指向其后继N32，然后通知N32，N32接到通知后将N26标记为它的前序节点（predecessor）。然后N26修改路由表，下一次N21运行stabilize()询问其后继节点N32的前序节点是不是还是自己，此时发现N32的前序节点已经是N26。于是N21就将后继节点修改为N26，并通知N26自己已经将其设置为后继节点，N26接到通知后将N21设置为自己的前序节点。
（每个节点加入系统时，先找到合适的位置，再通知其后继将前序改为自己，节点遍历时会询问是否下一个节点的前序是自己，若不是，则改后继）
Chord资源定位
**
资源定位是Chord协议的核心功能，这个功能会带来两方面的影响：
1、正确性方面。当一个节点加入系统，而一个查找发生在stabilization结束前，那么此时系统会有三个状态：
- 所有后继指针和路由表项都正确时：对正确性没有影响。
- 后继指针正确但表项不正确：查找结果正确，但速度稍慢（在目标节点和目标节点的后继处加入非常多个节点时）（这时中间每个节点遍历时都得修改为正确的后继）
2、效率方面。可以证明，只要路由表调整速度快于网络节点数量加倍的速度，性能就不受影响：
- 当stabilization完成时，对查找效率的影响不会超过O(log N) 的时间。
- 当stabilization未完成时，在目标节点和目标节点的后继处加入非常多个节点时才会有性能影响。
Chord节点失败的处理
Chord依赖后继指针的正确性以保证整个网络的正确性。
若N14, N21, N32同时失效，那么N8是不会知道N38是它新的后继节点。（多个连续节点失效，两个正确的节点中如何互联？）
解决：
每个节点都包含一个大小为r的后继节点列表，一个后续节点失效了就依次尝试列表中的其他后继节点。
**
Chord的特征和应用
特征：去中心化，高可用度，高伸缩性，负载平衡，命名灵活。
应用：全球文件系统、命名服务、数据库请求处理、互联网级别的数据结构、通信服务、事件通知、文件共享。
进程
不同层次的4个不同界面
- 由机器指令组成，可由任何程序及其的软硬件界面；
- 由机器指令组成，只有特权程序才可激活的软硬件界面；
- 由操作系统提供的系统调用组成的界面；
- 由库调用组成的界面，通常形成了所谓的应用程序编程接口。
虚拟化可采用的两种方式
- 构建运行时系统，提供一套抽象指令集执行程序—进程虚拟机；
- 做成一层完全屏蔽硬件但提供一个人同样指令集的界面—虚拟机监视器。
命名
无结构命名、有结构命名、无结构查找、有结构查找
无结构命名：名字本身不代表任何含义。
有结构命名：名字本身有特定的含义，代表某些信息。
无结构命名
给定一个无结构命名，如何定位相关接入点
广播、转发指针（每次实体移动留下一个指针）、基于家庭的方法（类似漫游，去你家问你去了哪）、分布式哈希表（结构化P2P）、分层位置服务。
分布式哈希表（DHT、结构化P2P）
Chord：将多个节点（存储着数据的server node）组织成逻辑环（使用DHT实现有结构的命名查找）
- 每个节点被分配一个随机的m比特标识符（分配一个无结构命名的标识符）
- 为每个实体分配唯一的m比特密钥
- 密钥为k的实体属于具有最小id>=k的节点（称为其后继者）的管辖范围（如12的管辖范围比11的大）
- 让节点id（k实体的后继者）跟踪SUCC(ID)并沿着环顺时针搜
怎么加入一个节点：
规则：
- 每个节点p维护最多具有m个条目的指针表FTp[]：
- 为了查找关键字k，节点p将请求转发到满足索引j的节点
- 如果p<k<FTp[1]，这个请求也会被发送到FTp[1]
每个节点都在维护自身的一个hash table
hash 函数是：
分层位置服务（HLS）
- 构建一颗大规模的搜索树，将底层网络划分为分层域，每个域由单独的目录节点表示。
- 除叶节点外其他都是索引用，只有叶节点是实体域。
- 根知道所有实体，实体由于被复制，可能有多个地址
- 查找时从本地节点开始找，若节点知道该实体，则跟随指针，否则向上一级
层次式位置服务也是无结构的命名，有结构的查找
就是把每个结点向上做索引（如图），比如a想与c相连，就得向上面的目录结点查找，没有就继续向上查找
直到找到该位置
有点像Napster，整个系统中有集中式服务器的存在用来记录索引
根节点负载过大
有结构的命名
名称空间、名称解析、名称空间的实现、域名系统（DNS）
有结构命名：名字是有含义的
有结构查找：有规律的进行查找结点，不是像多播那样以flooding方式查找。
怎么对名字进行解析？
采用就近原则，就是一层一层往上迭代找
名称解析过程确定我们读取节点的内容，特别是我们需要转到的另一个节点中的名称。
命名解析要先解析高级域名，所以高层服务器需要每秒处理大量请求，但高层服务器节点内容几乎不会变，所以我们可以把这些服务器但内容广泛复制到多个服务器，名称解析就近处理加快速度。
如果客户端和服务器隔得比较远，最好采用递归命名解析，因为迭代命名解析会通信多次
如果是集中式的Root Server直接返回目的主机IP（递归）
如果是分布式，A先RequestRoot，Root返回GL，A再RequestGL，GL返回AL，逐层请求直到返回目的主机。（迭代）
将集中式改为分布式，用’.’进行分隔层次
递归解析会对服务器负载压力过大，容易造成阻塞，是不可以的。
命名空间实现
命名空间始终将名称映射到某个对象。
可以将命名空间分为三层：
- 全局层：不经常更改，由根目录和最靠近根目录的一些节点组成
- 管理层：单一组织，一般隶属于某个组织或团体类型之下，每个节点代表某一特定组织
- 管理层：定期更换，可以是目录节点或终结点。主要作用是有效地将目录节点映射到本地名称服务器。
同步化
物理时钟
- 高频振荡器（石英晶体）、计数器和保持寄存器
- 高频振荡器的每次震荡使计数器减1，档计数器减为0时，产生一个中断，计数器从保持计数器中重新装入初始值。
国际原子时间（TAI）.UTC统一协调时间is TAI with leap seconds.
时钟同步算法
Cristian算法——时间服务器是被动的（集中式服务器，把时间当成信息，想知道就去请求一下。但发送过来的时间是有延迟的，不是当前时间。）
- Berkeley算法——时间服务器是主动的（时间服务器向每个机器询问，再告诉每个机器应该如何调整其值）
- 目的是为了减小误差
Lamport逻辑时钟
a->b意味着所有的进程都agree事件a发生在事件b之前。
- 如果事件a和事件b是同一个进程中的并且事件a发生在事件b前面，那么a->b；
- 如果进程A发送一条消息m给进程B，a代表进程A发送消息m的事件，b代表进程B接收消息m的事件，那么a->b(由于消息的传递需要时间)。
- 如果事件a和事件b发生在不同的进程，并且这两个进程没有传递消息，那么既不能推到a->b也不能推到b->a，这样的两个事件叫做并发事件。
增加一个timestampC(e) ，如果
，则C(e1)
所以，每个进程都会维护自己的逻辑时钟
进程本身的事件好维护，每发生一个事件，逻辑时钟+1
产生进程间通信也好维护，就直接把让接收消息的进程进行逻辑时钟调max+1
Lamport logical clocks的实现
每个进程Pi维护一个本地计数器Ci，相当于logical clocks，按照以下的规则更新Ci：
①每次执行一个事件(例如通过网络发送消息，或者将消息交给应用层，或者其它的一些内部事件)之前，将Ci加1；
② 当Pi发送消息m给Pj的时候，在消息m上附着上Ci；
③当接收进程Pj接收到Pi的发送的消息时，更新自己的Cj = max{Cj,Ci}+1。
调整时钟操作发生在中间层
全有序多播
代价很高
需要保证复制的数据库上的并发更新在任何地方都以相同的顺序出现。
所谓全序，就是所有进程统一顺序，只要最后所有进程的事件执行顺序相同就行。
对排序按时间的严格性分为
全序更新：全部事件都要排序**
因果序更新：有因果关系才排序
FIFO：同一进程内有先后顺序的才排序
这里在逻辑时钟（lamport时钟）就有疑问了，对于数据库和备选数据库来说，update1和update2两个操作是并发的，不好来规定逻辑时钟，但是这两操作必须要有先后顺序，不然不能保证两个数据库的数据一致，
怎么实现全序多播？
- 进程先给消息打上一个当前时间戳，然后把这个消息放进自己的本地队列中，再将这个消息发送给其他进程。
- 进程收到来自其他进程的消息后，也把这个消息放入本地队列，按时间戳排序。
- 进程Pi向所有其他进程发送时间戳消息MSGi，消息本身被放入本地队列Qi中。
- 任何传入Pj的消息都会在j的本地队列Qj中排队，并向每个其他进程确认。
- Pj执行msgi的条件：msgi在Qj的队头且收到了其他进程的确认。
- 只要是同一个进程，队列内遵循FIFO
永远是时间快的消息先执行，但接收消息时要校准时间。
向量时钟
因为逻辑时钟间无因果关系（只能由a->b推出C(a)<C(b)），因果关系可以由向量时钟来捕获。用VC(a)来表示事件a的Vector Clock。有性质：VC(a) < VC(b)可以推出事件a 发生在事件b之前。
为每个进程Pi维护一个向量VCi（就是一个数组），也就是Pi的Vector Clock，这个向量VCi有如下属性：
- VCi[i] 是到目前为止进程Pi上发生的事件的个数；
- VCi[k] 是进程Pi知道的进程Pk发生的事件的数量(即Pi对Pj的了解)
每个进程的VC可以通过以下规则进行维护：
- 进程Pi每次执行一个事件之前，将VCi[i]加1；
- 当Pi发送消息m给Pj的时候，在消息m上附着上VCi(m+VCi=进程Pi的向量时钟)；
- 当接收进程Pj接收到Pi的发送的消息时 ，对于所有的k，更新自己的VCj[k] = max{VCj[k],VCi[k]}，进程Pj要执行Pi的消息时，VCj[i]+1。
Vector Clock记录进程所发生的事件数
因果有序多播
一个进程组中，每个进程需要广播消息给其它进程(相当于一个并发更新问题)，一个消息被delivered到应用层，仅当所有的causally发生之前的消息都被收到。（当消息有因果消息才排序）
假设：Pi给Pj发送消息m，那么Pj可以将消息m交给应用层必须首先满足上面两个条件：
- VCj[i] = VCi[i] - 1，意思是指Pj看到了Pi发生的所有的事件(不包括本次发送消息m的时间)；所以接收后将VCi[i]+1
- VCi[k] <= VCj[k] for all k≠i，Pj看到了i看到的其它的所有的进程发生的事。
互斥
两种方案
基于令牌的解决方案
拥有令牌这获得使用资源的权限，可以避免饿死和死锁，但令牌可能会丢失；
基于许可的解决方案
获得其他进程的许可来使用资源。
四种算法
集中式算法
保证互斥的实现，且公平，但协调者是故障点，会出现单点崩溃。四种算法中集中式算法是最简单也最有效的。
非集中式算法（Decentralized）
使用分布式哈希表（DHT）散列到一个节点。扩展集中式协作者，每个资源都有n个协调人，进程每次访问资源需要多于一半的协作者同意即可，解决单点故障。如果资源被锁定，不是阻塞，会拒绝。
分布式算法
如该进程不想进入临界区，则立即发送OK消息；如该进程想进入临界区，则把自己的request消息时间戳与收到的request消息时间戳相比较。获得大多数进程的许可即可。缺点：节点崩溃，信息丢失。
（1）0号，2号都想要访问资源，所以0号，2号都要把访问资源时间发出去，1号不想访问资源，就不用发送时间戳
（2）1号接收别人请求资源的消息且自己不需要访问资源，就都回了个OK，
（3）2号因为访问资源的时间戳比0号小，所以就给0号发送OK，说0号节点，你先访问
（4）0号节点在都收到其他节点的OK后，就去访问资源，并且也记下了2号也是访问资源的，所以在访问完资源后，就对2号发送OK，叫2号节点去访问资源
令牌环算法
一旦令牌丢失就over了。适合重载网络。
选举算法
如何把进程选出来做协调者：
每个进程都有关联到优先级（权重）。选举具有最高优先级的进程作为协调者。
如何找到优先级最高的进程：
- 任何进程都可以通过向所有其他进程发送选举消息来启动选举。
- 如果进程Pheavy接收到来自进程Plight的选举消息，则Ph发送淘汰消息给Pl，Pl出局
- 若一个进程没有接收到淘汰消息，则获胜，并向所有进程发送胜利消息。
环形选举是将进程组织到逻辑环中获得进程优先级。
发现的进程发起选举消息，带自己的序号传到后继者，后继者崩溃则跳过，一直到选举出新的最大进程号，再传播一圈，告诉大家新的协调者是谁。
分布式系统死锁检测是重点。资源分配图是否有环判断死锁。
一致性和复制
进行数据复制主要出于两个目的：可靠性和性能。
数据一旦被复制，就会带来一致性的问题。一旦产生更新，则其副本也需要更新。
复制带来的问题
更新副本
拓展性和管理开销是冲突的
主要问题
为了保持副本的一致性，我们通常需要确保所有冲突操作（写操作）在任何地方都以相同的顺序完成。
冲突操作
对数据的操作
Wi(x)a——进程Pi对数据项x的写入，其值为a
Ri(x)b——进程Pi从数据项x读取返回b
以数据为中心的一致性模型
严格一致性(Strict Consistency)
对于数据项x的任何读操作将返回最近一次对x进行写操作的结果所对应的值。严格一致性是限制性最强的模型，但是在分布式系统中实现这种模型代价太大，所以在实际系统中运用有限。
顺序一致性(Sequential Consisitency)
一般要求底层实现全序多播。
- 任何执行结果都是相同的，就好像所有进程对数据存储的读、写操作是按某种序列顺序执行的，并且每个进程的操作按照程序所制定的顺序出现在这个序列中。
- 也就是说，任何读、写操作的交叉都是可接受的，但是所有进程都看到相同的操作交叉。（所有进程的读写操作都是顺序性发生的。）
图一符合顺序一致性，图二不符合！若图一最后读到的都是b则符合严格一致性。
顺序一致性重要的是所有进程看到的是一样的修改顺序
因果一致性(Causal Consistency)
所有进程必须以相同的顺序看到具有潜在因果关系的写操作。不同机器上的进程可以以不同的顺序看到并发的写操作（只有同一进程内部或有因果关系的两个进程的读写才需要相同顺序）。
假设P1和P2是有因果关系的两个进程，例如P2的写操作信赖于P1的写操作，那么P1和P2对x的修改顺序，在P3和P4看来一定是一样的。但如果P1和P2没有关系，那么P1和P2对x的修改顺序，在P3和P4看来可以是不一样的。（有因果关系则必须顺序，无因果则可并发）
因为P1P2无因果关系，所以其对x的修改顺序在P3P4看来可以不一样。若是顺序一致，则所有操作需一致。
P1操作后P2读取，说明存在因果一致性，则P1和P2对x的修改顺序，在P3和P4看来一定是一样的。先a后b。
FIFO一致性
在因果一致性模型上的进一步弱化，要求由某一个使用者完成的写操作可以被其他所有的使用者按照顺序的感知到，而从不同使用者中来的写操作则无需保证顺序，就像一个一个的管道一样。 相对来说比较容易实现。
弱一致性(Weak consistency)
要求对共享数据结构的访问保证顺序一致性。对于同步变量的操作具有顺序一致性，是全局可见的，且只有当没有写操作等待处理时才可进行，以保证对于临界区域的访问顺序进行。在同步时点(某个时刻多个进程S)**，所有使用者可以看到相同的数据。
事务一致性(Entry consistency)
释放一致性
弱一致性无法区分使用者是要进入临界区还是要出临界区， 释放一致性使用两个不同的操作语句进行了区分。需要写入时使用者acquire该对象，写完后release，acquire-release之间形成了一个临界区，提供释放一致性也就意味着当release操作发生后，所有使用者应该可以看到该操作。
入口一致性
入口一致性要求每个普通的共享数据项都要与某种同步变量(Sync var)关联。
每个同步变量保护一个相关数据
数据存储满足下列条件，那么它符合入口一致性：
- 在一个进程获取一个同步变量前，所有由此同步变量保护的共享数据的更新都必须已经由相应进程执行完毕。
- 在一个进程对一个同步变量的独占访问被允许前，其他进程不可以拥有这个同步变量，也不能以非独占方式拥有这个同步变量。
- 一个进程对一个同步变量执行独占访问之后，对该同步变量的所有者进行检查之前，任何其他的进程都不能执行下一个独占访问。
以客户为中心的一致性模型（Client-Centric）
目标
告诉我们如何通过专注于特定客户端需要的内容，而不是服务器应该维护的内容，来避免系统范围内的一致性。
最终一致性（适合一次写多次读的情况）
最终一致性指的是在一段时间内没有数据更新操作的话，那么所有的副本将逐渐成为一致的。
术语：
Xi[t]——t时刻本地副本Li中数据项x的版本
WS(xi[t])——对Li中的x进行一系列写操作得到Xi[t]，WS(xi[t])表示这一系列写操作的集合
WS(xi[t1],xj[t2])——t2时刻，WS(xi[t1])中的操作也已经在本地副本Li上执行完毕，表示更新传播了，记为WS(xi[t1],xj[t2])
单调读
如果一个进程读取数据项x的值，那么该进程对x执行的任何后续读操作将总是得到第一次读取的那个值或更新的值 。（不会出现回退的情况，要不就一样，要不就读到更新的值，不可能读到以前的值）
不同副本的x值应该要不更新要不一样。
单调写
一个进程对数据x执行的写操作必须在该进程对x执行任何后续写操作之前完成。（不是并发的，同一个进程对同一个数据的操作一定是顺序的）
L2对x进行写之前，把L1的结果更新过来了
写后读
任何读操作发生之前，应该完成全部写操作。
所以读操作之前要把副本值更新
读后写
要求同一个进程，对数据项x执行的读操作之后的写操作，要发生在x读相同或更新的值上
还是要求副本在写之前更新好
无论是单调读单调写，还是读写一致写读一致，都是先在一个地方发生写操作，如果以后其他副本发生了其他操作，而先前的写操作没有传播过来，就是不一致的，传播过来就一致。
容错性
系统容错的一些要求
可用性（availability）
可靠性（reliability）
指系统无故障的连续运行。与可用性相反，可靠性是根据时间间隔而不是任何时刻来进行定义的。如果系统在每小时中崩溃1ms，那么他的可用性就超过99.9999%，但是它还是高度不可靠的。与之相反，如果一个系统从来不崩溃，但是要在每年8月中停机两个星期，那么它是高度可靠的，但是它的可用性只有98%。因此，这两种属性并不相同。
安全性（safety）
可维护性（maintainability）
一些错误的定义
failure
error
一个系统在正常工作时会在若干种运行状态之间变迁，一旦出现异常，则该系统进入错误(error)状态。一个系统的错误状态可能是导致系统失灵的原因。但有的错误状态并不一定导致系统失灵，如系统死锁是一种错误状态，当死锁被排除后，系统又可以恢复正常运行。所以，失灵一定因为error但error不一定导致失灵。
fault
造成error的原因是fault，故障的种类繁多，软件和硬件都可能产生故障,而且,某些场合下，与系统无关的外部环境也可能引发故障。
故障分类
故障通常被分为暂时的（transient）、间歇的（intermittent）和持久的（permanent）。
不同类型的故障：
崩溃故障不是最严重的，随意性故障才是最严重的！
随意性故障就是拜占庭故障：组件（错误的节点）可能会产生任意输出并遭受任意定时故障。
使用冗余(Redundancy)掩盖故障以获得容错能力（Fault Tolerance）
容错的系统会对其他进程隐藏故障的发生。关键技术是使用冗余来掩盖故障。有三种可能：信息冗余、时间冗余和物理冗余。
信息冗余
时间冗余
物理冗余（如HDFS数据复制三份）
通过添加额外的装备或进程使系统作为一个整体来容忍部分组件的失效或故障成为可能。物理冗余可以在硬件上也可以在软件上进行。
一种著名的设计是TMR（三倍模块冗余，Tiple Modular Redundancy）。在包括TMR的系统中，每个关键模块中的部件都被复制了三份，采用多数表决的方法，确保当某些模块中的单个部件发生故障时，系统还可以正确的运行。
进程恢复
为防止进程失败，采用进程组的方式（多个进程做同一件事）。当消息发送到组时，组中所有成员都接收它，一个进程失败，其他进程可以接管它。
进程组是动态的，分为平等组和简单等级组。
平等组通信
对称的，没有单独的失败点，所有组成员会立即进行信息交换。P2P形式，无服务器，完全分布式，但做出决定比较复杂。增加了延迟和开销。
简单等级组
协调者的故障会使整个组崩溃，可以独自做出决定，不需要其他进程参加。进行的通信并不具有真正的容错和可伸缩性，但容易实现。
故障掩盖和复制
如果系统能够经受k个组件的故障并且还能满足规范的要求，就称k容错。
集中式的系统
k个组件故障，至少需要k+1个正确的组件进行多数表决，才能获得正确的结果，总2k+1。
分布式的系统
k个组件故障，至少需要2k+1个正确的组件进行多数表决，才能获得正确的结果，总3k+1。
签名的系统只需要k+1个组件。
拜占庭将军的错误有几个？
- 输出任意值
- 不知道自己叛变了
- 坏节点恶意协同
如果进程发生拜占庭失败，继续错误运行并发送出错误或随机的应答，那么至少需要2k+1个进程才能获得k容错。
拜占庭协定的目标是一致性意见只与无故障进程的值有关。
在一个含有k个有故障进程的系统中，只有有2k+1个无故障进程时才可以达到协定，即总进程为3k+1个。只有无故障进程数多于三分之二时才可以达成协定。**
GFS
将文件分为若干块(Chunk)存储
通过单个master来协调数据访问、元数据存储
- 结构简单，容易保持元数据一致性
单一Master问题
- 单点故障
-
单点故障问题
采用多个影子Master节点进行热备份，一旦主节点损坏，立刻选举新的主节点
真实数据放在Chunk Server上，metadata放在Master节点。用户访问时访问的是metadata（类似索引）。
Master节点的作用：
存储元数据（保证元数据的一致性）
- 文件系统目录管理和加锁
- 与Chunk Server进行周期性通信
- 数据块创建、复制及负载均衡（单个节点协调负载）
- 垃圾回收
-
GFS架构的特点
采用中心服务器模式（ChunkServer管理方便，负载均衡，元数据一致性）
不缓存数据（没必要，更简单）
在用户态实现（更简单，有利于开发，用户态的GFS不会影响ChunkServer的稳定性）
提供专用的访问接口（降低实现复杂度）GFS的容错方法
Chunk Server容错
每个Chunk有多个存储副本（通常是3个），分别存储于不同服务器
每个Chunk划分为多个Block，Block有校验码确保正确，若错误则转移至其他Chunk副本
Master容错（影子节点热备份）
三类元数据：命名空间、Chunk与文件名的映射（写日志提供容错）以及Chunk副本位置信息
- 前两类通过日志容错，后存储在Chunk Server通过Chunk Server恢复。
MapReduce
MapReduce是一种抽象模型，使我们只需执行简单计算，而将并行化、容错、数据分布、负载均衡等杂乱细节放在一个库里，使并行编程时不必关心它们。一个软件架构，是一种处理海量数据的并行编程模式。用于大规模数据集的并行运算。MapReduce的作用
对BigTable中的数据进行并行计算处理，使用BigTable或GFS存储计算结果。
MapReduce实现了Map和Reduce两个功能：
- Map（映射）把一个函数应用于集合中的所有成员，然后返回一个基于这个处理的结果集。
- Reduce（规约）对结果集进行分类和归纳。在数据被分割后通过Map函数的程序将数据映射成不同的区块，分配给计算机机群处理达到分布式运算的效果，在通过Reduce 函数的程序将结果汇整，从而输出开发者需要的结果。
MapReduce借鉴了函数式程序设计语言的设计思想，其软件实现是指定一个Map函数，把键值对(key/value)映射成新的键值对(key/value)，形成一系列中间结果形式的key/value 对，然后把它们传给Reduce(规约)函数，把具有相同中间形式key的value合并在一起。
文件存储位置：
源文件：GFS **Map处理结果：本地存储
Reduce处理结果：GFS 日志：GFS**
MapReduce的容错
Worker故障：
- Master 周期性的ping每个worker。如果master在一个确定的时间段内没有收到worker返回的信息，那么它将把这个worker标记成失效。（失效节点上的Map和Reduce需要重新执行）
- 重新执行该节点上已经执行或尚未执行的Map任务（Map任务未完成的不执行）
- 重新执行该节点上未完成的Reduce任务，已完成的不再执行
Master故障：
- 定期写入检查点数据
-
MapReduce的优化
任务备份机制
慢的workers严重拖延整个执行完成时间——在临近结束时启动多个进程来执行尚未完成的任务，谁先完成算谁的
本地处理
向GFS询问获得输入文件blocks副本的位置信息，按照所在位置进行调度，绝大部分机器从本地读取文件作为输入，极大节省带宽。
跳过有问题的记录
在worker里运行信号处理程序，捕获map或reduce任务崩溃时发出的信号，若有一条记录有两次崩溃信息，则对该记录进行标记，下次运行时，跳过该记录。
云计算
云计算的特点
超大规模
- 虚拟化
- 高可靠性
- 通用性
- 高可扩展性
- 极其廉价
- 潜在的危险性
HDFS关键运行机制——保障可靠性的措施
- 一个名字节点（NameNode）和多个数据节点（DataNode）——数据复制（冗余机制）
- 存放的位置（机架感知策略）——故障检测
- 数据节点——心跳包（检查是否宕机）——块报告（安全模式下检测）数据完整性检测（校验和比较）
- 名字节点（日志文件，镜像文件）——空间回收机制
HDFS关键运行机制—读文件流程
客户端缓存、流水线复制、并发写控制
客户端联系NameNode,得到所有数据块信息，以及数据块对应的所有数据服务器的位置信息，尝试从某个数据块对应的一组数据服务器中选出一个，进行连接（选取算法未加入相对位置的考虑），数据被一个包一个包发送回客户端，等到整个数据块的数据都被读取完了，就会断开此链接，尝试连接下一个数据块对应的数据服务器，整个流程，依次如此反复，直到所有想读的都读取完了为止
（一个数据块对应一组数据服务器，每读一个数据块选一个数据服务器进行连接，读后释放连接，开始下一个数据块的读取）
HDFS与GFS比较
①中心服务器模式的差异：
GFS：多台物理服务器，选择一台对外服务，损坏时可选择另外一台提供服务；
HDFS：单一中心服务器模式，存在单点故障。
②子服务器管理模式差异：
GFS：Chunk Server在Chubby中获取独占锁表示其生存状态，Master通过轮询这些独占锁获知Chunk Server的生存状态；
HDFS：DataNode通过心跳的方式告知NameNode其生存状态；
GFS中，Master损坏时，替补服务器可以快速获知Chunk Server的状态；
HDFS中，NameNode损坏后，NameNode恢复时需要花费一段时间获知DataNode的状态；
在添加数据存储节点时，GFS的伸缩性较HDFS要好
③安全模式的差异
HDFS具备安全模式：获知数据块副本状态，若副本不足，则拷贝副本至安全数目；
GFS不具备安全模式
④HDFS具备空间回收机制，GFS无
Google的云计算应用均依赖于四个基础组件
1）分布式文件存储 GFS
2）并行数据处理模型 MapReduce
3）分布式锁Chubby
4）结构化数据表BigTable
Chubby的作用
- 为GFS提供锁服务，选择Master节点；
- 记录Master的相关描述信息；
- 通过独占锁记录Chunk Server的活跃情况
- 为BigTable提供锁服务，记录子表元信息
- 记录MapReduce的任务信息
-
GFS的作用
存储BigTable的子表文件
-
MapReduce的作用
对BigTable中的数据进行并行计算处理
- 使用BigTable或GFS存储计算结果。
虚拟化的概念
虚拟化是表示计算机资源的抽象方法，通过虚拟化可以用与访问抽象前资源一致的方法来访问抽象后的资源。这种资源的抽象方法并不受实现地理位置或底层资源的物理配置限制。
虚拟化与云计算的关系
虚拟化技术以及各种计算机科学概念，虚拟化的发展和商业实现打开了云计算的大门，而云计算本质上说应该就是虚拟化服务。从虚拟化和云计算的过程，我们实现了跨系统的资源调度，将大量的计算机资源组成资源池，用于动态地创建高度虚拟化的资源提供给用户，从而最终实现应用、数据、IT 资源以服务的方式通过网络提供给客户。可以说云计算是虚拟化的最高境界，虚拟化是云计算的底层结构。
若有收获，就点个赞吧
0 人点赞
