これ必ずO(1)になると思っていた。なので大量削除だろうがコマンドごとにすぐに終わるので問題ないだろうと思っていたがSETなどを消す場合はO(M)になるらしい。M=100万とかの要素があった時に完全にブロッキングになるので本番で打つときはちょっと注意が必要そう。
時間計算量: Nが削除されるキーの数の時 O(N)。削除するキーが文字列以外の値を保持している場合、Mがリスト、セット、ソート済みセットあるいはハッシュの要素数の時にこのキーの個々の時間計算量は O(M) です。文字列の値を保持している1つのキーの削除は O(1) です。
ブロックするの怖いなぁと思ってみていたらUNLINKコマンドはRedisのバックグラウンドスレッドで削除を実行するらしいので大量削除とか大量に要素がある場合はこちらを使うと良さそう。