RedisのKEYSはO(n)な点に注意が必要、と各種文献に書かれている。なので実際にデータ作ってみて試してみる。

ソースコード

 <parent>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-parent</artifactId>
        <version>2.1.7.RELEASE</version>
        <relativePath />
    </parent>

    <properties>
        <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>
        <project.reporting.outputEncoding>UTF-8</project.reporting.outputEncoding>
        <java.version>11</java.version>
    </properties>

    <dependencies>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-data-redis</artifactId>
        </dependency>
    </dependencies>

Redisのエントリは以下のようにしてkey 0 - nをsetする。

        var list = redis.executePipelined(new RedisCallback<Object>() {
            @Override
            public Object doInRedis(RedisConnection connection) throws DataAccessException {
                StringRedisConnection stringRedisConn = (StringRedisConnection) connection;

                for (int i = 0; i < MAX; i++) {
                    stringRedisConn.set("" + i, "hogeValue");
                }

                return null;
            }
        });

あらかじめRedisにエントリを作った上で、以下のkeysメソッドの引数を色々変えて、その実行時間を計測する。

@Autowired
StringRedisTemplate redis;

long start = System.currentTimeMillis();
Set<String> keys = redis.keys("...");
System.out.println(System.currentTimeMillis() - start);

Redisエントリ2, 4, 6, 8 ,10百万件に対し、keys nのnを0, 100, 10000, *でその件数返るコマンドを実行する。ただし、keys 100*とかでピッタリ1000件とか返るわけではないが、今回そこは重要ではないので無視する。

結果

計測結果

以下はRedis件数とkeys nの取得件数に対する速度結果表。それぞれ3回実行してその平均値を記載。

	10,000,000	8,000,000	6,000,000	4,000,000	2,000,000
0	1915	1585	1400	1271	903
100	1963	1557	1426	1076	868
10000	1962	1600	1395	1094	898
*	14502	11901	8775	5642	3033

f:id:kagamihoge:20190826204117p:plain

※ https://keisan.casio.jp/exec/system/1403589783 で作成。

確かにおおむねO(n)になる。また、最終的な結果件数で実行時間はほぼ変化しない。

ただし、keys *で全件返すとクライアント側のオーバーヘッドが激増するため、実行時間が増す。おそらく、オーバーヘッドが全体の実行時間に影響を与え始めるn値があると思われるが調べていない。

1-2秒は確かに高速ではあるが、Redisはシングルスレッドなのでその間他の処理が出来なくなる。環境にも依るが、Redisで数秒止まるのは許容出来ない場合が多いと思われる。

KEYS(pattern)

この操作は計算時間O(n)となっているが、定数時間は非常に小さいものとなっています。（略）もちろんこのコマンドは注意深く使わないとデータベース性能を落としてしまうということを意識するにこしたことはありません。

言い換えると、このコマンドはデバッグやデータベースのスキーマの変更を行うなどの特別な操作を除いて使うべきではありません。通常のコードでは使わないでください。

http://redis.shibu.jp/commandreference/alldata.html#command-KEYS より抜粋

kagamihogeの日記

kagamihogeの日記です。

RedisのkeysがO(N)を実際に見る

ソースコード

結果

計測結果