Vector clock 的發明時間軸

一樣是在 Hacker News 上看到「Who invented vector clocks? (decomposition.al)」這篇文章,在找出誰發明了 vector clock,原文在「Who invented vector clocks?」。

主要有兩個不同的時間點,一個是 vector clock 概念的提出,另外一個是第一次用到 vector 這個詞。

這篇讓我覺得有趣的地方是,vector clock 本來就是在處理分散式系統裡面事件順序的問題,而這篇文章則是在找出真實世界裡面這些發明的先後順序,而且也牽扯到了各種 citation (類比到分散式系統裡事件的 dependency)。

用 Poetry 的相依性演算法解數獨 (Sudoku)

Daily Lobsters 上看到「Solving Sudoku with Poetry's dependency resolver」這篇完全是惡搞 PythonPoetry 套件 XDDD

作者搞出來的方法是這樣,指定 81 個版號來表示題目,然後跑 Poetry 找可以的版本組合:

[tool.poetry.dependencies]
python = "^3.6"
sudoku-cell11 = "*"
sudoku-cell12 = "2.0.0"
sudoku-cell13 = "*"
sudoku-cell14 = "8.0.0"
sudoku-cell15 = "*"
sudoku-cell16 = "9.0.0"
sudoku-cell17 = "*"
sudoku-cell18 = "*"
sudoku-cell19 = "*"
sudoku-cell21 = "3.0.0"
sudoku-cell22 = "7.0.0"
sudoku-cell23 = "*"
sudoku-cell24 = "6.0.0"
...

另外作者有提到,本來是打算用 Yarn 來解,但看起來各種嘗試都會搞爆 Yarn,才換到 Python 上面玩 XD

Ingo Molnár 提出讓 Linux Kernel 編譯速度提昇的 mega patch

Hacker News 首頁上看到「Massive ~2.3k Patch Series Would Improve Linux Build Times 50~80% & Fix "Dependency Hell"」這個,對應到 mailing list 上的信件是「* [PATCH 0000/2297] [ANNOUNCE, RFC] "Fast Kernel Headers" Tree -v1: Eliminate the Linux kernel's "Dependency Hell"」這個,看到「0000/2297」這個 prefix XDDD

他主要是想要改善 Linux Kernel 的 compile 時間 (從 project 的名稱「Fast Kernel Headers」可以看到),只是沒想到會縮短這麼多。另外一方面也順便處理了 dependency hell 的問題 (改善維護性)。

測試出來的結果相當驚人,從 231.34 +- 0.60 secs (15.5 builds/hour) 到 129.97 +- 0.51 secs (27.7 builds/hour),以編譯次數來看的話是 78% 的改善。如果以 CPU time 來看的話,從 11,474,982.05 msec cpu-clock 降到 7,100,730.37 msec cpu-clock,也是以編譯次數來算的話,有 61.6% 的改善...

這是花了一年多的時間嘗試才達成的目標,嘗試不同的方法,前幾次雖然都有改善,但改善幅度太小,變動卻太大,他覺得不值得丟出來,直到第三次才達成這樣的目標...

第一次:

When I started this project, late 2020, I expected there to be maybe 50-100 patches. I did a few crude measurements that suggested that about 20% build speed improvement could be gained by reducing header dependencies, without having a substantial runtime effect on the kernel. Seemed substantial enough to justify 50-100 commits.

第二次:

But as the number of patches increased, I saw only limited performance increases. By mid-2021 I got to over 500 commits in this tree and had to throw away my second attempt (!), the first two approaches simply didn't scale, weren't maintainable and barely offered a 4% build speedup, not worth the churn of 500 patches and not worth even announcing.

第三次:

With the third attempt I introduced the per_task() machinery which brought the necessary flexibility to reduce dependencies drastically, and it was a type-clean approach that improved maintainability. But even at 1,000 commits I barely got to a 10% build speed improvement. Again this was not something I felt comfortable pushing upstream, or even announcing. :-/

然後基於第三次的成果覺得有望,意外的發現後續的速度改善比想像中的多非常多:

But the numbers were pretty clear: 20% performance gains were very much possible. So I kept developing this tree, and most of the speedups started arriving after over 1,500 commits, in the fall of 2021. I was very surprised when it went beyond 20% speedup and more, then arrived at the current 78% with my reference config. There's a clear super-linear improvement property of kernel build overhead, once the number of dependencies is reduced to the bare minimum.

這次的 patch 雖然超大包,但看起來對於 compile 時間改善非常多,應該會有不少討論... 消息還蠻新的 (台灣時間今天早上五點的信),晚點可以看一下其他大老出來回什麼...

Google 提供掃描 JAR 檔內是否有中獎的 Log4j 的工具

Hacker News 首頁上看到 Google 提供了一套用 Golang 寫的工具,可以掃描 JAR 檔裡面是否有中獎的 Log4j:「log4jscanner」,對應的討論在「Log4jscanner (github.com/google)」這邊。

看起來是內部工具,放出來前先把 vcs history 清掉了:

We unfortunately had to squash the history when open sourcing. The following contributors were instrumental in this project's development: [...]

另外討論裡也有人提到「OWASP Dependency-Check」這個工具也可以掃,這套就更一般性了:

Dependency-check automatically updates itself using the NVD Data Feeds hosted by NIST.

用 Exodus 打包 Linux ELF 檔案到其他機器上

前幾天在 Hacker News Daily 上看到的工具:「Exodus」,官方的說明是這樣:

Painless relocation of Linux binaries–and all of their dependencies–without containers.

技術上是把 Linux ELF 檔案搬到其他機器上以外,也幫你把對應的 dynamic library 都一起包進去:

  • Finding and bundling all of a binary's dependencies.
  • Launching the binary in such a way that the proper dependencies are used without any potential interaction from system libraries on the destination machine.

而 Linux 的 Kernel 因為有儘量維持 ABI compatibility,應該是不會有太大的問題,除非剛好用到新的 API...

看起來是個除了用 static compile 以外的解法,好像可以來弄弄看 FFmpeg

把 npm 的 dependency 當作 PageRank 的資料來源,分析 npm 目前的生態...

在「An Analysis of the JavaScript Package Ecosystem npm」這篇看到作者把 npm 的 dependency 當作資料來源,計算出 npm 的 PageRank:

可以看到 Underscore.js 的 PageRank 一直都維持在第一位... 這個方法頗有趣的,不知道有沒有其他語言的 :o

Salt 要做到「當某個檔案存在時,執行某個指令」的方法...

愈用愈有感覺 SaltStack 是一堆 workaround 的集合,一開始在設計整個系統時沒有規劃好,然後一直堆上去。

標題的這個問題是出自於 Ubuntu 預設會將 CPU 調節成 ondemand,方式是透過 /etc/rc*.d/ 下的 symbolic link 在開機時自動執行。

拔掉的方法是 updated-rc.d ondemand disable (而非直接砍掉 /etc/rc*.d/ 裡面的檔案),想要透過 SaltStack 提供的 file.exists 或 file.missing 都發現不可行。

最後是 cmd.run + onlyif + test 搞定:

ondemand-disable:
  cmd.run:
    - name: update-rc.d ondemand disable
    - onlyif: test -e /etc/rc2.d/S99ondemand

SaltStack 對於 dependency 的設計看起來問題重重,如果想要用 SaltStack 的人可以好好考慮一下。

現在的作法是直接 trial and error 跟他拼,PuppetChefSaltStack 都直接用時間跟他換。原因是這東西實在太底層了,架構不好就是上面的管理員與 DevOps 一直 workaround。

現在有種互相在比爛的感覺...