zlib、gzip 與 zip 的關係 (Mark Adler 的回覆)

Hacker News 上看到「How are zlib, gzip and zip related? (stackoverflow.com)」這個討論,原文是 StackOverflow 上 2013 年時的問題與回答:「How are zlib, gzip and zip related? What do they have in common and how are they different?」。

short form 算是解釋了這三個的關係,另外多帶出了其他相關的格式以及演算法:

.zip is an archive format using, usually, the Deflate compression method. The .gz gzip format is for single files, also using the Deflate compression method. Often gzip is used in combination with tar to make a compressed archive format, .tar.gz. The zlib library provides Deflate compression and decompression code for use by zip, gzip, png (which uses the zlib wrapper on deflate data), and many other applications.

而 long form 則是描述了整段歷史,完整到下面的 comment 有人提到希望能夠提供一些引用的連結,當作 reference:

This post is packed with so much history and information that I feel like some citations need be added incase people try to reference this post as an information source. Though if this information is reflected somewhere with citations like Wikipedia, a link to such similar cited work would be appreciated.

回答的作者 Mark Adler 也在 comment 上很霸氣的回:

I am the reference, having been part of all of that. This post could be cited in Wikipedia as an original source.

翻了一下他的事蹟:

老人家交代了當年的一些脈絡 (像是專利問題),會更容易理解為什麼現在發展成這樣...

在 MacPorts 上裝 pyenv...

因為先前從 Homebrew 跳到 MacPorts 了,剛好有機會重新弄 pyenv,結果發現要解決的問題不少...

第一個遇到的是需要的 library 抓不到的問題,找了官方說明「Common build problems」後知道要自己加上一些環境變數讓 compiler 抓。

解決之後發現 pyenv 會自己編一個 openssl 版本給 Python 用,不會裝到系統內,但是又會因為 /usr/local/opt/ 寫不進去而失敗,所以給他一個可以寫入的目錄。

接下來是 zlib 的路徑也不在前面設定的目錄裡而抓不到,所以得想辦法再找出來塞到環境變數內... 也就是「Install failed, "zlib not available" on macOS Mojave #1219」這篇給的方法。

最後是這樣:

sudo mkdir /usr/local/opt; sudo chown "$(id -u):$(id -g)" /usr/local/opt
LDFLAGS="-L/usr/local/opt/openssl/lib" CPPFLAGS="-I/usr/local/opt/openssl/include" CFLAGS="-I/usr/local/opt/openssl/include -I$(xcrun --show-sdk-path)/usr/include" pyenv install 3.7.3

裝完後可以發現 /usr/local/opt/ 裡面沒有檔案 (但生了幾個空的目錄出來),但總算是裝起來了...

Node.js 安全性更新:zlib...

前幾天「Node.js 預定在十月 24 號發表安全性更新」提到 Node.js 會發表安全性更新,已經看到 4/6/8 都出新版了:「Node v4.8.5 (Maintenance)」、「Node v6.11.5 (LTS)」、「Node v8.8.0 (Current)」。

這次安全更新的 CVECVE-2017-14919

CVE-2017-14919 - In zlib v1.2.9, a change was made that causes an error to be raised when a raw deflate stream is initialized with windowBits set to 8. On some versions this crashes Node and you cannot recover from it, while on some versions it throws an exception. Node.js will now gracefully set windowBits to 9 replicating the legacy behavior to avoid a DOS vector. nodejs-private/node-private#95

zlib 的 manualwindowBits 說明:

For the current implementation of deflate(), a windowBits value of 8 (a window size of 256 bytes) is not supported. As a result, a request for 8 will result in 9 (a 512-byte window). In that case, providing 8 to inflateInit2() will result in an error when the zlib header with 9 is checked against the initialization of inflate(). The remedy is to not use 8 with deflateInit2() with this initialization, or at least in that case use 9 with inflateInit2().

唔?XD

另外文章可以看出來 Node.js 團隊是選擇在 GitHub 上用另外一個 organization 在管這類不會事前公開的事情...

Amazon Redshift 支援 Zstandard

Amazon Redshift 支援 Zstandard 壓縮資料:「Amazon Redshift now supports the Zstandard high data compression encoding and two new aggregate functions」。

Zstandard 是 Facebook 的人發展出來的壓縮與解壓縮方式,對比的對象主要是 zlib (或者說 gzip),官網上有不少比較圖。目標是希望在同樣的壓縮處理速度下,可以得到更好的壓縮率。

Redshift 支援 Zstandard 等於是讓現有使用 gzip 的使用者免費升級的感覺...

Pinterest 在 InnoDB Compression 的努力

Pinterest 用 InnoDB 儲存各式資料,而且使用了 InnoDB Compression 的功能。他們花了不少力氣跟 Percona 合作改善 InnoDB Compression 的效能:「Evolving MySQL Compression - Part 1」。

文章有點長度,重點在於他們在 MySQL 裡面放了大量的 JSON:

A Pin is stored as a 1.2 KB JSON blob in sharded MySQL databases.

他們發現新版 zlib 的 predefined dictionary 可以讓壓縮率變得更高 (從本來的 ~50% 到 ~66%);而除了壓縮率變高外,由於事先定義了字典內容,對於效能的提昇也不少 (warm up):

