排行榜 统计
  • 建站日期:2017-05-20
  • 文章总数:139 篇
  • 评论总数:482 条
  • 分类总数:26 个
  • 最后更新:昨天 21:08

Making a Scalable and Fault-Tolerant Database System: Partitioning and Replication

本文阅读 15 分钟
广告

当今的数据库通常存储TB到PB的数据,并且每秒处理数十万到数百万个客户端请求。单台服务器计算机不足以处理此类工作负载。我们如何建立一个不会因自身原因而崩溃的数据库?我们如何制作可扩展的系统?

现代数据库是容错的。即使系统出现故障,系统仍然可以运行。这是怎么做的?以及与此相关的可伸缩性如何?

Partitions 分区

为了建立一个可扩展的系统,我们首先要确定一个逻辑数据单元,我们将其称为分区。分区应该是独立的片段,可以分布在多台计算机上。

考虑一个键值存储。它是一种具有简单界面的数据库:对用户而言,它看起来像一组(键,值)对,例如:

keyval
k1aaa
k2bbb
k3ccc

该存储可能支持诸如在写入一个键值对,在键下读取值或执行原子比较和设置之类的操作。

在这样的存储中,我们可以将一个分区定义为简单的(键,值)对,比如:(k1,aaa)。我假设不同的键不相关,因此将它们彼此远离放置不会带来其他影响。

另一方面,考虑一个关系数据库。数据库中的数据类型由关系组成,比如一个元祖集(x1,x2,x3....xn),x1来自X1,x2来自X2等等,假设X1 是整数集,X2是英文字母上的一组单词,且X3是实数集。关系的示例如下:

X1X2X3
0“aba”1.5
42“universe”π
1“cdc”-1/3

这就是一张关系表,实际上,键值存储可以被认为是关系数据库的一种特殊情况,该关系数据库具有两列,并且对对的集合具有特定的约束。

关系数据库中表的某些列可能有特殊目的。例如,在Cassandra和Scylla中,clustering columns 用于对行进行排序。因此,行不是独立的,这与上一个示例中的(键,值)对不同。

维持行的全局顺序将使扩展数据库非常困难。因此,在Cassandra和Scylla中,基于另一组列(partitioning columns)将行分组为多个分区。这些数据库中的每个表必须至少具有一个分区列。这样,该表中的分区就是一组在这些列中具有相同值的行。这些值一起构成该行的分区键(partition key)。在每个分区中维护基于聚类列的顺序,但不跨分区维护。

假设我们的表有一个分区列(partitioning column)pk 和一个聚类列(clustering column )ck。每列都有整数类型。用户查询后可能会看到以下内容:

pkck
02
03
20
21
15

在此示例中,有3个分区:{(0,2),(0,3)},{(2,0),(2,1)},和{(1,5)}。请注意,在每个分区中,该表均根据聚类列(clustering column )进行了排序,但是在分区之间没有全局顺序。

对于一般的关系数据库,我们可以采用相同的策略:将表中列的子集标识为分区列,并且分区是在这些列下具有公共值的行的集合。这将引导我们进入通常所说的水平分区;该名称可能与通常描述表的方式有关。

重要的是每个分区都有一种唯一标识它的方式,即它具有一个key;对于关系数据库,key是分区内任何行的分区列下的值的元组(根据定义,行的选择无关紧要)。对于分区是键值对的键值存储,分区的键就是 key。

如何制作大型数据库

我们已经确定了数据库的分区。怎么办?

假设非分布式 store 如下:

有一个节点可以存储所有分区。只要以下条件,它就可以正常工作:

  • 定期备份,保证数据不会丢失。
  • 所有分区都适合单个节点,节点保持处理所有的客户端请求。

接下来,把数据切片。

这种分割叫分片,我们获得的部分在数据库世界中通常称为分片(shards)。在此示例中,我们有3个分片:一个带有 key {key1,key2,key3},一个 {key4,key5,key6},还有一个 {key7,key8}。有时,分片(shards )也称为 ranges 或者 tablets。

