背景

随着信息化的浪潮和互联网的兴起，传统的RDBMS（关系型数据库管理系统）在一些业务上开始出现问题。

首先，对数据库存储的容量要求越来越高，单机无法满足需求，很多时候需要用集群来解决问题，而RDBMS由于要支持join，union等操作，一般不支持分布式集群。
其次，在大数据大行其道的今天，很多的数据都“频繁读和增加，不频繁修改”，而RDBMS对所有操作一视同仁，这就带来了优化的空间。
另外，互联网时代业务的不确定性导致数据库的存储模式也需要频繁变更，不自由的存储模式增大了运维的复杂性和扩展的难度。

现在的大数据的特点是，数据维度比较多（宽行），但是每一行数据的却并不是所有信息都具备的，于是就形成稀疏矩阵。如果采取过去的存储方式的话，将会浪费大量的空间，在存储时，需要将没有数据内容置空等（这里的置空也是需要消耗存储空间的，并且也会增加寻址的时间），在小数据量的情况下，这样也没有什么劣势，但是到了大数据情况下，积少成多，便变得明显了起来。

传统的关系型数据库还存在以下缺点：

大数据场景下 I/O 较高 - 因为数据是按行存储，即使只针对其中某一列进行运算，关系型数据库也会将整行数据从存储设备中读入内存，导致 I/O 较高。
存储的是行记录，无法存储数据结构。
表结构 schema 扩展不方便 - 如要需要修改表结构，需要执行执行 DDL(data definition language)，语句修改，修改期间会导致锁表，部分服务不可用。
存储和处理复杂关系型数据功能较弱 - 许多应用程序需要了解和导航高度连接数据之间的关系，才能启用社交应用程序、推荐引擎、欺诈检测、知识图谱、生命科学和 IT/网络等用例。然而传统的关系数据库并不善于处理数据点之间的关系。它们的表格数据模型和严格的模式使它们很难添加新的或不同种类的关联信息。

理论基础

分布式系统

分布式系统的核心理念是让多台服务器协同工作，完成单台服务器无法处理的任务，尤其是高并发或者大数据量的任务。分布式是NoSQL数据库的必要条件。

分布式系统由独立的服务器通过网络松散耦合组成的。每个服务器都是一台独立的PC机，服务器之间通过内部网络连接，内部网络速度一般比较快。因为分布式集群里的服务器是通过内部网络松散耦合，各节点之间的通讯有一定的网络开销，因此分布式系统在设计上尽可能减少节点间通讯。此外，因为网络传输瓶颈，单个节点的性能高低对分布式系统整体性能影响不大。

因此，分布式系统每个节点一般不采用高性能的服务器，而是使用性能相对一般的普通PC服务器。提升分布式系统的整体性能是通过横向扩展（增加更多的服务器），而不是纵向扩展（提升每个节点的服务器性能）实现。

分布式系统最大的特点是可扩展性，它能够适应需求变化而扩展。

CAP理论与BASE理论

关系型数据库一般为了保证事务可靠，需要具备ACID四个特性。ACID，是指数据库管理系统（DBMS）在写入或更新资料的过程中，为保证事务（transaction）是正确可靠的，所必须具备的四个特性：原子性（atomicity，或称不可分割性）、一致性（consistency）、隔离性（isolation，又称独立性）、持久性（durability）。

NoSQL的基本需求就是支持分布式存储，严格一致性与可用性需要互相取舍，由此延伸出了CAP理论来定义分布式存储遇到的问题。CAP理论告诉我们：一个分布式系统不可能同时满足一致性(C:Consistency)、可用性(A:Availability)、分区容错性(P:Partitiontolerance)这三个基本需求，并且最多只能满足其中的两项。

C – Consistency – 一致性（与ACID的C完全不同，那里的C是保证数据库数据之间规则没有被破坏）

一致性是指“all nodes see the same data at the same time”，即更新操作成功并返回客户端完成后，所有节点在同一时间的数据完全一致。对于一致性，可以分为从客户端和服务端两个不同的视角。

