《三次給你聊清楚Redis》之Redis是個(gè)啥
那么，準(zhǔn)備好了嗎？我們開始吧，先嘮嘮redis是個(gè)啥（18629字）。
一、入門
Redis是一款基于鍵值對的NoSQL數(shù)據(jù)庫，它的值支持多種數(shù)據(jù)結(jié)構(gòu)：字符串(strings)、哈希(hashes)、列表(lists)、集合(sets)、有序集合(sorted sets)等。
? Redis將所有的數(shù)據(jù)都存放在內(nèi)存中，所以它的讀寫性能十分驚人，用作數(shù)據(jù)庫，緩存和消息代理。
Redis具有內(nèi)置的復(fù)制，Lua腳本，LRU逐出，事務(wù)和不同級別的磁盤持久性，并通過Redis Sentinel和Redis Cluster自動(dòng)分區(qū)提供了高可用性。
? Redis典型的應(yīng)用場景包括：緩存、排行榜、計(jì)數(shù)器、社交網(wǎng)絡(luò)、消息隊(duì)列等
1.1NoSql入門概述
1）單機(jī)Mysql的美好時(shí)代
瓶頸：
數(shù)據(jù)庫總大小一臺機(jī)器硬盤內(nèi)存放不下
數(shù)據(jù)的索引（B + tree）一個(gè)機(jī)器的運(yùn)行內(nèi)存放不下
訪問量（讀寫混合）一個(gè)實(shí)例不能承受
2）Memcached（緩存）+ MySql + 垂直拆分
通過緩存來緩解數(shù)據(jù)庫的壓力，優(yōu)化數(shù)據(jù)庫的結(jié)構(gòu)和索引
垂直拆分指的是：分成多個(gè)數(shù)據(jù)庫存儲數(shù)據(jù)（如：賣家?guī)炫c買家?guī)欤?/p>
3）MySql主從復(fù)制讀寫分離
主從復(fù)制：主庫來一條數(shù)據(jù)，從庫立刻插入一條。
讀寫分離：讀取（從庫Master），寫（主庫Slave）
4）分表分庫+水平拆分+MySql集群
主庫的寫壓力出現(xiàn)瓶頸（行鎖InnoDB取代表鎖MyISAM）
分庫：根據(jù)業(yè)務(wù)相關(guān)緊耦合在同一個(gè)庫，對不同的數(shù)據(jù)讀寫進(jìn)行分庫（如注冊信息等不常改動(dòng)的冷庫與購物信息等熱門庫分開）
分表：切割表數(shù)據(jù)（例如90W條數(shù)據(jù)，id 1-30W的放在A庫，30W-60W的放在B庫，60W-90W的放在C庫）
MySql擴(kuò)展的瓶頸
大數(shù)據(jù)下IO壓力大
表結(jié)構(gòu)更改困難
常用的Nosql
Redis
memcache
Mongdb
以上幾種Nosql 請到各自的官網(wǎng)上下載并參考使用
Nosql 的核心功能點(diǎn)
KV(存儲)
Cache(緩存)
Persistence(持久化)
……
1.2redis的介紹和特點(diǎn):
問題：
傳統(tǒng)數(shù)據(jù)庫：持久化存儲數(shù)據(jù)。
solr索引庫:大量的數(shù)據(jù)的檢索。
在實(shí)際開發(fā)中，高并發(fā)環(huán)境下，不同的用戶會(huì)需要相同的數(shù)據(jù)。因?yàn)槊看握埱螅?/p>
在后臺我們都會(huì)創(chuàng)建一個(gè)線程來處理，這樣造成，同樣的數(shù)據(jù)從數(shù)據(jù)庫中查詢了N次。
而數(shù)據(jù)庫的查詢本身是ＩＯ操作，效率低，頻率高也不好。
總而言之，一個(gè)網(wǎng)站總歸是有大量的數(shù)據(jù)是用戶共享的，但是如果每個(gè)用戶都去數(shù)據(jù)庫查詢
效率就太低了。
解決：
將用戶共享數(shù)據(jù)緩存到服務(wù)器的內(nèi)存中。
特點(diǎn)：
1、基于鍵值對
2、非關(guān)系型(redis)
關(guān)系型數(shù)據(jù)庫:存儲了數(shù)據(jù)以及數(shù)據(jù)之間的關(guān)系,oracle,mysql
非關(guān)系型數(shù)據(jù)庫:存儲了數(shù)據(jù),redis,mdb.
3、數(shù)據(jù)存儲在內(nèi)存中，服務(wù)器關(guān)閉后，持久化到硬盤中
4、支持主從同步
實(shí)現(xiàn)了緩存數(shù)據(jù)和項(xiàng)目的解耦。
redis存儲的數(shù)據(jù)特點(diǎn)：
大量數(shù)據(jù)
用戶共享數(shù)據(jù)
數(shù)據(jù)不經(jīng)常修改。
查詢數(shù)據(jù)
redis的應(yīng)用場景：
網(wǎng)站高并發(fā)的主頁數(shù)據(jù)
網(wǎng)站數(shù)據(jù)的排名
消息訂閱
1.3redis——數(shù)據(jù)結(jié)構(gòu)和對象的使用介紹
redis官網(wǎng)
微軟寫的windows下的redis
我們下載第一個(gè)
額案后基本一路默認(rèn)就行了
安裝后，服務(wù)自動(dòng)啟動(dòng)，以后也不用自動(dòng)啟動(dòng)。
出現(xiàn)這個(gè)表示我們連接上了。
redis命令參考鏈接
1.3.1String
數(shù)據(jù)結(jié)構(gòu)
struct sdshdr{ //記錄buf數(shù)組中已使用字節(jié)的數(shù)量 int len; //記錄buf數(shù)組中未使用的數(shù)量 int free; //字節(jié)數(shù)組，用于保存字符串 char buf[]; }
常見操作
127.0.0.1:6379> set hello world OK 127.0.0.1:6379> get hello "world" 127.0.0.1:6379> del hello (integer) 1 127.0.0.1:6379> get hello (nil) 127.0.0.1:6379>
應(yīng)用場景
String是最常用的一種數(shù)據(jù)類型，普通的key/value存儲都可以歸為此類，value其實(shí)不僅是String，也可以是數(shù)字：比如想知道什么時(shí)候封鎖一個(gè)IP地址（訪問超過幾次）。INCRBY命令讓這些變得很容易，通過原子遞增保持計(jì)數(shù)。
1.3.2LIST
數(shù)據(jù)結(jié)構(gòu)
typedef struct listNode{ //前置節(jié)點(diǎn) struct listNode *prev; //后置節(jié)點(diǎn) struct listNode *next; //節(jié)點(diǎn)的值 struct value; }
常見操作
> lpush list-key item (integer) 1 > lpush list-key item2 (integer) 2 > rpush list-key item3 (integer) 3 > rpush list-key item (integer) 4 > lrange list-key 0 -1 1) "item2" 2) "item" 3) "item3" 4) "item" > lindex list-key 2 "item3" > lpop list-key "item2" > lrange list-key 0 -1 1) "item" 2) "item3" 3) "item"
應(yīng)用場景
Redis list的應(yīng)用場景非常多，也是Redis最重要的數(shù)據(jù)結(jié)構(gòu)之一。
我們可以輕松地實(shí)現(xiàn)最新消息排行等功能。
Lists的另一個(gè)應(yīng)用就是消息隊(duì)列，可以利用Lists的PUSH操作，將任務(wù)存在Lists中，然后工作線程再用POP操作將任務(wù)取出進(jìn)行執(zhí)行。
1.3.3HASH
數(shù)據(jù)結(jié)構(gòu)
dictht是一個(gè)散列表結(jié)構(gòu)，使用拉鏈法保存哈希沖突的dictEntry。
typedef struct dictht{ //哈希表數(shù)組 dictEntry **table; //哈希表大小 unsigned long size; //哈希表大小掩碼，用于計(jì)算索引值 unsigned long sizemask; //該哈希表已有節(jié)點(diǎn)的數(shù)量 unsigned long used; } typedef struct dictEntry{ //鍵 void *key; //值 union{ void *val; uint64_tu64; int64_ts64; } struct dictEntry *next; }
Redis的字典dict中包含兩個(gè)哈希表dictht，這是為了方便進(jìn)行rehash操作。在擴(kuò)容時(shí)，將其中一個(gè)dictht上的鍵值對rehash到另一個(gè)dictht上面，完成之后釋放空間并交換兩個(gè)dictht的角色。
typedef struct dict { dictType *type; void *privdata; dictht ht[2]; long rehashidx; /* rehashing not in progress if rehashidx == -1 */ unsigned long iterators; /* number of iterators currently running */ } dict;
rehash操作并不是一次性完成、而是采用漸進(jìn)式方式，目的是為了避免一次性執(zhí)行過多的rehash操作給服務(wù)器帶來負(fù)擔(dān)。
漸進(jìn)式rehash通過記錄dict的rehashidx完成，它從0開始，然后沒執(zhí)行一次rehash例如在一次 rehash 中，要把 dict[0] rehash 到 dict[1]，這一次會(huì)把 dict[0] 上 table[rehashidx] 的鍵值對 rehash 到 dict[1] 上，dict[0] 的 table[rehashidx] 指向 null，并令 rehashidx++。
在 rehash 期間，每次對字典執(zhí)行添加、刪除、查找或者更新操作時(shí)，都會(huì)執(zhí)行一次漸進(jìn)式 rehash。
采用漸進(jìn)式rehash會(huì)導(dǎo)致字典中的數(shù)據(jù)分散在兩個(gè)dictht中，因此對字典的操作也會(huì)在兩個(gè)哈希表上進(jìn)行。
例如查找時(shí)，先從ht[0]查找，沒有再查找ht[1]，添加時(shí)直接添加到ht[1]中。
常見操作
> hset hash-key sub-key1 value1 (integer) 1 > hset hash-key sub-key2 value2 (integer) 1 > hset hash-key sub-key1 value1 (integer) 0 > hgetall hash-key 1) "sub-key1" 2) "value1" 3) "sub-key2" 4) "value2" > hdel hash-key sub-key2 (integer) 1 > hdel hash-key sub-key2 (integer) 0 > hget hash-key sub-key1 "value1" > hgetall hash-key 1) "sub-key1" 2) "value1"
1.3.4SET
常見操作
> sadd set-key item (integer) 1 > sadd set-key item2 (integer) 1 > sadd set-key item3 (integer) 1 > sadd set-key item (integer) 0 > smembers set-key 1) "item2" 2) "item" 3) "item3" > sismember set-key item4 (integer) 0 > sismember set-key item (integer) 1 > srem set-key item (integer) 1 > srem set-key item (integer) 0 > smembers set-key 1) "item2" 2) "item3"
應(yīng)用場景
Redis為集合提供了求交集、并集、差集等操作，故可以用來求共同好友等操作。
1.3.5ZSET
數(shù)據(jù)結(jié)構(gòu)
typedef struct zskiplistNode{ //后退指針 struct zskiplistNode *backward; //分值 double score; //成員對象 robj *obj; //層 struct zskiplistLever{ //前進(jìn)指針 struct zskiplistNode *forward; //跨度 unsigned int span; }lever[]; } typedef struct zskiplist{ //表頭節(jié)點(diǎn)跟表尾結(jié)點(diǎn) struct zskiplistNode *header, *tail; //表中節(jié)點(diǎn)的數(shù)量 unsigned long length; //表中層數(shù)最大的節(jié)點(diǎn)的層數(shù) int lever; }
跳躍表，基于多指針有序鏈實(shí)現(xiàn)，可以看作多個(gè)有序鏈表。
與紅黑樹等平衡樹相比，跳躍表具有以下優(yōu)點(diǎn)：
插入速度非?？焖?，因?yàn)椴恍枰M(jìn)行旋轉(zhuǎn)等操作來維持平衡性。
更容易實(shí)現(xiàn)。
支持無鎖操作。
常見操作
> zadd zset-key 728 member1 (integer) 1 > zadd zset-key 982 member0 (integer) 1 > zadd zset-key 982 member0 (integer) 0 > zrange zset-key 0 -1 1) "member1" 2) "member0" > zrange zset-key 0 -1 withscores 1) "member1" 2) "728" 3) "member0" 4) "982" > zrangebyscore zset-key 0 800 withscores 1) "member1" 2) "728" > zrem zset-key member1 (integer) 1 > zrem zset-key member1 (integer) 0 > zrange zset-key 0 -1 withscores 1) "member0" 2) "982"
應(yīng)用場景
以某個(gè)條件為權(quán)重，比如按頂?shù)拇螖?shù)排序
ZREVRANGE命令可以用來按照得分來獲取前100名的用戶，ZRANK可以用來獲取用戶排名，非常直接而且操作容易。
Redis sorted set的使用場景與set類似，區(qū)別是set不是自動(dòng)有序的，而sorted set可以通過用戶額外提供一個(gè)優(yōu)先級(score)的參數(shù)來為成員排序，并且是插入有序的，即自動(dòng)排序。
redis命令參考鏈接
1.4Spring整合Redis
引入依賴
- spring-boot-starter-data-redis
配置Redis
- 配置數(shù)據(jù)庫參數(shù)
# RedisProperties spring.redis.database=11#第11個(gè)庫，這個(gè)隨便 spring.redis.host=localhost spring.redis.port=6379#端口
- 編寫配置類，構(gòu)造RedisTemplate
這個(gè)springboot已經(jīng)幫我們配了，但是默認(rèn)object，我想改成string
import org.springframework.context.annotation.Bean; import org.springframework.context.annotation.Configuration; import org.springframework.data.redis.connection.RedisConnectionFactory; import org.springframework.data.redis.core.RedisTemplate; import org.springframework.data.redis.serializer.RedisSerializer; @Configuration public class RedisConfig { @Bean public RedisTemplate
訪問Redis
- redisTemplate.opsForValue()
- redisTemplate.opsForHash()
- redisTemplate.opsForList()
- redisTemplate.opsForSet()
- redisTemplate.opsForZSet()
@RunWith(SpringRunner.class) @SpringBootTest @ContextConfiguration(classes = CommunityApplication.class) public class RedisTests { @Autowired private RedisTemplate redisTemplate; @Test public void testStrings() { String redisKey = "test:count"; redisTemplate.opsForValue().set(redisKey, 1); System.out.println(redisTemplate.opsForValue().get(redisKey)); System.out.println(redisTemplate.opsForValue().increment(redisKey)); System.out.println(redisTemplate.opsForValue().decrement(redisKey)); } @Test public void testHashes() { String redisKey = "test:user"; redisTemplate.opsForHash().put(redisKey, "id", 1); redisTemplate.opsForHash().put(redisKey, "username", "zhangsan"); System.out.println(redisTemplate.opsForHash().get(redisKey, "id")); System.out.println(redisTemplate.opsForHash().get(redisKey, "username")); } @Test public void testLists() { String redisKey = "test:ids"; redisTemplate.opsForList().leftPush(redisKey, 101); redisTemplate.opsForList().leftPush(redisKey, 102); redisTemplate.opsForList().leftPush(redisKey, 103); System.out.println(redisTemplate.opsForList().size(redisKey)); System.out.println(redisTemplate.opsForList().index(redisKey, 0)); System.out.println(redisTemplate.opsForList().range(redisKey, 0, 2)); System.out.println(redisTemplate.opsForList().leftPop(redisKey)); System.out.println(redisTemplate.opsForList().leftPop(redisKey)); System.out.println(redisTemplate.opsForList().leftPop(redisKey)); } @Test public void testSets() { String redisKey = "test:teachers"; redisTemplate.opsForSet().add(redisKey, "劉備", "關(guān)羽", "張飛", "趙云", "諸葛亮"); System.out.println(redisTemplate.opsForSet().size(redisKey)); System.out.println(redisTemplate.opsForSet().pop(redisKey)); System.out.println(redisTemplate.opsForSet().members(redisKey)); } @Test public void testSortedSets() { String redisKey = "test:students"; redisTemplate.opsForZSet().add(redisKey, "唐僧", 80); redisTemplate.opsForZSet().add(redisKey, "悟空", 90); redisTemplate.opsForZSet().add(redisKey, "八戒", 50); redisTemplate.opsForZSet().add(redisKey, "沙僧", 70); redisTemplate.opsForZSet().add(redisKey, "白龍馬", 60); System.out.println(redisTemplate.opsForZSet().zCard(redisKey)); System.out.println(redisTemplate.opsForZSet().score(redisKey, "八戒")); System.out.println(redisTemplate.opsForZSet().reverseRank(redisKey, "八戒")); System.out.println(redisTemplate.opsForZSet().reverseRange(redisKey, 0, 2)); } @Test public void testKeys() { redisTemplate.delete("test:user"); System.out.println(redisTemplate.hasKey("test:user")); redisTemplate.expire("test:students", 10, TimeUnit.SECONDS); } }
這樣還是稍微有點(diǎn)麻煩，我們其實(shí)可以綁定key
// 多次訪問同一個(gè)key @Test public void testBoundOperations() { String redisKey = "test:count"; BoundValueOperations operations = redisTemplate.boundValueOps(redisKey); operations.increment(); operations.increment(); operations.increment(); operations.increment(); operations.increment(); System.out.println(operations.get()); }
二、數(shù)據(jù)結(jié)構(gòu)原理總結(jié)
這部分在我看來是最有意思的，我們有必要了解底層數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)，這也是我最感興趣的。
比如，你知道redis中的字符串怎么實(shí)現(xiàn)的嗎？為什么這么實(shí)現(xiàn)？
你知道redis壓縮列表是什么算法嗎？
你知道redis為什么拋棄了紅黑樹反而采用了跳表這種新的數(shù)據(jù)結(jié)構(gòu)嗎？
你知道hyperloglog為什么用如此小的空間就可以有這么好的統(tǒng)計(jì)性能和準(zhǔn)確性嗎？
你知道布隆過濾器為什么這么有效嗎？有沒有數(shù)學(xué)證明過？
你是否還能很快寫出來快排？或者不斷優(yōu)化性能的排序？是不是只會(huì)調(diào)庫了甚至庫函數(shù)怎么實(shí)現(xiàn)的都不知道？真的就是快排？
包括數(shù)據(jù)庫，持久化，處理事件、客戶端服務(wù)端、事務(wù)的實(shí)現(xiàn)、發(fā)布和訂閱等功能的實(shí)現(xiàn)，也需要了解。
2.1數(shù)據(jù)結(jié)構(gòu)和對象的實(shí)現(xiàn)
1） 字符串
redis并未使用傳統(tǒng)的c語言字符串表示，它自己構(gòu)建了一種簡單的動(dòng)態(tài)字符串抽象類型。
在redis里，c語言字符串只會(huì)作為字符串字面量出現(xiàn)，用在無需修改的地方。
當(dāng)需要一個(gè)可以被修改的字符串時(shí)，redis就會(huì)使用自己實(shí)現(xiàn)的SDS（simple dynamic string）。比如在redis數(shù)據(jù)庫里，包含字符串的鍵值對底層都是SDS實(shí)現(xiàn)的，不止如此，SDS還被用作緩沖區(qū)（buffer）：比如AOF模塊中的AOF緩沖區(qū)以及客戶端狀態(tài)中的輸入緩沖區(qū)。
下面來具體看一下sds的實(shí)現(xiàn)：
struct sdshdr { int len;//buf已使用字節(jié)數(shù)量（保存的字符串長度） int free;//未使用的字節(jié)數(shù)量 char buf[];//用來保存字符串的字節(jié)數(shù)組 };
sds遵循c中字符串以'
sds遵循c中字符串以'\0'結(jié)尾的慣例，這一字節(jié)的空間不算在len之內(nèi)。
'結(jié)尾的慣例，這一字節(jié)的空間不算在len之內(nèi)。這樣的好處是，我們可以直接重用c中的一部分函數(shù)。比如printf；
sds相對c的改進(jìn)
獲取長度：c字符串并不記錄自身長度，所以獲取長度只能遍歷一遍字符串，redis直接讀取len即可。
緩沖區(qū)安全：c字符串容易造成緩沖區(qū)溢出，比如：程序員沒有分配足夠的空間就執(zhí)行拼接操作。而redis會(huì)先檢查sds的空間是否滿足所需要求，如果不滿足會(huì)自動(dòng)擴(kuò)充。
內(nèi)存分配：由于c不記錄字符串長度，對于包含了n個(gè)字符的字符串，底層總是一個(gè)長度n+1的數(shù)組，每一次長度變化，總是要對這個(gè)數(shù)組進(jìn)行一次內(nèi)存重新分配的操作。因?yàn)閮?nèi)存分配涉及復(fù)雜算法并且可能需要執(zhí)行系統(tǒng)調(diào)用，所以它通常是比較耗時(shí)的操作。
redis內(nèi)存分配：
1、空間預(yù)分配：如果修改后大小小于1MB，程序分配和len大小一樣的未使用空間，如果修改后大于1MB，程序分配? 1MB的未使用空間。修改長度時(shí)檢查，夠的話就直接使用未使用空間，不用再分配。
2、惰性空間釋放：字符串縮短時(shí)不需要釋放空間，用free記錄即可，留作以后使用。
二進(jìn)制安全
c字符串除了末尾外，不能包含空字符，否則程序讀到空字符會(huì)誤以為是結(jié)尾，這就限制了c字符串只能保存文本，二進(jìn)制文件就不能保存了。
而redis字符串都是二進(jìn)制安全的，因?yàn)橛衛(wèi)en來記錄長度。
2） 鏈表
作為一種常用數(shù)據(jù)結(jié)構(gòu)，鏈表內(nèi)置在很多高級語言中，因?yàn)閏并沒有，所以redis實(shí)現(xiàn)了自己的鏈表。
鏈表在redis也有一定的應(yīng)用，比如列表鍵的底層實(shí)現(xiàn)之一就是鏈表。（當(dāng)列表鍵包含大量元素或者元素都是很長的字符串時(shí)）
發(fā)布與訂閱、慢查詢、監(jiān)視器等功能也用到了鏈表。
具體實(shí)現(xiàn)：
//redis的節(jié)點(diǎn)使用了雙向鏈表結(jié)構(gòu) typedef struct listNode { // 前置節(jié)點(diǎn) struct listNode *prev; // 后置節(jié)點(diǎn) struct listNode *next; // 節(jié)點(diǎn)的值 void *value; } listNode;
//其實(shí)學(xué)過數(shù)據(jù)結(jié)構(gòu)的應(yīng)該都實(shí)現(xiàn)過 typedef struct list { // 表頭節(jié)點(diǎn) listNode *head; // 表尾節(jié)點(diǎn) listNode *tail; // 鏈表所包含的節(jié)點(diǎn)數(shù)量 unsigned long len; // 節(jié)點(diǎn)值復(fù)制函數(shù) void *(*dup)(void *ptr); // 節(jié)點(diǎn)值釋放函數(shù) void (*free)(void *ptr); // 節(jié)點(diǎn)值對比函數(shù) int (*match)(void *ptr, void *key); } list;
總結(jié)一下redis鏈表特性：
雙端、無環(huán)、帶長度記錄、
多態(tài)：使用?void*?指針來保存節(jié)點(diǎn)值， 可以通過?dup?、?free?、?match?為節(jié)點(diǎn)值設(shè)置類型特定函數(shù)， 可以保存不同類型的值。
3）字典
其實(shí)字典這種數(shù)據(jù)結(jié)構(gòu)也內(nèi)置在很多高級語言中，但是c語言沒有，所以redis自己實(shí)現(xiàn)了。
應(yīng)用也比較廣泛，比如redis的數(shù)據(jù)庫就是字典實(shí)現(xiàn)的。不僅如此，當(dāng)一個(gè)哈希鍵包含的鍵值對比較多，或者都是很長的字符串，redis就會(huì)用字典作為哈希鍵的底層實(shí)現(xiàn)。
來看看具體是實(shí)現(xiàn)：
//redis的字典使用哈希表作為底層實(shí)現(xiàn) typedef struct dictht { // 哈希表數(shù)組 dictEntry **table; // 哈希表大小 unsigned long size; // 哈希表大小掩碼，用于計(jì)算索引值 // 總是等于 size - 1 unsigned long sizemask; // 該哈希表已有節(jié)點(diǎn)的數(shù)量 unsigned long used; } dictht;
table?是一個(gè)數(shù)組， 數(shù)組中的每個(gè)元素都是一個(gè)指向dictEntry?結(jié)構(gòu)的指針， 每個(gè)?dictEntry?結(jié)構(gòu)保存著一個(gè)鍵值對。
圖為一個(gè)大小為4的空哈希表。
我們接著就來看dictEntry的實(shí)現(xiàn)：
typedef struct dictEntry { // 鍵 void *key; // 值 union { void *val; uint64_t u64; int64_t s64; } v; // 指向下個(gè)哈希表節(jié)點(diǎn)，形成鏈表 struct dictEntry *next; } dictEntry;
（v可以是一個(gè)指針， 或者是一個(gè)?uint64_t?整數(shù)， 又或者是一個(gè)?int64_t?整數(shù)。）
next就是解決鍵沖突問題的，沖突了就掛后面，這個(gè)學(xué)過數(shù)據(jù)結(jié)構(gòu)的應(yīng)該都知道吧，不說了。
下面我們來說字典是怎么實(shí)現(xiàn)的了。
typedef struct dict { // 類型特定函數(shù) dictType *type; // 私有數(shù)據(jù) void *privdata; // 哈希表 dictht ht[2]; // rehash 索引 int rehashidx; //* rehashing not in progress if rehashidx == -1 } dict;
type?和?privdata?是對不同類型的鍵值對， 為創(chuàng)建多態(tài)字典而設(shè)置的：
type?指向?dictType?， 每個(gè)?dictType?保存了用于操作特定類型鍵值對的函數(shù)， 可以為用途不同的字典設(shè)置不同的類型特定函數(shù)。
而?privdata?屬性則保存了需要傳給那些類型特定函數(shù)的可選參數(shù)。
而dictType就暫時(shí)不展示了，不重要而且字有點(diǎn)多。。。還是講有意思的東西吧
rehash（重新散列）
隨著我們不斷的操作，哈希表保存的鍵值可能會(huì)增多或者減少，為了讓哈希表的負(fù)載因子維持在合理的范圍內(nèi)，有時(shí)需要對哈希表進(jìn)行合理的擴(kuò)展或者收縮。?一般情況下， 字典只使用?ht[0]?哈希表，?ht[1]?哈希表只會(huì)在對?ht[0]?哈希表進(jìn)行 rehash 時(shí)使用。
redis字典哈希rehash的步驟如下：
1）為ht[1]分配合理空間：如果是擴(kuò)展操作，大小為第一個(gè)大于等于ht[0]*used*2的，2的n次冪。
如果是收縮操作，大小為第一個(gè)大于等于ht[0]*used的，2的n次冪。
2）將ht[0]中的數(shù)據(jù)rehash到ht[1]上。
3）釋放ht[0]，將ht[1]設(shè)置為ht[0]，ht[1]創(chuàng)建空表，為下次做準(zhǔn)備。
漸進(jìn)rehash
數(shù)據(jù)量特別大時(shí)，rehash可能對服務(wù)器造成影響。為了避免，服務(wù)器不是一次性rehash的，而是分多次。
我們維持一個(gè)變量rehashidx，設(shè)置為0，代表rehash開始，然后開始rehash，在這期間，每個(gè)對字典的操作，程序都會(huì)把索引rehashidx上的數(shù)據(jù)移動(dòng)到ht[1]。
隨著操作不斷執(zhí)行，最終我們會(huì)完成rehash，設(shè)置rehashidx為-1.
需要注意：rehash過程中，每一次增刪改查也是在兩個(gè)表進(jìn)行的。
4）整數(shù)集合
整數(shù)集合（intset）是 Redis 用于保存整數(shù)值的集合抽象數(shù)據(jù)結(jié)構(gòu)， 可以保存?int16_t?、?int32_t?、?int64_t?的整數(shù)值， 并且保證集合中不會(huì)出現(xiàn)重復(fù)元素。
實(shí)現(xiàn)較為簡單：
typedef struct intset { // 編碼方式 uint32_t encoding; // 集合包含的元素?cái)?shù)量 uint32_t length; // 保存元素的數(shù)組 int8_t contents[]; } intset;
各個(gè)項(xiàng)在數(shù)組中從小到大有序地排列， 并且數(shù)組中不包含任何重復(fù)項(xiàng)。
雖然?intset?結(jié)構(gòu)將?contents?屬性聲明為?int8_t?類型的數(shù)組， 但實(shí)際上?contents?數(shù)組并不保存任何?int8_t?類型的值 ——?contents?數(shù)組的真正類型取決于?encoding?屬性的值：
如果?encoding?屬性的值為?INTSET_ENC_INT16?， 那么?contents?就是一個(gè)?int16_t?類型的數(shù)組， 數(shù)組里的每個(gè)項(xiàng)都是一個(gè)?int16_t?類型的整數(shù)值 （最小值為?-32,768?，最大值為?32,767?）。
如果?encoding?屬性的值為?INTSET_ENC_INT32?， 那么?contents?就是一個(gè)?int32_t?類型的數(shù)組， 數(shù)組里的每個(gè)項(xiàng)都是一個(gè)?int32_t?類型的整數(shù)值 （最小值為?-2,147,483,648?，最大值為?2,147,483,647?）。
如果?encoding?屬性的值為?INTSET_ENC_INT64?， 那么?contents?就是一個(gè)?int64_t?類型的數(shù)組， 數(shù)組里的每個(gè)項(xiàng)都是一個(gè)?int64_t?類型的整數(shù)值 （最小值為?-9,223,372,036,854,775,808?，最大值為?9,223,372,036,854,775,807?）。
升級
c語言是靜態(tài)類型語言，不允許不同類型保存在一個(gè)數(shù)組。這樣第一，靈活性較差，第二，有時(shí)會(huì)用掉不必要的內(nèi)存
比如用long long儲存1
為了提高整數(shù)集合的靈活性和節(jié)約內(nèi)存，我們引入升級策略。
當(dāng)我們要將一個(gè)新元素添加到集合里， 并且新元素類型比集合現(xiàn)有元素的類型都要長時(shí)， 集合需要先進(jìn)行升級。
分為三步進(jìn)行：
根據(jù)新元素的類型， 擴(kuò)展整數(shù)集合底層數(shù)組的空間大小， 并為新元素分配空間。
將底層數(shù)組現(xiàn)有的所有元素都轉(zhuǎn)換成與新元素相同的類型， 并將類型轉(zhuǎn)換后的元素放置到正確的位上
將新元素添加到底層數(shù)組里面。
因?yàn)槊看翁砑有略囟伎赡軙?huì)引起升級， 每次升級都要對已有元素類型轉(zhuǎn)換， 所以添加新元素的時(shí)間復(fù)雜度為?O(N)?。
因?yàn)橐l(fā)升級的新元素比原數(shù)據(jù)都長，所以要么他是最大的，要么他是最小的。我們把它放在開頭或結(jié)尾即可。
降級
略略略，不管你們信不信，整數(shù)集合不支持降級操作。。我也不知道為啥
5）壓縮列表
壓縮列表是列表鍵和哈希鍵的底層實(shí)現(xiàn)之一。
當(dāng)一個(gè)列表鍵只包含少量列表項(xiàng)，并且列表項(xiàng)都是小整數(shù)或者短字符串，redis就會(huì)用壓縮列表做列表鍵底層實(shí)現(xiàn)。
壓縮列表是 Redis 為了節(jié)約內(nèi)存而開發(fā)的， 由一系列特殊編碼的連續(xù)內(nèi)存塊組成的順序型（sequential）數(shù)據(jù)結(jié)構(gòu)。
一個(gè)壓縮列表可以包含任意多個(gè)節(jié)點(diǎn)（entry）， 每個(gè)節(jié)點(diǎn)可以保存一個(gè)字節(jié)數(shù)組或者一個(gè)整數(shù)值。
具體實(shí)現(xiàn)：
具體說一下entry：
由三個(gè)部分組成：
1、previous_entry_length:記錄上一個(gè)節(jié)點(diǎn)的長度，這樣我們就可以從最后一路遍歷到開頭。
2、encoding：記錄了content所保存的數(shù)據(jù)類型和長度。（具體編碼不寫了，不重要）
3、content：保存節(jié)點(diǎn)值，可以是字節(jié)數(shù)組或整數(shù)。（具體怎么壓縮的等我搞明白再補(bǔ)）
連鎖更新
前面說過， 每個(gè)節(jié)點(diǎn)的?previous_entry_length?屬性都記錄了前一個(gè)節(jié)點(diǎn)的長度：
如果前一節(jié)點(diǎn)的長度
如果前一節(jié)點(diǎn)的長度>=254?KB， 那么?previous_entry_length?需要用?5?字節(jié)長的空間
現(xiàn)在， 考慮這樣一種情況： 在一個(gè)壓縮列表中， 有多個(gè)連續(xù)的、長度介于?250?字節(jié)到?253?字節(jié)之間的節(jié)點(diǎn) ，這時(shí)， 如果我們將一個(gè)長度大于等于?254?字節(jié)的新節(jié)點(diǎn)?new?設(shè)置為壓縮列表的表頭節(jié)點(diǎn)。。。。
然后腦補(bǔ)一下，就會(huì)導(dǎo)致連鎖擴(kuò)大每個(gè)節(jié)點(diǎn)的空間對吧？e(i)因?yàn)閑(i-1)的擴(kuò)大而擴(kuò)大，i+1也是如此，以此類推... ...
刪除節(jié)點(diǎn)同樣會(huì)導(dǎo)致連鎖更新。
這個(gè)事情只是想說明一個(gè)問題：插入刪除操作的最壞時(shí)間復(fù)雜度其實(shí)是o(n*n)，因?yàn)槊扛乱粋€(gè)節(jié)點(diǎn)都要o(n)。
但是，也不用太過擔(dān)心，因?yàn)檫@種特殊情況并不多見，這些命令的平均復(fù)雜度依舊是o(n)。
數(shù)據(jù)庫
版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。
版權(quán)聲明：本文內(nèi)容由網(wǎng)絡(luò)用戶投稿，版權(quán)歸原作者所有，本站不擁有其著作權(quán)，亦不承擔(dān)相應(yīng)法律責(zé)任。如果您發(fā)現(xiàn)本站中有涉嫌抄襲或描述失實(shí)的內(nèi)容，請聯(lián)系我們jiasou666@gmail.com 處理，核實(shí)后本網(wǎng)站將在24小時(shí)內(nèi)刪除侵權(quán)內(nèi)容。
相關(guān)文章
