数据库扩展性问题

Posted on
Words count in article: 5.2k | Reading time ≈ 18

数据库扩展性问题

NoSQL

NoSQL数据库有四大分类：

分类 Examples 典型应用场景 数据模型 优点 缺点
键值 key-value Riak,Redis,Voldmort 内容缓存，用于处理大量数据的高访问负载，也用于一些日志系统等 Key指向Value的键值对，通常用哈希表实现 查找速度快 数据无结构化，通常只被当做字符串或者二进制数据
列存储数据库 wide-column Cassandra,HBase 分布式的文件系统 以列簇式存储，将同一列数据存在一起 查找速度快，可扩展性强，更容易进行分布式扩展 功能相对局限
文档型数据 document MongoDB, CouchDB web应用 Key-Value对应的键值对，Value为结构化数据 数据结构要求不严格，表结构可变，不需要像关系型数据库一样，需要预先定义表结构 查询性能不高，而且缺乏统一查询语法
图形数据库 Graph Neo4J,HyperGraphDB 社交网络，推荐系统。专注于构建关系图谱 图结构 利用图结构相关算法 很多时候需要对整个图做计算才能得出需要的信息。不太好做分布式扩展

NoSQL和SQL不同的开发过程

  • 传统的SQL数据库设计流程

概念模型(Conceptual Model) ——> 模式(Schema) ——> 物理设计优化(Physical Design) ——> 分库分表(Sharding)

  • NoSQL的数据库设计流程

应用功能 (App Operation) ——> 模式(Schema) ——> 横向扩展(Scaling)

NOSQL的优势

  • 易扩展
    NoSQL数据库种类繁多，但是一个共同的特点都是去掉关系数据库的关系型特性。数据之间无关系，这样就非常容易扩展。也无形之间，在架构的层面上带来了可扩展的能力。

  • 大数据量，高性能
    NoSQL数据库都具有非常高的读写性能，尤其在大数据量下，同样表现优秀。这得益于它的无关系性，数据库的结构简单。一般MySQL使用Query Cache，每次表的更新Cache就失效，是一种大粒度的Cache，在针对web2.0的交互频繁的应用，Cache性能不高。而NoSQL的Cache是记录级的，是一种细粒度的Cache，所以NoSQL在这个层面上来说就要性能高很多了。

  • 灵活的数据模型
    NoSQL无需事先为要存储的数据建立字段，随时可以存储自定义的数据格式。而在关系数据库里，增删字段是一件非常麻烦的事情。如果是非常大数据量的表，增加字段简直就是一个噩梦。

  • 高可用
    NoSQL在不太影响性能的情况，就可以方便的实现高可用的架构。比如Cassandra，HBase模型，通过复制模型也能实现高可用。

SQL 的劣势

  • 大数据场景下I/O较高

    因为数据是按行存储，即使只针对其中某一列进行运算，关系型数据库也会将整行数据从存储设备中读入内存，导致I/O较高

  • 存储的是行记录，无法存储数据结构

  • 表结构schema扩展不方便
    如要需要修改表结构，需要执行执行DDL(data definition language)，语句修改，修改期间会导致锁表，部分服务不可用

  • 全文搜索功能较弱
    关系型数据库下只能够进行子字符串的匹配查询，当表的数据逐渐变大的时候，like查询的匹配会非常慢，即使在有索引的情况下。况且关系型数据库也不应该对文本字段进行索引

  • 存储和处理复杂关系型数据功能较弱
    许多应用程序需要了解和导航高度连接数据之间的关系，才能启用社交应用程序、推荐引擎、欺诈检测、知识图谱、生命科学和 IT/网络等用例。然而传统的关系数据库并不善于处理数据点之间的关系。它们的表格数据模型和严格的模式使它们很难添加新的或不同种类的关联信息。

CAP

CAP理论非常重要，在分布式数据库的设计中起了很关键的理论支持(包括区块链)。我们先对CAP进行定义：

  • C（一致性 Consistency）：所有节点访问同一份最新的数据副本。(副本既可以是备份数据，也可以是冗余数据，比如索引)
  • A（可用性 Availability）：每次请求都能获取到非错的响应——但是不保证获取的数据是否为最新的数据
  • P（分区容错 Partitioning Tolerance）：通信故障的时候，系统的任意节点都可以正常工作。(以实际效果而言，分区就相当于对通信的时限要求，系统如果不能在时限内达成数据一致性，就意味着发生了分区的情况，必须就当前操作在C和A之间做出选择)

任何一个分布式数据库只能在C、A和P三者中兼顾两个

一致性

这里指的是强一致性，而最终一致性后续讨论
在写操作完成后开始的任何读操作都必须返回该值，或者后续写操作的结果
也就是说，在一致性系统中，一旦客户端将值写入任何一台服务器并获得响应，那么之后client从其他任何服务器读取的都是刚写入的数据

