4.并行系统

4.1 并行数据库的动机

万维网发展创造了许多网站，浏览器收集到的数据越来越多，过去的集中式数据库系统已经不足以处理此类应用。

4.2 并行系统的性能度量

数据库系统的衡量指标主要是两个：

吞吐量。

响应时间。

对应地，并行研究的两个重要问题是：加速比(更短时间运行一个任务)和扩展比(并行运行更多的任务数)。

如下图，为执行一个大型任务扩展cpu、磁盘等资源，假如资源增长N倍。其并行性也增长N倍，则称为线性加速比，否则称为亚线性加速比。

同样地，如果给定N倍的任务规模，扩大N倍的资源，其执行任务时间不变，则称为线性扩展比，否则为亚线性扩展比。

根据对问题规模的度量方式不同，并行系统的扩展比分为两种：

批量型扩展比。数据库的任务是运行时间依赖于数据库规模的大型作业。比如扫描与数据库规模成比例的关系。

对事务型扩展比，数据库的事务提交率增加，并且数据库规模的增长与事务率称正比。这类扩展比适用于的事务是小更新类的事务处理系统，比如银行的存款和取款。

下面这些因素影响并行操作的效率，并且可能同时降低加速比与扩展比。

串行计算，有些任务必须要串行执行。

干扰，并行系统中进程经常访问共享资源，因此当它们竞争共同持有资源时(如系统总线、共享磁盘、甚至锁)，会使速度降低。

倾斜。将单项任务分解为多个并行步骤来减少平均步骤的规则，很难分成均等部分，运行速度会取决于最慢的步骤的服务时间。

启动代价，进程初始化需要相对应的启动代价。

4.3 互连网络

并行系统包括一套组件(处理器、存储器和磁盘)，这些组件通过互连网络(interconnenction network)进行通信，下图显示了常见的互连网络类型。

总线。如图a，所有组件通过一根通信总线来收发数据。早期把它用于多个节点的互连，但总线在同一时间只能够处理一个组件的通信，这太不利于扩展了，现在甚至单个节点都采用环或网格互连机制了，因此总线方式不太主流了。

环。组件按环状互连。这样彼此之间可以并发通信，但是可能一个消息需要通过n/2个链接，而且节点越多，传输延迟越大。

网格。组件通过网格互联，图c是二维网格，一个组件最多与四个组件相连，对三维网格来说，一个组件最多与六个组件相连。网格互连用于将处理器中的多个核或单台服务器中的多个处理器相互连接。早期网格互连还用于节点互连，但是由于其节点越多，传输消息的链接也越多，现在网格也不用与节点互连了。

超立方体。每个组件采用二进制编码，如果节点的二进制编码差一位，则互连。因此，n个组件采用超立方体连接，每个组件将与log(n)个节点互连。超立方体的通信延迟显著低于立方体的通信延迟。

树形拓扑。组件之间按照树形拓扑互连。图中e是三层树形拓扑(tree-like topolopy)结构。

