關(guān)系型數(shù)據(jù)庫和非關(guān)系型數(shù)據(jù)庫
在絕大部分時候甘苍，我們都會首先考慮用關(guān)系型數(shù)據(jù)庫來存儲我們的數(shù)據(jù)尝蠕，比如 SQLServer，Oracle载庭，MySQL 等等看彼。
關(guān)系型數(shù)據(jù)庫
關(guān)系型數(shù)據(jù)庫的特點:
- 它以表格的形式，基于行存儲數(shù)據(jù)囚聚，是一個二維的模式靖榕。
- 它存儲的是結(jié)構(gòu)化的數(shù)據(jù)，數(shù)據(jù)存儲有固定的模式(schema)顽铸，數(shù)據(jù)需要適應(yīng)
表結(jié)構(gòu)茁计。 - 表與表之間存在關(guān)聯(lián)。
- 大部分關(guān)系型數(shù)據(jù)庫都支持 SQL(結(jié)構(gòu)化查詢語言)的操作谓松，支持復(fù)雜的關(guān)聯(lián)查
詢星压。 - 通過支持事務(wù)(ACID 酸)來提供嚴格或者實時的數(shù)據(jù)一致性践剂。
關(guān)系型數(shù)據(jù)庫也存在一些限制:
- 要實現(xiàn)擴容的話，只能向上(垂直)擴展娜膘，比如磁盤限制了數(shù)據(jù)的存儲逊脯，就要擴 大磁盤容量，通過堆硬件的方式竣贪，不支持動態(tài)的擴縮容军洼。水平擴容需要復(fù)雜的技術(shù)來實 現(xiàn)，比如分庫分表演怎。
- 表結(jié)構(gòu)修改困難匕争，因此存儲的數(shù)據(jù)格式也受到限制。
- 在高并發(fā)和高數(shù)據(jù)量的情況下颤枪，我們的關(guān)系型數(shù)據(jù)庫通常會把數(shù)據(jù)持久化到磁盤汗捡， 基于磁盤的讀寫壓力比較大。
ACID畏纲，是指數(shù)據(jù)庫管理系統(tǒng)（DBMS）在寫入或更新資料的過程中扇住，為保證事務(wù)（transaction）是正確可靠的，所必須具備的四個特性：原子性（atomicity盗胀，或稱不可分割性）艘蹋、一致性（consistency）、隔離性（isolation票灰，又稱獨立性）女阀、持久性（durability）。
非關(guān)系型數(shù)據(jù)庫
為了規(guī)避關(guān)系型數(shù)據(jù)庫的一系列問題屑迂，我們就有了非關(guān)系型的數(shù)據(jù)庫浸策，我們一般把 它叫做“non-relational”或者“Not Only SQL”。NoSQL 最開始是不提供 SQL 的數(shù) 據(jù)庫的意思惹盼，但是后來意思慢慢地發(fā)生了變化庸汗。
非關(guān)系型數(shù)據(jù)庫的特點:
- 存儲非結(jié)構(gòu)化的數(shù)據(jù)，比如文本手报、圖片蚯舱、音頻、視頻掩蛤。
- 表與表之間沒有關(guān)聯(lián)枉昏，可擴展性強。
- 保證數(shù)據(jù)的最終一致性揍鸟。遵循 BASE(堿)理論兄裂。 Basically Available(基本
可用); Soft-state(軟狀態(tài)); Eventually Consistent(最終一致性)。 - 支持海量數(shù)據(jù)的存儲和高并發(fā)的高效讀寫。
- 支持分布式懦窘，能夠?qū)?shù)據(jù)進行分片存儲前翎，擴縮容簡單。
BASE理論：BASE是對CAP中一致性和可用性權(quán)衡的結(jié)果畅涂，其來源于對大規(guī)母刍互聯(lián)網(wǎng)分布式系統(tǒng)實踐的總結(jié)，是基于CAP定律逐步演化而來午衰。其核心思想是即使無法做到強一致性立宜，但每個應(yīng)用都可以根據(jù)自身業(yè)務(wù)特點，才用適當(dāng)?shù)姆绞絹硎瓜到y(tǒng)打到最終一致性臊岸。
Redis的數(shù)據(jù)類型
- String
- Hash
- Set
- Zset
- List
- Hyperloglog
- Geo
- Streams
Redis的存儲結(jié)構(gòu)
Redis 是 KV 的數(shù)據(jù)庫橙数，它是通過 hashtable 實現(xiàn)的(我 們把這個叫做外層的哈希)。所以每個鍵值對都會有一個 dictEntry帅戒。里面指向了 key 和 value 的指針灯帮。next 指向下一個 dictEntry。
dictEntry
typedef struct dictEntry {
void *key; /* key 關(guān)鍵字定義 */
void *val;/* value 定義 */
struct dictEntry *next;/* 指向下一個鍵值對節(jié)點 */
} dictEntry;
在每個dictEntry中逻住，key 是以SDS存儲钟哥，val則是以redisObject形式存儲的。而redisObject存儲實際值也是通過SDS存儲的瞎访。
redisObject
typedef struct redisObject {
unsigned type:4;/*類型*/
unsigned encoding:4;/*編碼*/
// 對象最后一次被訪問的時間(用于進行LRU算法)
unsigned lru:REDIS_LRU_BITS; /* lru time (relative to server.lruclock) */
int refcount;/*引用計數(shù) 當(dāng) refcount 為 0 的時候腻贰，表示該對象已經(jīng)不被任何對象引用，則可以進行垃圾回收了*/
void *ptr;/*指向?qū)嶋H值的指針*/
} robj;
SDS是真正存儲數(shù)據(jù)的結(jié)構(gòu)扒秸，使用字符數(shù)組 char[]實現(xiàn)播演。
SDS的特點：
- 不用擔(dān)心內(nèi)存溢出問題，如果需要會對 SDS 進行擴容伴奥。
sdsMakeRoomFor()方法則可以對已有的sds進行擴容。 - 獲取字符串長度時間復(fù)雜度為 O(1)顶霞，因為定義了 len 屬性锣吼。
- 判斷是否結(jié)束的標志是 len 屬性。
- 通過“空間預(yù)分配”( sdsMakeRoomFor)和“惰性空間釋放”蓝厌，防止多次重分配內(nèi)存。
SDS
struct __attribute__ ((__packed__)) sdshdr8 {
uint8_t len; /* 獲取字段長度 */
uint8_t alloc;/*當(dāng)前字符數(shù)組總共分配的內(nèi)存大小 */
unsigned char flags;/* 當(dāng)前字符數(shù)組的屬性拓提、用來標識到底是 sdshdr8 還是 sdshdr16 等 */
char buf[];/* 字符串真正的值 */
String
存儲類型
可以用來存儲字符串、整數(shù)、浮點數(shù)寺惫。
存儲(實現(xiàn))原理
字符串類型的內(nèi)部編碼有三種:
1疹吃、int西雀，存儲 8 個字節(jié)的長整型(long，2^63-1)腔呜。
2再悼、embstr, 代表 embstr 格式的 SDS(Simple Dynamic String 簡單動態(tài)字符串)，
存儲小于 44 個字節(jié)的字符串谤草。
3莺奸、raw，存儲大于 44 個字節(jié)的字符串嚎杨。
embstr和raw的區(qū)別
embstr 的使用只分配一次內(nèi)存空間(因為 RedisObject 和 SDS 是連續(xù)的)氧腰，而 raw 需要分配兩次內(nèi)存空間(分別為 RedisObject 和 SDS 分配空間)古拴。
embstr和raw 底層都是sdshdr結(jié)構(gòu)體，但是在創(chuàng)建的時候只調(diào)用了一次zmalloc紧帕，而RAW編碼則會調(diào)用兩次桅打。因此，EMBSTR是將redisObject和sdshdr存放到一塊連續(xù)的內(nèi)存空間中去了鹅搪。
因此與 raw 相比丽柿，embstr 的好處在于創(chuàng)建時少分配一次空間，刪除時少釋放一次 空間馁筐，以及對象的所有數(shù)據(jù)連在一起坠非，尋找方便。
而 embstr 的壞處也很明顯赦抖，如果字符串的長度增加需要重新分配內(nèi)存時辅肾，整個RedisObject 和 SDS 都需要重新分配空間矫钓，因此 Redis 中的 embstr 實現(xiàn)為只讀。
Hash
存儲類型
Hash 本身也是一個 KV 的結(jié)構(gòu),外層的哈希(Redis KV 的實現(xiàn))只用到了 hashtable赵辕。當(dāng)存儲 hash 數(shù)據(jù)類型時概龄， 我們把它叫做內(nèi)層的哈希。內(nèi)層的哈希底層可以使用兩種數(shù)據(jù)結(jié)構(gòu)實現(xiàn)：ziplist 和 hashTable蚕键。
ziplist 壓縮列表
Ziplist 是為了盡可能地節(jié)約內(nèi)存而設(shè)計的特殊編碼雙端鏈表锣光。它不存儲指向上一個鏈表節(jié)點和指向下一 個鏈表節(jié)點的指針铝耻，而是存儲上一個節(jié)點長度和當(dāng)前節(jié)點長度，通過犧牲部分讀寫性能频丘， 來換取高效的內(nèi)存空間利用率泡态，是一種時間換空間的思想兽赁。只用在字段個數(shù)少，字段值小的場景里面惊科。ziplist在內(nèi)存中是連續(xù)存儲的亮钦，利用內(nèi)存的連續(xù)性可以方便查找下一個節(jié)點蜂莉，不需要和鏈表一樣存儲下一個節(jié)點的屬性。
ziplist結(jié)構(gòu)
zlbytes ：是一個無符號整數(shù)窖张，保存著 ziplist 使用的內(nèi)存數(shù)量宿接，通過這個值辕录，程序可以直接對 ziplist 的內(nèi)存大小進行調(diào)整。
zltail：保存著到達列表中最后一個節(jié)點的偏移量,這個偏移量使得對表尾的 pop 操作可以在無須遍歷整個列表的情況下進行副女。
zllen: 保存著列表中的節(jié)點數(shù)量碑幅。
typedef struct zlentry {
unsigned int prevrawlensize; /* 上一個鏈表節(jié)點占用的長度 */
unsigned int prevrawlen;/* 存儲上一個鏈表節(jié)點的長度數(shù)值所需要的字節(jié)數(shù) */
unsigned int lensize; /* 存儲當(dāng)前鏈表節(jié)點長度數(shù)值所需要的字節(jié)數(shù) */
unsigned int len;/* 當(dāng)前鏈表節(jié)點占用的長度 */
unsigned int headersize; /* 當(dāng)前鏈表節(jié)點的頭部大小(prevrawlensize + lensize)姻锁，即非數(shù)據(jù)域的大小 */
unsigned char encoding; /* 編碼方式 */
unsigned char *p;/* 壓縮鏈表以字符串的形式保存位隶，該指針指向當(dāng)前節(jié)點起始位置 */
} zlentry;
每個 ziplist 節(jié)點都包含兩部分信息：
- 前置節(jié)點的長度，在程序從后向前遍歷時使用篮昧。
- 當(dāng)前節(jié)點所保存的值的類型和長度笋妥。
Hashtable結(jié)構(gòu)(dict)
在 Redis 中，hashtable 被稱為字典(dictionary)酵颁，它是一個數(shù)組+鏈表的結(jié)構(gòu)躏惋。
Redis 的 KV 結(jié)構(gòu)是通過一個 dictEntry 來實現(xiàn)的，而hashtable 是對這個dictEntry進行多層的封裝距误。
dict--dictht--dictEntry
typedef struct dictEntry {
void *key; /* key 關(guān)鍵字定義 */
void *val;/* value 定義 */
struct dictEntry *next;/* 指向下一個鍵值對節(jié)點 */
} dictEntry;
typedef struct dictht {
dictEntry **table;/*哈希表數(shù)組*/
unsigned long size;// 哈希表大小
unsigned long sizemask; //哈希表大小掩碼扁位，用于計算索引值
unsigned long used; // 該哈希表已有節(jié)點的數(shù)量
} dictht;
typedef struct dict {
dictType *type; /* 字典類型 */
void *privdata; /* 私有數(shù)據(jù) */
dictht ht[2]; /* 一個字典有兩個哈希表 */
long rehashidx; /* rehash 索引 */
unsigned long iterators; /* 當(dāng)前正在使用的迭代器數(shù)量 */
} dict;
dictht 后面是 NULL 說明第二個 ht 還沒用到域仇。dictEntry*后面是 NULL 說明沒有 hash 到這個地址殉簸。dictEntry 后面是 NULL 說明沒有發(fā)生哈希沖突。
為什么dict字典中有兩個dictht結(jié)構(gòu)呢武鲁？
redis 的 hash 默認使用的是 ht[0]蝠检，ht[1]不會初始化和分配空間。
哈希表 dictht 是用鏈地址法來解決碰撞問題的饲梭。在這種情況下焰檩，哈希表的性能取決 于它的大小(size 屬性)和它所保存的節(jié)點的數(shù)量(used 屬性)之間的比率:
- 比率在 1:1 時(一個哈希表 ht 只存儲一個節(jié)點 entry)析苫，哈希表的性能最好;
- 如果節(jié)點數(shù)量比哈希表的大小要大很多的話(這個比例用 ratio 表示，5 表示平均
一個 ht 存儲 5 個 entry)国旷，那么哈希表就會退化成多個鏈表茫死，哈希表本身的性能
優(yōu)勢就不再存在峦萎。
在這種情況下需要擴容忆首。Redis 里面的這種操作叫做 rehash被环。
rehash 的步驟:
- 為字符 ht[1]哈希表分配空間蛤售，這個哈希表的空間大小取決于要執(zhí)行的操作妒潭，以
及 ht[0]當(dāng)前包含的鍵值對的數(shù)量雳灾。
擴展:ht[1]的大小為第一個大于等于 ht[0].used*2。 - 將所有的 ht[0]上的節(jié)點 rehash 到 ht[1]上炒嘲，重新計算 hash 值和索引匈庭，然后放
入指定的位置。 - 當(dāng) ht[0]全部遷移到了 ht[1]之后夭拌，釋放 ht[0]的空間鸽扁，將 ht[1]設(shè)置為 ht[0]表镶骗，
并創(chuàng)建新的 ht[1]，為下次 rehash 做準備骡和。
什么時候觸發(fā)擴容?:
負載因子ratio = used / size即横，已使用節(jié)點與字典大小的比例
dict_can_resize 為 1 并且 dict_force_resize_ratio 已使用節(jié)點數(shù)和字典大小之間的 比率超過 1:5裆赵，觸發(fā)擴容。
List
存儲(實現(xiàn))原理
quicklist
quicklist(快速列表)是 ziplist 和 linkedlist 的結(jié)合體页藻。
typedef struct quicklist {
quicklistNode *head; /* 指向雙向列表的表頭 */
quicklistNode *tail; /* 指向雙向列表的表尾 */
unsigned long count;/* 所有的 ziplist 中一共存了多少個元素 */
unsigned long len; /* 雙向鏈表的長度份帐，node 的數(shù)量 */
int fill : 16;/* fill factor for individual nodes */
unsigned int compress : 16; /* 壓縮深度，0:不壓縮; */
} quicklist;
quicklistNode 中的*zl 指向一個 ziplist畜挨，一個 ziplist 可以存放多個元素噩凹。
typedef struct quicklistNode {
struct quicklistNode *prev; /* 前一個節(jié)點 */
struct quicklistNode *next; /* 后一個節(jié)點 */
unsigned char *zl; /* 指向?qū)嶋H的 ziplist */
unsigned int sz; /* 當(dāng)前 ziplist 占用多少字節(jié) */
unsignedintcount:16;/* 當(dāng)前ziplist中存儲了多少個元素驮宴，占16bit(下同)，最大65536個*/ unsigned int encoding : 2; /* 是否采用了 LZF 壓縮算法壓縮節(jié)點修己，1:RAW 2:LZF */
unsigned int container : 2; /* 2:ziplist睬愤，未來可能支持其他結(jié)構(gòu)存儲 */
unsigned int recompress : 1; /* 當(dāng)前 ziplist 是不是已經(jīng)被解壓出來作臨時使用 */
unsigned int attempted_compress : 1; /* 測試用 */
unsigned int extra : 10; /* 預(yù)留給未來使用 */
} quicklistNode;
Set
存儲類型
String 類型的無序集合戴涝，最大存儲數(shù)量 2^32-1(40 億左右)钻蔑。
存儲(實現(xiàn))原理
Redis 用 intset 或 hashtable 存儲 set咪笑。如果元素都是整數(shù)類型，就用 inset 存儲映跟。 如果不是整數(shù)類型扬虚，就用 hashtable(數(shù)組+鏈表的存來儲結(jié)構(gòu))。
typedef struct intset {
uint32_t encoding; // 編碼方式
uint32_t length; //集合包含的元素數(shù)量
int8_t contents[];// 保存元素的數(shù)組
} intset;
ZSet 有序集合
存儲類型
sorted set荸镊，有序的 set躬存，每個元素有個 score。 score 相同時宛逗，按照 key 的 ASCII 碼排序盾剩。
存儲原理
同時滿足以下條件時使用 ziplist 編碼:
- 元素數(shù)量小于 128 個告私。
- 所有 member 的長度都小于 64 字節(jié)。
在 ziplist 的內(nèi)部，按照 score 排序遞增來存儲格嗅。插入的時候要移動之后的數(shù)據(jù)唠帝。
超過閾值之后襟衰，使用 skiplist+dict 存儲。
什么是 skiplist
skiplist.png
現(xiàn)在當(dāng)我們想查找數(shù)據(jù)的時候绍坝，可以先沿著這個新鏈表進行查找轩褐。當(dāng)碰到比待查數(shù) 據(jù)大的節(jié)點時玖详，再回到原來的鏈表中的下一層進行查找蟋座。比如，我們想查找 23巢墅，查找的路徑是先從最上層進行查找。
- 23首先和7比較作谚，再和19比較庵芭，比它們都大双吆，繼續(xù)向后比較。
- 但23和26比較的時候匾竿，比26要小蔚万，因此回到下面的鏈表(原鏈表)反璃，與22
比較。 - 23比22要大斋攀，沿下面的指針繼續(xù)向后和26比較淳蔼。23比26小裁眯，說明待查數(shù)
據(jù) 23 在原鏈表中不存在。
在這個查找過程中俯画，由于新增加的指針艰垂，我們不再需要與鏈表中每個節(jié)點逐個進行
比較了埋虹。需要比較的節(jié)點數(shù)大概只有原來的一半搔课。這就是跳躍表。
