Percona 連載到 PostgreSQL 存 JSON object 以及增加 Index 的方式了...

先前 Percona 的人在講 MySQL 存 JSON object 的方式,現在開始講在 PostgreSQL 裡存 JSON object,並且增加 index 的方式了:「Storing and Using JSON Within PostgreSQL Part One」。

這基本上就是不想用 MongoDB,但還是有需要極為彈性而選擇用 JSON object 的需求。

首先先先建立一個表格,這邊直接用 JSONB:

alice=# CREATE TABLE table1 (id SERIAL PRIMARY KEY, jb JSONB);

接著拿「A dataset of English plaintext jokes」這邊的 reddit_jokes.json 來玩,我先把 JSON 裡面的內容變成 JSON Lines 格式:

cat reddit_jokes.json | jq -c '.[]' > reddit_jokes.jsonl

然後 COPY 了十次,多一點資料,後面可以看效能:

alice=# COPY table1 (jb) FROM '/tmp/reddit_jokes.jsonl' CSV QUOTE e'\x01' DELIMITER e'\x02';
-- (repeat this command 10 times)

接著跑個 SELECT 看看速度,我跑了幾次大約都在 260ms 上下:

alice=# SELECT COUNT(*) FROM table1 WHERE (jb->>'score')::int = 10;
 count 
-------
 25510
(1 row)

Time: 264.023 ms

然後針對 score 生個數字的 index:

alice=# CREATE INDEX ON table1 (((jb->>'score')::int));
CREATE INDEX
Time: 1218.503 ms (00:01.219)

接著再跑 SELECT 下去,可以看到速度快超多:

alice=# SELECT COUNT(*) FROM table1 WHERE (jb->>'score')::int = 10;
 count 
-------
 25510
(1 row)

Time: 12.735 ms

另外也可以加 column:

alice=# ALTER TABLE table1 ADD COLUMN score INT GENERATED ALWAYS AS ((jb->>'score')::int) STORED;

然後可以看到速度也不快:

alice=# SELECT COUNT(*) FROM table1 WHERE score = 10;
 count 
-------
 25510
(1 row)

Time: 222.163 ms

幫他補 index:

alice=# CREATE INDEX ON table1 (score);

速度有變快,但不知道為什麼沒有 JSONB 的版本快:

alice=# SELECT COUNT(*) FROM table1 WHERE score = 10;
 count 
-------
 25510
(1 row)

Time: 81.346 ms

算是還蠻好用的,不過得學 JSON query 語法... (應該是還好)

AWS 推出 CloudWatch Metric Streams

AWS 推出了 CloudWatch Metric Streams,把 CloudWatch Metric 的資料往 Kinesis Data Firehose 裡面丟:「CloudWatch Metric Streams – Send AWS Metrics to Partners and to Your Apps in Real Time」。

其中一個賣點是即時性比用 API 去拉好很多:

In order to make it easier for AWS Partners and others to gain access to CloudWatch metrics faster and at scale, we are launching CloudWatch Metric Streams. Instead of polling (which can result in 5 to 10 minutes of latency), metrics are delivered to a Kinesis Data Firehose stream.

格式上可以是 JSON 或是 Open Telemetry

When you set up a stream you choose between the binary Open Telemetry 0.7 format, and the human-readable JSON format.

另外一個賣點是價位,每千次 $0.003:

Pricing – You pay $0.003 for every 1000 metric updates, and for any charges associated with the Kinesis Data Firehose. To learn more, check out the pricing page.

另外算一下 Kinesis Data Firehose 的價錢,是以資料量的大小計費,不過最小計價單位是 5KB (一筆應該是不會到),單價是 $0.029/GB (us-east-1) 或是 $0.037/GB (ap-southeast-1),算了一下跟 CloudWatch Metrics Streams 比起來只是零頭...

之前如果要自己拉出來的話是透過 API call 抓,每 1000 次是 USD$0.01,這個方法相較起來便宜不少,不過數量多的時候還是一筆費用 (而且有不少 metrics 是一分鐘更新一次)。

