Python 3.7+ 保證 dict 內容的順序

在「Dicts are now ordered, get used to it」這邊看到的,因為 Python 官方 (也就是 CPython) 實做 dict 的方式改變,然後決定把這個特性當作是 social contract,而不是當作 side effect 的特性 (也就是不保證之後版本會有相同特性)。

Changed in version 3.7: Dictionary order is guaranteed to be insertion order. This behavior was an implementation detail of CPython from 3.6.

作者裡面的兩張圖清楚表示出來以前的版本怎麼實做,與 3.7+ 的版本怎麼實做:

這樣就很好理解了。

不過考慮到還是有些系統用 Python 3.5 (像是 Ubuntu 16.04 內建的 python3) 與 Python 3.6 (Ubuntu 18.04 內建的 python3,雖然沒問題,但當時還沒有寫出來),也許還是先不要依賴這個行為會比較好。

不過以插入的順序列出好像不是很常用到...

比 Bloom filter 與 Cuckoo filter 再更進一步的 Xor filter

Bloom filter 算是教科書上的經典演算法之一,在實際應用上有更好的選擇,像是先前提到的 Cuckoo filter:「Cuckoo Filter:比 Bloom Filter 多了 Delete」。

現在又有人提出新的資料結構,號稱又比 Bloom filter 與 Cuckoo filter 好:「Xor Filters: Faster and Smaller Than Bloom Filters」。

不過並不是完全超越,其中馬上可以看到的差異就是不支援 delete:

Deletions are generally unsafe with these filters even in principle because they track hash values and cannot deal with collisions without access to the object data: if you have two objects mapping to the same hash value, and you have a filter on hash values, it is going to be difficult to delete one without the other.

論文的預印本可以在 arXiv 上下載:「Xor Filters: Faster and Smaller Than Bloom and Cuckoo Filters」。

PostgreSQL 的 Bloom index

前幾天才跟人提到 PostgreSQL 的功能與完整性比 MySQL 多不少,剛剛又看到 Percona 的「Bloom Indexes in PostgreSQL」這篇,裡面提到了 PostgreSQL 可以使用 Bloom filter 當作 index。

查了一下資料是從 PostgreSQL 9.6 支援的 (參考「PostgreSQL: Documentation: 9.6: bloom」這邊的說明),不過說明裡面沒看到 DELETE (以及 UPDATE) 會怎麼處理,因為原版的 Bloom filter 資料結構應該沒有能力處理刪除的情況...

另外這幾年比較有名的應該是 Cuckoo filter,不只支援刪除,而且空間與效能都比 Bloom filter 好,不知道為什麼是實做 Bloom filter...

PostgreSQL 裡的 B-tree 結構

在「Indexes in PostgreSQL — 4 (Btree)」這邊看到講 PostgreSQLB-tree 結構以及常見的查詢會怎麼使用 B-tree。

裡面講了三種查詢,第一種是等號的查詢 (Search by equality),第二種是不等號的查詢 (Search by inequality),第三種是範圍的查詢 (Search by range)。再後面講到排序與 index 的用法。

雖然是分析 PostgreSQL,但裡面是一般性的概念,其他使用 B-tree 結構的資料庫也是類似作法...

YAML 的痛點

Changelog 上看到「In defense of YAML」這篇講 YAML 的問題,裡面是引用「In Defense of YAML」這篇文章。

未必全盤接受文章裡面的說法,但裡面提到的兩個點的確是痛點,第一個是空白 (或者說 indent),第二格式特殊語法。這兩個是用 YAML 時都很頭痛的問題:

Whitespace is a minefield. Its syntax is surprisingly complex.

就像 JavaScript 的 == 一樣 (我指的是之前寫的「JavaScript 的 == 條列式比較」這篇),你可以把定義背下來,但你會覺得沒什麼道理可言而有種無奈的感覺...

文章裡也有提到 JSON 內沒有 comment 的設計的確是用起來比較無奈的地方...

Mark Callaghan 花五分鐘介紹 LSM trees

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

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

HyperLogLog 與 Bloom Filter

