您的位置: 首页  >  文章  >  大规模分布式存储系统——存储系统基本知识

大规模分布式存储系统——存储系统基本知识

分类: 文章 • 2024-08-24 10:19:04

硬件基础

CPU架构

经典的多CPU架构为对称多处理结构(SMP)，即在一个计算机上汇集了一组处理器，他们之间对称工作，共享相同的物理内存与总线
大规模分布式存储系统——存储系统基本知识

SMP架构主要是共享，系统中所有资源都是共享的，那么会导致竞争的时候性能下降。
为了提高可扩展性，现在主流服务器架构一般为NUMA
大规模分布式存储系统——存储系统基本知识

NUMA——Non-Uniform Memory Access 非一致性存储访问

IO 总线

大规模分布式存储系统——存储系统基本知识
存储系统的性能瓶颈一般在IO
Intel x48主板是典型的南北桥架构，北桥芯片通过前端总线与CPU相连，内存模块等挂载在北桥上。

北桥与南桥之间通过DMI链接，DMI带宽为1GB/s

网卡，硬盘则挂载在南桥上。

存储层次架构

  • 存储系统的性能瓶颈主要在磁盘的随机读写
  • 所以设计存储引擎的时候，需要对磁盘的特性做处理，如把随机写操作转化为顺序写，如通过缓存减少磁盘随机读的操作。
  • SSD磁盘一般比较昂贵，可以用于做缓存
  • 存储系统的性能主要包括两个维度：吞吐量以及访问延时
  • 在保证最低成本的同时，尽可能实现高吞吐，例如磁盘和SSD的延时差别很大，但是带宽差别不大。我们可以把热数据存储到SSD中，冷数据存储到磁盘中。

单机存储引擎

  • 哈希存储引擎----Bitcask

基于哈希表结构的键值存储系统，属于日志文件系统，即数据是append only的

  • 在bitcask中，每个文件有大小限制，当文件增加到相应大小时候，就会产生一个新的文件。老的文件只读不写。任意时刻只有一个文件可以写，叫做active data file

  • 数据结构
    大规模分布式存储系统——存储系统基本知识
    每一条数据的记录项如上。

那么所有记录以这样的方式存储在磁盘上

大规模分布式存储系统——存储系统基本知识
但文件这样持续的存下去，肯定是会无限膨胀的，为了解决个问题，和其他日志型存储系统一样Bitcask也有一个定期的合并操作。合并作，即定期将所有older data file中的数据扫描一遍并生成新的data file（没有包括active data file 是因为它还在不停写入），这里的merge其实就是将对同一个key的多个操作以只保留最新一个的原则进行删除。每次合并后，新生成的数据文件就不再有冗余数据了。

  • 基于Hash表建索引

大规模分布式存储系统——存储系统基本知识
如何基于Key快速定位value？

在内存中建立如图上的Hash索引表

hash表对应的这个结构中包括了三个用于定位数据value的信息，分别是文件id号(file_id)，value值在文件中的位置（value_pos）,value值的大小（value_sz），于是我们通过读取file_id对应文件的value_pos开始的value_sz个字节，就得到了我们需要的value值。

大规模分布式存储系统——存储系统基本知识

1.得到Key
2.根据file_id找到文件
3.根据value_pos找到存储value的行
4.根据value_sz偏移量找到存储的value的位置

这时候每一次写操作就伴随着一次磁盘顺序写以及内存写入操作

  • 快速恢复
    问题： hash索引是存储在内存中的，加入服务器断电重启hash表，需要扫描一遍数据文件，如果数据文件很大，耗时会很大，那怎么办？

A：可以通过索引文件来提高重建哈希表的速度

hintFile索引文件可以把内存中的哈希索引表转存储到磁盘上，这个索引文件只包含value的位置，不包含具体value值

所以重建哈希表的时候不需要扫描所有数据文件，仅仅需要把索引文件的数据一行行读取并且重建即可。

  • B树存储索引

B树存储引擎不仅支持随机读取，还会支持范围扫描。例如在Mysql的InnoDB中，有一个成为聚集索引的特殊索引，组织成B+树数据结构。

数据结构

  • B+树
    大规模分布式存储系统——存储系统基本知识
  • B+树按照Page来组织数据，每个页面对应了B+树一个节点
  • B+树叶子节点保存每行的完整数据，非叶子节点保存索引信息

读取操作： 从根节点开始二分查找一直到叶节点，如果对应页面不在内存中，需要从磁盘中读取该页并且缓存起来，每一次读取就是一次换页操作。

