《大规模分布式存储系统 原理解析与架构实践》第二章 单机存储系统

文章目录

• 一、单机存储系统

• 1.什么是单机存储引擎？事务？ACID特性？
• 2.硬件基础

• （1）CPU架构
• （2）IO总线：存储系统的性能瓶颈
• （3）网络拓扑
• （4）性能参数：存储系统的性能瓶颈主要在于磁盘随机读写
• （5）存储层次架构

• 二、单机存储引擎：是存储系统的发动机，增删读改CRUD，读取操作又分为：随机读取和顺序读取

• 1.哈希存储引擎：哈希表的持久化实现，支持CRUD，以及随机读取，但不支持顺序扫描，对应的存储系统为键值系统
• 2.B树存储引擎：B树的持久化实现，支持CRUD，支持顺序扫描，对应的存储系统是关系数据库

• LRU和LIRS算法

• 3.LSM树存储引擎：和B树存储引擎一样，支持CRUD和顺序扫描

• 三、数据模型：存储系统的外壳

• （1）文件模型：存储图片、文档、视频等二进制数据块

• （a）单机文件系统POSIX定义了**文件的操作接口**和**读写操作原语**
• （b）网络文件系统NFS

• （2）对象模型：存储图片、文档、视频等二进制数据块，但只能删除整个对象
• （3）关系模型：数据库
• （4）键值模型（引入表格模型）：大量的非关系数据库NoSQl系统采用表格模型

• （b）关系模型与表格模型的区别

• （4）SQL与NoSQL

• 四、事务与并发控制

• （1）事务：数据库操作的基本单位，具有ACID特性，类型包括：读事务，写事务，读写混合事务
• （2）并发控制：通过锁机制实现，类型：读锁和写锁

• （iii）解决死锁的两个思路

• 五、故障恢复：当系统重启时，需要能够恢复到一致的状态，即要么提交整个事务，要么回滚

• （1）操作日志
• （2）重做日志
• （3）优化手段

• 七、数据压缩

• （1）压缩算法
• （2）列式存储与行式存储

一、单机存储系统

1.什么是单机存储引擎？事务？ACID特性？

（1）单机存储引擎

• 就是哈希表、B树等数据结构在机械键盘、SSD等持久化介质上的实现；
• 单机存储系统是单机存储引擎的一种封装，对外提供文件、键值、表格或者关系模型；
• 单机存储系统的理论来源于关系数据库。

（2）数据库将一个或多个操作组成一组，称作事务。

• 事务必须满足原子性atomicty、一致性consistency、隔离性isolation、持久性durability，称之为ACID特性；

（3）对于多事务的并发执行和持久性的解释

（4）

• 哈希存储引擎是哈希表的持久化实现；
• B树存储引擎是B树的持久化实现；
• LSM树（Log Structure Merge Tree）存储引擎采用批量转存技术来避免磁盘随机写入；

2.硬件基础

（1）CPU架构

（a）摩尔定律：每18个月计算机等IT产品的性能会翻一番

（b）架构设计很重要的一点是：合理选择并且能最大限度地发挥底层架构的价值

（c）经典的多CPU架构，SMP结构如下：

SMP架构的特点：共享，系统中所有资源（CPU、内存、I/O等）都是共享的。由于多个CPU对前端总线的竞争，所以SMP的扩展能力是十分有限的。（d）现在的主流服务器架构一般是NUMA（Non-Uniform Memory Access）

（2）IO总线：存储系统的性能瓶颈

（3）网络拓扑

（a）传统的数据中心网络拓扑

（b）扁平化拓扑结构

（c）同一个数据中心内部的传输延时与数据中心之间的传输延时

（4）性能参数：存储系统的性能瓶颈主要在于磁盘随机读写

（a）常见硬件的性能参数

（b）读取磁盘1MB数据的时间的计算：磁盘寻道时间+数据读取时间

（c）固态硬盘SSD特点

（5）存储层次架构

二、单机存储引擎：是存储系统的发动机，增删读改CRUD，读取操作又分为：随机读取和顺序读取

1.哈希存储引擎：哈希表的持久化实现，支持CRUD，以及随机读取，但不支持顺序扫描，对应的存储系统为键值系统

（1）Bitcast是一个基于哈希表结构的键值存储系统

• BItcast数据文件中的数据是一条一条的写入操作，数据删除操作不会删除旧的条目，而是将value设定为一个特殊的值用作标识；
• 通过读取file_id对应文件的value_pos开始的value_sz个字节，这就得到了最终的value值；
• 写入时，首先将key-value记录追加到活跃数据文件的末尾，接着更新内存哈希表，so，每次写操作需要进行一次顺序的磁盘写入和一次内存操作。

（2）定期合并

对同一个key的多个操作只保留最新一个的原则进行删除。

（3）快速恢复
由于哈希索引存储在内存中，若服务器断电重启，重建哈希表非常耗时（即扫描一遍数据文件），所以通过索引文件hint file来提高重建哈希表的速度。

