幹壞事是進步最大的原動力
從「Redis 改變授權，變成非開源軟體」差不多過去一個禮拜了，瞬間冒出一卡車 Redis fork：「The race to replace Redis」。
文章裡提到的第一個是 Valkey，在 Redis 宣佈改變授權後幾天 fork 出來的。
第二個則是 KeyDB，是很久前就 fork 出來實作 multi-threading 的公司，後來公司被 Snap 買走後 open source，但因為 fork 的很早，後續 Redis 增加的功能就沒有跟上了...
第三個則是 Redict，這是 SourceHut 這邊的 fork 版本。
第四個不算是 fork，是微軟前幾天公開的 Garnet，用 C# 寫的，也因為不是 fork，相容性當然比不上前面幾個。
另外一個文章帶出來的重要資訊，是目前 Redis 的 contributor 分佈，可以看到其實 Redis 本家不算多，這樣 Redis 決定硬幹 BSL + SSPL 的決定就頗值得玩味了：
可以看看 Redis 接下來會不會有什麼重量級的功能要推出？
Redis 宣佈拿掉開源授權：「Redis Adopts Dual Source-Available Licensing」，對應的 git commit 在「Change license from BSD-3 to dual RSALv2+SSPLv1 (#13157)」這邊可以看到。
Starting with Redis 7.4, Redis will be dual-licensed under the Redis Source Available License (RSALv2) and Server Side Public License (SSPLv1).
算是今天蠻熱的新聞之一，不過算是在預期之內的變化，因為 Redis 在 2018 年就把很多他們自己開發的 proprietary component 變成 SSPL，現在主體也變其實不算太意外，後續就是看社群的 fork 凝聚的力量會比較大，還是 Redis 公司方的力量比較大... 尤其在 Redis 已經實作了許多 data structure 後，Redis 公司想要套現這件事情是否還有機會？
不過比較特別的反倒是微軟... 微軟早了一兩天發佈了 Redis 相容的實作 Garnet：
Garnet is a remote cache-store from Microsoft Research that offers strong performance (throughput and latency), scalability, storage, recovery, cluster sharding, key migration, and replication features. Garnet can work with existing Redis clients.
會是巧合嗎？這時間點其實真的很微妙...
HyperLogLog (HLL) 是用統計方式解決 Count-distinct problem 的資料結構以及演算法，不要求完全正確，而是大概的數量。
演算法其實沒有很難懂，在 2007 年的原始論文「HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm」裡面可以讀到演算法是長這樣：
可以看到一開始要決定好 b 的值 (於是就會有 2b 個 register)，以及單個 register M[j] 的大小，所以是一開始就會決定好固定大小，無論有多少元素都會先吃掉這麼多空間。
但在 Redis 的文件「HyperLogLog」裡面則是提到很少元素的時候會低於 12KB：
The magic of this algorithm is that you no longer need to use an amount of memory proportional to the number of items counted, and instead can use a constant amount of memory; 12k bytes in the worst case, or a lot less if your HyperLogLog (We'll just call them HLL from now) has seen very few elements.
網路上搜了一下沒看到怎麼做到的，不過直接翻 Redis 的程式碼 hyperloglog.c 可以看到答案。
在檔案開頭的註解可以看到有 16384 個 register (對應到論文裡面的 b = 14，因為 214 = 16384)，單個 register 的大小則是 6 bit (對應到論文裡面的 M[j])，相乘後是 12K bytes，剛好符合文件上的說明：
The use of 16384 6-bit registers for a great level of accuracy, using a total of 12k per key.
在「Dense representation」這邊也說明了每個 register 都是 6 bit 的存放方式，到這邊都與 HLL 論文提到的實作一樣。
省空間的方式是在「Sparse representation」這邊做到的，在大多數的 register 都沒有被設定的情況下，用這種方式可以省下大量的空間，而缺點是當元素「有點多」的時候會有比較高的 CPU time：
In the example the sparse representation used just 7 bytes instead of 12k in order to represent the HLL registers. In general for low cardinality there is a big win in terms of space efficiency, traded with CPU time since the sparse representation is slower to access.
依照註解上面的數字，看起來在 10000 個元素以下有機會低於 12KB，然後夠大的時候從 sparse 轉到 dense 上。
本來以為是什麼其他論文可以調整 b 參數 (enlarge)，結果是個比較像是 hack 的方式搞定，但的確是蠻有效的...
在 Hacker News 上看到有支援 Multithreading 的 Redis fork：「KeyDB – A Multithreaded Fork of Redis (keydb.dev)」，官網在「KeyDB - The Faster Redis Alternative」這邊。
不過這篇是要記錄從 Hacker News 看到的雷點，這樣以後自己再找資料的時候會比較容找到。
36022425 這篇是跳下去用發現不太行，最後在 application 端實作需要的 feature，後端還是用原廠的 Redis：
To counter what the other active business said, we tried using KeyDB for about 6 months and every fear you concern you stated came true. Numerous outages, obscure bugs, etc. Its not that the devs aren’t good, its just a complex problem and they went wide with a variety of enhancements. We changed client architecture to work better with tradition Redis. Combined with with recent Redis updates, its rock solid and back to being an after-thought rather than a pain point. Its only worth the high price if it solves problems without creating worse ones. I wish those guys luck but I wont try it again anytime soon.
* its been around 2 years since our last use as a paying customer. YMMV.
另外是在專案裡搜尋「is:open is:issue label:"Priority 1"」的結果可以看到不太妙，在 36021108 這邊有提到的問題：
Filed July, eventually marked priority 1 in early December, not a single comment or signs of fix on it since. That doesn't look good at all.
然後 36020184 有提到 Snap 買進去後沒有什麼在管 open source project 的部分了：
I think I'll stay far away from this thing anyway. Numerous show-stopper bug reports open and there hasn't been a substantial commit on the main branch in at least a few weeks, and possibly months. I'll be surprised if Snap is actually paying anybody to work on this.
前幾天在噗浪的偷偷說上看到有人提到 npmtrends 上的 redis (官方的) 與 ioredis：「https://www.plurk.com/p/p6wdc9」。
意外發現以下載量來看，ioredis 已經超越官方的 redis 了：
找了一下差異，看起來的確有些團隊在 loading 很高的情況下會考慮用 ioredis 取代 redis：「Migrating from Node Redis to Ioredis: a slightly bumpy but faster road」。
但沒有特別需求的話應該還是會用官方版本？
在 Hacker News 上看到「Redis vs. KeyDB vs. Dragonfly vs. Skytable」這篇，裡面介紹了四套 key-value store 軟體：
裡面看起來都蠻有趣的，可以追起來看看發展的情況，但如果真的要的用的話，應該還是先以 Redis 為主，穩定度以及功能還是重點...
看到 Linode 宣佈 Managed Databases 服務：「Linode Managed Databases in Open Beta」。
測試期間不用錢，但目前只有支援 MySQL，其他幾個像是 PostgreSQL、Redis 與 MongoDB 都還沒推出 (在 roadmap 上)：
Our new managed database service is now in open beta for new and existing customers! We currently support MySQL during this beta—with a near-term roadmap to add PostgreSQL, Redis, MongoDB—and plan to include additional features.
搜了一下隔壁 DigitalOcean 的資料，Manage Databases 這條產品線在 2019 年二月推出 PostgreSQL 的版本：「Our Valentine’s Gift to You: Managed Databases for PostgreSQL」，在 2019 年八月推出了 MySQL 與 Redis 的版本：「Take the worry out of managing your MySQL & Redis databases」，然後在 2021 年六月推出了 MongoDB 的版本：「Introducing DigitalOcean Managed MongoDB – a fully managed, database as a service for modern apps」。
不過 Vultr 看起來是還是完全沒有樣子，相比起來 Linode 好像不算慢？
另外看起來 DigitalOcean 是跟 MongoDB 合作，不像 AWS 自己另外用 PostgreSQL 搞了一套 XDDD
在 Lobsters Daily 上看到這篇 2017 年的文章，Figma 的工程師講怎麼做 rate limit：「An alternative approach to rate limiting」，只要大一點的站台就會遇到 spammer 之類的攻擊，就會希望實做自動化的機制擋住 spammer。
文章裡面提到了三種方式，第一種 (類) 提到了經典的 Token bucket 與 Leaky bucket，這邊文章提供的演算法是讓每個使用者都會有一筆資料紀錄在 Redis 裡面 (這邊的用法可以抽換換成 Memcached)，裡面記錄了最後一次的 access time 以及還剩下多少 token 可以用，接下來就可以照時間計算 token 的補充與消耗：
但這個演算法的缺點是 race condition，需要另外設計一些機制確保操作的 atomic：
不過大多數的實做就算不管 atomic 也還行 OK，只是會比較不精確一點。
第二個方法他叫做 Fixed window counters，這個方法把時間切齊為單位 (像是 60 秒為一個 window)，所以可以把起點的時間也放到 key 裡面，然後 value 就是數量：
這個作法的好處就是簡單，而且 Redis 與 Memcached 都有提供 atomic 的 +1 操作。但缺點是可能會發生兩倍以上的 request，像是 5 reqs/min 的限制有可能會有連續的一分鐘內達到 10 reqs/min：
不過我覺得就 antispam 來說算是夠用了，當年 (大概是 2007 或是 2008 年？) 在 PIXNET 時用 C 寫 Apache module 就是把資料丟到 Memcached 裡面就是這樣實做的，然後每次學術網路的實驗室跑來掃站的就會自動被擋 XDDD
第三種方式他們稱作 Sliding window log，就是把每個 request 的 timestamp 都存起來，這個部份用 Redis 的資料結構會比用 Memcached 方便一些：
這個方式在控制上更精確，不過空間成本上就高很多... 這樣算是把常見的實做方式都提到了。
在「Memcached vs Redis - More Different Than You Would Expect」這邊看到對 Memcached 與 Redis 的分析。
這兩套軟體都很常被拿來用作 cache 機制，所以一般來說比較時就是比兩邊都有的東西 (如果你要 pub-sub 之類的東西，在這兩套裡面只有 Redis 有)。
最前面還是先講了對使用者 (開發者) 的差異，很明顯的是 Redis 對各種不同的資聊結構都有支援，這點可以從 Redis 被官方被稱作 Data Structures Server 就可以知道 (在「An introduction to Redis data types and abstractions」這篇可以看到)，而 Memcached 只支援了 key-value 架構。
不過如果是以 cache 來說，的確 key-value 架構就還蠻好用的。
後面就開始比較硬的主題了，提到了 Memcached 與 Redis 內部是怎麼使用記憶體的。
Memcached 的部份先提了 page/slab/chunk 的架構以及產生的效能限制與浪費，接著有提到 2020 年 refactor 的部份 (太久沒有看 Memcached 的消息，去年沒跟到這個部份)，讓多 CPU 的支援度更好。
Redis 則是靠 jemalloc 來處理這個部份，另外加上 background thread 的機制降低 fragment。
然後是比較 cache expiration 的部份，可以看到兩者用的演算法在現實世界中都夠用 (尤其是當作 cache 來用)，這部份跟印象中的架構差不多，應該是沒有太大變化。
最後是比較 cluster 的部份，Memcached 是 share nothing，所以沒什麼好說的，主要是靠 client library 實做 consistent hash 之類的架構打散；而 Redis 的話看起來有實做新的機制出來 (也沒跟到)，之後有機會再看看可以做到什麼程度。
不過好像沒提到 proxy 之類的架構，基本上各大公司都有自己幹：
少了這塊對於 cluster 架構的完整性差蠻多的。
文章最後沒有下定論一定要用哪個比較好，兩者都有強項與弱項，還是得看情況來處理。不過我自己還是很喜歡用 Memcached 就是了...
Hacker News Daily 上看到一篇講 PostgreSQL 做 Job Queue、Application Lock 以及 Pub/Sub 的方法：「Do You Really Need Redis? How to Get Away with Just PostgreSQL」，對應的討論在「Do you really need Redis? How to get away with just PostgreSQL (atomicobject.com)」這邊可以翻到。
拿 PostgreSQL 跑這些東西的確有點浪費，不過如果是自己的專案，不想要把 infrastructure 搞的太複雜的話，倒是還不錯。
首先是 Job Queue 的部份，從他的範例看起來他是在做 async job queue (不用等回傳值的)，這讓我想到很久前寫的 queue service (應該是 2007 年與 2012 年都寫過一次)，不過我是用 MySQL 當作後端，要想辦法降低 InnoDB 的 lock 特性。
async job queue 設計起來其實很多奇怪的眉角，主要就是在怎麼處理失敗的狀態。大多數的需求可以放到兩個種類，最常見用的是 at-least-once，保證最少跑一次，大多數從設計上有設計成 idempotence 的都可以往這類丟，像是報表類的 (重複再跑一次昨天的報表是 OK 的)，另外每天更新會員狀態也可以放在這邊。
另外少見一點的是 at-most-once 與 exactly-once，最多只跑一次與只跑一次，通常用在不是 idempotence 的操作上，像是扣款之類的，這邊的機制通常都會跟商業邏輯有關，反正不太好處理...
第二個是 Application Lock，跨機器時的 lock 機制，量沒有很大時拿 PostgreSQL 跑還行，再大就要另外想辦法了，馬上想到的是 ZooKeeper，但近年設計的系統應該更偏向用 etcd 與 Consul 了...
最後提到的 Pub/Sub，一樣是在量大的時候拿 PostgreSQL 跑還行，更大的時候就要拿 Kafka 這種專門為了效能而設計出來的軟體出來用...