Content Defined Chunking (CDC)

前幾個禮拜在 Hacker News Daily 上看到「CDC File Transfer (github.com/google)」這則,連結是指到 GoogleGitHub 專案上,裡面實做了 FastCDC 演算法,另外說明他們為什麼要解這個問題以及對應的成果:「google/cdc-file-transfer」。

Google 的人看起來像是是在 CI/CD 階段遇到頻寬上的問題 (從「The builds are 40-45 GB large.」這邊猜),用 scprsync 看起來都不能解,所以他們自己刻了 FastCDC 演算法來解。

但我對 Content Defined Chunking (CDC) 不熟,所以先查一下 CDC 是什麼東西,就查到 restic 這篇講得很清楚:「Foundation - Introducing Content Defined Chunking (CDC)」。

要計算 delta 很直覺的作法就是要切 chunk,而接著的直覺就是固定大小的 chunk 切開,像是這樣每 16 bytes 切一個 chunk:

0123456789abcdef 0123456789abcdef 0123456789abcdef 0123456789abcdef

如果其中一個地方有變化,但其他沒變化的話就可以透過 cryptographic hash function (像是 SHA-256) 確認 chunk 內容一樣,進而省下很多傳輸的頻寬:

0123456789abcdef 0123456789ABCDEF 0123456789abcdef 0123456789abcdef

但可以馬上看出來這個方法的大缺點是只能處理 replacement,很難處理 insert & delete 的部份,舉例來說,如果變更是在開頭的地方加上 ABC,就會造成 chunk 會完全不一樣,而導致全部都要再傳一次:

ABC0123456789abc def0123456789abc def0123456789abc def0123456789abc def

這邊其實是個經典的演算法問題:想要找出兩個 string 的差異 (把舊的內容當作一個 string,新的內容也當作一個 string)。

這個問題算是 Edit distance 類型的題目,但你會發現解 Edit distance 的演算法會需要先傳輸完整個 string 才能開始跑演算法,這就本末倒置了。

而另外一個想法是,放棄固定的 chunk 大小,改用其他方式決定 chunk 的邊界要切在哪裡。而 CDC 就是利用一段 sliding window + hash 來找出切割的點。

文章裡面提到的 sliding window 是 64 bytes,這邊就可以算出對應的 HASH(b0, b1, ..., b63),然後往右滑動變成 HASH(b1, b2, ..., b64),再來是 HASH(b2, b3, ..., b65),一直往右滑動計算。

接下來 restic 會看 hash 值,如果最低的 21 bits 都是 0 就切開,所以 chunk 大小的期望值應該是 2MB?(這邊不確定,好像不能直接用 2^21 算,應該用積分之類的方法...)

For each fingerprint, restic then tests if the lowest 21 bits are zero. If this is the case, restic found a new chunk boundary.

而這個演算法可以適應新增與刪除的操作,不會造成從新增或刪除後的資料都要重傳,只有自己這個 chunk 需要重傳 (可能前或後的 chunk 也會要)。

然後挑一下 hash function 的特性,就可以讓計算的速度也很快。這邊提到了 hash function 可以用 Rolling hash,可以很快的從 HASH(b0, b1, ..., b63) 算出 HASH(b1, b2, ..., b64),而不需要全部重算。

有了 chunk 後,再用 cryptographic hash function 比較 chunk 的內容是否一樣,這樣就可以大幅降低傳輸所需要的頻寬了。

EULA 不能禁止使用者 decompile 修 bug

Hacker News Daily 上翻到的,歐洲法院認為 EULA 不能禁止使用者 decompile 修 bug:「EU court rules no EULA can forbid decompilation, if you want to fix a bug (europa.eu)」,官方的英文版文件在這邊可以翻到,不過原始判決是法文:

* Language of the case: French.

這是 Top System SA 與比利時政府打的訴訟,法院認為修 bug 而需要 decompile 這件事情是合法的,即使考慮到 Article 6 的規範:

In the light of the foregoing considerations, the answer to the first question referred is that Article 5(1) of Directive 91/250 must be interpreted as meaning that the lawful purchaser of a computer program is entitled to decompile all or part of that program in order to correct errors affecting its operation, including where the correction consists in disabling a function that is affecting the proper operation of the application of which that program forms a part.

In the light of the foregoing considerations, the answer to the second question referred is that Article 5(1) of Directive 91/250 must be interpreted as meaning that the lawful purchaser of a computer program who wishes to decompile that program in order to correct errors affecting the operation thereof is not required to satisfy the requirements laid down in Article 6 of that directive. However, that purchaser is entitled to carry out such a decompilation only to the extent necessary to effect that correction and in compliance, where appropriate, with the conditions laid down in the contract with the holder of the copyright in that program.