从客户端来看，一致性主要指的是多并发访问时更新过的数据如何获取的问题。
从服务端来看，则是更新如何复制分布到整个系统，以保证数据最终一致。一致性是因为有并发读写才有的问题，因此在理解一致性的问题时，一定要注意结合考虑并发读写的场景。
从客户端角度，多进程并发访问时，更新过的数据在不同进程如何获取的不同策略，决定了不同的一致性。对于关系型数据库，要求更新过的数据能被后续的访问都能看到，这是强一致性。如果能容忍后续的部分或者全部访问不到，则是弱一致性。如果经过一段时间后要求能访问到更新后的数据，则是最终一致性。

A – Availability – 可用性

可用性是指“Reads and writes always succeed”，即服务一直可用，而且是正常响应时间。

对于一个可用性的分布式系统，每一个非故障的节点必须对每一个请求作出响应。也就是说，该系统使用的任何算法必须最终终止。当同时要求分区容忍性时，这是一个很强的定义：即使是严重的网络错误，每个请求必须完成。

好的可用性主要是指系统能够很好的为用户服务，不出现用户操作失败或者访问超时等用户体验不好的情况。在通常情况下，可用性与分布式数据冗余、负载均衡等有着很大的关联。

P – Partition tolerance – 分区容错性

分区容错性是指“the system continues to operate despite arbitrary message loss or failureof part of the system”，即分布式系统在遇到某节点或网络分区故障的时候，仍然能够对外提供满足一致性和可用性的服务。

分区容错性和扩展性紧密相关。在分布式应用中，可能因为一些分布式的原因导致系统无法正常运转。好的分区容错性要求能够使应用虽然是一个分布式系统，但看上去却好像是一个可以运转正常的整体。比如现在的分布式系统中有某一个或者几个机器宕掉了，其它剩下的机器还能够正常运转满足系统需求，或者是机器之间有网络异常，将分布式系统分隔成未独立的几个部分，各个部分还能维持分布式系统的运作，这样就具有好的分区容错性。

CA without P

如果不要求P（不允许分区），则C（强一致性）和A（可用性）是可以保证的。但其实分区不是你想不想的问题，而是始终会存在，因此CA的系统更多的是允许分区后各子系统依然保持CA。

CP without A

如果不要求A（可用），相当于每个请求都需要在Server之间强一致，而P（分区）会导致同步时间无限延长，如此CP也是可以保证的。很多传统的数据库分布式事务都属于这种模式。

AP without C

要高可用并允许分区，则需放弃一致性。一旦分区发生，节点之间可能会失去联系，为了高可用，每个节点只能用本地数据提供服务，而这样会导致全局数据的不一致性。现在众多的NoSQL都属于此类。

CAP理论定义了分布式存储的根本问题，但并没有指出一致性和可用性之间到底应该如何权衡。于是出现了BASE理论，给出了权衡A与C的一种可行方案。

权衡一致性与可用性 - BASE理论

Base = Basically Available + Soft state + Eventually consistent 基本可用性+软状态+最终一致性，由eBay架构师DanPritchett提出。Base是对CAP中一致性A和可用性C权衡的结果，源于提出者自己在大规模分布式系统上实践的总结。核心思想是无法做到强一致性，但每个应用都可以根据自身的特点，采用适当方式达到最终一致性。

BA - Basically Available - 基本可用

基本可用。这里是指分布式系统在出现故障的时候，允许损失部分可用性，即保证核心功能或者当前最重要功能可用。对于用户来说，他们当前最关注的功能或者最常用的功能的可用性将会获得保证，但是其他功能会被削弱。

S – Soft State - 软状态

允许系统数据存在中间状态，但不会影响到系统的整体可用性，即允许系统在不同节点的数据副本之间进行数据同步时存在延时。

E - Eventually Consistent - 最终一致性

要求系统数据副本最终能够一致，而不需要实时保证数据副本一致。最终一致性是弱一致性的一种特殊情况。

总结：保证核心功能可用+允许同步延时（中间状态）+节点数据最终一致

一致性算法

在一个分布式数据库系统中，如果各节点的初始状态一致，每个节点执行相同的操作序列，那么他们最后能得到一个一致的状态。

通信

节点之间需要进行操作指令的同步，存在两种模型：

共享内存
消息传递

分区