假设树的高度为h，那么B+树检索最多需要h-1次磁盘IO，复杂度为O(h)

修改操作首先需要记录提交日志，然后修改内存中的B+树，如果内存中被修改的页面超过一定比率，后台线程会把这些页面刷写到磁盘中做持久化。

缓冲区管理

  • LRU

实现方法是把页按照最后一次被访问的时间组成一个链表，每次淘汰链表尾部的页。

  • LIRS

LRU的一个问题就是，如果一个查群做了一次全表扫描，会导致缓冲池的大量页面被替换，从而污染缓冲池。

LIRS算法就是把缓冲池分为两级，数据首先进入第一级，如果数据在短时间内被访问两次或者以上，可以看作是热点数据。热点数据会进入第二级缓冲池，每一级内部还是LRU替换算法。

以InnoDB为例，InnoDB内部的LRU链表分为两部分，新子链表和老子链表，页面首先插入到老子链表，并且在老子链表停留时间超过一定值的时候，才会被转移到新子链表。

出现全表扫描的时候，由于数据页表在老子链表停留时间不够，不会转移到新的子链表中。

  • LSM
    Log Structured Merge Tree

把对数据的修改增量保持在内存中，当达到指定大小后，再把这些修改操作批量写入磁盘中。读取数据的时候，需要合并磁盘中的历史数据和内存中最近的修改操作。

LSM树可以规避磁盘的随机写入问题，让磁盘的写入改为顺序写。但是读取的时候，还是需要访问比较多的磁盘文件。

LevelDB架构分析

LevelDB是一个可持久化的KV数据库引擎

类Redis的key/value存储，redis基于纯内存，而LevelDB是基于内存+SSD。内存存储最新的修改和热数据，SSD作为冷存储，与redis相比，写性能很好但是读性能由于读冷数据的时候需要进行磁盘IO，性能比较差。

LevelDB的Level指的是数据是分不同层级存储的，不同层的数据会定期从上往下移动。如果磁盘底层的冷数据被修改了，就会再次进入内存。一段时间又会被持久化回磁盘的底层。

  • 存储结构

内存中有MemTable(跳表实现)，分为可变和不可变的两种。
大规模分布式存储系统——存储系统基本知识
磁盘上的文件：

当前文件(Current)
清单文件(Manifest)
操作日志(Commit Log)
SSTable文件(SSTable)

写入过程：

LevelDB首先会把修改操作写入到操作日志文件，成功后再把修改操作应用到MemTable.

当MemTable占用内存达到上线之后，需要把内存的数据转存到外存文件中。LevelDB会把原先的MemTable冻结成为不可变的MemTable，然后在内存中生成一个新的MemTable.

然后新的数据就会写入到新的操作日志文件和新生成的MemTable中。LevelDB的后台线程会把不可变的MemTable的数据排序后转存到磁盘，然后形成一个新的SSTable文件。
这个操作称为Compaction.

SSTable文件是内存中的数据不断进行Compaction操作后形成的，并且SSTable所有文件都是层级结构。

SSTable中的文件时按照这些记录的主键来排序的，每个文件有最小主键和最大主键。

清单文件记录了这些元数据，包括数据属于那个层级，文件的名称，主键信息等。

当前文件记录了当前使用的清单文件名

在LevelDB运行过程中，随着Compaction的进行，SSTable文件会发生变化，新的文件会产生，老的文件会被废弃，因此往往需要生成新的清单文件来记录这些变化。而当前文件是用来指出哪个清单文件是有效的。

查询过程：

LevelDB对外只支持随机读取单条记录，查询的时候LevelDB首先会去查看内存中的MemTable，如果MemTable包含记录的主键以及对应值就返回记录。
如果MemTable没有读到主键，而接下来到内存不可变的MemTable中去读取。
如果还是没有读到，只能一次从新到老读取磁盘中的SSTable文件。

合并过程：

大规模分布式存储系统——存储系统基本知识
LevelDB会时不时对内存中的memTable执行合并操作

在磁盘中会存储很多sst文件，sst表示Sorted String Table,文件里所有的Key都会有序，每个文件都会对应一个Level,每一个Level会有多个文件。

底层的文件内容会来源于上一层，最终都是来源于0层。0层的文件又是来源于Memtable的序列化，一个Memtable会序列化为一个完整的0层文件。这个过程就是minor compaction

从n层的sst文件下沉到n+1层的sst文件称为Major Compaction 本质上就是跑一个多路归并算法，把相关的n层文件和1层sst文件作为输入，进行多路归并。最后生成多个n+1层的sst文件

数据模型

