View profile

#186 - Ứng dụng của RocksDB vào hệ thống Manhattan của Twitter

Grokking Vietnam
Grokking Vietnam
Grokking Newsletter là newsletter hàng tuần của Grokking cho các bạn software engineers người Việt. Tuần này: so sánh các engine K8S, sử dụng RocksDB, lịch sử các web browsers, công cụ xây dựng database document, và nhiều thông tin hay khác.

Những bài viết hay
Góc Distributed System
Tìm hiểu về Hybrid Logical Clock
Vấn đề đồng bộ thời gian trong các hệ thống phân tán thường được xử lý thông qua hai phương án: sử dụng đồng hồ vật lý đắt tiền (vd: atomic clock) giúp hạn chế tối đa tính sai khác thời gian giữa các server (clock skew), có thể thấy ví dụ trong Google Spanner với hệ thống TrueTime; hoặc sử dụng logical clock (vd: lamport clock, vector clock) để thể hiện thứ tự xảy ra của các events (1 số nguyên hoặc 1 vector) trong hệ thống với điều kiện: event a xảy ra trước event b thì C(a) < C(b) với C là đại lượng biểu diễn logical clock. Nếu không có sự hỗ trợ của đồng hồ vật lý đắt tiền, các hệ thống sử dụng Logical clock sẽ gặp phải 1 hạn chế là: client không biết được thời gian date-time cụ thể khi một event xảy ra.
Hybrid Logical Clock là giải pháp bổ sung cho vấn đề này. HLC cũng cung cấp đơn vị thời gian tăng dần như logical clock, nhưng có mối quan hệ mật thiết với thời gian vật lý (actual date-time). HLC được sử dụng rộng rãi trong các hệ thống distributed database, ví dụ có MongoDB, CockroachDB, YugabyteDB.
Nguồn: https://medium.com/geekculture/all-things-clock-time-and-order-in-distributed-systems-hybrid-logical-clock-in-depth-7c645eb03682
Nguồn: https://medium.com/geekculture/all-things-clock-time-and-order-in-distributed-systems-hybrid-logical-clock-in-depth-7c645eb03682
HLC thường được implement là một đối tượng có hai giá trị:
  • system time: thời gian vật lý trên local server.
  • counter (hoặc tick): số nguyên, tăng dần.
Một số thao tác cơ bản với HLC:
  • Khởi tạo: Khi khởi tạo giá trị cho 1 đối tượng HLC, counter thường được set là -1.
  • So sánh: khi so sánh this.HLC với other.HLC, thứ tự so sánh sẽ là: 1) so sánh system time trước, 2) nếu system time bằng nhau, so sánh counter.
  • cập nhật HLC: bao gồm cập nhật giá trị system time, và cập nhật counter (tăng lên). Khi HLC được reset thì counter lại về -1.
Cũng như Logical clock, mỗi server trong hệ thống sẽ khởi tạo và duy trì 1 đối tượng HLC của nó, gắn HLC vào event (đánh timestamp) gửi đi và cập nhật HLC khi nhận events từ server khác. Cũng như Vector clock, HLC có thể được đánh version và thường được lưu vào backend K-V store. Cách implement thì tuỳ vào từng software cụ thể.
HLC có thể được convert sang thời gian thực date-time, bạn tham khảo theo hướng dẫn trong paper gốc [1].
HLC được dùng trong các hệ thống distributed database như mongo, cockroachdb để xác định timestamp cho transaction khi nó được commit. Cách thiết kế và implement được giới thiệu trong bài viết.
Tài liệu tham khảo:
Góc Engineering Manager
Một trong những trách nhiệm mà Engineering Manager phải đối mặt đó là phỏng vấn tuyển dụng. Có nhiều kỹ thuật hoặc cách đặt câu hỏi có thể được, trong mục Góc EM tuần này, mời các bạn cùng tham khảo phương pháp phỏng vấn STAR.
Phương pháp này chú trọng việc đặt câu hỏi phỏng vấn thông qua khảo sát các tình huống cụ thể bằng cấu trúc:
  • Situation: yêu cầu ứng viên mô tả một tình huống cụ thể mà ứng viên phải đối mặt trong quá khứ. Hoặc người phỏng vấn cũng có thể nêu ra một tình huống giả định trong đó người phỏng vấn muốn khảo sát phương án xử lý của ứng viên. Đối với engineer, các tình huống này có thể là: một sự cố xảy ra lúc nửa đêm, hệ thống đột nhiên trả về toàn lỗi, database CPU tăng quá cao một cách bất chợt, sếp yêu cầu thay đổi kiến trúc trong một khoảng thời gian ngắn.
  • Task: Mô tả về mục tiêu đi kèm với tình huống đó. Ví dụ như khi tình huống đó xảy ra thì ứng viên phải ngay lập tức kiểm soát sự cố, hoặc phải đưa ra bản thiết kế mới, …
  • Action: Yêu cầu ứng viên mô tả những hành động cụ thể mà chính ứng viên đã làm (hoặc sẽ làm nếu đây là một tình huống giả định)
  • Results: Yêu cầu ứng viên mô tả kết quả của những hành động của mình. Cũng như những kinh nghiệm rút ra.
