首頁 >資料庫 >Redis >總結分享20個關於Redis的經典面試題(附答案分析)

總結分享20個關於Redis的經典面試題(附答案分析)

青灯夜游
青灯夜游轉載
2021-09-13 11:06:088494瀏覽

金九銀十即將到來,這篇文章為大家整理分享20道Redis經典面試題,希望對大家有幫助!

總結分享20個關於Redis的經典面試題(附答案分析)

1. 什麼是Redis?它主要用來什麼的?

Redis,英文全名為Remote Dictionary Server(遠端字典服務),是一個開源的使用ANSI C語言編寫、支援網路、可基於記憶體亦可持久化的日誌類型、Key-Value資料庫,並提供多種語言的API。 【相關推薦:Redis影片教學

與MySQL資料庫不同的是,Redis的資料是存在記憶體中的。它的讀寫速度非常快,每秒鐘可以處理超過10萬次讀寫操作。因此redis被廣泛應用於快取,另外,Redis也常用來做分散式鎖定。除此之外,Redis支援交易、持久化、LUA 腳本、LRU 驅動事件、多種叢集方案。

2.說Redis的基本資料結構型別

大多數小夥伴都知道,Redis有以下這五種基本型別:

  • String(字串)
  • Hash(雜湊)
  • List(列表)
  • Set(集合)
  • ##zset(有序集合)
它還有三種特殊的資料結構型別

    Geospatial
  • Hyperloglog
  • Bitmap
#2.1 Redis 的五種基本資料類型

總結分享20個關於Redis的經典面試題(附答案分析)

String(字串)

    簡介:String是Redis最基礎的資料結構類型,它是二進制安全的,可以儲存圖片或序列化的對象,值最大儲存為512M
  • #簡單使用舉例:
  • set key valueget key
  • 應用程式場景:共享session、分散式鎖定,計數器、限流。
  • 內部編碼有3種,
  • int(8位元組長整數)/embstr(小於等於39位元組字串)/raw(大於39個位元組字串)
C語言的字串是

char[]實作的,而Redis使用SDS(simple dynamic string) 封裝,sds原始碼如下:

struct sdshdr{
  unsigned int len; // 标记buf的长度
  unsigned int free; //标记buf中未使用的元素个数
  char buf[]; // 存放元素的坑
}

SDS 結構圖如下:

總結分享20個關於Redis的經典面試題(附答案分析)

Redis為什麼選擇

SDS結構,而C語言原生的 char[]不香嗎?

舉例其中一點,SDS中,O(1)時間複雜度,就可以取得字串長度;而C 字串,需要遍歷整個字串,時間複雜度為O(n)

Hash(雜湊)

    簡介:在Redis中,雜湊類型是指v(值)本身又是一個鍵值對(k-v)結構
  • 簡單使用範例:
  • hset key field valuehget key field
  • 內部編碼:
  • ziplist(壓縮清單)hashtable(雜湊表)
  • 應用程式場景:快取使用者資訊等。
  • 注意點:如果開發使用hgetall,則雜湊元素比較多的話,可能導致Redis阻塞,可以使用hscan。而如果只是取得部分field,建議使用hmget。
字串與雜湊類型比較如下圖:

總結分享20個關於Redis的經典面試題(附答案分析)

#List(列表)

    簡介:列表(list)類型是用來儲存多個有序的字串,一個清單最多可以儲存2^32-1個元素。
  • 簡單實用範例:
  • lpush  key  value [value ...]lrange key start end##內部編碼:ziplist(壓縮清單) 、linkedlist(鍊錶)
  • 應用場景: 訊息佇列,文章列表,
  • 一圖看懂list類型的插入與彈出:

總結分享20個關於Redis的經典面試題(附答案分析)

  • ##list應用程式場景參考以下:
lpush lpop=Stack(堆疊)

lpush rpop=Queue(佇列)

lpsh ltrim=Capped Collection(有限集合)總結分享20個關於Redis的經典面試題(附答案分析)

lpush brpop=Message Queue(訊息佇列)############Set(集合)########### #
  • 簡介:集合(set)類型也是用來保存多個的字串元素,但是不允許重複元素
  • #簡單使用範例:sadd key element [element ... ]smembers key
  • 內部編碼:intset(整數集合)hashtable(雜湊表)
  • 注意點:smembers和lrange、hgetall都屬於比較重的命令,如果元素過多存在阻塞Redis的可能性,可以使用sscan來完成。
  • 應用場景: 使用者標籤,產生隨機數字抽獎、社交需求。

有序集合(zset)

  • 簡介:已排序的字串集合,同時元素不能重複
  • 簡單格式範例: zadd key score member [score member ...]zrank key member
  • 底層內部編碼:ziplist(壓縮列表)skiplist (跳躍表)
  • 應用程式場景:排行榜,社交需求(如使用者按讚)。

2.2 Redis 的三種特殊資料類型

  • Geo:Redis3.2推出的,地理位置定位,用於儲存地理位置信息,並對儲存的信息進行操作。
  • HyperLogLog:用來做基數統計演算法的資料結構,如統計網站的UV。
  • Bitmaps :用一個位元位元來映射某個元素的狀態,在Redis中,它的底層是基於字串類型實現的,可以把bitmaps成作一個以位元為單位的陣列

3. Redis為什麼這麼快?

總結分享20個關於Redis的經典面試題(附答案分析)

3.1 基於記憶體儲存實作

我們都知道記憶體讀寫是比在磁碟快很多的,Redis基於記憶體儲存實作的資料庫,相對於資料存在磁碟的MySQL資料庫,省去磁碟I/O的消耗。

3.2 高效的資料結構

我們知道,Mysql索引為了提高效率,選擇了B 樹的資料結構。其實合理的資料結構,就是可以讓你的應用程式/程式更快。先看一下Redis的資料結構&內部編碼圖:

總結分享20個關於Redis的經典面試題(附答案分析)

SDS簡單動態字串

總結分享20個關於Redis的經典面試題(附答案分析)

  • 字串長度處理:Redis取得字串長度,時間複雜度為O(1),而C語言中,需要從頭開始遍歷,複雜度為O(n);
  • 空間預先分配:字串修改越頻繁的話,記憶體分配越頻繁,就會消耗效能,而SDS修改和空間擴充,會額外分配未使用的空間,減少效能損耗。
  • 惰性空間釋放:SDS 縮短時,不是回收多餘的記憶體空間,而是free記錄下多餘的空間,後續有變更,直接使用free中記錄的空間,減少分配。
  • 二進位安全性:Redis可以儲存一些二進位數據,在C語言中字串遇到'\0'會結束,而 SDS中標誌字串結束的是len屬性。