就是研究数据以什么样的模型存储在存储系统中？

  • 文件模型
    以目录树形式组织文件，以POSIX暴露文件系统的存储接口和操作集。

  • 关系模型
    每个关系称为一个表格，由多个元组(行)构成，每个元组包含多个属性。关系名，属性名以及属性类型称为关系的模式。

  • 键值模型

许多NOSQL采用的是K-V模型，更为广泛的是基于KV模型的表格模型。

表格模型弱化了关系模型中的多表关联，支持基于单表的简单操作。

事务与并发控制

事务：
ACID

原子性
要么全部执行，要么全部不执行，回滚到之前的状态。

一致性
数据库的数据要保证正确性，完整性和一致性。
如数据的类型正确，数据数值要在合理的范围内

隔离性
并发执行多个事务的时候，其中一个事务不能看到其他事务的中间状态

持久性
事务完成后，对数据库的影响是永久的。

一般而言，事务的并发控制一般通过锁机制实现。根据锁的粒度不同，可以锁住行，也可以锁住数据块或者整张表格。由于互联网业务中读事务的比例远远高于写事务，为了提高读事务的性能，可以采用写时复制或者MVCC来避免写事务阻塞读事务。

数据库可以选择牺牲隔离属性来获取并发度，从而获得性能提升。

SQL的四种隔离级别

  • Read Uncommited

最低的隔离级别，负责读取未提交的数据

  • Read Commited

读取已经提交的数据，但是在一个事务中，对同一个项前后两次的读取结果可能不一样。例如第一次读取的时候，由于另外一个事务修改还没有提交，第二次读取的时候就已经提交了。

  • Repeatable Read

保证在一个事务中，对同一个项，确保前后两次读取的结果一样

  • Serializable
    可序列化，即数据库事务可串行化执行，像一个事务执行的时候没有别的事务同时执行，隔离界别最高，效率最低

Read Commited 解决了脏读问题：

脏读：一个事务读取了另外一个事务更新却没有提交的数据项

Repeatable Read 解决了不可重复读：

不可重复读：一个事务对同一个数据项的多次读取可能会得到不同结果

Phantom Read 解决了幻读：

幻读：事务执行过程中，由于前面的查询和后面的查询期间有另外一个事务插入了数据，导致后面的查询结果出现了前面查询结果中未出现的数据。

并发控制

  • 数据库锁

数据库锁分为读锁和写锁，允许对同一个元素加多个读锁，但只允许加一个写锁。写事务将会阻塞读事务。

如下图,T1获得了A的读锁，需要申请B的写锁，需要B放弃读锁，但是B要放弃读锁就必须先申请A的写锁。这就产生了相互依赖。
大规模分布式存储系统——存储系统基本知识
解决死锁思路：

  • 为每个事务设置一个超时时间，超时后自动回滚

  • 死锁检测，可以通过回滚某些事务来消除循环依赖

  • 不加锁的方法——写时复制(Copy-on-Write)

B+树写操作(写时复制)

1.copy：把从叶子节点到根节点路径上的所有节点拷贝出来
2.modify: 对拷贝节点执行修改
3.commit: 原子性切换根节点的指针，使之指向新的根节点。
大规模分布式存储系统——存储系统基本知识
在提交之前如果读数据，那么会读取老节点的数据，读操作也不需要加锁保护。

写时复制还会涉及到引用计数，对每个节点维护引用计数。

  • 不加锁的方法——多版本并发控制

MVCC是对每一行数据维护多个版本，无论事务的执行时间有多长，MVCC总能提供与事务开始时刻一致的数据。

面试问题：
程序员A正在读数据库中某些内容，而程序员B正在给这些内容做修改（假设是在一个事务内修改，大概持续10s左右），A在这10s内 则可能看到一个不一致的数据，在B没有提交前，如何让A能够一直读到的数据都是一致的呢？

1.方法一：加锁

B修改数据的时候，加锁，但是会影响到程序运行的效率

2.方法二：多版本并发控制

  • 在更新数据库的时候，并非用新数据覆盖旧数据，而只是标记旧数据是过时的，同时在其他地方新增一个新数据版本。
  • 因此同一份数据有多个版本存储，但只有一个是最新的。
  • 所以用户在链接数据库的时候，看到的都是某一个特定时刻的数据库快照。
  • MVCC提供了时间一致性的处理思路：
    读事务的时候，用一个时间戳或者事务ID来确定访问哪个状态的数据库以及哪些版本的数据。
    读事务和写事务彼此隔离，彼此不受影响。对同一份数据，既有读事务访问，又有写事务操作。对于写事务，会新建一个新的数据版本，而读事务访问的是旧的数据版本。直到写事务提交。

