Redis解讀（4）：Redis中HyperLongLog、布隆過濾器、限流、Geo、及Scan等進階應用

Redis中的HyperLogLog

一般我們評估一個網站的訪問量，有幾個主要的參數：

pv，Page View，網頁的瀏覽量
uv，User View，訪問的用戶

一般來說，pv 或者 uv 的統計，可以自己來做，也可以借助一些第三方的工具，比如 cnzz，友盟等。

如果自己實現，pv 比較簡單，可以直接通過 Redis 計數器就能實現。但是 uv 就不一樣，uv 涉及到另外一個問題，去重。

我們首先需要在前端給每一個用戶生成一個唯一 id，無論是登錄用戶還是未登錄用戶，都要有一個唯一 id，這個 id 伴隨著請求一起到達后端，在后端我們通過 set 集合中的 sadd 命令來存儲這個 id，最后通過 scard 統計集合大小，進而得出 uv 數據。

HyperLogLog 問題場景:

例如：CSDN、博客園這種網站首頁，或者商城的爆款頁面、活動頁面。高峰時期都是千萬級別的 UV，需要的存儲空間就非常驚人，通過Redis中的 Set類型數據結構存儲，并不是最佳的解決方案。而且，像 UV 統計這種，一般也不需要特別精確，對于網站服務商來說，800w 的 uv 和 803w 的 uv 數據，其實差別不大。所以，這個場景下，Redis中的 HyperLogLog 就能很好的去解決這個問題。

HyperLogLog 提供了一套不怎么精確但是夠用的去重方案，會有誤差，官方給出的誤差數據是 0.81%，這個精確度，統計 UV 夠用了。

HyperLogLog 主要提供了兩個命令：pfadd 和 pfcount。

pfadd 用來添加記錄，類似于 sadd ，添加過程中，重復的記錄會自動去重。

pfcount 則用來統計數據。

127.0.0.1:6379> pfadd uv u1 u2 u3
(integer) 1
127.0.0.1:6379> PFCOUNT uv
(integer) 3
127.0.0.1:6379> pfadd uv u1 u2 u3 u3 u2 u1 u4 
(integer) 1
127.0.0.1:6379> PFCOUNT uv
(integer) 4

目前我們在服務器上統計UV 數據量少的時候看不出來誤差。在 Java 中，我們多添加幾個元素：

package org.taoguoguo.hyper;

import org.taoguoguo.redis.Redis;

/**
 * @author taoguoguo
 * @description HyperLogLog
 * @website http://www.rzrgm.cn/doondo
 * @create 2021-04-18 14:10
 */
public class HyperLogLog {
    public static void main(String[] args) {
        Redis redis = new Redis();
        redis.execute(jedis -> {
            for (int i = 0; i < 1000; i++) {
                //pfadd uv u0 u1
                jedis.pfadd("uv","u"+i,"u"+(i+1));
            }
            long uv = jedis.pfcount("uv");
            System.out.println("uv統計值為:" + uv);
        });
    }
}

控制臺打印值：

SLF4J: Failed to load class "org.slf4j.impl.StaticLoggerBinder".
SLF4J: Defaulting to no-operation (NOP) logger implementation
SLF4J: See http://www.slf4j.org/codes.html#StaticLoggerBinder for further details.
uv統計值為:994

Process finished with exit code 0

理論值是 1001，實際打印出來 994，有誤差，但是在可以接受的范圍內。

除了 pfadd 和 pfcount 之外，還有一個命令 pfmerge ，合并多個統計結果，在合并的過程中，會自動去重多個集合中重復的元素。

布隆過濾器

1.問題場景

我們用 HyperLogLog 來估計一個數，有偏差但是也夠用。HyperLogLog 主要提供兩個方法：

pfadd

pfcount

但是 HyperLogLog 沒有判斷是否包含的方法，例如 pfexists 、pfcontains 等。沒有這樣的方法存在，但是我們有這樣的業務需求。

例如刷今日頭條，推送的內容有相似的，但是沒有重復的，如何將未推送過的內容進行去重推送？50億個電話號碼，清單中的200個已經拉入工信部黑名單，判斷是否在這50億電話號碼中。此類場景如何進行過濾統計？

解決方案很多，例如將用戶的瀏覽歷史記錄下來，然后每次推送時去比較該條消息是否已經給用戶推送了。但是這種方式效率極低，不推薦。即便使用緩存，緩存數據量會特別多，效率也非常低，并不適合此類場景。

