#150 - (Re)Introducing Dropbox Edgestore

Dec 06, 2020

Những bài viết hay

Using Rust to Scale Elixir for 11 Million Concurrent Users | by Matt Nowack — blog.discord.com

Discord là một trong những công ty startups đầu tiên bắt đầu sử dụng Rust cho một số hệ thống quan trọng cần được tối ưu hóa càng nhiều càng tốt. Trong bài viết sau đây, Matt Nowack - một kỹ sư ở Discord - nói về cách họ đã sử dụng Rust như thế nào để xây dựng và tối ưu hóa SortedSet data structure. SortedSet được các kỹ sư ở Discord dùng cho việc cập nhật chức năng Member List (nằm ở góc phải của ứng dụng Discord khi bạn kết nối vào một Discord server) khi mà số người ở Member List có thể lên tới 11 triệu người.

Chức năng Member List được thành lập bằng ngôn ngữ Elixir. Sau khi nghiên cứu và thử nghiện nhiều data structures khác nhau như là SkipList, OrderedSet, và SortedSet, các kỹ sư ở Discord nhận ra rằng SortedSet đạt được tốc độ tốt nhất khi so sánh cả 3 data structures này trên Elixir. Tuy nhiên, việc ngôn ngữ Elixir mặc định dùng immutables cho data structures làm cho việc tối ưu hóa SortedSet trở nên phức tạp hơn. Do đó, khi các kỹ sư ở Discord đã quyết định sử dụng Rust cho công việc này. Kết quả thì họ đã cải thiện được tới gần 6.5 lần cho best case và 160 lần cho worst case khi so sánh với Elixir.

(Re)Introducing Edgestore — dropbox.tech

Cũng như các startups khác, nhiều hệ thống ở Dropbox được thiết lập trên nhiều MySQL clusters. Do đó, khi mà Dropbox cần phải mở rộng hệ thống và thiết lập nhiều đội ngũ kỹ sư riêng biệt, Dropbox gặp phải rắc rối khi thiết kế và quản lý các MySQL clusters của họ cho nhiều nhóm kỹ sư khác nhau. Tựa tựa như những công ty phần mềm khác, Dropbox dần dần nhận ra rằng họ cần phải có một hệ thống chung nằm trên MySQL để trừu tượng hóa cách lập dữ liệu và kết nối dữ liệu với nhau ở Dropbox.

Edgestore được thành lập ra để phục vụ mục đích trên. Nhờ vào Edgestore mà các teams ở Dropbox có thể xây dựng sản phẩm và dịch vụ của họ một cách hiệu quả hơn và không cần phải lo lắng quá về việc quản lý và thiết lập MySQL clusters cho mỗi dịch vụ. Edgestore có thể được hiểu như là một ORM system được thiết kế riêng cho Dropbox. Bài viết sau đây nói về cách Dropbox đã xây dựng hệ thống này như thế nào và những bài học họ đã rút ra trong quá trình xây dựng 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.

Link tham khảo: https://arxiv.org/abs/1608.06696

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ỳ đó.

Link bài báo: https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/sigrecord.pdf

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