字典

Redis 作為 K-V 型記憶體資料庫,所有的鍵值就是用字典來儲存。字典就是哈希表,例如HashMap,透過key就可以直接取得對應的value。而哈希表的特性,在O(1)時間複雜度就可以得到對應的值。

跳躍表

總結分享20個關於Redis的經典面試題(附答案分析)

  • 跳躍表是Redis特有的資料結構,就是在鍊錶的基礎上,增加多層索引提升尋找效率。
  • 跳躍表支援平均 O(logN),最壞 O(N)複雜度的節點查找,還可以透過順序性操作批次處理節點。

3.3 合理的資料編碼

Redis 支援多種資料資料類型,每種基本類型,可能對多種資料結構。什麼時候,使用什麼樣資料結構,使用什麼樣編碼,是redis設計者總結優化的結果。

  • String:如果儲存數字的話,是用int型別的編碼;如果儲存非數字,小於等於39位元組的字串,是embstr;大於39個位元組,則是raw編碼。
  • List:如果列表的元素個數小於512個,列表每個元素的值都小於64位元組(預設),使用ziplist編碼,否則使用linkedlist編碼
  • Hash:哈希型別元素個數小於512個,所有值小於64位元組的話,使用ziplist編碼,否則使用hashtable編碼。
  • Set:如果集合中的元素都是整數且元素個數小於512個,使用intset編碼,否則使用hashtable編碼。
  • Zset:當有序集合的元素個數小於128個,每個元素的值小於64位元組時,使用ziplist編碼,否則使用skiplist(跳躍表)編碼#​​

3.4 合理的執行緒模型

I/O 多路復用

總結分享20個關於Redis的經典面試題(附答案分析)

多路I /O復用技術可以讓單一執行緒高效的處理多個連線請求,而Redis則使用以epoll作為I/O多路復用技術的實作。並且,Redis本身的事件處理模型將epoll中的連接、讀寫、關閉都轉換為事件,不在網路I/O上浪費過多的時間。

什麼是I/O多路復用?

  • I/O :網路 I/O
  • 多路 :多個網路連線
  • 重複使用:重複使用同一個執行緒。
  • IO多路復用其實就是一種同步IO模型,它實作了一個執行緒可以監視多個檔案句柄;一旦某個檔案句柄就緒,就能夠通知應用程式進行對應的讀寫操作;而沒有文件句柄就緒時,就會阻塞應用程序,交出cpu。

單執行緒模型

  • Redis是單執行緒模型的,而單執行緒避免了CPU不必要的上下文切換和競爭鎖的消耗。也因為是單線程,如果某個指令執行過長(如hgetall指令),會造成阻塞。 Redis是一個面向快速執行場景的資料庫。 ,所以要慎用如smembers和lrange、hgetall等命令。
  • Redis 6.0 引入了多執行緒提速,它的執行指令操作記憶體的仍然是個單執行緒。

3.5 虛擬記憶體機制

Redis直接自己建構了VM機制 ,不會像一般的系統會呼叫系統函數處理,會浪費一定的時間去移動和請求。

Redis的虛擬記憶體機制是啥呢?

虛擬記憶體機制就是暫時把不經常存取的資料(冷資料)從記憶體交換到磁碟中,從而騰出寶貴的記憶體空間用於其它需要存取的資料(熱數據)。透過VM功能可以實現冷熱資料分離,使熱資料仍在記憶體中、冷資料儲存到磁碟。這樣就可以避免因為記憶體不足而造成存取速度下降的問題。

4. 什麼是快取擊穿、快取穿透、快取雪崩?

4.1 快取穿透問題

先來看一個常見的快取使用方式:讀取請求來了,先查下緩存,快取有值命中,就直接回傳;快取沒命中,就去查資料庫,然後把資料庫的值更新到緩存,然後再返回。

1總結分享20個關於Redis的經典面試題(附答案分析)

快取穿透:指查詢一個一定不存在的數據,由於快取是不命中時需要從資料庫查詢,查不到數據則不寫入緩存,這將導致這個不存在的資料每次請求都要到資料庫去查詢,進而給資料庫帶來壓力。

通俗點說,讀取請求存取時,快取和資料庫都沒有某個值,這樣就會導致每次對這個值的查詢請求都會穿透到資料庫,這就是快取穿透。

快取穿透一般都是這幾種情況產生的:

  • #業務不合理的設計,例如大多數用戶都沒開守護,但是你的每個請求都去緩存,查詢某個userid查詢有沒有守護。
  • 業務/維運/開發錯誤的操作,例如快取和資料庫的資料都被誤刪除了。
  • 駭客非法要求攻擊,例如駭客故意捏造大量非法請求,以讀取不存在的業務資料。

如何避免快取穿透呢? 一般有三種方法。

  • 1.如果是非法請求,我們在API入口,對參數進行校驗,過濾非法值。
  • 2.如果查詢資料庫為空,我們可以為快取設定個空值,或是預設值。但是如有寫請求進來的話,需要更新快取哈,以確保快取一致性,同時,最後給快取設定適當的過期時間。 (業務上較常用,簡單有效)
  • 3.使用布隆過濾器快速判斷資料是否存在。即一個查詢請求過來時,先透過布隆過濾器判斷值是否存在,存在才繼續往下查。

布隆過濾器原理:它由初始值為0的位圖數組和N個雜湊函數組成。一個對一個key進行N個hash演算法取得N個值,在位元數組中將這N個值散列後設定為1,然後查的時候如果特定的這幾個位置都為1,那麼布隆過濾器判斷該key存在。

4.2 快取雪奔問題

快取雪奔: 指快取中資料大批量到過期時間,而查詢資料量巨大,請求都直接訪問資料庫,造成資料庫壓力過大甚至down機。

  • 快取雪奔一般是由於大量資料同時過期造成的,對於這個原因,可透過均勻設定過期時間解決,即讓過期時間相對離散一點。如採用一個較大固定值 一個較小的隨機值,5小時 0到1800秒醬紫。
  • Redis 故障宕機也可能造成快取雪奔。這就需要構造Redis高可用群集啦。

4.3 快取擊穿問題

快取擊穿: 指熱點key在某個時間點過期的時候,而剛好在這個時間點對這個Key有大量的並發請求過來,從而大量的請求打到db。

快取擊穿看著有點像,其實它兩區別是,快取雪奔是指資料庫壓力過大甚至down機,快取擊穿只是大量並發請求到了DB資料庫層面。可以認為擊穿是緩存雪奔的子集吧。有些文章認為它倆區別,是區別在於擊穿針對某一熱點key緩存,雪奔則是很多key。