使用布隆過濾器，就能很好的解決這個問題。

2.Bloom Filter 介紹

Bloom Filter 專門用來解決我們上面所說的去重問題的，使用 Bloom Filter 不會像使用緩存那么浪費空間。當然，他也存在一個小小問題，就是不太精確。

Bloom Filter 相當于是一個不太精確的 set 集合，我們可以利用它里邊的 contains 方法去判斷某一個對象是否存在，但是需要注意，這個判斷不是特別精確。一般來說，通過 contains 判斷某個值不存在，那就一定不存在，但是判斷某個值存在的話，則他可能不存在。

以今日頭條為例，假設我們將用戶的瀏覽記錄用 B 表示，A 表示用戶沒有瀏覽的新聞，現在要給用戶推送消息，先去 B 里邊判斷這條消息是否已經推送過，如果判斷結果說沒推送過（B 里邊沒有這條記錄），那就一定沒有推送過。如果判斷結果說有推送（B 里邊也有可能沒有這條消息），這個時候該條消息就不會推送給用戶，導致用戶錯過該條消息，當然這是概率極低的。

3.Bloom Filter 原理

每一個布隆過濾器，在 Redis 中都對應了一個大型的位數組以及幾個不同的 hash 函數（無偏hash）。

所謂的 add 操作是這樣的：首先根據幾個不同的 hash 函數給元素進行 hash 運算一個整數索引值，拿到這個索引值之后，對位數
組的長度進行取模運算，得到一個位置，每一個 hash 函數都會得到一個位置，將位數組中對應的位置設置位 1 ，這樣就完成了添加操作。

當判斷元素是否粗存在時，依然先對元素進行 hash 運算，將運算的結果和位數組取模，然后去對應的
位置查看是否有相應的數據，如果有，表示元素可能存在（因為這個有數據的地方也可能是其他元素存
進來的），如果沒有表示元素一定不存在。

Bloom Filter 中，誤判的概率和位數組的大小有很大關系，位數組越大，誤判概率越小，當然占用的存
儲空間越大；位數組越小，誤判概率越大，當然占用的存儲空間就小。

4.Bloom Filter 安裝

布隆過濾器插件官方網站：https://oss.redislabs.com/redisbloom/Quick_Start/

這邊主要介紹三種安裝方式

Docker，指定容器映射端口和別名啟動

docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest

Git 克隆編譯安裝啟動

cd redis-6.2.1
git clone https://github.com/RedisBloom/RedisBloom.git
cd RedisBloom/
make
cd ..
redis-server redis.conf --loadmodule ./RedisBloom/redisbloom.so

上傳tar包，解壓安裝啟動

cd redis-6.2.1
tar -zxvf RedisBloom-2.2.5.tar.gz
mv ./RedisBloom-2.2.5 /home/redis-6.2.1/RedisBloom
redis-server redis.conf --loadmodule ./RedisBloom/redisbloom.so

安裝完成后，執行 bf.add 命令，測試安裝是否成功。

每次啟動時都輸入 redis-server redis.conf --loadmodule ./RedisBloom/redisbloom.so 比較
麻煩，我們可以將要加載的模塊在 redis.conf 中提前配置好。

################################## MODULES #####################################
# Load modules at startup. If the server is not able to load modules
# it will abort. It is possible to use multiple loadmodule directives.
#
# loadmodule /path/to/my_module.so
# loadmodule /path/to/other_module.so
loadmodule /root/redis-5.0.7/RedisBloom/redisbloom.so

最下面這一句，配置完成后，以后只需要 redis-server redis.conf 來啟動 Redis 即可

5.基本用法

主要是兩類命令，添加和判斷是否存在。

bf.add 添加
bf.madd 批量添加
bf.exists 判斷是否存在
bf.mexists 批量判斷

#命令使用示例
127.0.0.1:6379> BF.ADD k1 v1
(integer) 1
127.0.0.1:6379> BF.EXISTS k1 v1
(integer) 1
127.0.0.1:6379> BF.EXISTS k1 v2
(integer) 0
127.0.0.1:6379> BF.MADD k1 v1 v2 v3 v4 
1) (integer) 0
2) (integer) 1
3) (integer) 1
4) (integer) 1
127.0.0.1:6379> BF.MEXISTS k1 v1 v2 v3 v4 v5
1) (integer) 1
2) (integer) 1
3) (integer) 1
4) (integer) 1
5) (integer) 0
127.0.0.1:6379>