如果只是要備份起來或是跑分析的話,也許先前用 API 拉的作法可能還是比較好?一個小時拉一次對於備份與分析應該都很夠了,而 alarm 的機制還是掛在 CloudWatch 上。

這次產品的定位看起來是要把 ecosystem 做起來:

We designed this feature with the goal of making it easier & more efficient for AWS Partners including Datadog, Dynatrace, New Relic, Splunk, and Sumo Logic to get access to metrics so that the partners can build even better tools.

檔案壓縮順序造成壓縮率的差異

Hacker News Daily 上看到「Why are tar.xz files 15x smaller when using Python's tar library compared to macOS tar?」這篇,作者問了為什麼他用 Pythontarfile 壓出來比起用 tar 壓出來小了 15 倍,檔案都是 JSON 檔壓成 XZ 格式:

I'm compressing ~1.3 GB folders each filled with 1440 JSON files and find that there's a 15-fold difference between using the tar command on macOS or Raspbian 10 (Buster) and using Python's built-in tarfile library.

看到 1440 個檔案應該會有直覺是一分鐘一個檔案,跑一天的量...

隔天他把原因找出來了,在裝了 GNU Tar 並且加上 --sort='name' 參數後,壓出來的大小就跟 Python 的 tarfile 差不多了:

Ok, I think I found the issue: BSD tar and GNU tar without any sort options put the files in the archive in an undefined order.

After installing GNU tar on my Mac with:

brew install gnu-tar

And then tarring the same folder, but with the --sort option:

gtar --sort='name' -cJf zsh-archive-sorted.tar.xz /Users/user/Desktop/temp/tar/2021-03-11

I get a .tar.xz archive of 1.5 MB, equal to the archive created by the Python library.

底層的原因是檔名與檔案內容有正相關的相似度 (因為裡面都是 sensor 資料),依照檔名排序壓縮就等於把類似的 JSON 檔案放在一起壓,使得 xz 可以利用這點急遽拉高壓縮率:

My JSON files contain measurements from hundreds of sensors. Every minute I read out all sensors, but only a few of these sensors have a different value from minute to minute.

By sorting the files by name (which has the creation unixtime at the beginning of it), two subsequent files have very little different characters between them. Apparently this is very favourable for the compression efficiency.

遇到類似的情境可以當作 tuning 的一種,測試看看會不會變小很多...

GTA 的啟動讀取效能問題

這件事情也已經過了一個禮拜,來整理一下發生什麼事情...

起因是 GTA Online 的遊戲開啟速度很慢,而有人一路 reverse engineering 找出問題並且解決:「How I cut GTA Online loading times by 70%」,對應的 Hacker News 討論有提到其他有趣的事情也可以看看:「How I cut GTA Online loading times by 70% (nee.lv)」。

作者的電腦不算太差,但光開啟 GTA Online 就需要六分鐘,網路上甚至有辦投票蒐集大家的等待時間,發現也有很多人反應類似的問題:

接下來就開始 reverse engineering 了,先觀察各種狀態後發現是卡在 CPU,而不是網路或 Disk I/O,然後就拿出 Luke Stackwalker 這個工具 profiling,不過因為沒有 debug symbol 幫忙 group,所以只能人工判斷後,可以看到兩個問題:

第一個問題發現效能是卡在 strlen(),而 call stack 可以看出來是從 sscanf() 一路打進去的:

反追發現是在處理 10MB 的 JSON 檔造成的,裡面 sscanf() 因為拉出 strlen(),於是就造成把整個 10MB 的 JSON 掃過很多次 (一開始是 10MB,掃到後面會愈來愈少,平均下來應該是 5MB):

第二個問題產生的時間會在第一個問題跑完後,另外看問題的性質,應該跟第一個 JSON 處理有關,他會把 JSON 處理過的資料丟進 array,每個 entry 長這樣:

struct {
    uint64_t *hash;
    item_t   *item;
} entry;