基本的树形拓扑是，同一机架的数十台机器通过机架顶部交换机互连，机架顶部交换机与聚合交换机相连接，以便多组机架之间可以进行互连，聚合交换机依次连接到核心交换机。这被称为三层树拓扑(tree topolopy）。

组织机构的内部的局域网通常采用这种基本的树形结构，不过如果一个机架中的多台机器试图与来自其他机架的机器进行大量数据的通信，那么机架之间的可用带宽就会不够。

为了避免树形结构的带宽瓶颈，数据中心通常将每个机架顶部(边缘)交换机连接到多个聚合交换机，每个聚合交换机依次链接下一层的多台核心交换机。这被称为树形拓扑(tree-like topolopy)，这种结构增强了带宽，并且使网络具有容错性。

三层树形拓扑可以处理具有数万台机器的集群。三层树形拓扑及其变体在现在得到了广泛的应用，数据中心中复杂的互连网络被称为数据中心网络。

网络性能特别关键，网络性能的一个关键是用于单个链路的网络技术，流行的有：

以太网。当前网络连接的主流技术是以太网技术，主要是1GB以太网和10GB以太网。

光纤通道。光纤通道协议标准被设计用于存储系统和计算机之间的高速互连。

无限带宽。无限带宽标准为与数据中心的互连而设计，是专门为需要高带宽低延迟的高性能计算应用而设计的。

什么是以太网技术？

以太网技术提供的规则允许网络连接的设备相互通信，而无需相互通信。在口头对话中，当两个人同时说话时，每个人都可能难以理解对方在说什么。例如，当 10 个人同时说话时，这种情况就会被放大。想象一下一次 100 或 1000 个。

数据网络也是如此。如果共享网络上的两个或多个连接的设备尝试同时传输数据包，则会发生数据包冲突。构成数据包的电脉冲或光子在通过共享铜缆或光缆同时发送时重叠。

以太网旨在解决数据包冲突问题。它为网络设备提供了一套规则，基本上是说：“在你说话之前，确保没有其他人在说话。如果你在说话时听到有人说话，停下来，听，等谈话结束再说话。

关于无限带宽技术可以参考：Infiniband技术简介

一种用于降低延迟的重要技术是允许应用程序绕过操作系统直接与硬件接口，来收发消息。这会大大减少通信延迟。还可以采用远程直接内存访问(Remote Direct Memory Acess,RDMA)，一种允许一个节点的进程直接读取另一个节点的内存的技术减少延迟。

4.4 并行数据库体系结构

并行数据库有若干种体系结构模型，其中下图是最重要的几种，其中M表示内存，P表示处理器，圆柱体表示磁盘。

共享内存。所有处理器共享一个公共的内存

共享磁盘。一组节点共享一组公共的磁盘，每个节点都有单独的处理器和内存，共享磁盘系统有时候又被称作集群。

无共享。一组节点既不共享公共的内存，也不共享磁盘。

层次。这种模型是前三种的混合，是当前使用最广泛的模型。

4.5 共享内存

在共享内存体系结构中，处理器可以访问公共内存，这使得进程间通信变得特别高效，因为只需要把内容写到共享内存其他进程就可以“看到”。磁盘也被共享。

多核处理器现在迅猛发展，一个芯片上可以有若干个处理器，为了与传统意义上的处理器区分开，我们将片上处理器称为核。低成本多核处理器使得共享内存的并行处理越来越重要。

4.5.1 共享内存体系结构

早期的共享内存体系结构通过总线将处理器和内存互连。

这样无疑会造成扩展上的瓶颈。现代内存共享结构每个处理器都有本地连接的内存，并且可以访问其他处理器关联的内存。由于访问本地内存和其它处理器内存的速度差异，被称为非统一内存体系结构(Non-Uniform Memory Architecture,NUMA)。

由于共享内存体系需要在核与核之间和处理器之间互连，其规模限制为最多几百个核。

由于高速缓存比主存快的多，因此共享内存体系也加入了高速缓存，如果需要对不在高速缓存中的数据项访问，需要从主存提取，称为高速缓存未命中(cache miss).

许多处理器体系结构支持超线程(hyper-threading),或称为硬件线程(hardware threading)的功能，其中单个物理核可以划分为多个逻辑核，当一个逻辑核缓存未命中时，同一物理核的其他逻辑核可以开始工作，不至于等待从主存中提取数据而陷入空闲状态。

典型的多核处理器具有多级缓存，其中L1最快，但也最小，其他级别同理。L1，L2为核的本地缓存，L3被多核共享。数据以高速缓存行(cache line，通常为64个连续字节)为单位读写到高速缓存。

4.5.2 高速缓存一致性

只要存在多个核或者多处理器，每个核拥有自己的本地高速缓存，就可能出现高速缓存不一致(cache coherency)的问题。比如core0的本地缓存更新，但是core2中维护的还是同一内存地址的旧值。因此，当内存位置发生更新时，要确保该内存位置的副本都失效。

许多处理器体系结构中，内存失效从传输到执行会存在延迟，可能导致从一个处理器写入，但是在另一个处理器中读时无法读到更新。

这会导致问题，现代处理器支持内存屏障(memory barrier)指令,它确保了屏障之前的加载/存储操作与屏障之后的加载/存储操作之间的特定顺序。用通俗的话解释就是，它可以保证在之前的高速缓存失效前，让处理器等一等，直到确保接收到的作废消息已经被应用。

值得高兴的是，写程序是不需要包含任何额外的代码来处理高速缓存的一致性，只需要在访问数据之前获取锁，在访问数据之后释放锁即可。因为锁的获取与释放过程中就包括了所需的内存屏障指令。各种语言支持的同步原语也在内部执行内存屏障指令。

许多处理器体系还支持硬件级别的共享锁和排他锁来确保高速缓存的一致性，这比软件更高效，其中MESI协议是一种广泛使用的协议。缓存一致性协议通过监控独立的loads和stores指令来监控缓存同步冲突，并确保不同的处理器对于共享内存的状态有一致性的看法。当一个处理器loads或stores一个内存地址a时，它会在bus总线上广播该请求，其他的处理器和主内存都会监听总线（也称为snooping）。

MESI原理可以参考：缓存一致性协议(MESI)——缓存加锁协议

原则上，可以确保基于这种锁的高速缓存一致性协议具有"强"的高速缓存一致性，从而使得内存屏障指令冗余，然而，许多实现包含一些加速处理的优化，例如允许延迟传递无效的消息，但代价是不保证高速缓存的一致性，因此许多处理器体系结构需要内存屏障指令来确保高速缓存的一致性。

4.6 共享磁盘

共享磁盘系统模型中，一组节点共享一组公共的磁盘，每个节点都有单独的处理器和内存。这种体系结构有两个优点。共享磁盘系统可以扩展比共享内存系统更多的处理器。其次，它提供了一种经济的容错(fault ):如果一个节点发生故障，其他节点可以接管这个节点的任务，因为数据库驻留在所有节点都可以访问的磁盘上。

我们可以使用RAID来使磁盘子系统本身具有容错性，即使单个磁盘发生故障，系统也可以正常工作；RAID还提供了一定程度的并行性。

存储区域网SAN是一种高速局域网，可以将多个物理上磁盘阵列抽象称一个逻辑磁盘，隐藏物理磁盘的复杂细节。逻辑磁盘还可以随时扩展物理磁盘，处理节点可以像访问本地磁盘一样访问磁盘。

存储区域网通常具有冗余，例如节点之间有多条路径，因此诸如链接或到网络的连接这样的组件故障，网络还可以继续工作。

存储区域网非常适合构建共享磁盘系统。适用于对并发要求低但是对可靠性要求高的应用。

与共享内存系统相比，共享磁盘系统可以扩展更多的处理器，但是其网络通信较慢。

共享磁盘系统到网络连接的带宽小于本地存储器的可用带宽，因此存储器的访问可能成为瓶颈，限制了可扩展性。

4.7 无共享

无共享系统。一组节点既不共享公共的内存，也不共享磁盘。节点之间通过高速互连的网络进行通信。由于无共享模型的磁盘访问由本地磁盘提供，克服了所有I/O通过单个互连网络的缺点。

此外，无共享系统的互连网络(如树形互连网络)，通常被设计成为可扩展的，因此其传输容量会随着节点的增加而增加，因此，无共享网络更具有可扩展性，并可以轻松支持大量的节点。

无共享系统的主要缺点是本地磁盘和通信的成本更高、由于具有很高的扩展性，无共享体系结构被广泛用于处理非常大的数据量，支持对数千个节点或者极端情况下甚至数万个节点的可扩展性。

4.8 层次

层次模型是前三种的混合，是当前使用最广泛的模型。在顶层，系统由通过互连网络的无共享节点组成，因此其顶层是无共享体系结构。每个节点实际上是一个共享内存结构。或者可以是三层结构，顶层是无共享结构，底层是共享内存结构，中间还有一层是共享磁盘的体系结构。

当今的并行数据库系统通常运行在层次体系结构上，其中每个节点都支持共享内存的并行性，多个节点以无共享方式互连。

5.分布式系统

在分布式数据库系统中，数据存储在节点中，节点分布在地理上分散的站点上，它们不共享内存和磁盘，其结构如下。

无共享的并行数据库和分布式数据库的主要区别如下。

分布式数据库具有在地理位置上分散的站点，因此分布式的网络连接具有更低的带宽，更高的延迟和更大的故障概率。

并行数据库无法保证诸如自然灾害等导致数据中心故障时的系统可用性，但分布式可用。

分布式数据库可以单独管理，每个站点具有一定的自主权。许多分布式数据库其实是通过集成多个数据库构建的，这样可以允许查询和事务跨数据库边界。不过为了跨地理站点而构建的分布式数据库可能是集中式管理的。

分布式数据库中的节点往往在规模和功能上差异更大。

分布式数据库区分局部事务和全局事务，局部事务是仅从启动事务的节点访问数据的事务，全局事务要么从启动节点外的单个节点访问数据，要么则跨多个节点访问数据。

如今的web级应用运行在数据管理系统上，结合了并行性和分布式的支持，并行性保证高负载的支持，分布式则保证高可用。这种系统的一个特点是集中式管理。

相反，通过集成现有数据库系统构建的分布式数据库具有一些不同的特性。

共享数据。比如一个校园中的用户可以访问另外一个校园中的数据。

自治。

在同构分布式数据库系统中，节点共享一个通用的全局模式，所有节点都运行同一个分布式数据库管理软件，并且节点在处理事务和查询时积极合作。相反地，将多个已经存在的数据库系统链接在一起构成分布式数据库，每个数据库系统都有自己的模式，自己的数据库管理系统，称为联邦数据库系统或异构分布式数据库系统

分布式数据库的节点通过广域网进行通信，带宽昂贵且低速。网络故障可能会导致节点无法通信，即网络分区，影响系统的可用性。

6.并行和分布式系统中的事务处理

事务的原子性是构建并行和分布式数据库系统时的一个重要问题。如果事务跨两个节点，可能出现一个节点上提交事务，另一个节点上弃用事务的不一致情行。事务提交协议用来避免这样的情况，其中2PC(two-Phase commit Protocol)是最广泛的协议。

2PC协议的核心思想是，每个节点执行事务，直到事务进入部分提交状态，此时选择一个节点作为决策节点，该节点进入ready状态，当所有节点都ready以后，同一执行事务的提交，如果有节点出现故障，则决策节点同一执行中止或者恢复提交策略。

并发控制是并行和分布式系统的另一个关键问题，多个节点的事务管理器可能需要跨节点合作，如果使用封锁，可以在包含被访问数据项的本地执行封锁，但是涉及原子多个节点的事务也可能出现死锁。因此，死锁检测需要跨多个节点进行。

分布式的故障更常见，因为除了计算机故障，网络还可能故障。数据项的复制是分布式数据库在发生故障时运行的关键。这会使得并发控制进一步复杂化。

当要执行的任务很复杂，涉及到多个数据库和与人的多次交互时，可以使用工作流管理系统。

7.基于云的服务

对很多企业来说，自己管理服务器很贵而且很麻烦，因此近几年云计算变得很流行了，直接从云服务上购买云服务，包括硬件，甚至包括诸如数据库等软件。

7.1 云服务模型

利用云计算的方式有几种，下图是一个基础设施即服务的模型。

基础设施即服务模型

平台即服务模型

软件即服务模型