2018.4.26
分布式存储的数据类型有以下三种： 非结构化数据。 主要是文本图像等数据之间相关性较低的数据
结构化的数据：数据之间的关联很大，关系数据库可以用表表示
半结构化数据：介于上述两种数据类型之间，数据之间的关系很简单，典型的代码是html文件
分布式存储系统很适合处理各种类型的这种数据。 分布式存储系统分为以下几类：
分布式文件系统—处理非结构化数据，并将所有非结构化数据视为文件格式存储对象。 处理对象是文件，形成分布式文件系统。
分布式键值系统：存储数据关系简单的半结构化数据，通过键值管理半结构化数据，一般用作缓存系统，一致性哈希算法是键值系统中常见的数据分布技术。 支持简单的数据创建、读取、更新、删除操作。
分布式表系统：存储数据关系复杂的半结构化数据，不仅支持分布式键值系统的GRUD操作，还支持主键的范围扫描。 主要功能是只针对单个表，不支持表之间的连接等操作。
分布式数据库：存储结构化数据，从独立的关系数据库发展而来，提供多维表组织数据，提供SQL语言搜索，支持多表关联。 关系数据在软件生态链中非常好，但面临的问题是可扩展性问题，如果将传统的事务操作有效地扩展到各个节点。 目前出现了许多非关系数据库，虽然扩展性好，但只能解决某些问题，目前倾向于使用分布式关系数据库。
————————————————————————————————————————————
独立存储系统介绍了从独立关系数据库的存储引擎中诞生的独立存储系统的概念。 关系数据库为上层提供各种操作，并将这些操作封装在事务的操作中。 那么，这些数据库的数据存储是以什么结构组织的呢？ 这就是所谓的存储引擎。
存储引擎：基本功能包括其他删除更改。 为上层数据库提供增删更改。
典型的存储引擎包括：
哈希存储引擎：支持哈希表持久性、随机添加删除和读取，但不支持顺序扫描。 -分布式键值系统
Btree存储引擎：支持b树持久化，支持随机添加删除、读取和顺序扫描。 -分布式数据库
LSM存储引擎：支持随机添加、删除、读取和顺序扫描，将通过批量写入技术随机写入的数据批量顺序写入磁盘。 在互联网后台存储系统中被广泛使用
哈希存储引擎：基于哈希表结构的键值存储系统仅支持附加写入。 这意味着所有写入操作都只会添加而不修改旧数据，同一时间只有一个新文件处于活动状态。
主要思想如下。
1 .存储器采用基于散列表的机智服装结构。 即，hash表中存储数据在盘上的位置机智的服装，盘中存储主键和值的实际内容。
2 .定期合并，定期合并旧数据或删除操作，保留最新数据。
3 .掉电恢复，在光盘上留下机智的服饰记录，定期合并时生成该机智的服饰记录，在光盘掉电时直接用该机智的服饰记录重建到内存中即可。
有个问题。 机智服装的长度远远小于数据的长度，所以内存中机智服装越多，存储在磁盘上的数据就越多。
B树存储引擎：是关系数据库中常用的存储引擎，通过B树的结构进行数据的持久化
主要思想：
1 .利用b树的数据结构，非叶节点是一种机智的服装，叶节点中存储的数据
2 .根节点驻留在内存中，用二分法去寻找非叶节点，未命中取磁盘上的根节点。 最后快点取叶节点的值，最后从磁盘中取出。
3 .增加缓冲区管理，替换策略，加快叶节点缓存。
LSM树存储引擎：主要思想：
1 .将数据更改的增量保存在内存中，达到指定的大小限制后批量写入磁盘
2 .要读取数据，必须将磁盘历史数据与内存中最近修改的数据合并
3 .将增加的数据写入光盘时，根据新旧不同写入不同的sst文件，为这些问题提供不同的层次。 层次表示数据的新旧，在这样的层次上完成数据的持久化。
————————————————————————————————————————————
上面介绍的存储引擎是存储系统的发射器，下面介绍数据模型。 数据模型是存储系统的外形，是存储系统在上层存储数据的模型。
常见的模型分为三类。 文件、关系、键值1 .文件模型。 为上层APP应用程序提供文件存储，以目录格式管理文件，并提供文件的基本操作。 例如，打开读写或浏览目录的操作。
2 .关系模型：每个关系由一个表由多行组成，为上层提供对SQL数据库的访问特性。
3 .键值模型：按行存储，每行由主键和值两部分组成。
————————————————————————————————————————————
SQL和noSQL表示关系数据库，而非关系数据库。 两者都有优点和缺点。
SQL关系数据库问题： 1、事务处理本来是为了更方便地封装操作，但由于当前的数据都是大量的数据，而且数据都存储在不同的节点，导致事务的多个操作不同
2、我们知道
SQL为了同时操作多个表，支持表之间的联表操作，但是在海量数据面前，有时候联表操作并不是好的操作，海量数据有时候往往会利用那些冗余的数据。3、在性能上，SQL底层是B树，B树的更新性能是没有LSM树这些性能好，如果碰到频繁的增添的时候，在存储引擎上还没有key-value这种系统好。
noSQL非关系型数据库的挑战：1、缺少统一的标准，都是在针对特定的应用进行改进的
2、使用上及运维上比较复杂，没有形成一个统一的标准
3、这一类数据库一般用来缓存或者优化关系型数据库。
————————————————————————————————————————————
为了让数据库更加高效的进行，数据库将多个操作合成了一个事务，并且让这个事务变成一个基本的操作，也就是说数据库的事务必须满足ACID属性
1、原子操作：对数据的修改是原子的，也就是说要么修改，要么不修改。
2、一致性：保持数据的一致性，即数据是正确完整的
3、隔离性：事务之间是隔离的，每一个事务在它没有完全执行完成之前，对其他的事务是不可见的
4、持久性：事务完成后，对数据库的操作是永久性的。
————————————————————————————————————————————
分布式数据库中的并发操作多个事务并发操作的时候，这个时候很有可能对资源是有冲突的，例如一个事务要读某行，一个事务又要更新写这一行，那和避免这种冲突呢？
看起来并发导致资源冲突和多线程的资源冲突很类似，第一个想到的是通过锁的方式来解决。
对于分布式数据库中并发管理有以下几种方式：
1、数据库锁
2、写时复制技术
3、多版本并发控制
事务分成几种类型：读事务、写事务、读写事务
那么对应的锁也就有读锁，写锁，
对于读锁，允许对同一个元素加多个读锁
对于写锁，只能允许对一个元素加一个写锁，并且写事务将阻塞读事务
通过锁来控制和操作系统的线程是类似的，但是问题是可能会导致死锁，所以解决死锁需要靠回滚操作来完成。
2、写时复制技术由于互联网中读事务是远大于写事务，通过写时复制操作，可以在读操作不同加锁来解决冲突的问题
主要是分为三步：
拷贝：把根节点到叶子节点拷贝
修改：对节点内容进行修改
提交：切换根节点的指针，指向新的根节点
那么对于读操作来说，如果读操作发生在第3步之前，呢么将直接读取老的节点，在3之后，将直接读取新的节点。
用这种方法可以解决读写的冲突，但是写写的冲突还是存在的，写写必须得互斥操作才行。
多版本控制也可以实现读事务部加锁，它的思想也比较简单，对每行数据维护多个版本，版本实际是数据行的删除修改的时间，当写一个数据时，出现了读请求，那么写没有完成，读的版本就是老的数据，通过版本检查，就可以实现获得自己需要的数据版本。
最后，需要定义将无用的版本进行删除回收操作。
————————————————————————————————————————————
恢复的手段：操作日志，检查点
具体来说：
1、操作日志：为了保证数据的一致性，数据库的操作要持久化到磁盘，但不能频繁的访问磁盘，这样会导致性能很差，现在比较常见的做法是在内存中记录操作日志，在内存中去执行这些操作，然后通过批量定期刷新到磁盘，将随机的请求转换为顺序的写请求。
2、定期将日志刷新到磁盘上，当服务器出现宕机的时候，此时需要从磁盘中读取操作日志，进行恢复。
3、设置check检查点，实际是定义设置check点，这个check就自动将操作日志刷到磁盘上，每个check点就是一个恢复的时间点。
当出现故障的时候，此时将磁盘中对应的最新的check点进行恢复。
————————————————————————————————————————————
多种引擎之间的比较： 1、Hash存储引擎代表数据库：redis、memcache等
通常也常见于其他存储引擎的查找速度优化上。 Hash 机智的服饰结构的特殊性，其检索效率非常高，机智的服饰的检索可以一次定位，不像B-Tree 机智的服饰需要从根节点到枝节点，最后才能访问到页节点这样多次的IO访问，所以 Hash 机智的服饰的查询效率要远高于 B-Tree 机智的服饰。虽然 Hash 机智的服饰效率高，但是 Hash 机智的服饰本身由于其特殊性也带来了很多限制和弊端。
这里列举缺点：
（1）Hash 机智的服饰仅仅能满足"=",“IN"和”<=>"查询，不能使用范围查询。
（2）Hash 机智的服饰无法被用来避免数据的排序操作。
（3）Hash 机智的服饰不能利用部分机智的服饰键查询。
（4）Hash 机智的服饰在任何时候都不能避免表扫描。
（5）Hash 机智的服饰遇到大量Hash值相等的情况后性能并不一定就会比B-Tree机智的服饰高
由于不同机智的服饰键存在相同 Hash 值，所以即使取满足某个 Hash 键值的数据的记录条数，也无法从Hash机智的服饰中直接完成查询，还是要通过访问表中的实际数据进行相应的比较，并得到相应的结果。
———————————————————————————————————————————————
代表数据库：MongoDB、mysql(基本上关系型数据库)等
还有一种算是B树存储引擎：COLA树（CacheObliviousBTree）
代表数据库：tokudb
为了如何让B树更有效的执行，他们提出了一个缓存忘却CacheOblivious算法，该算法在不需要明确知道存储器层次中数据传输规模的情况下，也可以高效的工作。更多请参见：http://en.wikipedia.org/wiki/Cache-oblivious_algorithm。
说个大家熟悉的名称TokuMX : 目前非常流行的NoSQL数据库MongoDB的底层替换成与TokuDB同样的存储引擎[ ToKuMx]，达到了非常好的效 果
3、LSM树（Log-Structured Merge Tree）存储引擎代表数据库：nessDB、leveldb、hbase等
核心思想的核心就是放弃部分读能力，换取写入的最大化能力。LSM Tree ，这个概念就是结构化合并树的意思，它的核心思路其实非常简单，就是假定内存足够大，因此不需要每次有数据更新就必须将数据写入到磁盘中，而可以先将最新的数据驻留在磁盘中，等到积累到最后多之后，再使用归并排序的方式将内存内的数据合并追加到磁盘队尾(因为所有待排序的树都是有序的，可以通过合并排序的方式快速合并到一起)。
日志结构的合并树（LSM-tree）是一种基于硬盘的数据结构，与B-tree相比，能显著地减少硬盘磁盘臂的开销，并能在较长的时间提供对文件的高速插入（删除）。然而LSM-tree在某些情况下，特别是在查询需要快速响应时性能不佳。通常LSM-tree适用于机智的服饰插入比检索更频繁的应用系统。Bigtable在提供Tablet服务时，使用GFS来存储日志和SSTable，而GFS的设计初衷就是希望通过添加新数据的方式而不是通过重写旧数据的方式来修改文件。而LSM-tree通过滚动合并和多页块的方法推迟和批量进行机智的服饰更新，充分利用内存来存储近期或常用数据以降低查找代价，利用硬盘来存储不常用数据以减少存储代价。
磁盘的技术特性:对磁盘来说，能够最大化的发挥磁盘技术特性的使用方式是:一次性的读取或写入固定大小的一块数据，并尽可能的减少随机寻道这个操作的次数。
LSM和Btree差异就要在读性能和写性能进行舍和求。在牺牲读性能的同时，寻找其他方案来弥补。
1、LSM具有批量特性，存储延迟。当写读比例很大的时候（写比读多），LSM树相比于B树有更好的性能。因为随着insert操作，为了维护B树结构，节点分裂。读磁盘的随机读写概率会变大，性能会逐渐减弱。 多次单页随机写，变成一次多页随机写,复用了磁盘寻道时间，极大提升效率。
2、B树的写入过程:对B树的写入过程是一次原位写入的过程，主要分为两个部分，首先是查找到对应的块的位置，然后将新数据写入到刚才查找到的数据块中，然后再查找到块所对应的磁盘物理位置，将数据写入去。当然，在内存比较充足的时候，因为B树的一部分可以被缓存在内存中，所以查找块的过程有一定概率可以在内存内完成，不过为了表述清晰，我们就假定内存很小，只够存一个B树块大小的数据吧。可以看到，在上面的模式中，需要两次随机寻道（一次查找，一次原位写），才能够完成一次数据的写入，代价还是很高的。
3、LSM Tree放弃磁盘读性能来换取写的顺序性，似乎会认为读应该是大部分系统最应该保证的特性，所以用读换写似乎不是个好买卖。但别急，听我分析一下。
a、内存的速度远超磁盘，1000倍以上。而读取的性能提升，主要还是依靠内存命中率而非磁盘读的次数
b、写入不占用磁盘的io，读取就能获取更长时间的磁盘io使用权，从而也可以提升读取效率。例如LevelDb的SSTable虽然降低了了读的性能，但如果数据的读取命中率有保障的前提下，因为读取能够获得更多的磁盘io机会，因此读取性能基本没有降低，甚至还会有提升。而写入的性能则会获得较大幅度的提升，基本上是5~10倍左右。
LSM Tree弄了很多个小的有序结构，比如每m个数据，在内存里排序一次，下面100个数据，再排序一次……这样依次做下去，我就可以获得N/m个有序的小的有序结构。
在查询的时候，因为不知道这个数据到底是在哪里，所以就从最新的一个小的有序结构里做二分查找，找得到就返回，找不到就继续找下一个小有序结构，一直到找到为止。
很容易可以看出，这样的模式，读取的时间复杂度是(N/m)*log2N 。读取效率是会下降的。
这就是最本来意义上的LSM tree的思路。那么这样做，性能还是比较慢的，于是需要再做些事情来提升，怎么做才好呢？
a、Bloom filter: 就是个带随即概率的bitmap,可以快速的告诉你，某一个小的有序结构里有没有指定的那个数据的。于是就可以不用二分查找，而只需简单的计算几次就能知道数据是否在某个小集合里啦。效率得到了提升，但付出的是空间代价。
b、compact:小树合并为大树:因为小树他性能有问题，所以要有个进程不断地将小树合并到大树上，这样大部分的老数据查询也可以直接使用log2N的方式找到，不需要再进行(N/m)*log2n的查询了
参考链接：http://blog.csdn.net/map_lixiupeng/article/details/40897501