Tag: structure

Home » Posts tagged "structure"

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 問題。

Cassandra, Computer, Database, Murmuring, Programming, SoftwareNo Comment

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 差多少。

CDN, Computer, Murmuring, Network, ProgrammingNo Comment

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.

包括了權限繼承的概念。

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

Computer, Murmuring, Network, Security, Service, WWWNo Comment

Reddit 在處理 Page View 的方式

Reddit 說明了他們如何處理 pageview：「View Counting at Reddit」。

以 Reddit 的規模有提到兩個重點，第一個在善用 Redis 的 HyperLogLog 這個資料結構，當量大的時候其實可以允許有微小的誤差：

The amount of memory varies per implementation, but in the case of this implementation, we could count over 1 million IDs using just 12 kilobytes of space, which would be 0.15% of the original space usage!

維基百科上有說明當資料量在 109 這個等級時，用 1.5KB 的記憶體只有 2% 的誤差值：

The HyperLogLog algorithm is able to estimate cardinalities of > 109 with a typical error rate of 2%, using 1.5 kB of memory.

第二個則是寫入允許短時間的誤差 (pageview 不會即時反應)，透過批次處理降低對 Cassandra cluster 的負荷：

Writes to Cassandra are batched in 10-second groups per post in order to avoid overloading the cluster.

可以注意到把 Redis 當作 cache 層而非 storage 層。

主要原因應該跟 Redis 定位是 data structure server 而非 data structure storage 有關 (可以從對 Durability 的作法看出來)，而使用 Cassandra 存 key-value 非常容易 scale，但讀取很慢。剛好兩個相輔相成。

Cassandra, Computer, Database, Murmuring, Network, Programming, Service, SoftwareNo Comment Computer, Murmuring, ProgrammingNo Comment

Cuckoo Filter：比 Bloom Filter 多了 Delete

在「Cuckoo Filter implementation in Go, better than Bloom Filters」這邊看到這個資料結構，有興趣的人也可以看「Cuckoo Filter：设计与实现」這篇介紹，下面是我抓重點整理。

Bloom Filter 支援的操作：

  • Add(element)
  • Query(element)

1970 年提出來的資料結構。優點是空間複雜度是 O(1)，Query(element) 會有可接受的 false positive，缺點是不支援 Delete(element)、以及數量變多時誤判率的增加。

Cuckoo Filter 多了一組操作：

  • Delete(element)

2014 年提出來的資料結構。空間複雜度一樣是 O(1)，但相同的空間用量下 false positive 變低，然後支援 Delete(element) 了。也因此論文直接寫「Cuckoo Filter: Practically Better Than Bloom」，表示可以直接替代。

Computer, Murmuring, Programming1 Comment

看到 zmx 貼了之前的連結，更確信 Uber 的問題不是技術問題了...

在 Twitter 上看到 zmx 提了一個連結，講 Uber 年初時貼的「How We Built Uber Engineering’s Highest Query per Second Service Using Go」這篇文章的問題：

對照最近的事情還蠻有趣的，尤其是這篇文章後面提到的，酸～爆～了～XDDD：

It is clear to me that the team at Uber under-engineered this problem. Thoughtfully designing this service could trim down the number of nodes by an order of magnitude and save hundreds of thousands of dollars each year. That may sound like pittance to a company valued at more than the GDP of Delaware, but in my eyes that’s the salaries of a few engineers and a few good engineers can go a long way. Maybe even further than the few extra Mercedes-Benz S-Classes they could add to their fleet from the money they could be saving...

先不提政治問題，上面提到的 Quadtree 算是簡單易懂的結構，好久沒看到這個資料結構了：

Computer, Murmuring, Network, Programming, Search Engine, Software1 Comment

MySQL 的 Index 設計技巧

Percona 的「Indexing 101: Optimizing MySQL queries on a single table」這篇講了最基本的 index 設計技巧，雖然文章裡沒提到，但最好是需要 B-tree 與 B+ tree 的背景知識。

MySQL 的 query 大致分成幾個階段。先決定要使用哪些 index (或是完全不用)，然後透過 index 抓出符合條件資料 (或是 table scan)，最後再細部過濾。