使用 Jedis 操作布隆過濾器，首先添加依賴：

<dependency>
  <groupId>com.redislabs</groupId>
  <artifactId>jrebloom</artifactId>
  <version>1.2.0</version>
</dependency>

進行測試：

package org.taoguoguo.bloom;

import io.rebloom.client.Client;
import org.apache.commons.pool2.impl.GenericObjectPoolConfig;
import redis.clients.jedis.JedisPool;

/**
 * @author taoguoguo
 * @description BloomFilter
 * @website http://www.rzrgm.cn/doondo
 * @create 2021-04-21 21:04
 */
public class BloomFilter {

    public static void main(String[] args) {
        GenericObjectPoolConfig config = new GenericObjectPoolConfig();
        config.setMaxIdle(300);
        config.setMaxTotal(1000);
        config.setMaxWaitMillis(30000);
        config.setTestOnBorrow(true);
        JedisPool pool = new JedisPool(config, "192.168.124.5", 6379, 30000, "123456");
        Client client = new Client(pool);
        //存入數據
        for (int i = 0; i < 100000; i++) {
            client.add("name", "taoguoguo-"+ i );
        }
        //判斷是否存在
        boolean exists = client.exists("name", "taoguoguo-9");
        System.out.println(exists);
    }
}

控制臺打印：

SLF4J: Failed to load class "org.slf4j.impl.StaticLoggerBinder".
SLF4J: Defaulting to no-operation (NOP) logger implementation
SLF4J: See http://www.slf4j.org/codes.html#StaticLoggerBinder for further details.
true

布隆過濾器存在是有可能會誤判斷的，我們將判斷數量加大，嘗試執行多次，是會存在誤判的。所以布隆過濾器判斷不存在時一定準確，判斷存在時不一定準確。

6.參數配置

默認情況下，我們使用的布隆過濾器它的錯誤率是 0.01 ，默認的元素大小是 100。但是這兩個參數也
是可以配置的。
我們可以調用 bf.reserve 方法進行配置。

BF.RESERVE k1 0.0001 1000000

第一個參數是 key，第二個參數是錯誤率，錯誤率越低，占用的空間越大，第三個參數預計存儲的數
量，當實際數量超出預計數量時，錯誤率會上升。

7.應用場景

之前說的新聞推送過濾、電話號碼過濾是一個應用場景
緩存穿透問題，又叫緩存擊穿問題。

假設我有 1億條用戶數據，現在查詢用戶要去數據庫中查，效率低而且數據庫壓力大，所以我們會把請
求首先在 Redis 中處理（活躍用戶存在 Redis 中），Redis 中沒有的用戶，再去數據庫中查詢。

現在可能會存在一種惡意請求，這個請求攜帶上了很多不存在的用戶，這個時候 Redis 無法攔截下來請
求，所以請求會直接跑到數據庫里去。這個時候，這些惡意請求會擊穿我們的緩存，甚至數據庫，進而
引起“雪崩效應”。

為了解決這個問題，我們就可以使用布隆過濾器。將 1億條用戶數據存在 Redis 中不現實，但是可以存
在布隆過濾器中，請求來了，首先去判斷數據是否存在，如果存在，再去數據庫中查詢，否則就不去數
據庫中查詢。

Redis限流

1.預備知識

Pipeline（管道）本質上是由客戶端提供的一種操作。Pipeline 通過調整指令列表的讀寫順序，可以大幅度的節省 IO 時間，提高效率。

怎么理解這個呢？假設A用戶在客戶端做寫入緩存操作和讀取緩存操作，B用戶也在客戶端做寫入緩存操作和讀取緩存操作。如果沒有使用Piepline技術，那么A、B用戶寫操作和讀操作一共需要使用4個網絡來回。使用Pipeline進行指令調整，可以把寫操作放入同一個網絡來回進行寫，讀取操作放入同一個網絡來回進行讀取，大幅度節省網絡IO，提高效率。

2.簡單限流

簡單限流思路其實很簡單，就是在一個限流周期的時間窗口允許執行的操作次數，這邊自己編寫的一個代碼如下，能達到基本的限流需求。