丟進 array 是 OK 的,但問題在於他需要判斷 entry 是否重複,卻沒有用 hash 或是 tree 的結構,而這邊大約有 63k 筆資料,用 array 實做就產生了 O(n^2) 的演算法:

But before it’s stored? It checks the entire array, one by one, comparing the hash of the item to see if it’s in the list or not. With ~63k entries that’s (n^2+n)/2 = (63000^2+63000)/2 = 1984531500 checks if my math is right. Most of them useless. You have unique hashes why not use a hash map.

作者在 PoC 的章節裡面描述他怎麼解這兩個問題。

第一個問題比較好的解法是修正 JSON Parser,但這太複雜,所以他用 workaround 解:把 strlen() 包起來,針對長字串加上一層 cache:

  • hook strlen
  • wait for a long string
  • “cache” the start and length of it
  • if it’s called again within the string’s range, return cached value

而第二個問題他直接把檢查是否有重複的跳過,因為資料本身不重複:

And as for the hash-array problem, it’s more straightforward - just skip the duplicate checks entirely and insert the items directly since we know the values are unique.

整個開啟的速度從六分鐘降到一分五十秒,還是偏慢,但算是大幅緩解的 GTA Online 啟動速度的問題了。

不過故事到這邊還沒結束,有人一路去挖,發現其實 sscanf() 的效能地雷已經不是第一次了:YAML 的 Parser 也中過一樣的問題:「Parsing can become accidentally quadratic because of sscanf」,這篇也一樣上了 Hacker News:「Parsing can become accidentally quadratic because of sscanf (github.com/biojppm)」。

然後這又帶出了六年前在 StackOverflow 上就有人問過這個問題:「Why is glibc's sscanf vastly slower than fscanf on Linux?」。

另外也有人整理出來,應該是大家把同樣的演算法拿來實做:

JdeBP 3 days ago

I found this while making a collection of what C implementation does what at https://news.ycombinator.com/item?id=26298300.

There are two basic implementation strategies. The BSD (FreeBSD and OpenBSD and more than likely NetBSD too), Microsoft, GNU, and MUSL C libraries use one, and suffer from this; whereas the OpenWatcom, P.J. Plauger, Tru64 Unix, and my standard C libraries use another, and do not.

The 2002 report in the comp.lang.c Usenet newsgroup (listed in that discussion) is the earliest that I've found so far.

後續的更新動作可以再追一下進度 (包括 GTA Online 與各家的 libc)。

在 HTTP Header 裡面傳結構性資料

忘了在哪邊看到的,好像是 Twitter 上看到的,mnotphk 兩個人弄了一個新的 RFC 標準,可以在 HTTP header 裡面傳結構性資料:「Structured Field Values for HTTP」。

第一個最直接的問題就在「A.1. Why Not JSON?」這個章節說明,考慮了既有的限制,包括 JSON spec,以及市場上既有的 JSON library 的實做。

但也因為自己定義了資料結構,Serializing & Parsing 就得另外再開發 library 處理,這樣會有多少 framework 支援就是個問題了,而且對於開發者來說,直接塞 JSON 很好理解,這個標準的前景不知道會怎麼樣...

RFC 定義的 application/problem+json (或是 xml)

剛剛在 Clubhouse 上聽到保哥提到了 RFC 7807 這個東西 (Problem Details for HTTP APIs),剛剛翻瀏覽器累積的 tab,發現原來先前有看到,而且有打算要出新版的消息:

RFC 7807 裡面這樣定義的方式可以讓 client 端直接判斷 Content-Type 知道這個回傳資料是不是錯誤訊息,不然以前都是 JSON 就得再另外包裝。用 Content-Type 的作法可以讓判斷條件變得清晰不少。

除了 application/problem+jsonapplication/problem+xml 以外,在「3.1. Members of a Problem Details Object」裡面則是說明 JSON (或是 XML) 裡面有哪些必要以及可選的資訊要填,然後「3.2. Extension Members」這邊則大概描述一下怎麼擴充。

先有個印象,之後新規劃的東西可以考慮進去...

