什么是Redis

Redis(Remote Dictionary Server) 是一個(gè)使用 C 語言編寫的，開源的（BSD許可）高性能非關(guān)系型（NoSQL）的鍵值對(duì)數(shù)據(jù)庫(kù)。

Redis 可以存儲(chǔ)鍵和五種不同類型的值之間的映射。鍵的類型只能為字符串，值支持五種數(shù)據(jù)類型：字符串、列表、集合、散列表、有序集合。

與傳統(tǒng)數(shù)據(jù)庫(kù)不同的是 Redis 的數(shù)據(jù)是存在內(nèi)存中的，所以讀寫速度非常快，因此 redis 被廣泛應(yīng)用于緩存方向，每秒可以處理超過 10萬次讀寫操作，是已知性能最快的Key-Value DB。另外，Redis 也經(jīng)常用來做分布式鎖。除此之外，Redis 支持事務(wù) 、持久化、LUA腳本、LRU驅(qū)動(dòng)事件、多種集群方案。

為什么要用 Redis /為什么要用緩存

主要從“高性能”和“高并發(fā)”這兩點(diǎn)來看待這個(gè)問題。

高性能：

假如用戶第一次訪問數(shù)據(jù)庫(kù)中的某些數(shù)據(jù)。這個(gè)過程會(huì)比較慢，因?yàn)槭菑挠脖P上讀取的。將該用戶訪問的數(shù)據(jù)存在數(shù)緩存中，這樣下一次再訪問這些數(shù)據(jù)的時(shí)候就可以直接從緩存中獲取了。操作緩存就是直接操作內(nèi)存，所以速度相當(dāng)快。如果數(shù)據(jù)庫(kù)中的對(duì)應(yīng)數(shù)據(jù)改變的之后，同步改變緩存中相應(yīng)的數(shù)據(jù)即可！

高并發(fā)：

直接操作緩存能夠承受的請(qǐng)求是遠(yuǎn)遠(yuǎn)大于直接訪問數(shù)據(jù)庫(kù)的，所以我們可以考慮把數(shù)據(jù)庫(kù)中的部分?jǐn)?shù)據(jù)轉(zhuǎn)移到緩存中去，這樣用戶的一部分請(qǐng)求會(huì)直接到緩存這里而不用經(jīng)過數(shù)據(jù)庫(kù)。

為什么要用 Redis 而不用 map/guava 做緩存?

緩存分為本地緩存和分布式緩存。以 Java 為例，使用自帶的 map 或者 guava 實(shí)現(xiàn)的是本地緩存，最主要的特點(diǎn)是輕量以及快速，生命周期隨著 jvm 的銷毀而結(jié)束，并且在多實(shí)例的情況下，每個(gè)實(shí)例都需要各自保存一份緩存，緩存不具有一致性。

使用 redis 或 memcached 之類的稱為分布式緩存，在多實(shí)例的情況下，各實(shí)例共用一份緩存數(shù)據(jù)，緩存具有一致性。缺點(diǎn)是需要保持 redis 或 memcached服務(wù)的高可用，整個(gè)程序架構(gòu)上較為復(fù)雜。

Redis為什么這么快

1、完全基于內(nèi)存，絕大部分請(qǐng)求是純粹的內(nèi)存操作，非?？焖?。數(shù)據(jù)存在內(nèi)存中，類似于 HashMap，HashMap 的優(yōu)勢(shì)就是查找和操作的時(shí)間復(fù)雜度都是O(1)；

2、數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單，對(duì)數(shù)據(jù)操作也簡(jiǎn)單，Redis 中的數(shù)據(jù)結(jié)構(gòu)是專門進(jìn)行設(shè)計(jì)的；

3、采用單線程，避免了不必要的上下文切換和競(jìng)爭(zhēng)條件，也不存在多進(jìn)程或者多線程導(dǎo)致的切換而消耗 CPU，不用去考慮各種鎖的問題，不存在加鎖釋放鎖操作，沒有因?yàn)榭赡艹霈F(xiàn)死鎖而導(dǎo)致的性能消耗；

4、使用多路 I/O 復(fù)用模型，非阻塞 IO；