解決方案有兩種:

  • 1.使用互斥鎖定方案。快取失效時,不是立即去載入db數據,而是先使用某些帶成功返回的原子操作指令,如(Redis的setnx)去操作,成功的時候,再去載入db資料庫資料和設定快取。否則就去重試取得快取。
  • 2. “永不過期”,是指沒有設定過期時間,但是熱點資料快要過期時,非同步執行緒去更新和設定過期時間。

5. 什麼是熱Key問題,如何解決熱key問題

什麼是熱Key呢?在Redis中,我們把訪問頻率高的key,稱為熱點key。

如果某一熱點key的請求到伺服器主機時,由於請求量特別大,可能會導致主機資源不足,甚至宕機,從而影響正常的服務。

1總結分享20個關於Redis的經典面試題(附答案分析)

而熱點Key又是怎麼產生的呢?主要原因有兩個:

  • 用戶消費的數據遠大於生產的數據,如秒殺、熱點新聞等讀取多寫少的場景。
  • 請求分片集中,超過單一Redi伺服器的效能,例如固定名稱key,Hash落入同一台伺服器,瞬​​間訪問量極大,超過機器瓶頸,產生熱點Key問題。

那麼在日常開發中,如何辨識到熱點key呢?

  • 以經驗判斷哪些是熱Key;
  • 客戶端統計上報;
  • 服務代理程式層上報

如何解決熱key問題?

  • Redis叢集擴容:增加分片副本,均衡讀取流量;
  • 將熱key分散到不同的伺服器;
  • 使用二級緩存,即JVM本地緩存,減少Redis的讀取請求。

6. Redis 過期策略與記憶體淘汰策略

1總結分享20個關於Redis的經典面試題(附答案分析)

#6.1 Redis的過期策略

我們在set key的時候,可以給它設定一個過期時間,例如expire key 60。指定這key60s後過期,60s後,redis是如何處理的嘛?我們先來介紹幾個過期策略:

定時過期

每個設定過期時間的key都需要建立一個計時器,到過期時間就會立即對key進行清除。此策略可以立即清除過期的數據,對記憶體很友善;但是會佔用大量的CPU資源去處理過期的數據,從而影響快取的回應時間和吞吐量。

惰性過期

只有當存取一個key時,才會判斷該key是否已過期,過期則清除。此策略可以最大化地節省CPU資源,卻對記憶體非常不友善。極端情況可能出現大量的過期key沒有再次被訪問,從而不會被清除,佔用大量內存。

定期過期

每隔一定的時間,會掃描一定數量的資料庫的expires字典中一定數量的key,並清除其中已過期的key。該策略是前兩者的一個折衷方案。透過調整定時掃描的時間間隔和每次掃描的限定耗時,可以在不同情況下使得CPU和記憶體資源達到最優的平衡效果。

expires字典會保存所有設定了過期時間的key的過期時間數據,其中,key是指向鍵空間中的某個鍵的指針,value是該鍵的毫秒精度的UNIX時間戳表示的過期時間。鍵空間是指該Redis集群中保存的所有鍵。

Redis中同時使用了惰性過期和定期過期兩種過期策略。

  • 假設Redis目前存放30萬個key,並且都設定了過期時間,如果你每隔100ms就去檢查這全部的key,CPU負載會特別高,最後可能會掛掉。
  • 因此,redis採取的是定期過期,每隔100ms就隨機抽取一定數量的key來檢查和刪除的。
  • 但是呢,最後可能會有很多已經過期的key沒被刪除。這時候,redis採用惰性刪除。在你取得某個key的時候,redis會檢查一下,這個key如果設定了過期時間並且已經過期了,此時就會刪除。

但是呀,如果定期刪除漏掉了很多過期的key,然後也沒走惰性刪除。就會有很多過期key積在內存內存,直接會導致內存爆的。或者有些時候,業務量大起來了,redis的key被大量使用,內存直接不夠了,維運小哥哥也忘記加大內存了。難道redis直接這樣掛掉?不會的! Redis用8種記憶體淘汰策略保護自己~

6.2 Redis 記憶體淘汰策略

  • #volatile-lru:當記憶體不足以容納新寫入資料時,從設置了過期時間的key中使用LRU(最近最少使用)演算法進行淘汰;
  • allkeys-lru:當記憶體不足以容納新寫入資料時,從所有key中使用LRU(最近最少使用)演算法進行淘汰。
  • volatile-lfu:4.0版本新增,當記憶體不足以容納新寫入資料時,在過期的key中,使用LFU演算法進行刪除key。
  • allkeys-lfu:4.0版本新增,當記憶體不足以容納新寫入資料時,從所有key中使用LFU演算法進行淘汰;
  • volatile-random:當記憶體不足以容納新寫入資料時,從設定了過期時間的key中,隨機淘汰資料;。
  • allkeys-random:當記憶體不足以容納新寫入資料時,從所有key中隨機淘汰資料。
  • volatile-ttl:當記憶體不足以容納新寫入資料時,在設定了過期時間的key中,根據過期時間進行淘汰,越早過期的優先被淘汰;
  • noeviction:預設策略,當記憶體不足以容納新寫入資料時,新寫入操作會報錯。

7.說說Redis的常用應用程式場景

  • 快取
  • 排行榜
  • ##計數器應用程式
  • 共享Session
  • 分散式鎖定
  • 社交網路
  • 訊息佇列
  • 位元操作
7.1 快取

我們一提到redis,自然而然就想到緩存,國內外中大型的網站都離不開緩存。合理的利用緩存,例如快取熱點數據,不僅可以提升網站的存取速度,還可以降低資料庫DB的壓力。並且,Redis相比於memcached,也提供了豐富的資料結構,並且提供RDB和AOF等持久化機制,強的一批。

7.2 排行榜

當今網路應用,有各種各樣的排行榜,如電商網站的月度銷售排行榜、社交APP的禮物排行榜、小程式的投票排行榜等等。 Redis提供的

zset資料類型能夠實現這些複雜的排行榜。

例如,用戶每天上傳視頻,獲得點讚的排行榜可以這樣設計:

  • 1.用户Jay上传一个视频,获得6个赞,可以酱紫:
zadd user:ranking:2021-03-03 Jay 3
    1. 过了一段时间,再获得一个赞,可以这样:
zincrby user:ranking:2021-03-03 Jay 1
    1. 如果某个用户John作弊,需要删除该用户:
zrem user:ranking:2021-03-03 John
    1. 展示获取赞数最多的3个用户
zrevrangebyrank user:ranking:2021-03-03 0 2

7.3 计数器应用

