什么是Redis

Redis(Remote Dictionary Server) 是一個使用 C 語言編寫的盟蚣，開源的（BSD許可）高性能非關系型（NoSQL）的鍵值對數據庫黍析。

Redis 可以存儲鍵和五種不同類型的值之間的映射。鍵的類型只能為字符串屎开，值支持五種數據類型：字符串橄仍、列表、集合牍戚、散列表侮繁、有序集合。

與傳統數據庫不同的是 Redis 的數據是存在內存中的如孝，所以讀寫速度非诚芰ǎ快，因此 redis 被廣泛應用于緩存方向第晰，每秒可以處理超過 10萬次讀寫操作锁孟，是已知性能最快的Key-Value DB彬祖。另外，Redis 也經常用來做分布式鎖品抽。除此之外储笑，Redis 支持事務 、持久化圆恤、LUA腳本突倍、LRU驅動事件、多種集群方案盆昙。

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

主要從“高性能”和“高并發(fā)”這兩點來看待這個問題羽历。

高性能：

假如用戶第一次訪問數據庫中的某些數據。這個過程會比較慢淡喜，因為是從硬盤上讀取的秕磷。將該用戶訪問的數據存在數緩存中，這樣下一次再訪問這些數據的時候就可以直接從緩存中獲取了炼团。操作緩存就是直接操作內存澎嚣，所以速度相當快。如果數據庫中的對應數據改變的之后瘟芝，同步改變緩存中相應的數據即可币叹！

高并發(fā)：

直接操作緩存能夠承受的請求是遠遠大于直接訪問數據庫的顷啼，所以我們可以考慮把數據庫中的部分數據轉移到緩存中去亮瓷，這樣用戶的一部分請求會直接到緩存這里而不用經過數據庫。

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

緩存分為本地緩存和分布式緩存柴罐。以 Java 為例嚼鹉，使用自帶的 map 或者 guava 實現的是本地緩存贩汉，最主要的特點是輕量以及快速，生命周期隨著 jvm 的銷毀而結束锚赤，并且在多實例的情況下匹舞，每個實例都需要各自保存一份緩存，緩存不具有一致性线脚。

使用 redis 或 memcached 之類的稱為分布式緩存赐稽，在多實例的情況下，各實例共用一份緩存數據浑侥，緩存具有一致性姊舵。缺點是需要保持 redis 或 memcached服務的高可用，整個程序架構上較為復雜寓落。

Redis為什么這么快

1括丁、完全基于內存，絕大部分請求是純粹的內存操作伶选，非呈贩桑快速尖昏。數據存在內存中，類似于 HashMap构资，HashMap 的優(yōu)勢就是查找和操作的時間復雜度都是O(1)抽诉；

2、數據結構簡單吐绵，對數據操作也簡單迹淌，Redis 中的數據結構是專門進行設計的；

3拦赠、采用單線程巍沙，避免了不必要的上下文切換和競爭條件葵姥，也不存在多進程或者多線程導致的切換而消耗 CPU荷鼠，不用去考慮各種鎖的問題，不存在加鎖釋放鎖操作榔幸，沒有因為可能出現死鎖而導致的性能消耗允乐；

4、使用多路 I/O 復用模型削咆，非阻塞 IO牍疏；

5、使用底層模型不同拨齐，它們之間底層實現方式以及與客戶端之間通信的應用協議不一樣鳞陨，Redis 直接自己構建了 VM 機制 ，因為一般的系統調用系統函數的話瞻惋，會浪費一定的時間去移動和請求厦滤；

緩存異常

緩存雪崩

緩存雪崩是指緩存同一時間大面積的失效，所以歼狼，后面的請求都會落到數據庫上掏导，造成數據庫短時間內承受大量請求而崩掉。

解決方案

1. 緩存數據的過期時間設置隨機羽峰，防止同一時間大量數據過期現象發(fā)生趟咆。
2. 一般并發(fā)量不是特別多的時候，使用最多的解決方案是加鎖排隊梅屉。
3. 給每一個緩存數據增加相應的緩存標記值纱，記錄緩存的是否失效，如果緩存標記失效坯汤，則更新數據緩存计雌。

緩存擊穿

緩存擊穿是指緩存中沒有但數據庫中有的數據（一般是緩存時間到期），這時由于并發(fā)用戶特別多玫霎，同時讀緩存沒讀到數據凿滤，又同時去數據庫去取數據妈橄，引起數據庫壓力瞬間增大，造成過大壓力翁脆。和緩存雪崩不同的是眷蚓，緩存擊穿指并發(fā)查同一條數據，緩存雪崩是不同數據都過期了反番，很多數據都查不到從而查數據庫沙热。