以文章裡提到的「Multiple inequalities」範例裡這樣的 SQL query 來討論：

SELECT * FROM t WHERE c > 100 and b < 10 and d = 'xyz'

如果 index 是 (d, c)，需要在透過這組 index 抓出資料後再過濾 b < 10 的條件。而如果 index 是 (d, b)，需要在取出資料後再過濾 c > 100 的條件。也就是 B+ tree 做不到的事情，就要另外 post-processing。

另外也有提到 covering index 對效能提昇的原理，不過這就有點屬於怪招了...

Computer, Database, Murmuring, MySQL, SoftwareNo Comment

資料結構、RDBMS、ORM

欠了很久的雜記。既然是雜記，只是把一些事情記錄下來，許多句子的主題會跳來跳去，請多見諒。

先解釋標題的三個詞彙。這邊要講的是三種存取資料的方式：

  • 資料結構：直接操作最底層的資料結構。
  • RDBMS (Relational Database Management System，關聯式資料庫)：透過 RDBMS 存取資料的方式，在 open source 領域比較常遇到 MySQL 與 PostgreSQL。由於與下面的 ORM 比較，這一條指的是透過 SQL query 去存取資料。
  • ORM (Object-Relational Mapping)：透過程式語言的 object 以及 object 之間的關聯性存取資料。

彈性最高、效能也最好的是直接的資料存取，但寫起來也最複雜；而 ORM 大致上就是反過來。

現代的 RDBMS 大多都有實做 ACID，在自己操作資料結構時考慮這塊會比較辛苦。兩個層級之間有一些 library 試著解決這個問題 (像是 BerkeleyDB 或是 LevelDB)，不過這篇文章暫時跳過。

MySQL 與其他的 RDBMS 比較起來欠了許多東西，但 High Availability 的成熟度以及效能而成為 open source 的第一選項。而也因為許多人使用，大家都知道 MySQL 的先天限制，也有許多 workaround 出現，所以大多數的狀況下這不是問題。

MySQL 的 InnoDB 其實寫的相當不錯，但 MySQL 的 SQL parser 一直都是 MySQL 的痛處，所以許多人使用 MySQL 時會儘量使用 simple query，而 ORM 的特性剛好可以搭上風。

使用 ORM 時最常見要避免的是 N+1 的問題，其他常見到的問題大多都不是 ORM 專有的。

先整理到這邊。

Computer, Database, Murmuring, MySQL, PostgreSQL, Programming, SoftwareNo Comment

ESR 解釋 C 的 Compiler 對 Structure Packing 的處理...

ESR (Eric S. Raymond) 寫了一篇 C Compiler 對 struct 實際如何佔用記憶體空間的說明：「The Lost Art of C Structure Packing」，全文在「The Lost Art of C Structure Packing」。

以前都學過也都還記得，但沒用就不容易想起來...

以文章裡的例子用這個 struct 說明：

struct {
    char *p;
    char c;
    int x;
};

(下面就不列出 struct 的部份了)

實際上在記憶體裡面會因為 alignment requirement 的關係，多了一個 padding (pad)：

char *p;      /* 4 or 8 bytes */char c;       /* 1 byte */char pad[3];  /* 3 bytes */int x;        /* 4 bytes */

而如果 x 是 8 bytes 的 long 時：

char *p;
char c;
long x;

padding 會變成：

char *p;     /* 8 bytes */char c;      /* 1 byte
char pad[7]; /* 7 bytes */long x;      /* 8 bytes */

這是因為硬體架構的關係。有些是因為硬體只支援切齊 alignment 的存取指令，有些是因為效率的差異而預設會增加 padding。

在處理 protocol 這類必須依照原始的 struct 設計時，需要指定 

#pragma pack

強迫 compiler 關掉，不然 compiler 還是會補上 padding。

而在一般的情況下，調整 struct 裡元素的位置就能夠在不影像存取效能的前提下節省空間，如果是大量的 struct 時效果就會變得很明顯...

Computer, Hardware, Murmuring, Programming, Software2 Comments

Recent Comments

Archives

Blogroll