用如下系统进行解释

  1. 客户端向G1写入数据v1，并等待响应
  2. 此时，G1服务器的数据为v1，而G2服务器的数据为v0，两者不一致
  3. 接着，在返回响应给客户端之前，G2服务器会自动同步G1服务器的数据，使得G2服务器的数据也是v1
  4. 一致性保证了不管向哪台服务器（比如这边向G1）写入数据，其他的服务器（G2）能实时同步数据
  5. G2已经同步了G1的数据，会告诉G1，我已经同步了
  6. G1接收了所有同步服务器的已同步的报告，才将“写入成功”信息响应给client
  7. client再发起请求，读取G2的数据
  8. 此时得到的响应是v1，即使client从未写入数据到G2

可用性

系统中非故障节点收到的每个请求都必须有响应
在可用系统中，如果我们的客户端向服务器发送请求，并且服务器未崩溃，则服务器必须最终响应客户端，不允许服务器忽略客户的请求

分区容错性

允许网络丢失从一个节点发送到另一个节点的任意多条消息，即不同步
也就是说，G1和G2发送给对方的任何消息都是可以放弃的，也就是说G1和G2可能因为各种意外情况，导致无法成功进行同步，分布式系统要能容忍这种情况。

CAP三者不可能同时满足

假设确实存在三者能同时满足的系统

  • 那么我们要做的第一件事就是分区我们的系统，由于满足分区容错性，也就是说可能因为通信不佳等情况，G1和G2之间是没有同步

  • 接下来，我们的客户端将v1写入G1，但G1和G2之间是不同步的，所以如下G1是v1数据，G2是v0数据。

  • 由于要满足可用性，即一定要返回数据，所以G1必须在数据没有同步给G2的前提下返回数据给client，如下

  • 接下去，client请求的是G2服务器，由于G2服务器的数据是v0，所以client得到的数据是v0

很明显，G1返回的是v1数据，G2返回的是v0数据，两者不一致。
其余情况也有类似推导，也就是说CAP三者不能同时出现。

CAP三者如何权衡

三选二利弊如何

  • CA (Consistency + Availability)：关注一致性和可用性，它需要非常严格的全体一致的协议，比如“两阶段提交”（2PC）。CA 系统不能容忍网络错误或节点错误，一旦出现这样的问题，整个系统就会拒绝写请求，因为它并不知道对面的那个结点是否挂掉了，还是只是网络问题。唯一安全的做法就是把自己变成只读的。
    • 注意：redis 和 MongoDB 均满足CP原则。
  • CP (consistency + partition tolerance)：关注一致性和分区容忍性。它关注的是系统里大多数人的一致性协议，比如：Paxos 算法 (Quorum 类的算法)。这样的系统只需要保证大多数结点数据一致，而少数的结点会在没有同步到最新版本的数据时变成不可用的状态。这样能够提供一部分的可用性。
  • AP (availability + partition tolerance)：这样的系统关心可用性和分区容忍性。因此，这样的系统不能达成一致性，需要给出数据冲突，给出数据冲突就需要维护数据版本。Dynamo 就是这样的系统。

如何进行三选二

权衡三者的关键点取决于业务
放弃了一致性，满足分区容错，那么节点之间就有可能失去联系，为了高可用，每个节点只能用本地数据提供服务，而这样会容易导致全局数据不一致性。对于互联网应用来说（如新浪，网易），机器数量庞大，节点分散，网络故障再正常不过了，那么此时就是保障AP，放弃C的场景，而从实际中理解，像门户网站这种偶尔没有一致性是能接受的，但不能访问问题就非常大了。

对于银行来说，就是必须保证强一致性，也就是说C必须存在，那么就只用CA和CP两种情况。

  • 当保障强一致性和可用性（CA），那么一旦出现通信故障，系统将完全不可用。
  • 另一方面，如果保障了强一致性和分区容错（CP），那么就具备了部分可用性。

实际究竟应该选择什么，是需要通过业务场景进行权衡的（并不是所有情况都是CP好于CA，只能查看信息但不能更新信息有时候还不如直接拒绝服务）

NewSQL

newSQL 提供了与 noSQL 相同的可扩展性，而且仍基于关系模型，还保留了极其成熟的 SQL 作为查询语言，保证了ACID事务特性。

简单来讲，newSQL 就是在传统关系型数据库上集成了 noSQL 强大的可扩展性。

传统的SQL架构设计基因中是没有分布式的，而 newSQL 生于云时代，天生就是分布式架构。

newSQL 的主要特性：

  • SQL 支持，支持复杂查询和大数据分析。
  • 支持 ACID 事务，支持隔离级别。
  • 弹性伸缩，扩容缩容对于业务层完全透明。
  • 高可用，自动容灾。