各大网站、APP应用经常需要计数器的功能,如短视频的播放数、电商网站的浏览数。这些播放数、浏览数一般要求实时的,每一次播放和浏览都要做加1的操作,如果并发量很大对于传统关系型数据的性能是一种挑战。Redis天然支持计数功能而且计数的性能也非常好,可以说是计数器系统的重要选择。

7.4 共享Session

如果一个分布式Web服务将用户的Session信息保存在各自服务器,用户刷新一次可能就需要重新登录了,这样显然有问题。实际上,可以使用Redis将用户的Session进行集中管理,每次用户更新或者查询登录信息都直接从Redis中集中获取。

7.5 分布式锁

几乎每个互联网公司中都使用了分布式部署,分布式服务下,就会遇到对同一个资源的并发访问的技术难题,如秒杀、下单减库存等场景。

  • 用synchronize或者reentrantlock本地锁肯定是不行的。
  • 如果是并发量不大话,使用数据库的悲观锁、乐观锁来实现没啥问题。
  • 但是在并发量高的场合中,利用数据库锁来控制资源的并发访问,会影响数据库的性能。
  • 实际上,可以用Redis的setnx来实现分布式的锁。

7.6 社交网络

赞/踩、粉丝、共同好友/喜好、推送、下拉刷新等是社交网站的必备功能,由于社交网站访问量通常比较大,而且传统的关系型数据不太适保存 这种类型的数据,Redis提供的数据结构可以相对比较容易地实现这些功能。

7.7 消息队列

消息队列是大型网站必用中间件,如ActiveMQ、RabbitMQ、Kafka等流行的消息队列中间件,主要用于业务解耦、流量削峰及异步处理实时性低的业务。Redis提供了发布/订阅及阻塞队列功能,能实现一个简单的消息队列系统。另外,这个不能和专业的消息中间件相比。

7.8 位操作