案子看起來應該還有得打?看起來好像不是最終判決...

REQUEST for a preliminary ruling under Article 267 TFEU from the Cour d’appel de Bruxelles (Court of Appeal, Brussels, Belgium), made by decision of 20 December 2019, received at the Court on 14 January 2020[.]

但不管怎樣,算是有些東西出來了... 然後 Hacker News 上面的討論就看到一些很歡樂的例子:

This becomes incredibly interesting in terms of e.g. Denuvo. This anti-piracy middleware has been shown to make games unplayable, and this EU law seems to support removing it.

哭啊怎麼提到該死的 Denuvo XDDD

從 Oracle 轉移到 PostgreSQL 的工具 Orafce

在「Migrating from Oracle to PostgreSQL: Tips and Tricks」這邊看到在討論怎麼從 Oracle 資料庫轉移到 PostgreSQL 上。

開頭介紹了 Orafce,實做了一些 Oracle 上的 function,可以使得轉移時不用改寫太多 SQL:

The "orafce" project implements of some functions from the Oracle database. The functionality was verified on Oracle 10g, and the module is useful for production work.

先記錄起來,之後如果有機會的話比較好找...

講求速度的 Cryptographic Hash Function:BLAKE3

今年年初發表的 cryptographic hash function,重點在於速度:「The BLAKE3 cryptographic hash function」。

在 1 thread 的情況下就遠遠拉開目前的 cryptographic hash function:

因為速度是主打項目,所以提供的範例已經是使用 x86 與 ARM 的 SIMD 加速的版本,另外也可以透過平行化加速。

所以是要拼 de-facto standard 嗎,不知道 browser 這邊有沒有機會採用,雖然在現在都是使用 AEAD cipher 的情況下好像沒有太多出場機會...

AWS Lambda 支援 Ruby 2.5 以及其他語言

AWS 宣佈 Lambda 支援 Ruby 2.5:「AWS Lambda Supports Ruby」。

另外宣佈可以透過 Layer 的方式讓任何程式語言在上面跑 (前面提到的 Ruby 看起來就是用這個方式支援的):「New for AWS Lambda – Use Any Programming Language and Share Common Components」。

The Runtime API is the future of how we’ll support new languages in Lambda. For example, this is how we built support for the Ruby language.

Trac 1.2 上惡搞 TracTicketReferencePlugin 讓他會動...

TracTicketReferencePlugin 是個 Trac 上設定 ticket 之間關聯性的 plugin,與子母票有比較強烈的關係不同,有些人喜歡把相關的資料都掛在這邊。先前用都是在 Trac 1.0 上用,也沒什麼問題,最近在 Trac 1.2 上跑發現直接有 js error...

原因是 TracTicketReferencePlugin 用到 jQuery.live(),而這個函式在 jQuery 1.7 被宣告 deprecated,在 jQuery 1.9 被正式拔掉了。而 Trac 1.0 用的是 jQuery 1.7,所以不會有問題;Trac 1.2 用的是 jQuery 1.12,於是就爛掉了...

剛好就是昨天,有人在作者的 repository 上發 issue 出來 (另外也提供了 patch):「t2y / trac.plugins.ticketref / issues / #9 - JavaScript errors with Trac 1.2 — Bitbucket」。雖然 patch 本身不算難,但我實在懶的查 Mercurial 的操作,於是決定用 workaround 解...

想法是讓 jQuery.live() 會動,這點在 jQuery 官方出的 Migrate 就可以達到 (需要用 1.4.1 版,而不是 3.0.1 版),於是第一步就是在 site.html 內直接先下手為強,讀 jQuery 後馬上讀 Migrate:

  <!--! Add site-specific style sheet -->
  <head py:match="head" py:attrs="select('@*')">
    <script src="https://code.jquery.com/jquery-1.12.4.min.js"></script>
    <script src="https://code.jquery.com/jquery-migrate-1.4.1.min.js"></script>
    ${select('*|comment()|text()')}

但 Trac 還是會再載入一次的 jQuery 而蓋過去,所以我們要讓 Trac 不會載入,在 trac.ini 內的 jquery_location 設定讓他讀一個空的 js 檔:

jquery_location = site/null.js

然後生一個空的 trac/htdocs/null.js 讓他讀。

最後開一張票追蹤,看什麼時候官方放新版,再把這串 workaround 拔掉...

兩個 gperf...

翻資料的時候覺得怎麼跟印象中的不太一樣,多花些時間翻了一下,發現原來有兩個東西同名...

一個是 GNUgperf,給定字串集合,產生 C 或 C++ 的 perfect hash function (i.e. no collision):