5、使用底層模型不同，它們之間底層實(shí)現(xiàn)方式以及與客戶端之間通信的應(yīng)用協(xié)議不一樣，Redis 直接自己構(gòu)建了 VM 機(jī)制 ，因?yàn)橐话愕南到y(tǒng)調(diào)用系統(tǒng)函數(shù)的話，會(huì)浪費(fèi)一定的時(shí)間去移動(dòng)和請(qǐng)求；

緩存異常

緩存雪崩

緩存雪崩是指緩存同一時(shí)間大面積的失效，所以，后面的請(qǐng)求都會(huì)落到數(shù)據(jù)庫(kù)上，造成數(shù)據(jù)庫(kù)短時(shí)間內(nèi)承受大量請(qǐng)求而崩掉。

解決方案

1. 緩存數(shù)據(jù)的過期時(shí)間設(shè)置隨機(jī)，防止同一時(shí)間大量數(shù)據(jù)過期現(xiàn)象發(fā)生。
2. 一般并發(fā)量不是特別多的時(shí)候，使用最多的解決方案是加鎖排隊(duì)。
3. 給每一個(gè)緩存數(shù)據(jù)增加相應(yīng)的緩存標(biāo)記，記錄緩存的是否失效，如果緩存標(biāo)記失效，則更新數(shù)據(jù)緩存。

緩存擊穿

緩存擊穿是指緩存中沒有但數(shù)據(jù)庫(kù)中有的數(shù)據(jù)（一般是緩存時(shí)間到期），這時(shí)由于并發(fā)用戶特別多，同時(shí)讀緩存沒讀到數(shù)據(jù)，又同時(shí)去數(shù)據(jù)庫(kù)去取數(shù)據(jù)，引起數(shù)據(jù)庫(kù)壓力瞬間增大，造成過大壓力。和緩存雪崩不同的是，緩存擊穿指并發(fā)查同一條數(shù)據(jù)，緩存雪崩是不同數(shù)據(jù)都過期了，很多數(shù)據(jù)都查不到從而查數(shù)據(jù)庫(kù)。

解決方案

1. 設(shè)置熱點(diǎn)數(shù)據(jù)永遠(yuǎn)不過期。
2. 加互斥鎖，互斥鎖

緩存穿透

緩存穿透是指緩存和數(shù)據(jù)庫(kù)中都沒有的數(shù)據(jù)，導(dǎo)致所有的請(qǐng)求都落到數(shù)據(jù)庫(kù)上，造成數(shù)據(jù)庫(kù)短時(shí)間內(nèi)承受大量請(qǐng)求而崩掉。

解決方案

1. 接口層增加校驗(yàn)，如用戶鑒權(quán)校驗(yàn)，id做基礎(chǔ)校驗(yàn)，id<=0的直接攔截；
2. 從緩存取不到的數(shù)據(jù)，在數(shù)據(jù)庫(kù)中也沒有取到，這時(shí)也可以將key-value對(duì)寫為key-null，緩存有效時(shí)間可以設(shè)置短點(diǎn)，如30秒（設(shè)置太長(zhǎng)會(huì)導(dǎo)致正常情況也沒法使用）。這樣可以防止攻擊用戶反復(fù)用同一個(gè)id暴力攻擊
3. 采用布隆過濾器，將所有可能存在的數(shù)據(jù)哈希到一個(gè)足夠大的 bitmap 中，一個(gè)一定不存在的數(shù)據(jù)會(huì)被這個(gè) bitmap 攔截掉，從而避免了對(duì)底層存儲(chǔ)系統(tǒng)的查詢壓力

1、 布隆過濾器的概念

布隆過濾器(BloomFilter)是一種緊湊型的、比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu)，特點(diǎn)是高效地插入和查詢，可以用來告訴你 某樣?xùn)|西一定不存在或者可能存在，它是用多個(gè)哈希函數(shù)，將一個(gè)數(shù)據(jù)映射到位圖結(jié)構(gòu)中。此種方式不僅可以提升查詢效率，也可以節(jié)省大量的內(nèi)存空間，但是布隆過濾器也存在一定的缺陷：數(shù)據(jù)只能插入不能刪除。
布隆過濾器的底層實(shí)現(xiàn)是位圖。

2、 布隆過濾器的插入與查找

2.1 布隆過濾器的插入