用于数据量上亿的场景下,例如几亿用户系统的签到,去重登录次数统计,某用户是否在线状态等等。腾讯10亿用户,要几个毫秒内查询到某个用户是否在线,能怎么做?千万别说给每个用户建立一个key,然后挨个记(你可以算一下需要的内存会很恐怖,而且这种类似的需求很多。这里要用到位操作——使用setbit、getbit、bitcount命令。原理是:redis内构建一个足够长的数组,每个数组元素只能是0和1两个值,然后这个数组的下标index用来表示用户id(必须是数字哈),那么很显然,这个几亿长的大数组就能通过下标和元素值(0和1)来构建一个记忆系统。

8. Redis 的持久化机制有哪些?优缺点说说

Redis是基于内存的非关系型K-V数据库,既然它是基于内存的,如果Redis服务器挂了,数据就会丢失。为了避免数据丢失了,Redis提供了持久化,即把数据保存到磁盘。

Redis提供了RDB和AOF两种持久化机制,它持久化文件加载流程如下:

1總結分享20個關於Redis的經典面試題(附答案分析)

8.1 RDB

RDB,就是把内存数据以快照的形式保存到磁盘上。

什么是快照?可以这样理解,给当前时刻的数据,拍一张照片,然后保存下来。

RDB持久化,是指在指定的时间间隔内,执行指定次数的写操作,将内存中的数据集快照写入磁盘中,它是Redis默认的持久化方式。执行完操作后,在指定目录下会生成一个dump.rdb文件,Redis 重启的时候,通过加载dump.rdb文件来恢复数据。RDB触发机制主要有以下几种:

1總結分享20個關於Redis的經典面試題(附答案分析)

RDB 的优点

  • 适合大规模的数据恢复场景,如备份,全量复制等

RDB缺点

  • 沒辦法做到即時持久化/秒級持久化。
  • 新舊版存在RDB格式相容問題

AOF

AOF(append only file) 持久化,採用日誌的形式來記錄每個寫入操作,追加到檔案中,重新啟動時再重新執行AOF檔案中的指令來恢復資料。它主要解決資料持久化的即時性問題。預設是不開啟的。

AOF的工作流程如下:

1總結分享20個關於Redis的經典面試題(附答案分析)

AOF的優點

  • 資料的一致性和完整性更高

AOF的缺點

  • AOF記錄的內容越多,檔案越大,資料恢復變慢。

9.怎麼實現Redis的高可用?

我們在專案中使用Redis,絕對不會是單點部署Redis服務的。因為,單點部署一旦宕機,就不可用了。為了實現高可用,通常的做法是,將資料庫複製多個副本以部署在不同的伺服器上,其中一台掛了也可以繼續提供服務。 Redis 實作高可用有三種部署模式:主從模式,哨兵模式,叢集模式

9.1 主從模式

主從模式中,Redis部署了多台機器,有主節點,負責讀寫操作,有從節點,只負責讀取操作。從節點的資料來自主節點,實作原理就是主從複製機制

主從複製包含全量複製,增量複製兩種。一般當slave第一次啟動連接master,或認為第一次連接,就採用全量複製,全量複製流程如下:

1總結分享20個關於Redis的經典面試題(附答案分析)

  • 1.slave發送sync指令到master。
  • 2.master接收到SYNC指令後,執行bgsave指令,產生RDB全量檔。
  • 3.master使用緩衝區,記錄RDB快照產生期間的所有寫入指令。
  • 4.master執行完bgsave後,傳送RDB快照檔給所有slave。
  • 5.slave收到RDB快照檔案後,載入、解析收到的快照。
  • 6.master使用緩衝區,記錄RDB同步期間產生的所有已寫入的命令。
  • 7.master快照發送完畢後,開始向slave發送緩衝區中的寫入命令;
  • 8.salve接受命令請求,並執行來自master緩衝區的寫入命令

redis2.8版本之後,已經使用psync來取代sync,因為sync指令非常消耗系統資源,psync的效率更高。

slave與master全量同步之後,master上的數據,如果再次發生更新,就會觸發增量複製

當master節點發生資料增減時,就會觸發replicationFeedSalves()函數,接下來在Master節點上呼叫的每一個指令會使用replicationFeedSlaves()來同步到Slave節點。執行此函數之前呢,master節點會判斷使用者執行的指令是否有資料更新,如果有資料更新的話,且slave節點不為空,就會執行此函數。這個函數作用就是:把使用者執行的指令傳送到所有的slave節點,讓slave節點執行。流程如下:

1總結分享20個關於Redis的經典面試題(附答案分析)

9.2 哨兵模式

主從模式中,一旦主節點因故障無法提供服務,需要人工將從節點晉升為主節點,同時也要通知應用方更新主節點位址。顯然,多數業務場景都不能接受這種故障處理方式。 Redis從2.8開始正式提供了Redis Sentinel(哨兵)架構來解決這個問題。

哨兵模式,由一個或多個Sentinel實例組成的Sentinel系統,它可以監視所有的Redis主節點和從節點,並在被監視的主節點進入下線狀態時,會自動將下線主伺服器屬下的某個從節點升級為新的主節點。但是呢,一個哨兵程序對Redis節點進行監控,就可能會出現問題(單點問題),因此,可以使用多個哨兵來進行監控Redis節點,並且各個哨兵之間還會進行監控。

總結分享20個關於Redis的經典面試題(附答案分析)

簡單來說,哨兵模式就三個作用:

  • #發送命令,等待Redis伺服器(包括主伺服器和從伺服器)返回監控其運作狀態;
  • 哨兵監測到主節點宕機,會自動將從節點切換成主節點,然後透過發布訂閱模式通知其他的從節點,修改設定文件,讓它們切換主機;
  • 哨兵之間也會互相監控,從而達到高可用。

故障切換的過程是怎麼樣的呢

假設主伺服器宕機,哨兵1先偵測到這個結果,系統並不會馬上進行 failover 過程,只是哨兵1主觀的認為主伺服器不可用,這個現象成為主觀下線。當後面的哨兵也偵測到主伺服器不可用,數量達到一定值時,那麼哨兵之間就會進行一次投票,投票的結果由一個哨兵發起,進行 failover 操作。切換成功後,就會透過發布訂閱模式,讓各個哨兵把自己監控的從伺服器實作切換主機,這個過程稱為客觀下線。這樣對於客戶端而言,一切都是透明的。

哨兵的工作模式如下:

  • 每個Sentinel以每秒鐘一次的頻率向它所知的Master,Slave以及其他Sentinel實例發送一個PING命令。

  • 如果一個實例(instance)距離最後一次有效回覆PING 指令的時間超過down-after-milliseconds 選項所指定的值, 則這個實例會被Sentinel標記為主觀下線。

  • 如果一個Master被標記為主觀下線,則正在監視這個Master的所有 Sentinel 要以每秒一次的頻率確認Master的確進入了主觀下線狀態。

  • 當有足夠數量的Sentinel(大於等於設定檔指定的值)在指定的時間範圍內確認Master的確進入了主觀下線狀態, 則Master會被標記為客觀下線。

  • 在一般情況下, 每個 Sentinel 會以每10秒一次的頻率向它已知的所有Master,Slave發送 INFO 命令。

  • 當Master被Sentinel 標記為客觀下線時,Sentinel 向下線的Master 的所有Slave 發送INFO 命令的頻率會從10 秒一次改為每秒一次

  • 若沒有足夠數量的Sentinel同意Master已經下線, Master的客觀下線狀態就會被移除;若Master 重新向Sentinel 的PING 命令返回有效回复, Master 的主觀下線狀態就會被移除。

9.3 Cluster叢集模式

哨兵模式基於主從模式,實現讀寫分離,它還可以自動切換,系統可用性更高。但是它每個節點存儲的數據是一樣的,浪費內存,並且不好在線擴容。 因此,Cluster叢集應運而生,它在Redis3.0加入的,實現了Redis的分散式儲存。將資料分片,也就是說每台Redis節點上儲存不同的內容,來解決線上擴充的問題。並且,它也提供複製和故障轉移的功能。

Cluster叢集節點的通訊

一個Redis叢集由多個節點組成,各個節點之間是怎麼通訊的呢?透過Gossip協定

Redis Cluster叢集透過Gossip協定進行通信,節點先前不斷交換訊息,交換的訊息內容包括節點出現故障、新節點加入、主從節點變更訊息、slot訊息等等。常用的Gossip訊息分為4種,分別是:ping、pong、meet、fail。

總結分享20個關於Redis的經典面試題(附答案分析)

  • meet訊息:通知新節點加入。訊息發送者通知接收者加入到目前集群,meet訊息通訊正常完成後,接收節點會加入到集群中並進行週期性的ping、pong訊息交換。
  • ping訊息:叢集內交換最頻繁的訊息,叢集內每個節點每秒向多個其他節點發送ping訊息,用於偵測節點是否在線上和交換彼此狀態資訊。
  • pong訊息:當接收到ping、meet訊息時,作為回應訊息回覆給發送方確認訊息正常通訊。 pong訊息內部封裝了自身狀態資料。節點也可以向叢集內廣播自身的pong訊息來通知整個叢集對自身狀態進行更新。
  • fail訊息:當節點判定叢集內另一個節點下線時,會向叢集內廣播一個fail訊息,其他節點接收到fail訊息之後把對應節點更新為下線狀態。

特別的,每個節點是透過叢集匯流排(cluster bus) 與其他的節點進行通訊的。通訊時,使用特殊的連接埠號,即對外服務埠號加10000。例如如果某個node的連接埠號碼是6379,那麼它與其它nodes通訊的連接埠號碼是 16379。 nodes 之間的通訊採用特殊的二進位協定。

Hash Slot插槽演算法

既然是分散式存儲,Cluster叢集使用的分散式演算法是一致性Hash嘛?並不是,而是Hash Slot插槽演算法

插槽演算法把整個資料庫被分成16384個slot(槽),每個進入Redis的鍵值對,根據key進行散列,分配到這16384插槽中的一個。使用的雜湊映射也比較簡單,用CRC16演算法計算出一個16 位元的值,再對16384取模。資料庫中的每個鍵都屬於這16384個槽的其中一個,叢集中的每個節點都可以處理這16384個槽。

叢集中的每個節點負責一部分的hash槽,例如目前叢集有A、B、C個節點,每個節點上的雜湊槽數=16384/3,那麼就有:

  • 節點A負責0~5460號雜湊槽
  • 節點B負責5461~10922號雜湊槽
  • 節點C負責10923~16383號雜湊槽

Redis Cluster叢集

Redis Cluster叢集中,需要確保16384個插槽對應的node都正常運作,如果某個node出現故障,它負責的slot也會失效,整個集群將不能工作。

因此為了保證高可用,Cluster叢集引入了主從複製,一個主節點對應一個或多個從節點。當其它主節點 ping 一個主節點 A 時,如果半數以上的主節點與 A 通訊逾時,那麼就認為主節點 A 宕機了。如果主節點宕機時,就會啟用從節點。

在Redis的每一個節點上,都有兩個玩意,一個是插槽(slot),它的取值範圍是016383。另外一個是cluster,可以理解為一個叢集管理的插件。當我們訪問的key到達時,Redis 會根據CRC16演算法得到一個16 bit的值,然後把結果對16384取模。醬紫每個key都會對應一個編號在016383 之間的哈希槽,透過這個值,去找到對應的插槽所對應的節點,然後直接自動跳到這個對應的節點上進行訪問操作。

雖然資料是分開儲存在不同節點上的,但對客戶端來說,整個叢集Cluster,被看做一個整體。客戶端端連接任一個node,看起來跟操作單實例的Redis一樣。當客戶端操作的key沒有被指派到正確的node節點時,Redis會回傳轉向指令,最後指向正確的node,這有點像是瀏覽器頁面的302 重定向跳轉。

2總結分享20個關於Redis的經典面試題(附答案分析)

故障轉移

Redis叢集實現了高可用,當叢集內節點發生故障時,透過故障轉移,以確保集群正常對外提供服務。

redis叢集透過ping/pong訊息,實現故障發現。這個環境包括主觀下線和客觀下線

主觀下線: 某個節點認為另一個節點不可用,即下線狀態,這個狀態並不是最終的故障判定,只能代表一個節點的意見,可能存在誤判情況。

2總結分享20個關於Redis的經典面試題(附答案分析)

客觀下線: 指標記一個節點真正的下線,集群內多個節點都認為該節點不可用,從而達成共識的結果。如果是持有槽的主節點故障,則需要為該節點進行故障轉移。

  • 假如節點A標記節點B為主觀下線,一段時間後,節點A透過訊息把節點B的狀態發到其它節點,當節點C接受到訊息並解析出訊息體時,如果發現節點B的pfail狀態時,會觸發客觀下線流程;
  • 當下線為主節點時,此時Redis Cluster叢集為統計持有槽的主節點投票,看投票數是否達到一半,當下線報告統計數大於一半時,被標記為客觀下線狀態。

流程如下:

2總結分享20個關於Redis的經典面試題(附答案分析)

故障復原:故障發現後,如果下線節點的是主節點,則需要在它的從節點中選一個替換它,以保證叢集的高可用。流程如下:

2總結分享20個關於Redis的經典面試題(附答案分析)

  • 資格檢查:檢查從節點是否具備替換故障主節點的條件。
  • 準備選舉時間:資格檢查通過後,更新觸發故障選舉時間。
  • 發起選舉:到了故障選舉時間,進行選舉。
  • 選舉投票:只有持有槽的主節點才有票,從節點收集到足夠的選票(大於一半),觸發替換主節點操作

#10. 使用過Redis分散式鎖嘛?有哪些注意點呢?

分散式鎖定,是控制分散式系統不同程序共同存取共享資源的一種鎖的實作。秒殺下單、搶紅包等等業務場景,都需要用到分散式鎖,我們專案中常使用Redis作為分散式鎖。

选了Redis分布式锁的几种实现方法,大家来讨论下,看有没有啥问题哈。

  • 命令setnx + expire分开写
  • setnx + value值是过期时间
  • set的扩展命令(set ex px nx)
  • set ex px nx + 校验唯一随机值,再删除

10.1 命令setnx + expire分开写

if(jedis.setnx(key,lock_value) == 1){ //加锁
    expire(key,100); //设置过期时间
    try {
        do something  //业务请求
    }catch(){
  }
  finally {
       jedis.del(key); //释放锁
    }
}

如果执行完setnx加锁,正要执行expire设置过期时间时,进程crash掉或者要重启维护了,那这个锁就“长生不老”了,别的线程永远获取不到锁啦,所以分布式锁不能这么实现。

10.2 setnx + value值是过期时间

long expires = System.currentTimeMillis() + expireTime; //系统时间+设置的过期时间
String expiresStr = String.valueOf(expires);

// 如果当前锁不存在,返回加锁成功
if (jedis.setnx(key, expiresStr) == 1) {
        return true;
} 
// 如果锁已经存在,获取锁的过期时间
String currentValueStr = jedis.get(key);

// 如果获取到的过期时间,小于系统当前时间,表示已经过期
if (currentValueStr != null && Long.parseLong(currentValueStr) < System.currentTimeMillis()) {

     // 锁已过期,获取上一个锁的过期时间,并设置现在锁的过期时间(不了解redis的getSet命令的小伙伴,可以去官网看下哈)
    String oldValueStr = jedis.getSet(key_resource_id, expiresStr);
    
    if (oldValueStr != null && oldValueStr.equals(currentValueStr)) {
         // 考虑多线程并发的情况,只有一个线程的设置值和当前值相同,它才可以加锁
         return true;
    }
}
        
//其他情况,均返回加锁失败
return false;
}

