View profile

#150 - (Re)Introducing Dropbox Edgestore

Revue
 
 

Grokking Newsletter

December 6 · Issue #151 · View online

Tuyển tập những bài viết hay cùng sự kiện bổ ích dành cho kĩ sư phần mềm tại Việt Nam.


Những bài viết hay
Using Rust to Scale Elixir for 11 Million Concurrent Users | by Matt Nowack Using Rust to Scale Elixir for 11 Million Concurrent Users | by Matt Nowack
 (Re)Introducing Edgestore (Re)Introducing Edgestore
Góc Distributed System
Trong các bài toán về đồng thuận, việc sử dụng thuộc tính quá bán (tổng số node > N/2) cho quorum là rất quan trọng: khi đó 2 quorum bất kì đều sẽ giao ít nhất là một node. Ví dụ thực tế là ZooKeeper; etcd cluster với 3 và 5 nodes sẽ đạt được đồng thuận nếu có ít nhất lần lượt 2 và 3 nodes hoạt động tốt.
Điểm qua cách chứng minh của Paxos / Multi-Paxos / Raft đều tận dụng tính chất quan trọng trên: giao giữa 2 phase Prepare và Propose (Paxos) hoặc leader election và log replication (Raft) đều phải giao nhau bởi ít nhất một node.
Paper về “Flexible Paxos” mở rộng khái niệm trên: nếu ta vẫn cố gắng để 2 phase giao nhau bởi tối thiểu một node, nhưng kích thước ở mỗi phase khác nhau, thì đồng thuận vẫn được đảm bảo. Cụ thể:
  • X là số node đồng ý gói tin Prepare(N)
  • Y là số node đồng ý gói tin Propose(N, V)
Nếu X + Y > N, với N là tổng số node trong hệ thống, thì đồng thuận vẫn đảm bảo.
Nhận xét này là cực kì hiệu quả trong vận hành. Cụ thể là khi Paxos mở rộng qua mô hình single leader, gói tin Prepare(N) đóng vai trò như leader election, Propose(N, V) đóng vai trò như log replication khi người dùng gửi request. Khi đó, số gói tin Prepare(N) nhỏ hơn rất nhiều với số gói tin Propose(N, V). Do vậy ta có thể tăng số node đồng thuận ở phase 1 và giảm số node đồng thuận ở phase 2 để giảm lưu lượng các gói tin gửi trong hệ thống.
Ví dụ với hệ thống có 10 node: số node đồng ý phase Prepare(N) tối thiểu là 8; số node đồng ý phase Propose(N, V) tối thiểu là 3 thì hệ thống vẫn an toàn và đạt được đồng thuận.
Đây là ví dụ minh họa trường hợp trên:
Paper cũng đã benchmark và đưa ra kết quả so sánh giữa vanilla Paxos và Fast Paxos với các cấu hình khác nhau của phase 2:
Kết quả cho thấy Fast Paxos khi số replicas giảm dần ở phase 2 thì latency giảm và throughput tăng, và luôn có hiệu năng cao hơn vanilla Paxos.
Ý tưởng này rất giống với Cassandra. Gọi R là số node đồng ý việc read và W là só node đồng ý việc ghi. nếu R+W > N thì hệ thống đạt được high consistency. từ đó engineer có thể tinh chỉnh 2 tham số R và W tùy thuộc vào nhu cầu và đặc tính hệ thống.
Góc Database
Trước khi bắt đầu vào bài báo, chúng ta cùng ôn lại ba khái niệm Read amplification, Write amplification và Space amplification đã từng đề cập ở paper “Designing Access Methods: The RUM Conjecture” trong số newsletter 146.
  • Read amplification là chỉ số ám chỉ tỉ lệ lượng dữ liệu dư thừa mà bạn phải đọc chỉ để lấy ra thông tin cần thiết. Ví dụ như bạn có một file có 500 dòng chứa thông tin học sinh của một khoa. Bạn muốn lấy thông tin của học sinh A ở dòng thứ 31. Tuy nhiên do hệ thống chỉ cho phép bạn đọc dữ liệu theo batch mỗi lần 30 dòng nên bạn phải tải hết dữ liệu từ dòng 31 đến dòng 60 lên bộ nhớ chỉ để lấy thông tin về dòng thứ 31. Trong ví dụ này, 29 dòng dữ liệu từ 32 đến 60 được xem là “read overhead”. Và tỉ lệ giữa phần read overhead này và phần dữ liệu hữu dụng được xem là read amplification.
  • Write amplification là chỉ số ám chỉ tỉ lệ lượng dữ liệu phải được cập nhật một cách không chủ đích chỉ để các dòng dữ liệu mà bạn muốn thay đổi. Tương tự ví dụ trên, bạn có thể hình dung nếu ta chỉ muốn cập nhật dữ liệu của dòng 31, tuy nhiên do giới hạn phần cứng buộc ta phải ghi 30 dòng một lúc thì 29 dòng dữ liệu được ghi kèm theo (mặc dù không có thay đổi gì) được xem là “write overhead”. Tương tự ở trên, tỉ lệ giữa write overhead và phần dữ liệu hữu dụng sẽ được xem là write amplification.
  • Space amplification là chỉ số ám chỉ tỉ lệ phần không gian lưu trữ phải tiêu tốn chỉ để lưu trữ các dữ liệu dư thừa đi kèm phần dữ liệu chính muốn xử lý. Trong ví dụ trên, phần bộ nhớ dùng để lưu trữ 29 dòng dữ liệu kèm theo được xem là “space overhead”. Và tương ứng là space amplification.