索引文件：就是将内存中的哈希索引表转存到磁盘生成的结果文件。索引文件并不存储具体的value的值，只存储value的位置（与内存哈希表一样）。 so，在重建哈希表时，就不需要扫描所有的数据文件，而仅仅将索引文件中的数据一行行读取并重建，大大减少重启后的时间。

2.B树存储引擎：B树的持久化实现，支持CRUD，支持顺序扫描，对应的存储系统是关系数据库

（1）关系数据库通过索引来访问数据，mysql innoDB按照页面（Page）来组织数据，每个页面对应B+树的一个节点

（2）缓冲区管理

缓冲区管理器将可用的内存划分为缓冲区，缓冲区是与页面同等大小的区域，磁盘块的内容可以传送到缓冲区中。

缓冲区的关键作用是：选择将哪些页面淘汰出缓冲池。

LRU和LIRS算法

3.LSM树存储引擎：和B树存储引擎一样，支持CRUD和顺序扫描

（1）LSM树的特点

（2）LevelDB存储引擎

（3）LevelDB的查询过程

（4）合并

三、数据模型：存储系统的外壳

（1）文件模型：存储图片、文档、视频等二进制数据块

（a）单机文件系统POSIX定义了文件的操作接口和读写操作原语

（b）网络文件系统NFS

（2）对象模型：存储图片、文档、视频等二进制数据块，但只能删除整个对象

（3）关系模型：数据库

（a）定义

（b）数据库语言sql查询语句的说明

（c）sql强大特性：子查询，索引和事务

（4）键值模型（引入表格模型）：大量的非关系数据库NoSQl系统采用表格模型

（a）由于键值模型过于简单，所以NoSQL系统中使用比较广泛的模型是表格模型，表格模型支持简单的基于主键的操作，扫描范围，也支持基于列的操作。

主键操作如下

表格模型的操作如下

（b）关系模型与表格模型的区别

（4）SQL与NoSQL

（a）Nosql：具有良好扩展性、弱化了一致性要求、在一定程度上解决了海量数据和高并发的问题

（b）SQL面临的问题

（c）NoSQL面临的问题

（c）不必纠结SQL与NoSQl的区别，而是着重理解关系数据库的原理以及NoSQL关系的高可扩展性

四、事务与并发控制

（1）事务：数据库操作的基本单位，具有ACID特性，类型包括：读事务，写事务，读写混合事务

（a）事务是干啥的？

（b）原子性

（c）一致性

（d）隔离性

（e）持久性

（i）SQL定义了4种隔离级别

（ii）SQL隔离级别降低可能导致读到脏数据或事务执行异常

（iii）所有的隔离级别都保证不会出现第一类丢失更新

（2）并发控制：通过锁机制实现，类型：读锁和写锁

（a）可串行化

（b）数据库锁

（i）定义

（ii）eg

（iii）解决死锁的两个思路

（iiii）写时复制，能够极大提高读取性能

eg如下

（iiii）多版本的并发控制

定义如下：

eg如下：

五、故障恢复：当系统重启时，需要能够恢复到一致的状态，即要么提交整个事务，要么回滚

（1）操作日志

（a）数据库系统以及其他的分布式存储系统一般采用操作日志技术来实现故障恢复；

（b）操作日志分为：回滚日志UNDO Log（记录事务修改之间的状态）、重做日志REDO Log（记录事务修改后的状态）以及UNDO、REDO日志

（c）eg

（2）重做日志

（3）优化手段

（a）为啥要对存储系统进行优化？

（b）成组提交Group commit

（c）检查点

将所有的数据放到内存中，可能出现的问题？

怎么用？

对不具有幂等性操作的数据，该怎么办？

七、数据压缩

（1）压缩算法

（a）

• 有损压缩算法：压缩比率高，但数据可能丢失，一般用于：图片，音频，视频；
• 无损压缩算法：能够完全还原原始数据；
• 存储系统在选择压缩算法时，要考虑压缩比和压缩算法的执行效率。 读操作需要先读取磁盘中的内容再解压缩，写操作需要先压缩再将压缩结果写入到磁盘，整个操作的延时包括：压缩/解压缩和磁盘读写的延时，压缩比越大，磁盘读写的数据量越小，冲压缩/解压缩的时间会越长。Google Bigtable系统采用BMDiff和Zippy压缩算法，通过牺牲一定的压缩比，换来执行效率的提升。
• 压缩算法的核心是找重复数据
• 
  

（b）Huffman编码

（c）LZ系列压缩算法

• LZ系列压缩算法是基于字典的压缩算法
• LZ系列的算法是一种动态创建字典的方法，压缩过程中动态创建字典并保存在压缩信息里面
• eg如下：
  
  
  
  
  （d）Google系统中的BMDiff和Zippy压缩算法

（i）Zippy压缩算法

（ii）BMDiff压缩算法

（2）列式存储与行式存储

（a）

• 列式存储技术通过把相同列的数据组织在一起，不仅减少了大数据分析需要查询的数据量，还大大提高了数据的压缩比；
• OLYP（Online Transaction Processing）:联机事务处理
  （b）对比如下