笔者看过有开发小伙伴是这么实现分布式锁的,但是这种方案也有这些缺点

  • 过期时间是客户端自己生成的,分布式环境下,每个客户端的时间必须同步。
  • 没有保存持有者的唯一标识,可能被别的客户端释放/解锁。
  • 锁过期的时候,并发多个客户端同时请求过来,都执行了jedis.getSet(),最终只能有一个客户端加锁成功,但是该客户端锁的过期时间,可能被别的客户端覆盖。

10.3: set的扩展命令(set ex px nx)(注意可能存在的问题)

if(jedis.set(key, lock_value, "NX", "EX", 100s) == 1){ //加锁
    try {
        do something  //业务处理
    }catch(){
  }
  finally {
       jedis.del(key); //释放锁
    }
}

这个方案可能存在这样的问题:

  • 锁过期释放了,业务还没执行完。
  • 锁被别的线程误删。

10.4 set ex px nx + 校验唯一随机值,再删除

if(jedis.set(key, uni_request_id, "NX", "EX", 100s) == 1){ //加锁
    try {
        do something  //业务处理
    }catch(){
  }
  finally {
       //判断是不是当前线程加的锁,是才释放
       if (uni_request_id.equals(jedis.get(key))) {
        jedis.del(key); //释放锁
        }
    }
}

在这里,判断当前线程加的锁和释放锁是不是一个原子操作。如果调用jedis.del()释放锁的时候,可能这把锁已经不属于当前客户端,会解除他人加的锁

2總結分享20個關於Redis的經典面試題(附答案分析)

一般也是用lua脚本代替。lua脚本如下:

