從有序集合隨機取一個值，應該用什麼方案？

• 2020 年 3 月 3 日
• 筆記

今天做了一個小實驗，起因如下：

先在redis里構造了測試數據，如下：

> zadd my_zset_999 1 35570  (integer) 1  > zadd my_zset_999 2 40617  (integer) 1  > zadd my_zset_999 3 40956  (integer) 1  > zadd my_zset_999 4 41151  (integer) 1  >  > zrange my_zset_999 0 -1 WITHSCORES  1) "35570"  2) "1"  3) "40617"  4) "2"  5) "40956"  6) "3"  7) "41151"  8) "4"  >  > zrange my_zset_999 0 -1  1) "35570"  2) "40617"  3) "40956"  4) "41151"

測試方法就是很簡單的計算程式運行時間。

$t1 = microtime(true);  // 程式碼片段  $t2 = microtime(true);  $t = $t2 - $t1;

方法1
zrange key 0 -1 取出所有的值
array_rand() 從數組中隨機取出一個值

方法2
zcount key -inf +inf 計算該集合有多少個元素（cnt）
rand(1, cnt) 生成一個隨機數（random）
zrangebyscore key random random

方法3：對方法2的改造
zcard key 計算該集合有多少個元素（cnt）
rand(1, cnt) 生成一個隨機數（random）
zrangebyscore key random random

方法4：對方法1的改造
zrangebyscore key -inf +inf
array_rand() 從數組中隨機取出一個值

方法 1 和方法 4 都是先取出有序集合的所有值，再隨機取出一個值；
方法 2 和方法 3 則是隨機從有序集合中取出一個值。

下面是各方法的運行時間對比。

方法 2 和方法 3，即 zcount 和 zcard 的運行時間對比：

可以看出 zcount 比 zcard 的波動大，且用時長，所以淘汰方法2，這是因為 zcard 的時間複雜度是 O(1)，而 zcount 的時間複雜度是 O(log(N))。

方法 1 和方法 3，即 zrange 和 zrangebyscore 的運行時間對比：

可以看出方法 2 比方法 1 要快一些。那如果把方法 1 改成用 zrangebyscore 取出所有值，再隨機取元素呢，也就是方法 4，再比較方法 4 和方法 3 的運行時間：

可以看到方法 4 比方法 3 快一些，再用 ab 測試工具測一下

# 模擬100個並發用戶，對一個資源發送100個請求。  ab -c 100 -n 100 url

方法 4 的測試結果如下：

Server Software:        nginx/1.15.11  Server Hostname:        127.0.0.1  Server Port:            80    Document Path:          test1.php  Document Length:        38 bytes    Concurrency Level:      100  Time taken for tests:   0.520 seconds  Complete requests:      100  Failed requests:        0  Non-2xx responses:      100  Total transferred:      23400 bytes  HTML transferred:       3800 bytes  Requests per second:    192.25 [#/sec] (mean)  Time per request:       520.161 [ms] (mean)  Time per request:       5.202 [ms] (mean, across all concurrent requests)  Transfer rate:          43.93 [Kbytes/sec] received    Connection Times (ms)                min  mean[+/-sd] median   max  Connect:       18   25   5.6     26      35  Processing:    41  219  87.1    219     359  Waiting:       41  219  87.4    219     359  Total:         60  245  92.3    246     393    Percentage of the requests served within a certain time (ms)    50%    246    66%    296    75%    326    80%    340    90%    372    95%    392    98%    392    99%    393   100%    393 (longest request)

方法 3 的測試結果如下：

Server Software:        nginx/1.15.11  Server Hostname:        127.0.0.1  Server Port:            80    Document Path:          /test2.php  Document Length:        38 bytes    Concurrency Level:      100  Time taken for tests:   0.526 seconds  Complete requests:      100  Failed requests:        0  Non-2xx responses:      100  Total transferred:      23400 bytes  HTML transferred:       3800 bytes  Requests per second:    189.97 [#/sec] (mean)  Time per request:       526.390 [ms] (mean)  Time per request:       5.264 [ms] (mean, across all concurrent requests)  Transfer rate:          43.41 [Kbytes/sec] received    Connection Times (ms)                min  mean[+/-sd] median   max  Connect:       16   23   3.8     25      31  Processing:    36  216  89.5    220     372  Waiting:       36  216  89.2    220     372  Total:         54  239  92.9    245     403    Percentage of the requests served within a certain time (ms)    50%    245    66%    295    75%    316    80%    333    90%    362    95%    374    98%    402    99%    403   100%    403 (longest request)

通過 Time taken for tests、Requests per second 等結果，可以看出方法 4 比方法 3 的性能更高一些。

也就是先取出所有元素，再隨機取出一個值 和 構造一個隨機數取出一個元素 這兩種方案，前者更好一些。

到這裡就結束了嗎？並沒有~

最終結果就是不採用有序集合這種數據結構了，用列表或集合這種數據結構即可。因為有序集合 zset 還要構造 score 值，比如插入元素，要查出最大的score值，再加 1。
既然需求只是從一堆元素中隨機取一個值，用列表或集合這種數據結構就能滿足所需了。