原来所有的数据都是在一个数据库上的，网络IO及文件IO都集中在一个数据库上的，因此CPU、内存、文件IO、网络IO都可能会成为系统瓶颈。而分区的方案就是把某一个表或某几个相关的表的数据放在一个独立的数据库上，这样就可以把CPU、内存、文件IO、网络IO分解到多个机器中，从而提升系统处理能力。

分片

分区有两种模式，一种是主从模式，用于做读写分离；另外一种模式是分片模式，也就是说把一个表中的数据分解到多个表中。一个分区只能是其中的一种模式，要么主从（副本），一个读一个写；要么分片，把数据分解。

一致性哈希

将数据分离后，需要映射到不同的节点上，可用使用一致性哈希，允许动态扩展，每个节点仅需要维护少量相邻节点的信息。

优缺点

关系型数据库的优势：

便于理解：二维表构造非常贴近逻辑；
应用方便：支持通用的SQL（结构化查询语言）语句；
易于维护：全部由表结构组成，文件格式一致；
事务管理：促使针对安全性性能很高的数据信息浏览规定得到完成。

关系型数据库存在的不足

读写性能差，尤其是海量信息的效率高读写能力；
格式不灵活，固定不动的表构造；
高并发读写时，硬盘I/O存在瓶颈；
可扩展性不足，不像web server和app server那样简单的添加硬件和服务节点来拓展性能和负荷工作能力（数据之间耦合度高，不易扩展）

非关系型数据库的优点

格式灵活：数据存储格式非常多样，应用领域广泛，而关系型数据库则只适用基础的关系模型。
性能优越：NOSQL得益于无关系性，数据结构简单，NoSQL的Cache是记录级的，是一种细粒度的Cache。一般MySQL使用Query Cache，每次表更新Cache就失效，是一种大粒度的Cache，针对web2.0的交互频繁的应用，Cache性能不高。
可扩展性：数据之间无关系，数据之间耦合度极低，因此容易水平扩展。
低成本：非关系型数据库部署简易，且大部分可以开源使用。
高可用：NoSQL在不太影响性能的情况下，就可以方便地实现高可用的架构。

非关系型数据库的不足：

不支持sql，学习和运用成本比较高；
特性不够丰富，产品不够成熟。
不支持事务。

关系型与非关系型数据库的区别：

成本：Nosql数据库易部署，不用像Oracle那般花费较高成本选购。
查询速率：Nosql数据库将数据储存于缓存当中，不用历经SQL层的分析；关系型数据库将数据储存在电脑硬盘中，查询速率远不如Nosql数据库。
储存格式：Nosql的储存文件格式是key,value方式、文本文档方式、照片方式这些，能储存的对象种类灵活；关系数据库则只适用基础类型。
可扩展性：关系型数据库有join那样的多表查询机制限定造成拓展性较差。Nosql依据键值对，数据中间沒有耦合度，因此容易水平拓展。
数据一致性：非关系型数据库注重最终一致性；关系型数据库注重数据整个生命周期的强一致性。
事务处理：SQL数据库支持事务原子性粒度控制，且方便进行事务回滚；NoSQL也支持事务处理，但可靠性不足，其价值在于可扩展性和大数据量处理。

NoSQL与SQL的对比

	RDBMS	NoSQL
模式	预定义的模式	没有预定义的模式
查询语言	结构化查询语言（SQL）	没有声明性查询语言
一致性	严格的一致性	最终一致性
事务	支持	不支持
理论基础	ACID	CAP, BASE
扩展	纵向扩展	横向扩展(分布式)

K-V数据库

K-V 数据库特性

用一个key标识一行数据（一个数据实例）。
在一行数据的列部分，每个列的数据都包含元数据（键），数据（值），时间戳（为了某些其他目的，非必须）。

优点如下：

避免造成数据表稀疏矩阵，高效利用空间。
大数据时代需求变化快，能灵活更改结构。比如新增一个属性，传统数据库模型需要对表中所有行同时增加一列（不需要的置空或者默认），而kv存储只需要在列族中添加一个列信息，找到要修改的一行即可。

缺点如下：

针对 ACID，Redis 事务不能支持原子性和持久性(A 和 D)，只支持隔离性和一致性(I 和 C)
特别说明一下，这里所说的无法保证原子性，是针对 Redis 的事务操作，因为事务是不支持回滚（roll back），而因为 Redis 的单线程模型，Redis 的普通操作是原子性的。

