redis PUBLISHコマンドの計算量について


# 調べることになった経緯

プロダクションで稼働しているredisサーバーのCPU使用率が高い状態が続いていました。
キャッシュサーバーとして使用しているというよりは、Publish / Subscribe関連の使用頻度がとても多いため、それらのコマンドの負荷を調べることにしました。



# Publish / Subscribe 関連のコマンドについて

以下のコマンドを主に使用します。
詳しい使用方法は他の記事を参照してください。

* PUBLISH
* SUBSCRIBE
* UNSUBSCRIBE
* PSUBSCRIBE
* PUNSUBSCRIBE


## PUBLISHコマンド
メッセージを配信したいクライアントは、PUBLISHコマンドを使用します。

PUBLISHコマンドには、チャネル名とメッセージ内容、2つの文字列を指定します。



## SUBSCRIBEコマンド, PSUBSCRIBEコマンド
メッセージを購読したいクライアントは、SUBSCRIBEコマンド、または、PSUBSCRIBEコマンドを使用します。

SUBSCRIBEコマンドでは、チャネル名を指定します。PUBLISHコマンドで指定されるチャネル名と一致している必要があります。

PSUBSCRIBEコマンドでは、SUBSCRIBEコマンドと同様にチャネル名を指定するのですが、globスタイルでの記述ができます。ワイルドカードを記述することができるため、複数のチャネル名が該当します。

※ドキュメントでは、SUBSCRIBEの引数は```channel```、PSUBSCRIBEの引数は```pattern```と書かれており、明確に言葉が区別されています。


## UNSUBSCRIBEコマンド, PUNSUBSCRIBEコマンド

購読をやめる場合は、UNSUBSCRIBEコマンド、または、PUNSUBSCRIBEコマンドを使用します。

SUBSCRIBEコマンドで購読した場合には、UNSUBSCRIBEコマンドを使用します。

PUNSUBSCRIBEコマンドで購読した場合には、PUNSUBSCRIBEコマンドを使用します。


# PUBLISHコマンドの計算量

redisのドキュメントから引用します。
https://redis.io/commands/publish

> Available since 2.0.0.
> 
> Time complexity: O(N+M) where N is the number of clients subscribed to the receiving channel and M is the total number of subscribed patterns (by any client).

計算量がオーダー記法により示されています。N、Mはそれぞれ以下となります。

> * N: 受信するチャネルへ購読しているクライアントの数。
> * M: 任意のクライアントにより、登録されているパターンの総数。

Mより、どのようなパターンであっても計算量に含まれているとすれば、購読するパターンを増やすほど計算量も増えることになります。

例えば、複数のクライアントが同じパターンを購読しているとします。
購読するパターンを新しく1つ増やすことになった場合、計算量が少なくともクライアント数だけ増えることになるのでしょう。



# 疑問点について

以下の疑問をさらに調べることにしました。

1. 「パターンの総数」とあるが、同じパターンを複数購読した場合はどうなるか? 、同じパターンであればパターンに該当するかどうかを評価するのは1度で済むので、計算量は増えないのでは?
1. ワイルドカードが含まれていなければ、チャネル名との一致になるのでは? (SUBSCRIBEと同じように扱われる?)


以下のページで内部動作が解説されています。
___redis 3.2.6___の時の記事です。
https://making.pusher.com/redis-pubsub-under-the-hood/

Pattern subscriptions より引用 (※実装に興味がある場合はこれより以前も読むといいと思います)

> This system may surprise you: 
> multiple clients subscribed to the same pattern do not get grouped together!
> If 10,000 clients subscribe to food.*, you will get a linked list of 10,000 patterns, each of which is tested on every publish!
> This design assumes that the set of pattern subscriptions will be small and distinct.

> Another cause for surprise is that patterns are stored in their surface syntax. 
> They are not compiled (e.g. to DFAs). 
> This is especially interesting since Redis’s matching function stringmatch has some … interesting worst-cases. 
> Here is how Redis tests the pattern *a*a*b against the string aa:
> 
```
stringmatch("*a*a*b", "aa")
    stringmatch("a*a*b", "aa")
        stringmatch("*a*b", "a")
            stringmatch("a*b", "a")
                stringmatch("*b", "")
                    stringmatch("b", "")
                        false
            stringmatch("a*b", "")
                false
    stringmatch("a*a*b", "a")
        stringmatch("*a*b", "")
            stringmatch("a*b", "")
                false
    stringmatch("a*a*b", "")
      false
```
> This malicious pattern with many “globs” causes an exponential blowup in the running time of the match! 
> Redis’s pattern language could be compiled to a DFA, which would run in linear time. But it is not.

> In short, you should not expose Redis’s pattern subscriptions to untrusted clients, because there are at least > two attack vectors: multiple pattern subscribes, and crafted patterns. 
> At Pusher, we tread very carefully with Redis pattern subscriptions.



以下、訳です。

> このシステムはあなたを驚かせるかもしれません。
> 同じパターンを購読した複数のクライアントは、同一のグループにされていません。
> もし、10000クライアントが"food*"を購読すると、10000パターンのリンクドリストになります。それぞれはPUBLISHの度にテストされます。
> このデザインは、パターンの購読のセットが小さく別個であることを前提にしています。
> 
> あなたを驚かせる別の点は、パターンはそれらの表面的な構文で保持されている、点です。
> それらは、コンパイルされていません(例えば、DFAsへ)。
> Redisのマッチング関数stringmatchはいくつか最悪の場合があるので、これは特に興味深いです。
> 以下は、Redisが文字"aa"に対してパターン"*a*a*b"をテストする方法です。

> (略) 再帰的にstringmatchを呼び出しているらしい

> 多くの"globs"を含むこの最悪のパターンは、マッチの実行時間を急激に増加させます。
> Redisのパターン言語は線形時間で実行されるDFAへコンパイルできます。しかし、そうではありません。
> 端的に、Redisのパターン購読を信用のないクライアントへ公開すべきではありません。
> なぜなら、少なくとも2つの攻撃経路があるです。(複数のパターン購読、細工されたパターン)
> 私たちはRedisのパターン購読をとても慎重に行います。


まとめ

1. クライアントがパターンを購読した場合、以前に同じパターンの文字列があっても、別のパターンとして追加されている。
1. パターンは、コマンドで渡されたそのままの文字列で保持されている。