一个事务，不管执行多长时间，在内部看到的数据都是一致的。

InnoDB的MVCC实现

通过在每行记录后面保存两个隐藏的列：一个保存了行的创建时间，另外一个保存了行的过期时间。这里的时间指的是系统版本号，每开始一个新的事务，系统版本号就会递增。

  • select操作

InnoDB查找版本早于当前事务版本的数据行，确保事务读取的行，要么在事务开始之前就存在，要么是事务自身插入或者修改的记录

行的删除版本要么没有定义，要么大于当前事务版本号，保证事务读取的行，在事务开始之前未删除

  • insert操作

把新插入的行保存为当前版本号为行版本号

  • delete操作

将删除的行保存当前版本号为删除标识

  • update操作

综合insert+delete

innodb后台会执行一个线程执行清理工作，具体是删除版本号小于当前系统版本号的行

故障恢复

通过操作日志回滚来实现故障的恢复。
分为两种：
回滚日志：记录事务修改前的状态

重做日志：记录事务修改的操作

  • 操作日志

为了保证数据库的一致性，对数据库的操作记录都要持久化到磁盘。

如果每次操作都要落盘，会随机更新磁盘中的某个数据块，系统性能会很差，

因此通过操作日志顺序记录每个数据库操作并且在内存中执行这些操作，然后内存中的数据再定期刷写到磁盘中，这样可以实现把随机写请求转化为顺序写请求。

别忘了，磁盘的顺序写性能是远远高于随机写性能的。

  • 重做日志
    1.把REDO日志以追加写的方式写入磁盘日志文件
    2.把REDO日志的修改操作应用到内存中
    3.返回操作成功或者失败

REDO日志约束：
修改内存中的元素X之前，要确保与这个修改相关的日志已经刷写到磁盘

这么做是因为如果先修改内存数据，而在完成内存修改与写入日志之间发生了故障，那么最近的修改操作将无法恢复，这就导致了不一致的情况。

日志提交的优化手段：

1.成组提交

因为存储系统要求把REDO日志先刷写到磁盘中才可以更新内存中的数据。如果每个事务执行完之后，都要求日志立刻刷写入磁盘，那么吞吐率会很差。

对于一致性要求很高的应用，可以设置为立刻刷入，
对于一致性不高的应用，可以先把REDO日志缓存到操作系统或者存储系统的内存缓冲区，再定期刷入磁盘。

Group commit：
a.日志缓冲区的数据流超过一定大小或者
b.距离上次刷盘超过一定时间

才会把日志缓冲区中的多个事务操作一次性刷写入磁盘。
然后一次性把多个事务中的修改操作应用到内存中，并且逐个返回操作结果。

与定期刷盘不同的是，group commit保证了REDO日志成功刷盘之后，才返回写操作成功。

  1. checkpoint机制

如果所有数据都保存在内存中，问题是：

1.故障恢复需要回放所有的REDO日志，效率比较低。如果REDO日志比较多，例如超过了100GB，那么故障恢复时间是无法接受的。
2.内存不够大

因此需要把内存中的数据定期转存到磁盘中，这种技术称为checkpoint技术。
系统将会定期把内存中的操作以某种易于加载的方式转存到磁盘中，并且记录checkpoint时刻的日志回放点。

以后故障恢复的时候，只需要回放checkpoint时刻之后的所有REDO日志

checkpoint具体流程如下：

1.日志文件记录"START CKPT"
2.把内存中的数据以某种易于加载的组织方式存储到磁盘中，形成checkpoint文件(存储的是修改操作之后的数据结果)，checkpoint文件往往会记录"START CKPT"的日志回放点，用于故障恢复。
3.日志文件中记录"END CKPT"

故障恢复流程如下：
1.把checkpoint文件加载到内存中，这一步通常只加载索引数据
2.读取checkpoint文件中记录的"START CKPT"日志回放点，然后回放之后的REDO日志

一个问题：如果REDO日志里面记录的操作不是幂等操作怎么办？例如APPEND操作

那么checkpoint文件中的数据一定不能包含这些操作的数据

内存数据结构支持快照，执行checkpoint操作的时候首先要对内存数据结构做一次快照，接着把快照中的数据转存到磁盘中生成ckpt文件，再记录这个时候对应的REDO日志回放点。
这个时候再进行哪些不幂等的操作，ckpt的快照数据也不会包含这些操作的结果。

数据压缩

tbc

ref

《大规模分布式存储系统》

相关推荐