大部分业务不需要严格遵循 ACID 原则，例如游戏实时排行榜，粉丝关注等场景，即使部分数据持久化失败，其实业务影响也非常小。因此在设计方案时，需要根据业务特征和要求来做选择

K-V 数据库使用场景

适用场景 - 储存用户信息(比如会话)、配置文件、参数、购物车等等。这些信息一般都和 ID（键）挂钩。
不适用场景
需要通过值来查询，而不是键来查询。Key-Value 数据库中根本没有通过值查询的途径。
需要储存数据之间的关系。在 Key-Value 数据库中不能通过两个或以上的键来关联数据
需要事务的支持。在 Key-Value 数据库中故障产生时不可以进行回滚。

Redis存储简单介绍

redis快的原因

单线程的处理机制

一个主线程负责读写数据，其他附属的线程负责维护 Redis 服务的稳定，单线程的一个好处就是没有线程资源竞争的问题，采用多线程开发一般会引入同步原语来保护共享资源的并发访问，这也会降低系统代码的易调试性和可维护性。为了避免这些问题，Redis 直接采用了单线程模式。Redis 6.0 支持了多线程，具体大家可以自行了解。

io 的多路复用模型

使用了 epoll 多路复用的模型，该机制允许内核中，同时存在多个监听套接字和已连接套接字。内核会一直监听这些套接字上的连接请求或数据请求。一旦有请求到达，就会交给 Redis 线程处理，这就实现了一个 Redis 线程处理多个 IO 流的效果，本质上就是通过事件监听的方式，如果有个连接没有请求，那就进入休眠状态，让出时间片，等待被激活。

优秀的底层数据结构

一个好的数据存储结构决定了一半的性能，Redis 底层实现了多种数据结构，包括简单动态字符串（SNS)，压缩列表，双向链表，哈希表，跳表，整形数组等底层数据结构，当然它也同样支持我们将自己实现的数据结构也添加到底层中，Redis 会根据性能来判断选择使用哪一个数据结构作为存储，并作自动转换，除了字符串类型统一使用了SNS,其他的类型（list，hash, set ,sortset )均有两种底层结构的支持

基于内存的读写

Redis 是直接读写内存中的数据的，我们知道只有内存中的数据才能够被程序使用，很多存储都有基于内存的优化策略，像 MySQL 的buffer机制，有效的利用内存，可以减少大量的磁盘随机 io 读取，毕竟从文件中读取数据到内存是一个十分消耗性能的操作，为了数据的稳定，Redis 也提供了 RDB 和 AOF 机制，来保证数据的稳定性

过期删除

过期数据的清除从来不容易，为每一条key设置一个timer，到点立刻删除的消耗太大，每秒遍历所有数据消耗也大，Redis使用了一种相对务实的做法：当client主动访问key会先对key进行超时判断，过时的key会立刻删除。

如果clien永远都不再get那条key呢？它会在Master的后台，每秒10次的执行如下操作： 随机选取100个key校验是否过期，如果有25个以上的key过期了，立刻额外随机选取下100个key。

存储原理

存储结构

Redis 的存储方式使用的是散列表（哈希桶）的形式。

redis的存储结构从外层往内层依次是redisDb、dict、dictht、dictEntry。
redis的Db默认情况下有16个，每个redisDb内部包含一个dict的数据结构。
redis的dict内部包含dictht的数组，数组个数为2，主要用于hash扩容使用。
dictht内部包含dictEntry的数组，可以理解就是hash的桶，然后如果冲突通过挂链法解决。

整体架构如下：

dict是一个用于维护key和value映射关系的数据结构，底层用来存数据的hash表 2个， dictht。至于为什么是2个，主要涉及到hash表的扩容和缩容。
dictht 定义了一个hash表的结构，表中保存的是指向dictEntry的指针。如果产生了hash冲突，这些dictEntry会采用链表的方式使用next指针来连接。
dictEntry是redis中key和value的结合。
- key是字符串，但是Redis没有直接使用C的字符数组，而是存储在自定义的SDS中。同一个桶中key是不一样的，key要保存起来作为rehash的根据。
- value既不是直接作为字符串存储，也不是直接存储在SDS中，而是存储在redisObject中。实际上五种常用的数据类型的任何一种，都是通过redisObject来存储的。