Trong nội dung bài báo xuất bản năm 2014 này, tác giả Bradley (Chief Architect ở Tokutek) đưa ra những so sánh về mặt hiệu năng giữa Fractal index (một cấu trúc dữ liệu được cải tiến trên nền tảng B-tree) và Log-structured Merge Tree dựa trên 3 chỉ số quan trọng trên.
Nhắc lại về Btree thì một trong những điểm yếu của Btree đó chính là write amplification (hay write overhead) khá cao. Mặc dù Btree đã được thiết kế trên tinh thần một node có kích thước vừa với block size của đĩa, nhờ vậy việc cập nhật nội dung của Btree xuống đĩa sẽ hiệu quả do mỗi lần ghi là cả một block. Tuy nhiên, đặc điểm này trở thành yếu điểm của Btree trong những tình huống phải thực hiện random-insert với tần suất cao dẫn đến phải cập nhật cây index nhiều lần.
Ví dụ như trong một database sử dụng Btree, có kích thước một node là 16KB. Với một ổ đĩa thông thường có seek time tầm 5ms và băng thông 100MB/s thì việc cập nhật một node đơn lẻ sẽ tốn 5.16ms (5ms seek time và 0.16ms truyền tải). Phần băng thông còn lại bị lãng phí.
Một trong những cách tiếp cận phổ biến để thay thế là Log Structure Merge Tree (LSM) vốn cũng đang được sử dụng rộng rãi. Với Log Structure Merge Tree, mỗi lần ghi sẽ là một lượng lớn dữ liệu đã được sắp xếp sẵn (sorted runs of data), nhờ vậy sẽ tận dụng được băng thông tốt hơn. Tuy nhiên LSM lại có nhược điểm là read amplification cao.
Trong bài báo này tác giả sẽ giới thiệu về Fractal Tree, một cấu trúc dữ liệu được xây dựng trên ý tưởng mỗi node của Btree có thể có một phần buffer riêng để lưu dữ liệu được insert, và trì hoãn việc ghi dữ liệu xuống đĩa cũng như điều chỉnh cấu trúc cây đến khi lượng dữ liệu trong buffer đủ lớn (ví dụ như bên dưới)
Theo những phân tích của tác giả thì Fractal tree tỏ ra khá hiệu quả khi so sánh với LSM và BTree (hay BTree+) truyền thống trong 3 khía cạnh write amplification, read amplification, space amplification.
Mời các bạn cùng đọc bài báo để hiểu thêm. Link bài báo.
Góc Data Warehouse
Data warehouse và Online analytical processing (OLAP) là các thuật ngữ phổ biến hiện nay nói về các hệ thống được thành lập chuyên để giúp các công ty chứa, xử lý, và phân tích dữ liệu của họ cho việc đưa ra những quyết định và hướng đi cho doanh nghiệp dựa trên dữ liệu mà doanh nghiệp lưu trữ được. Đa phần, các hệ thống này thường được thiết kế để chứa một lượng dữ liệu đáng kể và hơn vài magnitudes so với các OLTP database systems (có thể lên tới petabytes hoặc exabytes nếu công ty bạn có tầm phủ sóng như Google và Facebook).
Mặc dù các hệ thống này đã được thành lập và sử dụng khá là lâu và rộng rãi, cách thiết kế các hệ thống này và schema cho dữ liệu ở data warehouse đa phần đều giống như cách bài báo này trình bày ở ACM SIGMOD vào năm 1997. Cách nhìn tổng quát về data warehouse và schema cho dữ liệu có thể được tóm tắt qua 2 biểu đồ sau đây:
Biểu đồ 1 đưa ra cái nhìn tổng quát về hệ thống data warehouse khi mà dữ liệu ở các OLTP database systems sẽ được đi qua ETL processing trước khi tiếp nhận vào data warehouse nơi mà dữ liệu được phân bố rộng rãi ở nhiều nodes. Người dùng có thể truy vấn dữ liệu qua các ứng dụng UI để hiểu rõ hơn về dữ liệu. Đồng thời, các admin có thể quản lý và giám sát data warehouse hoạt động như thế nào.
Biểu đồ 2 đưa ra 1 ví dụ về cách dữ liệu được trình bày như thế nào ở data warehouse. Đa phần dữ liệu sẽ được chuyển đổi về multidimensional data model để việc phân tích dữ liệu dễ dàng hơn.
Tuy bài báo này đã được phát hành khá là lâu, nhưng bài báo được viết khá là súc tích về việc hệ thống data warehouse được thành lập như thế nào và lý do tại sao data warehouse được thành lập theo kiểu như trên vào thời kỳ đó.
Code & Tools
This Week Sponsors
Established in 2012, Chotot.com is the leading online classified website in Vietnam with more than 1,2 billion monthly page views, 10 million monthly users, 3,6 million transactions in 2019. With the motto “Muốn Là Có” (“A Way to Your Wants”), Chotot.com provides an effective online marketplace for Vietnamese to buy and sell various types of products easily. For more information, please visit www.chotot.com.
Góc tuyển dụng
Cho Tot creates products using a variety of open source and cloud native technologies, to name some: Kubernetes, Kafka, Elastic Search, PostgreSQL, MongoDB, TimescaleDB. We utilize Google Cloud Platform services such as Google Kubernetes, AI Platform, Cloud Composer, Data Catalog, BigQuery, Google Analytics for our infrastructure needs while running our heavy workloads on our own on-premises infrastructure. Visit careers.chotot.com to learn more about our vacancies and company culture.
Quotes
Without requirements or design, programming is the art of adding bugs to an empty text file.
- Louis Srygley
Did you enjoy this issue?
If you don't want these updates anymore, please unsubscribe here.
If you were forwarded this newsletter and you like it, you can subscribe here.
Powered by Revue
Charmington La Pointe, 181 Cao Thang, Dist 10, Ho Chi Minh city, Viet Nam