package org.taoguoguo.limit;

import org.taoguoguo.redis.Redis;
import redis.clients.jedis.Jedis;
import redis.clients.jedis.Pipeline;
import redis.clients.jedis.Response;

/**
 * @author taoguoguo
 * @description RateLimiter Redis簡單限流
 * @website http://www.rzrgm.cn/doondo
 * @create 2021-04-21 21:49
 */
public class RateLimiter {
    private Jedis jedis;

    public RateLimiter(Jedis jedis) {
        this.jedis = jedis;
    }

    /**
     * 限流方法
     * @param user 操作用戶，相當于限流的對象
     * @param action 具體的操作
     * @param period 時間戳 限流的周期
     * @param maxCount 限流次數
     * @return
     */
    public boolean isAllowed(String user, String action, int period, int maxCount){
        //1.首先生成一個key,數據用zset保存
        String key = user + "-" + action;
        //2.獲取當前時間戳
        long nowTime = System.currentTimeMillis();
        //3.建立管道
        Pipeline pipelined = jedis.pipelined();
        //開啟任務執行
        pipelined.multi();
        //4.將當前操作先存儲下來
        pipelined.zadd(key, nowTime, String.valueOf(nowTime));
        //5.移除時間窗之外的數據 假設我要統計30S內的操作次數 先移除當前時間之前的統計時間周期內的操作次數
        pipelined.zremrangeByScore(key, 0, nowTime- period * 1000);
        //6.統計周期內剩下的key
        Response<Long> response = pipelined.zcard(key);
        //7.將當前key設置一個過期時間，過期時間就是時間窗
        pipelined.expire(key, period+1);
        //執行任務
        pipelined.exec();
        //關閉管道
        pipelined.close();
        return response.get() <= maxCount;
    }

    public static void main(String[] args) {
        Redis redis = new Redis();
        redis.execute(j -> {
            RateLimiter rateLimiter = new RateLimiter(j);
            for (int i = 0; i < 20; i++) {
                boolean allowed = rateLimiter.isAllowed("taoguoguo", "addOrder", 5, 3);
                System.out.println(allowed);
            }
        });
    }
}

3.Redis-Cell 限流

Redis4.0 開始提供了一個 Redis-Cell 模塊，這個模塊使用漏斗算法，提供了一個非常好用的限流指令。

漏斗算法就像名字一樣，是一個漏斗，請求從漏斗的大口進，然后從小口出進入到系統中，這樣，無論
是多大的訪問量，最終進入到系統中的請求，都是固定的。

使用漏斗算法，需要我們首先安裝 Redis-Cell 模塊：https://github.com/brandur/redis-cell

安裝步驟

安裝redis-cell插件

wget https://github.com/brandur/redis-cell/releases/download/v0.2.4/redis-cell-
v0.2.4-x86_64-unknown-linux-gnu.tar.gz
tar -zxvf redis-cell-v0.2.4-x86_64-unknown-linux-gnu.tar.gz
mkdir redis-cell
mv libredis_cell.d ./redis-cell
mv libredis_cell.so ./redis-cell

安裝 GLIBC依賴，不裝GLIBC可能會出現配置完成 reids-cell ,reids服務缺少依賴啟動不成功。

// 下載 glibc 壓縮包
wget http://ftp.gnu.org/gnu/glibc/glibc-2.18.tar.gz 
// 解壓 glibc 壓縮包
tar -zxvf glibc-2.18.tar.gz
// 進入解壓后的目錄
cd glibc-2.18
// 創建編譯目錄
mkdir build
// 進入到創建好的目錄
cd build/
// 編譯、安裝
../configure --prefix=/usr --disable-profile --enable-add-ons --with-headers=/usr/include --with-binutils=/usr/bin

//這步會比較慢
make -j 8

make install

接下來修改 redis.conf 文件，加載額外的模塊

loadmodule /home/redis-6.2.1/redis-cell/libredis_cell.so

然后，啟動 Redis：

redis-server redis.conf

redis 啟動成功后，如果存在 CL.THROTTLE 命令，說明 redis-cell 已經安裝成功了。

CL.THROTTLE 命令使用

該命令一共有五個參數：

第一個參數是 key
第二個參數是漏斗的容量
時間窗內可以操作的次數
時間窗
每次漏出數量

執行完成后，返回值也有五個：