SQL NoSQL NewSQL
关系模型 Yes No Yes
SQL语句 Yes No Yes
ACID Yes No Yes
水平扩展 No Yes Yes
大数据 No Yes Yes
无结构化 No Yes No

CAP再探

当在分布式系统上发生通信故障的时候(Partitioning)，由于P是必须要有的，因此只有CP和AP两种选择。

对于A，也有两种方式： Node Avalability 和 Service Availability

  • Node Availability (nA)
    • 通信故障发生时，任一节点都可用。
  • Service Availability (sA)
    • 通信故障发生时，部分节点不可用。但是，总有一部分节点可用。系统可以将用户自动切换到可用的节点。使得服务不中断。

因此，对于 CnAP来说，只能在CP和nAP中二选一，但是对于CsAP，在某种条件下，可以兼顾(使用Raft.Paxos)

Spanner数据库

Spanner 就是利用 CsAP的NewSQL数据库。Spanner最重要的设计点就是做全球数据库，要求可扩展性、多数据版本、多replica数据一致性和事务。是第一个款能实现全球数据分布而且还能实现分布式事务的数据库系统，从他的架构图来看底层也是基于Colossus(GFS二代)来存储文件，只不过上层的tablet还通过Paxos协议在做数据的replica。这点和HBase当前1.1版本引进的region高可用有点类似，但看起来又不全是。

整体架构

Spanner 是由一系列的 zone 组成, zone 是 Spanner 中的部署的单元, 一般会在某 datacenter 部署一个 zone, 但是也可以有多个 zone。数据副本就是存放在这一系列的 zone 中, zone 之间的物理距离越大, 数据的安全性越高。

universemaster：是一个控制台, 监控universe里所有zone状态信息, 用于debug；

placement driver：帮助维持特定副本数量，自动搬迁数据，实现负载均衡；

zonemaster：管理 spanserver 上的数据；

location proxy：作用不详, 可能是为 client 提供数据的位置信息, client 要先访问它来定位需要访问的 spanserver；

spanserver：对 client 提供服务, 包括读写数据。

Spanserver 架构

在Spanner中，tablet的概念和Bigtable类似，都是B-tree的存储结构，和HBase的region对等关系。只不过在Spanner中创造了目录的概念，把不同表中相同rowkey前缀的数据放入到同一个directory中。这也是之所有能在几十TB数据量情况下做到多表关联的必要条件(而并非现在传说的遵循标准关系型数据库的schema模式可以随意来设计)

同时，Spanner引入了Group概念，这个和HBase当前的Region Group类似，不同的Dir归属于不同的Group，数据以Group为单位进行逻辑上的存储。Group内数据被同一个Paxos管理起来，而不同的Group间Paxos不同。当然目录可以在Group之间来回移动，以达到负载均衡和容灾的目的。

为了实现分布式事务，除了Paxos协议和两阶段提交。还有一个非常重要的前提，就是不同客户端提交的事务时间戳需要非常精确，因为这个决定了究竟哪个事务在前，哪个事务在后。这个时间戳的概念比较容易被误读成数据时间戳。在这里Spanner定义了读写事务、只读事务、快照读。读写事务对时间精确性要求较高，也许在10ms内会同时有客户端在读写同一条数据，谁先谁后对最终结果影响很大。只读事务和快照读目前还没分太清楚，大概是指定时间戳版本的读，读当前最新还是读一个历史版本

Timestamps-Based Protocals

https://blog.csdn.net/weixin_45583158/article/details/100143234

每个事务在进入系统时都会被授予一个时间戳。如果一个旧的事务 $T_i$有时间戳 $TS(T_i)$，一个新的交易$T_j$被分配时间戳$TS(T_j)$，使$TS(T_i)<TS(T_j)$。

该协议管理并发的执行，使时间戳决定可序列化的顺序。

为了保证这种行为，协议为每个数据Q保持两个时间戳值。

  • W-timestamp(Q)是任何成功执行write(Q) 的事务的最大时间戳。
  • R-timestamp(Q)是任何成功执行read(Q) 的事务的最大时间戳。

Multiversion Schemes

Multiversion Schemes 保留数据项的旧版本，以增加并发性。

  • Multiversion Timestamp Ordering
  • Multiversion Two-Phase Locking

每一次成功的写入都会导致所写数据项的新版本的产生。

我们使用时间戳来标记版本。

当一个read(Q)操作被发出时，根据事务的时间戳选择Q的适当版本，并返回所选版本的值。

执行读取操作时不必等待，因为适当的版本会立即返回。

Multiversion Timestamp Ordering

