JavaScript 的 sort 變成 stable

看到「Stable Array.prototype.sort」這篇在講 JavaScript 規格書裡的 sort...

本來 JavaScript 的規格書裡,各種 sort 都沒有保證 stable,而在「[Normative] Make Array.prototype.sort stable #1340」與「[Normative] Make %TypedArray%.prototype.sort stable #1433」這兩個地方則有了變化,提案在規格裡加入 stable 的要求,可以減少開發者因為不知道 unstable 而造成的問題...

Firefox 則是很久前就決定使用 Merge sort 了 (看了一下,當時還在從 Firebird 轉換名稱到 Firefox 的時期):「Array.sort isn't a stable sort (switch to MergeSort)」。

另外這篇也剛好提到了 V8 使用 Timsort 當作 stable sorting algorithm,之前就有看到但發現沒在 blog 上提過...

Timsort 是 1993 年發明出來的演算法,與 Merge sort 的情況類似,除了 stable 外,還可以保證最差的情境下的時間複雜度是 O(n*log(n))

Timsort is a hybrid stable sorting algorithm, derived from merge sort and insertion sort, designed to perform well on many kinds of real-world data.

這個演算法的重點是善用已經排好的子序列,藉此降低記憶體操作次數而提昇效能,符合真實環境裡常見到的資料:

The algorithm finds subsequences of the data that are already ordered, and uses that knowledge to sort the remainder more efficiently.

除了 V8 採用這個演算法以外,其他常見的包括了 PythonAndroid 上的 Java SE:

Timsort has been Python's standard sorting algorithm since version 2.3. It is also used to sort arrays of non-primitive type in Java SE 7, on the Android platform, in GNU Octave, and Google Chrome.

被動靈氣加成:用 git rerere 解決同樣的 conflict 問題

Git 上一個很好用的設定,不需要改變原來的工作模式,有種「被動靈氣」的感覺 XD

Twitter 上看到這則推:

裡面提到了 git rerere 這個指令,投影片裡面雖然有給方法,不過一時間沒看懂... (oops)

找了一下官方文件與其他文件後發現其實意外的簡單,就是在 .gitconfig 設定檔內開啟個 flag 後就沒事了,其他的動作照以前的方式走。Git 的被動技能就是在每次遇到 conflict 以及解決的時候就會記錄下來,當下次遇到同樣的情況就自動幫你解。

先開起來再說,之後來看看有什麼副作用再來抱怨 XDDD

Mark Callaghan 花五分鐘介紹 LSM trees

實做 MyRocksMark Callaghan 花五分鐘在 CIDR 2019 上介紹 LSM tree:「Geek code for LSM trees」。翻了一下發現 CIDR 是兩年辦一次,跟之前遇過的 conference 不太一樣...

投影片在「Diversity of LSM tree shapes」這邊可以看到,在五分鐘內講完的前提下規劃出的重點...

合併 RRD 資料的工具

昨天把跑在 Raspberry Pi 上的 SmokePing 資料改用統一版本 (我在 GitHub 上公開的 smokeping-config.d 這個),但有些節點的 naming 改變了,所以會需要將資料整在一起。

在透過 Google 搜尋後,用的工具是「A very simple script to merge multiple RRD files, since none of those available seem to work.」這個,是一隻 Python 的程式。另外可以從程式碼裡面看到他使用了 rrdtool 這個 CLI 工具 (SmokePing 用了 RRD 格式儲存資料),所以使用這隻程式前需要先安裝 rrdtool 這個套件:

$ sudo apt install rrdtool

接下來就是照說明來轉換。由於 rrdtool 這隻程式沒有對 filename 做特殊處理 (i.e. 把 - 當作 stdin),所以會使用到 /dev/stdin 這種特殊方式來當作 input:

./simple-rrd-merge.py input-a.rrd input-b.rrd | rrdtool restore /dev/stdin output.rrd

當然,要記得先把 SmokePing 停掉再跑會比較好 XD

生出的 RRD 檔案再覆蓋回去 (我是先備份起來,以免有意外...),然後再把 SmokePing 跑起來就可以了。

GitHub 引入 Code Owner 的概念

GitHub 推出了 Code Owner 的概念:「Introducing code owners」。也很直接說這個能是向 Chromium「致敬」出來的:

The code owners feature was inspired by Chromium's use of OWNERS files.

檔案名稱是 CODEOWNERS,可以放在根目錄或是 .github/ 下,可以針對不同的目錄設不同的人:

To specify code owners, create a file named CODEOWNERS in the repository's root directory (or in .github/ if you prefer) with the following format[.]

這樣一來,在 pull request 的時候就會跳出來:

另外也可以設定需要 code owner 同意才能 merge:

Percona 宣佈支援 MyRocks (MySQL 上的 RocksDB engine)

RocksDBFacebookGoogle 放出的 LevelDB 改出來,然後被更多人接受並且投注資源的 library... (看兩邊的 GitHub 應該就會有感覺了)

而 Facebook 的人在改進後又花了不少力氣 porting 到 MySQL 上...

之前 Twitter 上就有看到不少消息,這次算是在 Percona 官方的 blog 上正式公佈要支援 MyRocks 的消息:「Announcing MyRocks in Percona Server for MySQL」。

依照目前的計畫次在明年 2017 的 Q1 放出 experimental build,依照 Percona 的品質慣例,應該是可以拿來在測試環境下跑的順順的 (在還沒有 heavy loading 的前提下):

We will provide the experimental builds of MyRocks in Percona Server in Q1 2017, and we encourage you to start testing and experimenting so we can quickly release a solid GA version.

文章下面的 comment 剛好有人提到 Percona 另外一個產品線 TokuDB,這兩個產品線重複的問題:

MyRocks seems pretty similar to TokuDB. They are both write-optimized. MyRocks uses LSM tree while TokuDB uses fractal tree.

How do the 2 compare? Which one would you recommend using?

之前被 Percona 買下的 TokuDB 跟 Facebook 所發展出來的 MyRocks 的產品重複性頗高 (都是為了寫入的部分最佳化)。應該還是因為 fractal treeLSM tree 成熟度造成的效能差異還是太明顯吧 (當然另外也跟後面公司投入的資源有關),讓 Percona 決定還是要支援 MyRocks,而不是全力推動自家買下的 TokuDB... (唔,變成阿斗了?)

不知道成熟後有沒有機會變成 InnoDB replacement...

PostgreSQL 9.5 釋出,UPSERT!

PostgreSQL 9.5 正式發行,這次新增了大家期待已久的 UPSERT 功能:「PostgreSQL 9.5: UPSERT, Row Level Security, and Big Data」。

SQL:2003 正式定義出 UPSERT,被稱為 Merge,不過看網路上一般還是比較習慣 UPSERT 這個用法:

A relational database management system uses SQL MERGE (also called upsert) statements to INSERT new records or UPDATE existing records depending on whether condition matches.

也就是當沒資料的時候就 INSERT,有資料的時候就 UPDATE 的語法。常見的使用情境是拿來當 counter 用 (雖然這很傷資料庫的效能)。

沒有 UPSERT 的時候只能用 transaction 或是 store procedure 搭出來,效能上會比在 database engine 裡實作來的差,所以 UPSERT 還是被實作出來了。