GNU gperf is a perfect hash function generator. For a given list of strings, it produces a hash function and hash table, in form of C or C++ code, for looking up a value depending on the input string. The hash function is perfect, which means that the hash table has no collisions, and the hash table lookup needs a single string comparison only.

另外一個是 Google 弄出來的 gperftoolsmalloc() 的替代品以及效能分析工具:

gperftools is a collection of a high-performance multi-threaded malloc() implementation, plus some pretty nifty performance analysis tools.

AWS Lambda 可使用的記憶體空間從 1.5GB 變成 3GB

AWS 是說 AWS Lambda 可用的記憶體空間 double 啦,不過 3008MB 這個數字有點怪...:「AWS Lambda Doubles Maximum Memory Capacity for Lambda Functions」。

You can now allocate 3008MB of memory to your AWS Lambda functions. Previously, the maximum amount of memory available to your functions was 1536MB. Now, it's easier to process workloads with higher memory or denser compute requirements, such as big data analysis, large file processing, and statistical computations.

這個就真的全區都生效了,包括一般人不能註冊的 AWS GovCloud (US) 與中國區:

This feature is available in US East (N. Virginia), US East (Ohio), US West (N. California), US West (Oregon), AWS GovCloud (US), Canada (Central), South America (São Paulo), EU (Frankfurt), EU (Ireland), EU (London), Asia Pacific (Mumbai), Asia Pacific (Seoul), Asia Pacific (Singapore), Asia Pacific (Sydney), Asia Pacific (Tokyo), and China (Beijing).

在 CLI 下開關以及查詢 EC2 的狀態...

有時候需要開 Ubuntu 測試東西,會在 AWS 上開 EC2 起來測試,但開 console 太麻煩了,寫幾個 function 丟進 shell script 裡面比較乾脆。其中查詢 Ubuntu AMI 的程式出自「How do I know what Ubuntu AMI to launch on EC2?」這邊。

ec2.ls() 裡,我的 jq 版本比較舊,不過不影響我的 copy & paste,所以就沒有 hack 他了。新版的應該可以多加上 | @tsv 變成 tab 隔開 (沒測過,查資料時查到而已)。

ec2.run() 裡,我這邊是先到 console 上查出 security group 與 subnet 的 id,然後這邊 hard code 進去。我的預設是開 t2.medium,臨時要指定的話就 ec2.run t2.nano 就可以改開 t2.nano 了,不過要注意的是,這邊程式在查詢時的條件是 hvm:ebs,換的時候要注意 image 相容性...

# AWS-related
function ec2.ls() {
    aws ec2 describe-instances | \
        jq -c -M '.Reservations[] | .Instances[] | [.InstanceId, .InstanceType, .PublicIpAddress]'
}

function ec2.rm() {
    local INSTANCE_ID=${1:i-xxxxxxxxxxxxxxxxx}
    aws ec2 terminate-instances --instance-id ${INSTANCE_ID}
}

function ec2.run() {
    local INSTANCE_TYPE=${1:-t2.medium}
    aws ec2 run-instances --image-id $(ec2.ubuntu_ami()) --key-name gslin --security-group-ids sg-xxxxxxxx --instance-type ${INSTANCE_TYPE} --subnet-id subnet-xxxxxxxx
}

function ec2.ubuntu_ami() {
    curl -s "https://cloud-images.ubuntu.com/locator/ec2/releasesTable" | \
    sed '$x;$G;/\(.*\),/!H;//!{$!d};$!x;$s//\1/;s/^\n//' | \
    jq -c '.aaData[] | select(contains(["16.04", "us-east-1", "hvm:ebs"]))' | \
    grep -o 'ami-[a-z0-9]\+' | \
    head -1
}

這種工具自己用的順手比較重要,要什麼功能自己改自己加...

話說 Ubuntu 網站上的 JSON 居然吐出 malformed data (trailing comma),這是自己 printf() 之類硬幹出來的嗎... XD

PHP 7.3 的 function 也會支援 trailing comma 了

這投票殺來殺去了好幾次才過,從 PHP 7.3 開始在 function 呼叫時就能接受 trailing comma 了:「PHP RFC: Allow a trailing comma in function calls」。

Wait, didn't we just vote on this?

Yes, there was an RFC to add trailing commas to all list syntax in PHP 7.2. Unfortunately due to an oversight on my end, the vote for function calls and function declarations was combined into one vote so the vote failed (but just barely!)

I was contacted by many “no” voters saying that they would have voted “yes” for function calls, but “no” for function declarations. This RFC proposes allowing a trailing comma in function call syntax only.

We are allowed to put this feature up for vote again since the mandatory 6-month waiting period has passed since the last vote and this RFC targets a new major version of PHP.

這次以 30:10 過了... (需要 2/3 以上同意)