Phương pháp này không chỉ dùng để đánh giá hành vi (behavior) mà còn có thể dùng để đánh giá kinh nghiệm xử lý sự cố, kinh nghiệm điều chỉnh kiến trúc, … đặc biệt hữu dụng để phỏng vấn vai trò senior, lead trở lên.
Góc Lập Trình
Đề ra tuần này:
Bạn được cho trước một mảng  k linked-lists lists, mỗi linked-list đều đã được sắp xếp theo thứ tự tăng dần.
Nhiệm vụ của bạn là merge tất cả các linked-list đó lại vào một linked-list duy nhất.
Lời giải tuần trước:
Bài toán yêu cầu tìm hoán vị thứ k trong chuỗi hoán vị của tập hợp [1, 2, 3, ..., n], nên cách đầu tiên ta có thể thử là sinh toàn bộ hoán vị của tập hợp và chọn hoán vị thứ k tương ứng. Tập hợp [1, 2, 3, ..., n] sẽ có n! (n giai thừa), vì vậy ta cũng có Time Complextiy và Space Complexity tương ứng là O(n!)
Để tối ưu cho giải thuật trên, ta có phân tích như sau:
Nếu ta cố định số thứ 1 ta có thể sinh được (n-1)! hoán vị, nếu ta tiếp tục cố định số thử 2 ta có (n-2) hoán vị. Ví dụ: với tập hợp [1, 2, 3], số hoán vị là 6, nếu ta cố định 1 là số thứ nhất, ta sinh được 2 hoán vị là: 123 132.
Như vậy, ta có thể xác định được vị trí của hoán vị cần tìm trong chuỗi hoán vị. Thuật toán được thực hiện như sau đây.
Có thể bạn chưa biết
Chúng ta sẽ cùng điểm lại một vài sự kiện lịch sử liên quan tới Internet và các trình duyệt.
Vào tháng 1 năm 1993, Marc Andreesen (người sáng lập a16z) đã viết Mosaic, một trong số các trình duyệt web đầu tiên đóng vai trò quan trọng trong việc phổ biến WWW. Tuy nhiên bản quyền lại thuôc về Trung tâm Ứng dụng siêu máy tính quốc gia (NCSA) tại Đại học Illinois tại Urbana, vì thời điểm này, anh ta đang thực tập tại đây!
Sau đó, vào tháng 4 năm 1994, Marc đã bắt đầu Netscape, viết những dòng code đầu tiên, và rất nhanh chóng phát triển công ty lên tới hơn 1000 nhân viên. Năm 1995, từ quý 1 tới quý 4, doanh thu của công ty đã tăng từ 5 triệu $ lên 40 triệu $, và lên tới 100 triệu $ vào năm 1996.
Chứng kiến sự trỗi dậy của Netscape, Bill Gates đã viết vào cuốn sổ tay của mình dòng chữ “The Internet Wave Tidal”, và đẩy Internet lên vị trí ưu tiên hàng đầu của Microsoft, khi đó là tháng 5 năm 1995.
Chỉ 3 tháng sau đó, Microsoft đã tung ra Internet Explorer, tích hợp miễn phí vào hệ điều hành Windows 95. Điều này đã dẫn tới việc Netscape mất dần thị trường vào tay Internet Explorer, và sau đó đã phải bán cho AOL.
Thực tế dự án IE đã bắt đầu từ 1994, và vào cuối năm 1994, Microsoft đã thương lượng được với Spyglass trong việc nắm bản quyền source code của Spyglass Mosaic, phiên bản thương mại của NCSA Mosaic (được viết bởi… Marc Andreesen). Và IE đã được phát triển trên chính nền tảng Spyglass Mosaic!
Nói cách khác, Marc Andreesen đã phát triển Mosaic, trình duyệt web đầu tiên phổ biến trên internet, Netscape trình duyệt thương mại thành công đầu tiên, và sau đó IE - trình duyệt được xây dựng trên nền tảng Mosaic - đã khai tử Netscape!
Nguồn: LinkedIn
Các bạn có thể nghe thêm podcast sau để nghe Marc Andreesen chia sẻ câu chuyện về Netscape.
Code & Tools
Database documentation tự động với dbdocs.io
Giao diện dbdocs
Giao diện dbdocs
[Nội dung tài trợ] dbdocs.io là một công cụ giúp các bạn Dev có thể tự sinh ra nguyên trang document về cấu trúc database của mình chỉ bằng vài dòng lệnh command-line. Nó giúp quá trình planning và design database trong team dev dễ dàng hơn.
Hiện team dbdocs (ở TPHCM) đang tìm thêm 2 bạn fullstack/backend engineers để tham gia phát triển sản phẩm dev tool này. Bạn nào quan tâm có thể xem thêm tại: https://careers.holistics.io/job-openings/open-source-full-stack-engineer
(Team dbdocs cũng là team xây dựng công cụ dbdiagram.io phổ biến mà nhiều bạn dev đang dùng.)
Quotes
A distributed system is one in which the failure of a computer you didn’t even know existed can render your own computer unusable.
— Leslie Lamport
Did you enjoy this issue? Yes No
Grokking Vietnam
Grokking Vietnam

Cảm ơn bạn đã dành thời gian đọc newsletter kỳ này và chúng tôi hi vọng rằng bạn đã khám phá ra một số điều mới mẻ từ các bài viết trên. Các bạn có thể đọc lại các số cũ tại website newsletter.grokking.org

Ngoài ra các bạn có thể gửi feedback cho Grokking Newsletter team ở https://bit.ly/3k3Jdw5 hoặc đóng góp bài viết tại https://bit.ly/2XaBUtF

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.
Created with Revue by Twitter.
Charmington La Pointe, 181 Cao Thang, Dist 10, Ho Chi Minh city, Viet Nam