網頁本身是個合法的 JSON 的展示

Hacker News Daily 上看到「Web Data Render」這個有趣的東西,這個網頁本身是個 JSON,透過一些技巧載入 javascript 後就可以讀取資料 render...

不過網頁本身就不是合法的 HTML 了:「Showing results for https://webdatarender.com/」,只能算是個有趣的作法...

用 GitHub Actions 記錄 API 資料的變化

Hacker News Daily 上看到的方式,Simon Willison 利用了 GitHub Actions 定時去抓資料更新 git repository:「Git scraping: track changes over time by scraping to a Git repository」。

文章裡面測試了 JSON 檔案的變化:

這個方式利用了 GitHub 自家的架構做完所有的事情,因為他的範例是拉加州政府的資料,感覺 g0v 裡應該有些專案也用這個方式搞,翻了一下 Telegram 上的記錄,果然翻到記錄了:「零營運費用開源開發」。

另外我猜用 free-for.dev 這邊的資源應該也有機會堆出類似的東西...

PHP 8 的提案,將 JSON library 放入必須項目

Twitter 上看到的通知,這個提案將 PHPJSON 列為語言的必須項目,目前的狀態是 Under Discussion:「PHP RFC: Always available JSON extension」。

以前沒有引入的一個原因是因為底層使用的 library 的授權 JSON license 不是 open-source license,這對於要打包出 binary 散佈時的問題很大 (跟其他 license 衝突):

The Software shall be used for Good, not Evil.

在 PHP 7 之後,JSON 的實做決定改用 jsond (參考「PHP RFC: Replacing current json extension with jsond」),這邊用的是 PHP License 授權:「LICENSE」,這個因素就緩解了。

而這個提案提議拔掉 ./configure –-disable-json 關閉 JSON library 的能力,把 JSON library 變成 PHP language 的一部份:

Make it impossible to disable the JSON extension through configuration or build options. Require that JSON be built statically instead of as a shared library.

這個提案如果通過的話,對大多數人應該還是沒什麼影響,因為一般在用的版本都會裝 JSON library。而且現在會透過 Composor 管理套件,很容易就會有 dependency 會用到 JSON 而需要安裝 JSON library,問題不太大...

JSON Canonicalization

這篇是講 JSON object 上的簽名,但實際上就是在討論 JSON Canonicalization 的前因後果:「How (not) to sign a JSON object」。

在處理 JSON 資料時,「判斷兩個 JSON object 是否相同」是一個不怎麼簡單的問題,其中一個想法是找一個機制可以把意義相同的 JSON object 都轉成相同的 (byte)string representative,這也就是 JSON Canonicalization。當你可以確保意義相同的 JSON Canonicalization 後,你就可以對 string 本身簽名。

這件事情其實在 XML 就有過同樣的歷史故事 (yeah,總是有人愛在某種資料格式上面疊上簽名),也就是「XML Signature」這個方式。

在 XML 這邊不幸的是,還不少標準選用 XML Signature,像是當年為了實做 Google Apps (現在叫做 G Suite) 的 SSO,而需要接 SAML...

回到原來的 JSON Canonicalization,可以馬上想到的變化包括了空白與 object 裡 key 的順序,也就是這兩個:

{"a":1,"b":2}
{
  "b": 2,
  "a": 1
}

但不幸的是,還有 Unicode 來一起亂,也就是下面這個跟上面有相同的意思:

{
  "\u0062": 2,
  "\u0061": 1
}

另外還有其他的地雷是平常不會想到的,如果你因為複雜而決定用 library 來做,那也代表 library 必須面對這些複雜的情境,未必沒有 bug...

所以文章作者在最後面才會請大家不要再來亂了 XDDD

Maybe you don’t need request signing? A bearer token header is fine, or HMAC(k, timestamp) if you’re feeling fancy, or mTLS if you really care.

Canonicalization is fiendishly difficult.

Add a signature on the outside of the request body, make sure the request body is complete, and don’t worry about “signing what is said versus what is meant” – it’s OK to sign the exact byte sequence.