看到 FacebookPresto 裡增加使用 HyperLogLog 計算數量的能力,突然想到常常忘記這兩個拿準確度換速度的資料結構:「HyperLogLog in Presto: A significantly faster way to handle cardinality estimation」。

HyperLogLog (HLL) 是解決 Count-distinct problem 的資料結構,用很少的記憶體就可以給出一個誤差不大的值 (用 1.5KB 的空間處理十億等級的資料,誤差大約在 2%),所以 Presto 利用這個資料結構引進了 APPROX_DISTINCT() 以及其他的函數,就很容易在 L2/L3 cache 裡運算,藉此大幅提昇速度。

Depending upon the problem at hand, we can achieve speed improvements of anywhere from 7x to 1,000x.

先前也提過 Reddit 也用 HLL 統計資料:「Reddit 在處理 Page View 的方式」。

Bloom Filter 也是在處理大量資料的問題,但這個資料結構的功能不太一樣,是給出「有沒有存在」,使用空間與誤差大約是 10 bits per key (1% false positive),另外先前也有提到一些變形,可以提供其他功能。像是「Quotient filter」與「Cuckoo Filter:比 Bloom Filter 多了 Delete」。

Instagram 解決 Cassandra 效能問題的方法

在解決 Cassandra 效能問題中大概就 ScyllaDB 特別有名,用 C++ 重寫一次使得效能大幅改善。而 Instagram 的人則是把底層的資料結構換掉,改用 RocksDB (這公司真的很愛自家的 RocksDB...):「Open-sourcing a 10x reduction in Apache Cassandra tail latency」。

主要原因是他們發現 Cassandra 在處理資料的部份會有 JVM 的 GC 問題,而且是導致 Cassandra 效能差的主要原因:

Apache Cassandra is a distributed database with it’s own LSM tree-based storage engine written in Java. We found that the components in the storage engine, like memtable, compaction, read/write path, etc., created a lot of objects in the Java heap and generated a lot of overhead to JVM.

然後在換完後測試可以看到效能大幅提昇,也可以看到 GC 的延遲大幅降低:

In one of our production clusters, the P99 read latency dropped from 60ms to 20ms. We also observed that the GC stalls on that cluster dropped from 2.5% to 0.3%, which was a 10X reduction!

比較一下這兩者的差異:在 ScyllaDB 是全部都用 C++ 改寫 (資料結構不換),這樣就直接解決掉 JVM 的 GC 問題。在 Rocksandra 則是在 profiling 後挑重點換掉 (這邊看起來是處理資料的 code,直接換成 RocksDB),另外順便把一些界面抽象化... 兩個不一樣的解法,都解決了 JVM 的 GC 問題。

Quotient filter

之前有提過「Cuckoo Filter:比 Bloom Filter 多了 Delete」,最近在「A general purpose counting filter: making every bit count」這邊看到 Quotient filter,也是類似 Bloom filter 的資料結構,但想要解決更多問題。

一般的 Bloom filter (BF) 會有這些問題:

  • The inability to delete items
  • Poor scaling out of RAM
  • The inability to resize dynamically
  • The inability to count the number of occurrences of each item, especially with skewed input distributions.

而文章裡提到的 Quotient filter (QF) 就是要解這些問題。另外還提到了 Rank-and-Select-based Quotient filter (RSQF) 以及 Counting Quotient filter (CQF)。雖然多了一些空間需求,但看起來解掉不少問題... (尤其是刪除的能力)

效能上也還不錯,尤其是讀取速度的部份... 不過不知道相對於 Cuckoo filter 差多少。

GitHub 的組織管理可以堆階層了...

GitHub 的組織管理可以堆階層了:「Nested teams add depth to your team structure」。

If you're a member of Engineering and someone creates a child team called Security, team members of Engineering aren't automatically direct team members of Security. Security and all other teams nested under the Engineering will inherit repository permissions and @mentions but nothing else.

包括了權限繼承的概念。

這功能等好久了,剛好最近會用到... 本來得硬幹做,現在看起來可以比較方便的管理了。