Scylla还使用 shards 来指代CPU内核,该术语来自Seastar框架,它是Scylla的基础。与我们当前的讨论没有任何关系。

现在我们有了分片数据库;现在,我们将每个分片放在单个节点上。在每个分片中都保留了许多分区。

分片解决了两个问题:

  • 分区占用空间,但现在它们分布在一组节点中。如果我们的数据库增加并且出现了更多分区,我们可以添加更多节点。只要分区本身不会变得太大,这就是一种有效的策略:在Scylla中,我们将其称为“大分区问题”,通常可以通过更好的数据建模来解决。您可以阅读有关Scylla如何处理大型分区的信息
  • 节点不需要处理所有客户端请求:它们根据客户端要访问的分区进行分配。只要没有一个每个人都喜欢的分区,此方法就起作用:在Scylla中,我们称此为“热分区问题”,对于大型分区,通常可以通过更好的数据建模来解决。Scylla还收集有关最热分区的统计信息,可通过nodetool toppartitions命令对其进行调查。

如果我们注意跨分区均匀地分配数据,我们的数据库现在可以很好地扩展。它还提供了一定程度的容错能力:如果其中一个节点发生故障,我们只会丢失一个分片,而不会丢失所有分片。但这还不够,因为每个分片都可能包含重要数据。

解决方案是复制:,做冗余,将每个分片保留在一部分节点上!

我们可能不想将每个分片保留在每个节点上。这将使我们以前的可伸缩性成就无法实现(但是对于某些表来说,这可能是一种有效的策略)。我们将它们保留在足够大的节点上,以实现高度的容错能力。每份副本的位置也很重要;我们可能希望将每个分片放置在至少两个位于不同地理位置的节点上。

对于碎片 S ,此分片复制到的节点集将称为的副本集。在上面的示例中,分片 shard5 的副本集是{A,B,E}。

分区方案和复制策略

每个分区都包含在一个单独的分片中,并且每个分片都复制到一组节点上。我将使用短语分区方案 来表示将分区分配给分片的方法,并使用复制策略 来表示将分片分配给其副本集的方法。

正式地,让 $K$ 到 是一组分区键(请记住,每个键唯一地标识一个分区), $S$ 是碎片的集合,并且 $N$ 是节点集。有两个功能:

  • $P:K\rightarrow S$ ,分区方案
  • $R:S\rightarrow P(N)$ ,复制策略

对于一套 $X$ , 符号 $P(X)$ 表示 $X$ 的幂集,比如:$X$ 的所有的子集。

比如,假设 $K={1,2,3,4,5,6},S={s1,s2,s3}, N={A,B,C}$ 。一个可能的分区方案为:

$\mathcal P = \{ \langle 1, s_1 \rangle, \langle 2, s_2 \rangle, \langle 3, s_3 \rangle, \langle 4, s_2 \rangle, \langle 5, s_3 \rangle, \langle 6, s_6 \rangle \}$

符号 $f$ 表示一个映射关系 $f = \{\langle x_1, y_1 \rangle, \langle x_2, y_2 \rangle, \dots\}$ ,$f(x_1) = y_1,f(x_2) = y_2$ ,

一种复制策略可以是:

$ \mathcal R = \{ \langle s_1, \{A, B\} \rangle, \langle s_2, \{B, C\} \rangle, \langle s_3, \{C\} \rangle \} $

为了计算每一个 key 的位置,我们只需要简单的计算,通过函数 $\mathcal R \circ \mathcal P$

比如 : $ (\mathcal R \circ \mathcal P)(2) = \mathcal R(\mathcal P(2)) = \mathcal R(s_2) = \{B, C\} $

此分区方案和复制策略的最终结果如下所示:

有时,复制策略不是返回一组节点,而是返回一个(有序的)列表。给定分片的此列表中的第一个节点通常具有特殊含义,称为该分片的主要副本,其他节点称为次要副本