第一個 0 表示允許，1表示拒絕
第二個參數是漏斗的容量
第三個參數是漏斗的剩余空間
如果拒絕了，多長時間后，可以再試
多長時間后，漏斗會完全空出來

命令示例

127.0.0.1:6379> CL.THROTTLE taoguoguo-publish 10 10 60 1
1) (integer) 0
2) (integer) 11
3) (integer) 10
4) (integer) -1
5) (integer) 6

4.客戶端Lettuce拓展

定義一個Redis命令拓展接口，可通過命令描述在客戶端自由拓展Redis的命令

package org.taoguoguo;

import io.lettuce.core.dynamic.Commands;
import io.lettuce.core.dynamic.annotation.Command;

import java.util.List;

/**
 * @author taoguoguo
 * @description RedisCommandInterface   Redis漏斗限流拓展接口
 * @website http://www.rzrgm.cn/doondo
 * @create 2021-04-22 15:29
 */
public interface RedisCommandInterface extends Commands {

    @Command("CL.THROTTLE ?0 ?1 ?2 ?3 ?4")
    List<Object> throttle(String key, long init, long count, Long period, Long quota);

}

命令調用

package org.taoguoguo;

import io.lettuce.core.RedisClient;
import io.lettuce.core.api.StatefulRedisConnection;
import io.lettuce.core.dynamic.RedisCommandFactory;

import java.util.List;

/**
 * @author taoguoguo
 * @description ThrottleTest
 * @website http://www.rzrgm.cn/doondo
 * @create 2021-04-22 15:32
 */
public class ThrottleTest {
    public static void main(String[] args) {
        RedisClient redisClient = RedisClient.create("redis://123456@172.20.10.2");
        StatefulRedisConnection<String, String> connect = redisClient.connect();
        RedisCommandFactory factory = new RedisCommandFactory(connect);
        RedisCommandInterface commands = factory.getCommands(RedisCommandInterface.class);
        List<Object> list = commands.throttle("taoguoguo", 10L, 10L, 60L, 1L);
        System.out.println(list);
    }
}

Redis Geo

Redis3.2 開始提供了 GEO 模塊。該模塊也使用了 GeoHash 算法

1.Geo Hash算法

核心思想：GeoHash 是一種地址編碼方法，使用這種方式，能夠將二維的空間經緯度數據編碼成一個一維字符串。

地球上經緯度的劃分：以經過倫敦格林尼治天文臺舊址的經線為 0 度經線，向東就是東經，向西就是西經。如果我們將西經定
義負，經度的范圍就是 [-180,180]。緯度北緯 90 度到南緯 90 度，如果我們將南緯定義負，則緯度的范圍就是 [-90,90]。

接下來，以本初子午線和赤道為界，我們可以將地球上的點分配到一個二維坐標中：

GeoHash 算法就是基于這樣的思想，劃分的次數越多，區域越多，每個區域中的面積就更小了，精確度就會提高。

GeoHash 具體算法：

? 以北京天安門廣場為例（39.9053908600,116.3980007200）

緯度的范圍在 (-90,90) 之間，中間值為 0，對于 39.9053908600 值落在 (0,90),因此得到的值為 1
(0,90) 的中間值為 45，39.9053908600 落在 (0,45) 之間，因此得到一個 0
(0,45) 的中間值為 22.5，39.9053908600 落在 (22.5,45)之間，因此得到一個 1
......

這樣，我們得到的緯度二進制是 101，按照同樣的步驟，我們可以算出來經度的二進制是 110

接下來將經緯度合并（經度占偶數位，緯度占奇數位）：111001

按照 Base32 （0-9,b-z,去掉 a i l 0）對合并后的二進制數據進行編碼，編碼的時候，先將二進制轉換為
十進制，然后進行編碼。

將編碼得到的字符串，可以拿去 geohash.org 網站上解析

GeoHash 有哪些特點：

用一個字符串表示經緯度
GeoHash 表示的是一個區域，而不是一個點
編碼格式有規律，例如一個地址編碼之后的格式是 123，另一個地址編碼之后的格式是 123456，從字符串上就可以看出來，123456 處于 123 之中。

2.Redis 中的使用

經緯度查詢網站：http://www.gpsspg.com/maps.htm

添加地址：

GEOADD city 116.3980007200 39.9053908600 beijing
GEOADD city 114.0592002900 22.5536230800 shenzhen