解決方案

1. 設置熱點數據永遠不過期。
2. 加互斥鎖罢缸，互斥鎖

緩存穿透

緩存穿透是指緩存和數據庫中都沒有的數據篙贸，導致所有的請求都落到數據庫上，造成數據庫短時間內承受大量請求而崩掉枫疆。

解決方案

1. 接口層增加校驗爵川，如用戶鑒權校驗，id做基礎校驗息楔，id<=0的直接攔截寝贡；
2. 從緩存取不到的數據，在數據庫中也沒有取到值依，這時也可以將key-value對寫為key-null圃泡，緩存有效時間可以設置短點，如30秒（設置太長會導致正常情況也沒法使用）愿险。這樣可以防止攻擊用戶反復用同一個id暴力攻擊
3. 采用布隆過濾器颇蜡，將所有可能存在的數據哈希到一個足夠大的 bitmap 中，一個一定不存在的數據會被這個 bitmap 攔截掉辆亏，從而避免了對底層存儲系統的查詢壓力

1风秤、 布隆過濾器的概念

布隆過濾器(BloomFilter)是一種緊湊型的、比較巧妙的概率型數據結構褒链，特點是高效地插入和查詢唁情，可以用來告訴你 某樣東西一定不存在或者可能存在，它是用多個哈希函數甫匹，將一個數據映射到位圖結構中甸鸟。此種方式不僅可以提升查詢效率，也可以節(jié)省大量的內存空間兵迅，但是布隆過濾器也存在一定的缺陷：數據只能插入不能刪除抢韭。
布隆過濾器的底層實現是位圖。

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

2.1 布隆過濾器的插入

布隆過濾器是由一個很長的bit數組和一系列哈希函數組成的刻恭。

數組的每個元素都只占1bit空間，并且每個元素只能為0或1。

布隆過濾器還擁有k個哈希函數鳍贾，當一個元素加入布隆過濾器時鞍匾，會使用k個哈希函數對其進行k次計算,得到k個哈希值，并且根據得到的哈希值骑科，在數組中把對應下標的值置位1橡淑。

image.png

2.2 布隆過濾器的查找

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

所以在查詢某個是否存在時咆爽，若該值利用三個不同的哈希函數返回的哈希值對應的下標至少有一個為0梁棠，則說明該值一定不存在，若對應的值均為1斗埂，說明該值可能存在符糊。

為什么說是可能存在而不是一定存在呢？
因為可能會出現不同的值利用哈希函數返回的哈希值對應的下標相同呛凶，所以說只能得出可能存在的結果男娄，即某些哈希函數存在一定誤判。

2.3 布隆過濾器產生誤判的原因（Hash碰撞）

當插入的元素越來越多時把兔，當一個不在布隆過濾器中的元素沪伙，經過同樣規(guī)則的哈希計算之后瓮顽，得到的值在數組中查詢县好，有可能這些位置因為其他的元素先被置1了。

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

Hash碰撞沖突

我們知道拣播，對象Hash的前提是實現equals()和hashCode()兩個方法晾咪，那么HashCode()的作用就是保證對象返回唯一hash值，但當兩個對象計算值一樣時贮配，這就發(fā)生了碰撞沖突谍倦。如下將介紹如何處理沖突，當然其前提是一致性hash泪勒。

1.開放地址法

開放地執(zhí)法有一個公式:Hi=(H(key)+di) MOD m i=1,2,…,k(k<=m-1)
其中昼蛀，m為哈希表的表長。di 是產生沖突的時候的增量序列圆存。如果di值可能為1,2,3,…m-1叼旋，稱線性探測再散列。
如果di取1沦辙，則每次沖突之后夫植，向后移動1個位置.如果di取值可能為1,-1,2,-2,4,-4,9,-9,16,-16,…kk,-kk(k<=m/2)，稱二次探測再散列油讯。
如果di取值可能為偽隨機數列详民。稱偽隨機探測再散列延欠。

2.再哈希法

當發(fā)生沖突時，使用第二個沈跨、第三個衫冻、哈希函數計算地址，直到無沖突時谒出。缺點：計算時間增加隅俘。
比如上面第一次按照姓首字母進行哈希，如果產生沖突可以按照姓字母首字母第二位進行哈希笤喳，再沖突为居，第三位，直到不沖突為止

3.鏈地址法（拉鏈法）

將所有關鍵字為同義詞的記錄存儲在同一線性鏈表中杀狡。

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

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

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