我们可以辩称“分区方案”的概念是多余的:为什么不简单地将每个分区映射到一个单独的分片(即每个分片将仅由一个分区组成)?然后,我们可以完全放弃该概念,并使复制策略直接在分区上运行。

但其实将这两个概念分开只是一种好的“工程实践”,并且使思考问题变得更加容易。有一些重要的实际考虑因素:

  • 分区方案应快速计算。因此,它仅应查看分区键,而不应例如遍历现有分区的整个集合。最后一件事甚至可能是不可能的,因为分区集的大小可能是无限制的。
  • 如果分区方案将分区键映射到少量可维护的分片(例如成千上万个分片),那么我们可以使复制策略变得更加复杂:

    • 在决定在何处复制分片时,它可以查看整个分片集。
    • 它可以根据节点的地理位置做出复杂的决定。
    • 由于分片数量少,我们可以轻松地缓存其结果。

一致的哈希

分区方案是将分区分组为分片的一种方法。复制策略决定分片的存储位置。但是我们如何选择这两个功能呢?如果我们考虑所有变量,该任务将变得非常简单。为了简化我们的生活,让我们做以下假设(不幸的是,这只是更长列表的开始):

  • 我们的数据库节点具有相同的存储容量。
  • 我们的数据库节点具有相同的计算能力(在CPU和I / O方面)。

可以列出在这些假设下我们希望实现的以下目标:

  • 存储应该在节点之间均匀分布。
  • 客户端请求应在节点之间均匀分布。

进行一些进一步的假设将很方便:

  • 有很多分区(很多)。对于大型数据集和一些良好的数据建模,分区的数量可能达到数百万,甚至数十亿。
  • 与整个数据集相比,大分区的大小仍然很小。
  • 同样,与最受欢迎的分区相比,请求总数仍然很少。
  • 跨分区的工作负载分配是静态的。

想到的一种分区方案的“明显”理想特性是将分区分组为大小大致相等的分片(就所包含分区的存储和普及程度而言)。但是,这并不是绝对必要的:如果分片本身的数量足够大,我们可以负担得起一些不平衡。然后,复制策略可以将一些“较小”的分片与一些“较大”的分片一起放置在通用副本集上,从而实现节点间分区的平衡。换句话说,可以在分区方案和复制策略之间转移负载平衡的职责。

我们假设工作负载分配是静态的,例如,在正常的数据库操作期间不会动态更改。但是,仍然存在添加和删除节点的问题,这至少迫使复制策略功能进行调整; 考虑到这一点,让我们说明另一个条件:

  • 如果添加了新节点,则移动数据应该很容易;移动过程不应使单个节点过载,而应在多个节点之间分配应变。

对于删除节点的问题,可以说明类似的条件。

事不宜迟,让我们介绍一种使用称为一致性哈希的技术的简单分区方案。考虑一个圆。

让 $C$表示圆上的一组点。我们从选择圆上一小部分(有限的)点开始$T \subseteq C$:

T 称为令牌。

现在定义一个函数 $first: C \rightarrow T$ 给定圆上的一个点,它会返回该点“向右”的第一个标记(想象您从该点开始沿顺时针方向走圆,并在第一个标记处停止)。例如:

现在假设我们有一个函数 $hash: \mathcal K \rightarrow C$ 给定分区键的键将在圆上返回一个点。假设函数将散列均匀地分布在整个圆上。定义如下:

$ \mathcal P(k) = first(hash(k)). $

您的大名:
万水千山总是情,给个打赏行不行。 打赏
原创文章,作者:gogobody ,如若转载,请注明出处:https://www.ijkxs.com/416.html
-- 展开阅读全文 --
Emoji表情正则匹配
« 上一篇 04-01
MULTI-RAFT-GROUP kv 小记
下一篇 » 04-08
广告

发表评论

成为第一个评论的人
作者信息
热门文章
标签TAG
热评文章