查看兩個地址之間的距離：

127.0.0.1:6379> GEODIST city beijing shenzhen km
"1942.5435"

獲取元素的位置：

127.0.0.1:6379> GEOPOS city beijing
1) 1) "116.39800339937210083"
 2) "39.90539144357683909"

獲取元素 hash 值：

127.0.0.1:6379> GEOHASH city beijing
1) "wx4g08w3y00"

通過 hash 值可以查看定位。http://geohash.org/wx4g08w3y00

查看附近的人：

127.0.0.1:6379> GEORADIUSBYMEMBER city beijing 200 km count 3 asc
1) "beijing"

以北京為中心，方圓 200km 以內的城市找出來 3 個，按照遠近順序排列，這個命令不會排除北京。
當然，也可以根據經緯度來查詢（將 member 換成對應的經緯度）：

127.0.0.1:6379> GEORADIUS city 116.3980007200 39.9053908600 2000 km withdist
withhash withcoord count 4 desc

Redis Scan

1.簡單介紹

scan 實際上是 keys 的一個升級版。

可以用 keys 來查詢 key，在查詢的過程中，可以使用通配符。keys 雖然用著還算方便，但是沒有分頁功能。同時因為 Redis 是單線程，所以 key 的執行會比較消耗時間，特別是當數據量大的時候，影響整個程序的運行。

為了解決 keys 存在的問題，從 Redis2.8 中開始，引入了 scan。

scan 具備 keys 的功能，但是不會阻塞線程，而且可以控制每次返回的結果數。

2.基本用法

首先準備 10000 條測試數據：

package org.taoguoguo.scan;

import org.taoguoguo.redis.Redis;

/**
 * @author taoguoguo
 * @description ScanTest
 * @website http://www.rzrgm.cn/doondo
 * @create 2021-04-25 14:27
 */
public class ScanTest {
    public static void main(String[] args) {
        Redis redis = new Redis();
        redis.execute(jedis -> {
            for (int i = 0; i < 10000; i++) {
                jedis.set("k" + i, "v" + i);
            }
        });
    }
}

scan 命令一共提供了三個參數，第一個 cursor，第二個參數是 key，第三個參數是 limit。

cursor 實際上是指一維數組的位置索引，limit 則是遍歷的一維數組個數（所以每次返回的數據大小可能不確定）。

scan 0 match k8* count 1000

3.遍歷原理及漸進式 rehash機制

SCAN的遍歷順序

假設目前有三條數據：

127.0.0.1:6379> keys *
1) "key1"
2) "db_number"
3) "myKey"
127.0.0.1:6379> scan 0 match * count 1
1) "2"
2) 1) "key1"
127.0.0.1:6379> scan 2 match * count 1
1) "1"
2) 1) "myKey"
127.0.0.1:6379> scan 1 match * count 1
1) "3"
2) 1) "db_number"
127.0.0.1:6379> scan 3 match * count 1
1) "0"
2) (empty list or set)
127.0.0.1:6379>

在遍歷的過程中，大家發現游標的順序是 0 2 1 3，從十進制來看好像沒有規律，但是從轉為二進制，則是有規律的：

00->10->01->11

這種規律就是高位進1，傳統的二進制加法，是從右往左加，這里是從左往右加。

實際上，在 Redis 中，它的具體計算流程給是這樣：

將要計算的數字反轉
給反轉后的數字加 1
再反轉

那么為什么不是按照 0、1、2、3、4...這樣的順序遍歷呢？因為主要考慮到兩個問題：

字典擴容
字典縮容

根據Scan遍歷原理假如我們將要訪問 110 時，發生了擴容，此時 scan 就會從 0110 開始遍歷，之前已經被遍歷過的元素就不會被重復遍歷了

假如我們將要訪問 110 時，發生縮容，此時 scan 就會從 10 開始遍歷，這個時候，也會遍歷到 010，但是 010 之前的不會再被遍歷了。所以，在發生縮容的時候，可能返回重復的元素。

Redis一共支持5種數據結構，hash是其中的一種，在hash擴容的時候采用的是漸進式rehash的方式。要想深入理解漸進式rehash，首先要了解以下Redis中hash的數據結構。哈希表節點 typedef struct...

哈希表節點

typedef struct dictEntry {
    void *key; // 鍵
    union {
        void *val;
        uint64_t u64;
        int64_t s64;
        double d;
    } v; // 值
    struct dictEntry *next; // 下一個節點
} dictEntry;