每个数据项Q都有一连串的版本。每个版本$Q_k$包含三个数据字段。

  • Content — 版本$Q_k$的值。
  • W-timestamp($Q_k$) — 创建(写) 版本$Q_k$的事务的时间戳
  • R-timestamp($Q_k$) — 成功读取版本$Q_k$的事务的最大时间戳

当一个事务$T_i$创建了Q的新版本$Q_k$，$Q_k$的 W-timestamp和R-timestamp 被初始化为$TS(T_i)$。
每当一个事务$T_j$读取$Q_k$，并且$TS(T_j)>R-timestamp(Q_k)$时，$Q_k$的R-timestamp被更新。

假设事务$T_i$发出一个read(Q)或write(Q)操作。 让$Q_k$表示$Q$的版本，其写入时间戳是小于或等于$TS(T_i)$的最大写入时间戳。

  1. 如果事务$T_i$发出 read(Q)，那么返回的值就是版本$Q_k$的内容。
  2. 如果事务$T_i$发出一个 write(Q)
    1. 如果$TS(T_i)< R-timestamp(Q_k)$，则事务$T_i$被回滚。
    2. 如果$TS(T_i) = W-timestamp(Q_k)$，$Q_k$的内容被覆盖。
    3. 否则将创建一个新的Q版本。

请注意

  • 读取总是成功的
  • 如果其他事务$T_j$（在由时间戳值定义的序列化顺序中）应该读取$T_i$的写，但已经读取了比$T_i$更早的事务创建的版本，那么$T_i$的写就会被拒绝。
  • 协议保证可序列化

Reads in spanner

Snapshot read

Snapshot read 指的是读取过去时间的某个快照, 无需加锁。

client可以指定一个 timestamp t, 或者时间范围，Spanner 会寻找一个数据充分更新好的 replica 来提供读服务。

所谓数据充分更新好, 是指 t <= tsafe，其中 tsafe 定义如下:

前者指的已经提交的事务 timestamp, 后者指的是正在 2PC 过程中未决的事务 timestamp - 1。

如果 t > tsafe，Spanner 需要等待 replica 一段时间, 待 tsafe 推进后再进行读操作。

基于 External Consistency 特性，Spanner 可以感知操作的先后顺序, 给定一个时间戳 t, Spanner 能够明确哪些是历史数据, 并提供一致的快照。

Read-only transactions

  • Assign timestamp sread and do snapshot read at sread

  • $s_{read} = TT.now().latest() $ 保证外部一致性（线性化）。

  • 应该分配最古老的时间戳，保持外部一致性，以避免阻塞。

    • For read at single paxos group:
      • Let LastTS() = timestamp of the last committed write at the Paxos group.
      • 如果没有准备好的事务，让 $s_{read} = LastTS()$很容易满足外部一致性：事务将看到最后一次写入的结果。
    • 在一般情况下，选择TT.now().latest()更简单。

小结

Spanner 的 TureTime API 设计非常巧妙, 保证了绝对时间一定是落在 TT.now() 返回的区间之中。基于这个保证, 使得分布在全球的 spanserver 分配的 timestamp 都是基于同一参考系, 具有可比性。进而让 Spanner 能够感知分布式系统中的事件的先后顺序, 保证了 External Consistency。

但是 TureTime API 要求对误差的测量具有非常高的要求, 如果实际误差 > 预计的误差, 那么绝对时间很可能就飘到了区间之外, 后续的操作都无法保证宣称的 External Consistency。另外, Spanener 的大部分响应时间与误差的大小是正相关的。

自 Spanner 在 OSDI12 发表论文后, Spanner 一直在努力减少误差, 并提高测量误差的技术[3], 但是并没有透露更多细节。

在一个大规模的分布式系统中，集中分配时间戳是不可行的。解决方案: TrueTime设备

  • GPS时钟
  • 原子钟

总结

  • 分布式多版本数据库
    • General-Purpose Transactions（ACID）
    • SQL查询语言
    • 模式化的表(Schematized Tables)
    • 半关系型数据模型（F1 is more relational/SQL）
  • 重点：管理跨数据中心的复制
  • 特点：提供外部一致的读写。
    • 提供外部一致的读和写。
    • 全局一致的跨数据库读取

F1最初定位是一个SQL查询引擎，本来是架构在Mysql的分布式集群上。由于Mysql本身的reshared以及分布式事务上的冲突几乎是无解，最终放弃Mysql分布式存储，而转而使用Spanner。单独的F1并不能称为一款数据库。这点在F1论文题目有所误导，更准确的来讲F1是一款SQL执行引擎，包含了二级索引等一些常见的传统数据库功能。和Spanner结合起来才完成了Nosql+Sql=newSQL的壮举。

Spanner/F1似乎是第一个能称得上可真正扩展的分布式SQL系统。

-------------本文结束，感谢您的阅读-------------