Zlib version 1.2.7.1 was released in early 2013 and added the ability to use a predefined “dictionary” to prefill the lookback window for LZ77. This seemed promising since we could “warm up” the lookback window with field names and other common strings. We ran a few tests using the Python Zlib library with a naive predefined dictionary consisting of an arbitrary Pin JSON blob. The compression savings increased from ~50% to ~66% at what appeared to be relatively little cost.

另外他們做了 read-only 的 benchmark (畢竟這是重點)。圖片資料有點糊,但可以看出 y 軸是 Queries/sec。而 x 軸上則用文字給了些說明,黃色是 TokuDB,紅色是本來的 InnoDB Compression,剩下的都是不同的字典集的成果:

Below is a graph from our presentation which showed a read-only version of our production workload at concurrency of 256, 128, 32, 16, 8, 4 and 1 clients. TokuDB is in yellow, InnoDB page compression is in red and the other lines are column compression with a variety of dictionaries.

整體效率都比之前高不少,尤其是當 concurrent query 的數量偏高的時候差距會很大。

而這個功能將會納入未來的 Percona 版本,對於在 MySQL 裡面會塞 JSON 或是 XML 的人應該會很有幫助:

We worked with Percona to create a specification for column compression with an optional predefined dictionary and then contracted with Percona to build the feature.

Facebook 推出的 Zstandard 壓縮

Facebook 發了一篇出來,講 Zstandard:「Smaller and faster data compression with Zstandard」,可以看到:

如果與 Google 去年 open source 出來的 Brotli 相比,Zstandard 則是著重在速度,想要做出一個比 zlib 快很多但又比 zlib 壓的好的壓縮演算法。

CloudFlare 對 Brotli 的測試

之前有提過這件事情,由於 Firefox 已經支援 Brotli 了 (Google 推出 Brotli 無損壓縮法),所以 CloudFlare 的人整理了目前的效能比較:「Results of experimenting with Brotli for dynamic web content」。

主要還是 Brotli 拿了不少資源來換壓縮率,對於 static content 由於可以事先算好而大勝不少 (大約可以再榨出 15% 的壓縮率,從 zlib 9 的 27.7% 降到 brotli 10 的 23.3%):

The current state of Brotli gives us some mixed impressions. There is no yes/no answer to the question "Is Brotli better than gzip?". It definitely looks like a big win for static content compression, but on the web where the content is dynamic we also need to consider on-the-fly compression.

另外對於大檔案、網路速度不快的連線來說也頗有幫助,但對於 on-the-fly 的壓縮反而會比較慢。

Google 推出 Brotli 無損壓縮法

Google 推出了 Brotli 這個無損壓縮法:「Introducing Brotli: a new compression algorithm for the internet」。

Google 推出的 Zopfli 相容於 DEFLATE 的超慢壓縮演算法,但可以多壓榨出 3%~8% 的壓縮率。而 Brotli 則是重新設計,壓縮與解壓縮速度跟 DEFLATE 差不多,但壓縮率比 Zopfli 多了 20%~26%。

This new format allows us to get 20–26% higher compression ratios over Zopfli. In our study ‘Comparison of Brotli, Deflate, Zopfli, LZMA, LZHAM and Bzip2 Compression Algorithms’ we show that Brotli is roughly as fast as zlib’s Deflate implementation.

由於目標是希望讓瀏覽器支援新的壓縮法,Google 把 Brotli 往 RFC 提案,試著變成公開標準:「Brotli Compressed Data Format」。

看了看 commit log,看起來已經開發一陣子了...

CloudFlare 加速 zlib library

CloudFlare 大幅改善 zlib,使得速度相較原來的版本快了許多:「Fighting Cancer: The Unexpected Benefit Of Open Sourcing Our Code」。

改變的部份主要是 CPU 指令集的特性,以及 longest-match function 的改善。可以看出不同的測試樣本 (corpus) 在壓縮率沒有變差的情況下,大幅改善了速度。

Calgary corpus

Canterbury corpus

Large corpus

Silesia corpus

速度快非常多,跟 Google 以壓縮率為導向而放出來的 zopfli 剛好是兩個極端:「Google 發表與 zlib/deflate 相容的壓縮程式,再小 5%...」。

Google 將發現安全問題的獎勵延伸到 Open Source 專案上...

Slashdot 上看到 Google 將發現安全問題的獎勵從自家產品延伸到 Open Source 專案上:「Google Offers Cash For Security Fixes To Linux and Other FOSS Projects」。

官方的公告在「Going beyond vulnerability rewards」,規則則是在「Patch Rewards – Application Security – Google」。

初期限制在這些專案上:(直接複製過來)

  • Core infrastructure network services: OpenSSH, BIND, ISC DHCP
  • Core infrastructure image parsers: libjpeg, libjpeg-turbo, libpng, giflib
  • Open-source foundations of Google Chrome: Chromium, Blink
  • Other high-impact libraries: OpenSSL, zlib
  • Security-critical, commonly used components of the Linux kernel (including KVM)

獎勵金額從 USD$500 到 USD$3133.7,這邊的 31337 應該是出自「Leet」吧...

這算是一種回饋社群的方式...