哈希表

/* This is our hash table structure. Every dictionary has two of this as we
 * implement incremental rehashing, for the old to the new table. */
typedef struct dictht {
    dictEntry **table; // 哈希表數組
    unsigned long size; // 哈希表大小
    unsigned long sizemask; // 掩碼，計算索引值，size-1
    unsigned long used; // 哈希表已有節點的數量
} dictht;

字典

typedef struct dict {
    dictType *type; // 類型特定函數
    void *privdata; // 私有數據
    dictht ht[2]; // 哈希表
    // rehash索引
    long rehashidx; /* rehashing not in progress if rehashidx == -1 */
    unsigned long iterators; /* number of iterators currently running */
} dict;

特定函數

typedef struct dictType {
    // 計算哈希值的函數
    uint64_t (*hashFunction)(const void *key);
    // 復制鍵的函數
    void *(*keyDup)(void *privdata, const void *key);
    // 復制值的函數
    void *(*valDup)(void *privdata, const void *obj);
    // 對比鍵的函數
    int (*keyCompare)(void *privdata, const void *key1, const void *key2);
    // 銷毀鍵的函數
    void (*keyDestructor)(void *privdata, void *key);
    // 銷毀值的函數
    void (*valDestructor)(void *privdata, void *obj);
} dictType;

字典中包含一個數據結構dictht的ht數組，一般情況下字典只是用ht[0]用來存儲數據，ht[1]在rehash時使用。

哈希算法原理

當向字典中添加一個元素時（假設此時 rehashidx = -1，也就是沒有進行rehash），首先通過dict->type->hashFunction計算該元素的hash值，然后通過hash & dict->ht[x].sizemask計算哈希地址index。如果該元素對應的下標沒有數據，則直接添加，否則采用鏈地址法添加到hash對應index元素的鏈表尾部。

rehash原理

隨著操作的不斷執行，哈希表中的元素會逐漸增加或者減少，為了讓哈希表的負載因子維持在一個合理的范圍內，程序需要對哈希表的大小進行相應的擴容和收縮。步驟如下：

為ht[1]哈希表分配空間。如果是擴容操作，ht[1]的大小為第一個大于等于ht[0].used*2的2的n次方冪，如果是收縮操作，ht[1]的大小為第一個大于等于ht[0].used的2的n次方冪
將保存在ht[0]中的所有鍵值對rehash到ht[1]：rehash指的是重新計算鍵的哈希值和索引值，然后將鍵值對放到ht[1]對應位置上
當ht[0]包含的所有鍵值對都遷移到ht[1]之后，釋放ht[0]，將ht[1]設置為ht[0]，并在ht[1]新創建一個空白哈希表，為下一次rehash做準備

漸進式rehash原理

在擴容和收縮的時候，如果哈希字典中有很多元素，一次性將這些鍵全部rehash到ht[1]的話，可能會導致服務器在一段時間內停止服務。所以，采用漸進式rehash的方式，詳細步驟如下：

為ht[1]分配空間，讓字典同時持有ht[0]和ht[1]兩個哈希表
將rehashindex的值設置為0，表示rehash工作正式開始
在rehash期間，每次對字典執行增刪改查操作是，程序除了執行指定的操作以外，還會順帶將ht[0]哈希表在rehashindex索引上的所有鍵值對rehash到ht[1]，當rehash工作完成以后，rehashindex的值+1
隨著字典操作的不斷執行，最終會在某一時間段上ht[0]的所有鍵值對都會被rehash到ht[1]，這時將rehashindex的值設置為-1，表示rehash操作結束

漸進式rehash采用的是一種分而治之的方式，將rehash的操作分攤在每一個的訪問中，避免集中式rehash而帶來的龐大計算量。

需要注意的是在漸進式rehash的過程，如果有增刪改查操作時，如果index大于rehashindex，訪問ht[0]，否則訪問ht[1]

4.Scan其他指令

scan 是一系列的指令，除了遍歷所有的 key 之外，也可以遍歷某一個類型的 key，對應的命令有：

zscan-->zset
hscan-->hash
sscan-->set

posted @ 2021-07-28 15:25 DOONDO 閱讀(1153) 評論(0) 收藏舉報

刷新頁面返回頂部

DOONDO