布隆過濾器是由一個(gè)很長(zhǎng)的bit數(shù)組和一系列哈希函數(shù)組成的。

數(shù)組的每個(gè)元素都只占1bit空間，并且每個(gè)元素只能為0或1。

布隆過濾器還擁有k個(gè)哈希函數(shù)，當(dāng)一個(gè)元素加入布隆過濾器時(shí)，會(huì)使用k個(gè)哈希函數(shù)對(duì)其進(jìn)行k次計(jì)算,得到k個(gè)哈希值，并且根據(jù)得到的哈希值，在數(shù)組中把對(duì)應(yīng)下標(biāo)的值置位1。

image.png

2.2 布隆過濾器的查找

布隆過濾器的思想是將一個(gè)元素用多個(gè)哈希函數(shù)映射到一個(gè)位圖中，因此被映射到的位置的比特位一定為1.

所以在查詢某個(gè)是否存在時(shí)，若該值利用三個(gè)不同的哈希函數(shù)返回的哈希值對(duì)應(yīng)的下標(biāo)至少有一個(gè)為0，則說明該值一定不存在，若對(duì)應(yīng)的值均為1，說明該值可能存在。

為什么說是可能存在而不是一定存在呢？
因?yàn)榭赡軙?huì)出現(xiàn)不同的值利用哈希函數(shù)返回的哈希值對(duì)應(yīng)的下標(biāo)相同，所以說只能得出可能存在的結(jié)果，即某些哈希函數(shù)存在一定誤判。

2.3 布隆過濾器產(chǎn)生誤判的原因（Hash碰撞）

當(dāng)插入的元素越來越多時(shí)，當(dāng)一個(gè)不在布隆過濾器中的元素，經(jīng)過同樣規(guī)則的哈希計(jì)算之后，得到的值在數(shù)組中查詢，有可能這些位置因?yàn)槠渌脑叵缺恢?了。

所以布隆過濾器存在誤判的情況，但是如果布隆過濾器判斷某個(gè)元素不在布隆過濾器中，那么這個(gè)值就一定不在。

Hash碰撞沖突

我們知道，對(duì)象Hash的前提是實(shí)現(xiàn)equals()和hashCode()兩個(gè)方法，那么HashCode()的作用就是保證對(duì)象返回唯一hash值，但當(dāng)兩個(gè)對(duì)象計(jì)算值一樣時(shí)，這就發(fā)生了碰撞沖突。如下將介紹如何處理沖突，當(dāng)然其前提是一致性hash。

1.開放地址法

開放地執(zhí)法有一個(gè)公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)
其中，m為哈希表的表長(zhǎng)。di 是產(chǎn)生沖突的時(shí)候的增量序列。如果di值可能為1,2,3,…m-1，稱線性探測(cè)再散列。
如果di取1，則每次沖突之后，向后移動(dòng)1個(gè)位置.如果di取值可能為1,-1,2,-2,4,-4,9,-9,16,-16,…kk,-kk(k<=m/2)，稱二次探測(cè)再散列。
如果di取值可能為偽隨機(jī)數(shù)列。稱偽隨機(jī)探測(cè)再散列。

2.再哈希法

當(dāng)發(fā)生沖突時(shí)，使用第二個(gè)、第三個(gè)、哈希函數(shù)計(jì)算地址，直到無沖突時(shí)。缺點(diǎn)：計(jì)算時(shí)間增加。
比如上面第一次按照姓首字母進(jìn)行哈希，如果產(chǎn)生沖突可以按照姓字母首字母第二位進(jìn)行哈希，再?zèng)_突，第三位，直到不沖突為止

3.鏈地址法（拉鏈法）

將所有關(guān)鍵字為同義詞的記錄存儲(chǔ)在同一線性鏈表中。

4.建立一個(gè)公共溢出區(qū)

假設(shè)哈希函數(shù)的值域?yàn)閇0,m-1],則設(shè)向量HashTable[0..m-1]為基本表，另外設(shè)立存儲(chǔ)空間向量OverTable[0..v]用以存儲(chǔ)發(fā)生沖突的記錄。

參考文章：https://blog.csdn.net/qq_35190492/article/details/102889333
參考文章：https://blog.csdn.net/tianduidui/article/details/104772178