View profile

#184 - Partitioned Consensus và Unified Consensus trong hệ thống phân tán

Grokking Vietnam
Grokking Vietnam
Những bài viết hay
Keeping Google Meet ahead of usage demand during COVID-19
Góc Distributed System
Qua các loạt bài trước, ta đã tìm hiểu về ý nghĩa của CAP theorem trong hệ thống cơ sở dữ liệu (CSDL) phân tán và dẫn đến khái niệm NewSQL - đại diện tiêu biểu là Google Spanner. Thiết kế của Google Spanner có các đặc điểm chính như sau:
  • 2PL (2-phase locking): đảm bảo tính serializability trên cùng một data shard.
  • 2PC (2-phase commit): đảm bảo tính atomic giữa các data shard.
  • TrueTime API: đảm bảo strict serializability.
  • Thuật toán đồng thuận (cụ thể là Paxos): đảm bảo đồng thời tính thứ tự của event và replicate data giữa các replication trên cùng một data shard.
Các loạt bài trước đã cho thấy ưu điểm, và đồng thời nhược điểm của giao thức 2PC và TrueTime API trong thiết kế hệ thống CSDL phân tán. Bài viết sau sẽ giải thích mảnh ghép cuối cùng - ứng dụng của thuật toán đồng thuận. Cụ thể, trong hệ thống phân tán, thuật toán đồng thuận có thể chia thành 2 dạng:
  • Partition consensus (ví dụ Google Spanner): mỗi data shard sẽ tham gia vào các quá trình đồng thuận độc lập nhau.
  • Unified consensus: toàn bộ thao tác trong hệ thống phải cùng tham gia vào cùng một quá trình đồng thuận.
Sử dụng partition consensus là suy nghĩ rất tự nhiên khi muốn thiết kế một hệ thống đảm bảo scalability. Tuy vậy, nhược điểm của việc sử dụng partition consensus là khó đồng thuận một thứ tự duy nhất các event giữa các node trong hệ thống. Do vậy, Google Spanner nói riêng, hoặc các hệ thống phái sinh từ Spanner nói chung, cần sử dụng 2PC và TrueTime API (hoặc biến thể), để đảm bảo strict serializability. Điều này, theo ý tác giả, dẫn đến những khó khăn trong việc thiết kế, và mở rộng hệ thống.
Từ nhận định trên, tác giả đưa ra thiết kế unified consensus: toàn bộ event đều sẽ được đưa vào một “global event queue”, nói cách khác, chạy trên cùng một thuật toán đồng thuận. Thứ tự toàn cục này có thể đóng vai trò thay thế đồng hồ thời gian trong việc diễn tả khái niệm trước/sau của các sự kiện. Qua đó, thiết kế có thể bỏ qua việc phụ thuộc vào 2PC và TrueTime API, với kết quả là có thể deploy trên các phần cứng thông thường (commodity hardware).
Ta có thể tham khảo kĩ hơn những nhận định trên qua bài viết sau.
Góc Engineering Manager
Đối với các bạn engineer bắt đầu chuyển sang vai trò manager, hẳn bạn sẽ ít nhiều bỡ ngỡ với một hoạt động đó là 1:1 meeting. Hiểu một cách nôm na thì 1-1 meeting là những buổi gặp gỡ định kỳ chỉ giữa quản lý và một thành viên nào đó trong team để thảo luận về các vấn đề liên quan đến công việc, career path, định hướng, … với từng thành viên.
Để xây dựng được các buổi đối thoại 1-1 thành công là không dễ. Nhiều khó khăn thường gặp phải như:
  • Gặp 1:1 rồi sẽ nói gì? Nếu chỉ là trao đổi về tasks sao ko trao đổi trong các buổi họp team?
  • Gặp 1:1 nên gặp thường hay ko? Ai nên là người lead cuộc nói chuyện?
  • Có nên có agenda cụ thể hay nên làm theo kiểu tự do, thích gì nói đó?
Để mở đầu cho chuyên mục Góc Engineering Manager. Kỳ này mời các bạn cùng tham khảo vài tips được chia sẻ dành cho quản lý ở Gitlab về cách tổ chức cuộc gặp 1:1 hiệu quả nhé. Đọc bài viết ở đây.
Góc Lập Trình
Đề ra kỳ này: Unique Paths III (harder follow-up của tuần trước)
Lời giải tuần trước:
Do robot chỉ có thể di chuyển từ trái qua phải, hoặc từ trên xuống dưới, ta có thể dễ dàng nhận thấy số đường đi từ điểm xuất phát tới ô (r, c) bằng tổng của số đường đi từ điểm xuất phát tới ô phía trên và ô bên trái.
uniquePaths(r, c) = uniquePahts(r - 1, c) + uniquePaths(r, c - 1)
Tuy nhiên ta không thể có đường đi nào qua ô chướng ngại vật, vì vậy khi gặp chướng ngại vật, số đường đi tới ô chướng ngại vật là 0.
Ta có thuật toán như sau: https://pastebin.com/CJtSdN5B
Code & Tools
This Week Sponsors
ENGINEERING RECRUITMENT FROM GRAB
Grab is Southeast Asia’s leading superapp, providing everyday services such as mobility, deliveries (food, packages, groceries), mobile payment and financial services to millions of Southeast Asians. At Grab, we believe that talent is the heart of the company. Therefore, we strive to create a wonderful working environment to optimize the potential of our Grabbers to achieve our common mission: drive Southeast Asia forward by creating economic empowerment for everyone.1
Why you will love working at Grab:
  • MacBook and 24-inches-monitor are provided.
  • Attractive salary and performance bonus.
  • Extra Medical Insurance from 1st joined date.
  • 14 days Annual leaves + 5 days of other leaves
  • GrabFlex allowance (up to 4.500.000 VND per month) for Family’s vacation, Education, Gym, Learning, etc…
  • GrabLove as vouchers for using Grab’s services.
  • Relocation opportunities to Regional or other countries.
  • Online Learning System & Offline Training courses are provided.
  • Opportunity to work, learn & grow with world-class professional engineers.
  • Opportunity to work for South East Asian Tech Decacorn.
  • Working day: Monday - Friday.
Join our Squad team today to drive Southeast Asia forward!
Check out our open positions at https://grab.careers/jobs/
Apply directly to ta.vn@grab.com as: Full Name_Applied position_Grokking
Quotes
I wish I could find a witty quote about column databases
— Guy Harrison, Next Generation Databases
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