Home » Posts tagged "secondary"

InnoDB 的 MVCC 繁忙時的效能問題

Facebook 上看到 Percona 的人修正了 InnoDB 的 MVCC 在繁忙時會有 O(n^2) 的效能問題:

MySQL 官方的 bug tracking system 是「InnoDB's MVCC has O(N^2) behaviors」這個,可以看到給的重製範例是在 transaction 內大量塞 INSERT 進去後,另外一個 transaction 使用 secondary index 就會受到影響。

裡面也有提到「Secondary index updates make consistent reads do O(N^2) undo page lookups」,雖然修正了,但看起來跟當時實做的規劃有關?所以導致許多地方都是 O(n^2)...

這個 bug 感覺是批次作業的行為?因為批次作業可能會用 transaction 包起來,一次寫入萬筆資料後再 COMMIT 進去。而這個行為很有機會觸發這個 bug,導致影響到線上的服務...

既有的 VPC 可以增加更多 subnet 了

既有的 Amazon VPC 可以增加更多的 subnet 了:「Amazon Virtual Private Cloud (VPC) now allows customers to expand their existing VPCs」。

Amazon Virtual Private Cloud (VPC) now allows customers to expand their VPCs by adding secondary IPv4 address ranges (CIDRs) to their VPCs.

除了中國與 GovCloud 以外都支援了:

There is no additional charge to use this feature. This feature is available in all AWS regions except GovCloud and AWS China (Beijing) regions.

這樣就不用另外開一個 VPC 再用 peering 的方式打通...

Redis 的 Secondary Indexing

Redis 官方說明 Secondary Indexing 的文件:「Secondary indexing with Redis」。

Secondary Indexing 算是 RDBMS 最底層基礎功能,如果有了這個功能已經可以做非常多事情... 查了文章裡提到的 Z* 系列指令是在 3.0.2 支援的 (目前是 3.0.4),看起來這個功能很新,不知道實際上跑起來跟 PostgreSQL 拼的效能如何... (因為 PostgreSQL 也可以自訂 Index 的內容)

Amazon DynamoDB 筆記

Amazon DynamoDB 頁面上的介紹:

Amazon DynamoDB is a fast and flexible NoSQL database service for all applications that need consistent, single-digit millisecond latency at any scale.

資料型態的部份就跳過去了,這篇筆記的重點在於 index 的部份 (了解他如何 scale),尤其是對 RDBMS 有了解的人要如何從他所設計的架構理解 DynamoDB 的 index。

理論基礎是 Amazon 在 2007 年丟出的論文「Dynamo: Amazon’s Highly Available Key-value Store」,這篇論文影響了很多 open source project。

DynamoDB 的 index 有 Primary Key、Local Secondary Index Key (LSI) 以及 Global Index Key (GSI),在「DynamoDB Data Model」這篇有介紹。

這邊會拿 Blogger.com 這種多人的 Blog Hosting 當例子:

  • 一個 user 可以有很多 blog。(table user)
  • 一個 blog 可以有很多 post。(table blog)
  • 一篇 post 可以有很多 comment。(table post)

接下來就從 Primary Key 開始講。

Primary Key

Primary Key 保證唯一,這也是 DynamoDB 裡面可以達到 RDBMS 的 UNIQUE KEY 效果的最佳方式。

有兩種 Primary Key 的型態,一種叫做 Hash,另外一種叫做 Hash-Range。

兩種都需要指定某一個欄位是 Hash-based column,當作切割 (partition) 的依據。

第一種:Hash

以 table user 來說,可以拿 user_id 來當作 Hash-based column,裡面有 blog_id 的 list。

以 table blog 來說,可以拿 blog_id 來當作 Hash-based column,裡面有 post_id 的 list。

要注意的是,如果表格 PK 是 Hash,那麼就不能使用 LSI 與 GSI 了。只有另外一種型態 (Hash-Range) 才可以用 LSI 與 GSI。

相對的,Hash-based 的表格因為功能有限,效率通常很好 XDDD

第二種:Hash-Range

其實 Hash-Range 是一種別的 LSI,兩者最大的差異就是唯一性了。

另外一種 Primary Key 是 Hash-Range,他需要指定兩個欄位,其中其中 Hash 的欄位就如同上面的解釋,當作資料切割的依據。這邊的唯一性是指 (Hash column, Range column) 唯一,而非只有 Hash 唯一或是 Range 唯一。

剛剛說到需要指定的另外一個欄位,被稱為「Range」的原因是因為他可以有效率的以 hash + range query 查詢資料。

以 table post 來說,可以拿 blog_id 當作 Hash-based column,再拿 post_id 當作 Range-based column,等下我們介紹 LSI 時再拿發表時間欄位排序。

同理,table comment 可以拿 (post_id, commend_id) 當 PK。

Query

PK 是 Hash 的當然就是指定 Hash-based column 直接查,條件只能是等號。

PK 是 Hash-Range 的除了可以用 Hash-based column 直接查 (還是只能用等號),另外可以用 Hash-based column + Range-based column 查。

以 SQL 的想法就像是 WHERE hash_col = 123 AND range_col BETWEEN (123, 456) 的感覺。反正 Hash-based column 一定要等號。

講到這邊,其實讀過上面提到的 Amazon 那篇論文應該就大概有感覺架構是怎麼搞的了:(這是推敲出來的,未必是實際架構)

  • 用 Hash-based column 切 consistent hash ring 塞到不同機器上。PK 是 Hash 的到這邊就搞定了。
  • PK 是 Hash-Range 的,還是照上面一條提到的,用 Hash-based column 切開,所以同樣的 Hash-based column 的資料都會塞到同一台機器上,於是就可以用有效率的 ordered tree 來存放 Range-based column 的資料,這樣就可以提供 query 了。

當然,考慮到需要實做 rebalance 機制以逐步擴充,這邊 consistent hash ring 的部份的作法可以更細膩,不過就不是這篇要談的重點了。

接下來要講重頭戲 LSI 與 GSI 了。

Local Secondary Index (LSI) 與 Global Secondary Index (GSI)

前面有提到 LSI 與 GSI 必須 PK 是 Hash-Range 的情況下能用,兩者都不強制唯一性。

LSI 與 GSI 都是 (Hash-column based, Range-column based) 的形式,差別在 LSI 的 Hash-column based column 必須跟 PK 的相同,GSI 的可以不用一樣。

所以對於 table post 可以加一個 LSI (blog_id, post_datetime),就可以用 WHERE blog_id = 123 ORDER BY post_datetime DESC 拉出對應的文章了。

同理,table comment 是 (post_id, comment_datetime)。

Archives