if redis.call(&#39;get&#39;,KEYS[1]) == ARGV[1] then 
   return redis.call(&#39;del&#39;,KEYS[1]) 
else
   return 0
end;

这种方式比较不错了,一般情况下,已经可以使用这种实现方式。但是存在锁过期释放了,业务还没执行完的问题(实际上,估算个业务处理的时间,一般没啥问题了)。

11. 使用过Redisson嘛?说说它的原理

分布式锁可能存在锁过期释放,业务没执行完的问题。有些小伙伴认为,稍微把锁过期时间设置长一些就可以啦。其实我们设想一下,是否可以给获得锁的线程,开启一个定时守护线程,每隔一段时间检查锁是否还存在,存在则对锁的过期时间延长,防止锁过期提前释放。

当前开源框架Redisson就解决了这个分布式锁问题。我们一起来看下Redisson底层原理是怎样的吧:

2總結分享20個關於Redis的經典面試題(附答案分析)

只要线程一加锁成功,就会启动一个watch dog看门狗,它是一个后台线程,会每隔10秒检查一下,如果线程1还持有锁,那么就会不断的延长锁key的生存时间。因此,Redisson就是使用Redisson解决了锁过期释放,业务没执行完问题。

12. 什么是Redlock算法

Redis一般都是集群部署的,假设数据在主从同步过程,主节点挂了,Redis分布式锁可能会有哪些问题呢?一起来看些这个流程图:

2總結分享20個關於Redis的經典面試題(附答案分析)

如果线程一在Redis的master节点上拿到了锁,但是加锁的key还没同步到slave节点。恰好这时,master节点发生故障,一个slave节点就会升级为master节点。线程二就可以获取同个key的锁啦,但线程一也已经拿到锁了,锁的安全性就没了。

为了解决这个问题,Redis作者 antirez提出一种高级的分布式锁算法:Redlock。Redlock核心思想是这样的:

搞多个Redis master部署,以保证它们不会同时宕掉。并且这些master节点是完全相互独立的,相互之间不存在数据同步。同时,需要确保在这多个master实例上,是与在Redis单实例,使用相同方法来获取和释放锁。

我们假设当前有5个Redis master节点,在5台服务器上面运行这些Redis实例。

2總結分享20個關於Redis的經典面試題(附答案分析)

RedLock的实现步骤:如下

  • 1.取得目前時間,以毫秒為單位。
  • 2.依序向5個master節點要求加鎖。客戶端設定網路連線和回應逾時時間,且逾時時間要小於鎖的失效時間。 (假設鎖自動失效時間為10秒,則超時時間一般在5-50毫秒之間,我們就假設超時時間是50ms吧)。如果逾時,跳過該master節點,盡快去嘗試下一個master節點。
  • 3.客戶端使用目前時間減去開始取得鎖定時間(即步驟1記錄的時間),以取得鎖定使用的時間。當且僅當超過一半(N/2 1,這裡是5/2 1=3個節點)的Redis master節點都獲得鎖,且使用的時間小於鎖失效時間時,鎖才算成功。 (如上圖,10s> 30ms 40ms 50ms 4m0s 50ms)
  • 如果取到了鎖,key的真正有效時間就變啦,需要減去取得鎖所使用的時間。
  • 如果取得鎖定失敗(沒有在至少N/2 1個master實例取到鎖,有或取得鎖定時間已經超過了有效時間),客戶端要在所有的master節點上解鎖(即便有些master節點根本沒有加鎖成功,也需要解鎖,以防止有些漏網之魚)。

簡化下步驟就是:

  • 依序向5個master節點請求加鎖
  • 根據設定的逾時時間來判斷,是不是要跳過該master節點。
  • 如果大於等於三個節點加鎖成功,且使用的時間小於鎖的有效期,即可認定加鎖成功啦。
  • 如果取得鎖定失敗,解鎖!

13. Redis的跳躍表

總結分享20個關於Redis的經典面試題(附答案分析)

  • #跳躍表是有序集合zset的底層實作之一
  • 跳躍表支援平均O(logN),最壞O(N)複雜度的節點查找,也可以透過順序性操作批次處理節點。
  • 跳躍表實作由zskiplist和zskiplistNode兩個結構組成,其中zskiplist用於保存跳躍表資訊(如表頭節點、表尾節點、長度),而zskiplistNode則用於表示跳躍表節點。
  • 跳躍表就是在鍊錶的基礎上,增加多層索引提升查找效率。

14. MySQL與Redis 如何保證雙重寫入一致性

  • 快取延時雙刪
  • 刪除快取重試機制
  • 讀取biglog非同步刪除快取

14.1 延時雙刪?

什麼是延時雙刪呢?流程圖如下:

總結分享20個關於Redis的經典面試題(附答案分析)

  • 先刪除快取

  • 再更新資料庫

  • #休眠一會(例如1秒),再次刪除快取。

這個休眠一會,通常多久呢?都是1秒?

這個休眠時間 =  讀業務邏輯資料的耗時 幾百毫秒。為了確保讀取請求結束,寫入請求可以刪除讀取請求可能帶來的快取髒資料。

這種方案還算可以,只有休眠那一會(比如就那1秒),可能有髒數據,一般業務也會接受的。但是如果第二次刪除快取失敗呢?快取和資料庫的資料還是可能不一致,對吧?給Key設定一個自然的expire過期時間,讓它自動過期怎麼樣?那業務要接受過期時間內,數據的不一致咯?還是有其他更佳方案呢?

14.2 刪除快取重試機制

因為延時雙刪可能會存在第二步驟的刪除快取失敗,導致的資料不一致問題。可以使用這個方案優化:刪除失敗就多刪除幾次呀,保證刪除快取成功就可以了呀~ 所以可以引入刪除快取重試機制

3總結分享20個關於Redis的經典面試題(附答案分析)

  • #寫入請求更新資料庫

  • 快取因為某些原因,刪除失敗

  • 把刪除失敗的key放到訊息佇列

  • 消費訊息佇列的訊息,取得要刪除的key

  • #重試刪除快取作業

14.3 讀取biglog非同步刪除快取

重試刪除快取機制還可以吧,就是會造成好多業務程式碼入侵。其實,還可以這樣優化:透過資料庫的binlog來非同步淘汰key。

3總結分享20個關於Redis的經典面試題(附答案分析)

以mysql為例吧

  • 可以使用阿里的canal將binlog日誌擷取傳送到MQ佇列裡面
  • 然後透過ACK機制確認處理這條更新訊息,刪除緩存,保證資料快取一致性

15. 為什麼Redis 6.0 之後改多執行緒呢?

  • Redis6.0之前,Redis在處理客戶端的請求時,包括讀socket、解析、執行、寫socket等都由一個順序串行的主線程處理,這就是所謂的「單線程」。
  • Redis6.0之前為什麼一直不使用多執行緒?使用Redis時,幾乎不存在CPU成為瓶頸的情況, Redis主要受限於記憶體和網路。例如在一個普通的Linux系統上,Redis透過使用pipelining每秒可以處理100萬個請求,所以如果應用程式主要使用O(N)或O(log(N))的命令,它幾乎不會佔用太多CPU。

redis使用多線程並非是完全摒棄單線程,redis還是使用單線程模型來處理客戶端的請求,只是使用多線程來處理資料的讀寫和協議解析,執行命令還是使用單線程。

這樣做的目的是因為redis的效能瓶頸在於網路IO而非CPU,使用多執行緒能提升IO讀寫的效率,進而整體提升redis的效能。

16. 聊聊Redis 事務機制

Redis透過MULTI、EXEC、WATCH等一組指令集合,來實現交易機制。事務支援一次執行多個命令,一個事務中所有命令都會被序列化。在事務執行過程,會依照順序串列化執行佇列中的命令,其他客戶端提交的命令請求不會插入到交易執行命令序列中。

簡言之,Redis事務就是順序性、一次性、排他性的執行一個佇列中的一系列指令。

Redis執行交易的流程如下:

  • 開始交易(MULTI)
  • 命令入隊
  • 執行交易(EXEC)、撤銷事務(DISCARD )
##EXECEXEC執行所有事務區塊內的指令DISCARD#取消事務,放棄執行事務區塊內的所有指令MULTI標記一個交易區塊的開始UNWATCH取消WATCH 指令對所有key 的監視。
指令 #描述
#########WATCH######監視key ,如果在交易執行之前,該key 被其他指令所改動,那麼事務將被打斷。 ############

17. Redis的Hash 衝突怎麼辦

Redis 作為一個K-V的記憶體資料庫,它使用用一張全域的哈希來保存所有的鍵值對。這張哈希表,有多個哈希桶組成,哈希桶中的entry元素保存了key和value指針,其中*key指向了實際的鍵,*value指向了實際的值。

3總結分享20個關於Redis的經典面試題(附答案分析)

哈希表查找速率很快的,有點類似Java中的HashMap,它讓我們在O(1) 的時間複雜度快速找到鍵值對。首先透過key計算哈希值,找到對應的哈希桶位置,然後定位到entry,在entry找到對應的資料。

什麼是哈希衝突?

哈希衝突: 透過不同的key,計算相同的雜湊值,導致落在同一個哈希桶中。

Redis為了解決哈希衝突,採用了鍊式哈希。鍊式雜湊是指同一個雜湊桶中,多個元素用一個鍊錶來保存,它們之間依序用指標連接。

3總結分享20個關於Redis的經典面試題(附答案分析)

有些讀者可能還會有疑問:哈希衝突鏈上的元素只能透過指標逐一找到再操作。當往哈希表插入資料很多,衝突也會越多,衝突鍊錶就會越長,那麼查詢效率就會降低了。

為了保持高效,Redis 會對哈希表做rehash操作,也就是增加哈希桶,減少衝突。為了rehash更有效率,Redis也預設使用了兩個全域雜湊表,一個用於目前使用,稱為主雜湊表,一個用於擴容,稱為備用雜湊表

18. 在產生 RDB期間,Redis 可以同時處理寫入請求麼?

可以的,Redis提供兩個指令產生RDB,分別是save和bgsave

  • 如果是save指令,會阻塞,因為是主執行緒執行的。
  • 如果是bgsave指令,是fork一個子程序來寫入RDB檔案的,快照持久化完全交給子程序來處理,父程序則可以繼續處理客戶端的請求。

19. Redis底層,使用的什麼協定?

RESP,英文全名為Redis Serialization Protocol,它是專門為redis設計的一套序列化協定. 這個協定其實在redis的1.2版本時就已經出現了,但是到了redis2.0才最終成為redis通訊協議的標準。

RESP主要有實作簡單、解析速度快、可讀性好等優點。

20. 布隆過濾器

應對快取穿透問題,我們可以使用布隆過濾器。布隆過濾器是什麼呢?

布隆過濾器是一種佔用空間很小的資料結構,它由一個很長的二進位向量和一組Hash映射函數組成,它用於檢索一個元素是否在一個集合中,空間效率和查詢時間都比一般的演算法好的多,缺點是有一定的誤辨識率和刪除困難。

布隆過濾器原理是? 假設我們有個集合A,A中有n個元素。利用k個雜湊雜湊函數,將A中的每個元素映射到長度為a位的陣列B中的不同位置上,這些位置上的二進位數均設定為1。如果待檢查的元素,經過這k個雜湊函數的映射後,發現其k個位置上的二進制數全部為1,這個元素很可能屬於集合A,反之,一定不屬於集合A

來看個簡單例子吧,假設集合A有3個元素,分別為{d1,d2,d3}。有1個哈希函數,為Hash1。現在將A的每個元素映射到長度為16位數組B。

3總結分享20個關於Redis的經典面試題(附答案分析)

我們現在把d1映射過來,假設Hash1(d1)= 2,我們就把數組B中,下標為2的格子改成1,如下:

3總結分享20個關於Redis的經典面試題(附答案分析)

我們現在把d2也映射過來,假設Hash1(d2)= 5,我們把陣列B中,下標為5的格子也改成1,如下:

3總結分享20個關於Redis的經典面試題(附答案分析)

接著我們把d3也映射過來,假設Hash1(d3)也等於2,它也是把下標為2的格子標1:

3總結分享20個關於Redis的經典面試題(附答案分析)

因此,我們要確認一個元素dn是否在集合A裡,我們只要算出Hash1(dn)得到的索引下標,只要是0,那就表示這個元素不在集合A,如果索引下標是1呢?那該元素可能是A中的某一個元素。因為你看,d1和d3得到的下標值,都可能是1,還可能是其他別的數映射的,布隆過濾器是存在這個缺點的:會存在hash碰撞導致的假陽性,判斷存在誤差。

如何減少這個誤差呢?

  • 搞多幾個雜湊函數映射,降低雜湊碰撞的機率
  • 同時增加B數組的bit長度,可以增加hash函數產生的資料的範圍,也可以降低哈希碰撞的機率

我們又增加一個Hash2哈希映射函數,假設Hash2(d1)=6,Hash2(d3)=8,它兩個不就不衝突了嘛,如下:

總結分享20個關於Redis的經典面試題(附答案分析)

即使存在誤差,我們可以發現,布隆過濾器並沒有存放完整的資料,它只是運用一系列雜湊映射函數計算出位置,然後填入二進位向量。如果數量很大的話,布隆過濾器透過極少的錯誤率,換取了儲存空間的極大節省,還是挺划算的。

目前布林過濾器已經有對應實作的開源類別庫啦,例如Google的Guava類別庫,Twitter的Algebird 類別庫,信手拈來即可,或是基於Redis自帶的Bitmaps自行實作設計也是可以的。

更多程式相關知識,請造訪:程式設計影片! !

以上是總結分享20個關於Redis的經典面試題(附答案分析)的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文轉載於:juejin.cn。如有侵權,請聯絡admin@php.cn刪除