SDS

为什么Redis要用SDS实现字符串？

C语言本身没有字符串类型（只能用字符数组char[]实现）。

1、使用字符数组必须先给目标变量分配足够的空间，否则可能会溢出。

2、如果要获取字符长度，必须遍历字符数组，时间复杂度是O(n)。

3、C字符串长度的变更会对字符数组做内存重分配。

4、通过从字符串开始到结尾碰到的第一个’\0’来标记字符串的结束，因此不能保存图片、音频、视频、压缩文件等二进制(bytes)保存的内容，二进制不安全。

SDS的特点：

1、不用担心内存溢出问题，如果需要会对SDS进行扩容。

2、获取字符串长度时间复杂度为O(1)，因为定义了len属性。

3、通过“空间预分配”（sdsMakeRoomFor）和“惰性空间释放”，防止多次重分配内存。

4、判断是否结束的标志是len属性（它同样以’\0’结尾是因为这样就可以使用C语言中函数库操作字符串的函数了），可以包含’\0’。

redisObject

redisObject 是 Redis 类型系统的核心, 数据库中的每个键、值, 以及 Redis 本身处理的参数, 都表示为这种数据类型。比如list，set, hash等redis支持的数据类型，在底层都会以redisObject的方式来存储。

typedef struct redisObject {
    unsigned type:4;  
    unsigned encoding:4;
    
    unsigned lru:LRU_BITS; 
    int refcount;	
    void *ptr;
} robj;

type: 4位，表示具体的数据类型，比如String, Hash, List, Set, Sorted Set等。

encoding: 表示该值具体的编码方式或使用的数据结构，比如sds，压缩列表， hash表等

lru：最近一次被访问的时间。用于通过LRU算法进行内存淘汰的时候使用

refcount：对象引用计数

ptr：指向真正数据的指针，在我们通过key获取value时，其实最终就是通过这个ptr指针找到真正的数据。

数据类型

扩容与缩容

rehash

当存在冲突的时候，会将对应的冲突实体放在一起搞成一个链表，此时哈希桶的指针会增加一个next 指针，用来指向下一个冲突实体，当数据量足够大的时候，这个链表可能会被拉的越来越长，因为链表的查询只能从头结点开始遍历下去，也就是 O(n) 的复杂度(n为链表长度)，所以当链表过长时，会影响最终的查询速度。所以这时候不能袖手旁观。

因此，在这种情况下，Redis 会有另外一个线程专门去处理。我们称这种方式为 rehash ，和很多语言的数组底层一样，这种rehash 机制也是基于复制状态机的，说白了就是申请另一块空间（通常是原来的两倍），然后把数据信息复制过去，再释放原来的空间。通常来说程序不会快死的时候才想着救自己，当数值达到预警值时，就会开始自救，我们常常将其称之为装填因子，计算方式十分的简单，就是 use/total, 不同的存储对装填因子的判断规则不同，内容也比较底层，这里我们就不展开叙述了。

所以在 Redis 中，会存在另一张全局哈希表，其实它就是一个备胎，每次需要拓容的时候，这个备胎往往空间要比原配更大，rehash 线程会将原配的数据复制到备胎中，然后备胎就可以转正了。但是在复制的过程中，会有两个问题，一个是内存占用率会突然飙升，另一个就是Redis 阻塞的问题，复制的操作又耗时又耗空间，因此我们还需要更加聪明一点，能不能让一次的操作分成多步呢？温水煮青蛙听过没，如果每次来一个请求我就迁徙一点，这样的话，是不是慢慢的我就复制完了。这就是 Redis 的渐进式 rehash。

渐进式rehash

假设我要取 key 为 csdn 的 value ，而通过hash 算法得到的索引位置为 1，但是该索引上有一个三个 entry, 此时处理的线程正常的去遍历这个链表拿到真正正确的值，此时 rehash进程顺便把这个索引的 entry 从 ht0 复制到 ht1 中。并且释放 ht0 该索引的空间。

JySama

NoSQL和K-V存储简介

背景