#198 - Tìm hiểu về Parallel Commit trong CockroachDB

Nov 22, 2021

Trong số này, chúng ta sẽ cùng tìm hiểu về: Chặng đường các kỹ sư ở Meltwater chuyển hệ thống của họ sang Data Lake; Cách Spotify tối ưu hóa hệ thống data flow của họ; Cách các nhà nghiên cứu ở MIT dùng deep convolutional neural networks để chẩn đoán ung thư hắc tố da; Cách CockroachDB thiết kế Parallel Commit; Thử thách lập trình về đếm số nodes ở một complete binary tree; Tìm hiểu về một bảng mạch modem cổ điển đã được xây dựng cách đây 60 năm của IBM; và cuối cùng là sự kiện Grokking Techtalk #42 về cách thiết kế và hiện thực một platform phục vụ các bài toán về Machine learning.

Những bài viết hay

Our Journey from Database to Data Lake

Tại Melwater, họ cần theo dõi cách khách hàng của họ sử dụng nội dung mà họ cung cấp và đồng thời cung cấp những báo cáo để Sales team có thể hiểu về hành vi khách hàng. Điều này đòi hỏi phải thu thập và truy vấn hàng tỷ events sử dụng mỗi tháng. Bài báo nói về việc tác giả chia sẻ giải pháp kỹ thuật mà họ đã xây dựng và những gì họ đã học được khi xây dựng hệ thống lần thứ hai.

Mục tiêu: xây dựng một pipeline thống nhất để thu thập dữ liệu được sử dụng từ ứng dụng của họ và tạo báo cáo tự động theo định kỳ.

Giải pháp đầu tiên, một dịch vụ điều hướng và những database chuyên dụng: Họ xây dựng một dịch vụ điều hướng để nhận dữ liệu sử dụng từ ứng dụng Media Intelligence và định tuyến nó một cách có điều kiện đến một pipeline để xử lý sự kiện - mỗi pipeline sẽ chịu trách nhiệm cho 1 báo cáo. Mỗi pipeline sẽ bao gồm 1 API để nhận dữ liệu sử dụng, lọc dữ liệu theo yêu cầu của từng báo cáo đưa ra và lưu trữ dữ liệu đã được lọc vào 1 database chuyên dụng. Một AWS Lamda function được sử dụng để kích hoạt tạo báo cáo và tải báo cáo cuối cùng lên S3. Tuy vậy, số lượng nội dung được tích hợp tăng lên theo thời gian dẫn đến số lượng pipeline cũng vậy, chỉ khác nhau ở quy tắc lọc.

Xem xét lại cách thiết kế:

Xây dựng càng ít dịch vụ và càng ít mã càng tốt
Giảm sự trùng lặp về xử lý, dữ liệu và hạ tầng
Đảm bảo tính đàn hồi của pipeline
Giữ chi phí ở mức tối thiểu
Đảm bảo việc tạo các báo cáo mới dễ dàng

Giải pháp mới, xây dựng một Data Lake: Họ quyết định rút gọn toàn bộ xử lý của họ vào bốn bước đơn giản. Thu thập events, làm giàu chúng với tất cả thông tin được yêu cầu bởi tất cả các giải pháp báo cáo, lưu trữ chúng vào 1 kho dữ liệu duy nhất, và chỉ lọc các events ở một nơi duy nhất tại thời điểm truy vấn. Do nhu cầu thay đổi cấu trúc dữ liệu liên tục khi tích hợp các giải pháp mới hơn và họ nhận thấy rằng về cơ bản họ cần một data lake.

Apache Kafka for Data Collection: Sau khi cân nhắc họ quyết định chọn AWS Managed Streaming for Kafka (MSK) cung cấp một cụm Kafka được quản lý đầy đủ như một dịch vụ thay vì sử dụng AWS Kinesis and Apache Kafka.
Kafka Consumer/Producers for Enrichment: Để làm phong phú thêm dữ liệu sử dụng, họ đã xây dựng Kafka consumer and producer đơn giản với Kotlin & Spring sử dụng spring-kafka. Dịch vụ này sử dụng dữ liệu thô từ một topic và published dữ liệu đã được bổ sung chi tiết đến 1 topic khác từ đó nó sẽ được chuyển đến kho dữ liệu.
AWS S3 for Storage: Có vài yếu tố tại sao họ sử dụng S3 để lưu trữ: chi phí rẻ, hỗ trợ lưu trữ dữ liệu theo nhiều chính sách, không có nhu cầu cập nhật dữ liệu
AWS Athena for Querying: Athena cho phép bạn truy vấn dữ liệu trên S3. Bạn chỉ cần một lược đồ tại thời điểm truy vấn, có thể được tạo bằng AWS Glue. Nó được xây dựng dựa trên Presto - 1 engine truy vấn dữ liệu phân tán.

How Spotify Optimized the Largest Dataflow Job Ever for Wrapped 2020

Để tổng hợp được dữ liệu lớn trong một khoảng thời gian dài thì các công ty sẽ phải xây dựng những pipeline transforms rất lớn bao gồm những vấn đề về shuffle dữ liệu. Bên cạnh đó, các pipeline này sẽ chứa một loạt các phép tính rất phức tạp, điển hình là GroupByKey hoặc là Reduce. Những phép tính này thường là những nguyên nhân gây ra chi phí rất tốn kém trong quá trình hoạt động của pipeline. Ở Spotify, Sort Merge Bucket (SMB) là một phương pháp nhằm tối ưu hóa giúp tối ưu việc shuffle dữ liệu bằng cách thực hiện công việc này trực tiếp từ phía môi trường production. Các events của người dùng với metadata của người dùng dựa vào ID, có thể ghi chúng vào các bucket files với các records được phân loại và sắp xếp theo khóa đó. Bằng cách biết tệp nào chứa một tập hợp khóa con và theo thứ tự nào, shuffle sẽ trở thành vấn đề phân loại giá trị hợp nhất từ các tệp nhóm phù hợp, loại bỏ hoàn toàn network I/O và costly disk của việc di chuyển các cặp key–value.

Phần lớn các data pipeline tại Spotify được viết bằng Scio, một API Scala cho Apache Beam và chạy trên dịch vụ Google Cloud Dataflow. Việc các kỹ sư tại đây áp dụng SMB cho nhiều trường hợp sử dụng khác nhau, đã tiết kiệm chi phí rất lớn cho dự án Wrapped năm 2020 tại Spotify. Bằng cách tận dụng SMB, các kỹ sư ở đây đã quản lý để kết hợp gần như tổng cộng 1PB dữ liệu, ước tính chi phí Dataflow giảm khoảng 50% trong năm nay so với phương pháp dựa trên Bigtable của các năm trước.

An artificial intelligence tool that can help detect melanoma

Sử dụng mạng neuron tích chập các nhà nghiên cứu đã sáng chế ra một hệ thống giúp nhanh chóng chẩn đoán ung thư hắc tố da từ ảnh chụp da của bệnh nhân.

Ung thư hắc tố là một dạng u ác tính chiếm đến 70% ca tử vong liên quan tới ung thư da trên thế giới. Trong nhiều năm, các bác sĩ dựa vào việc kiểm tra bằng thị giác để nhận diện các tổn thương sắc tố đáng nghi (suspicious pigmented lesions (SPLs)), do nó là dấu hiệu của ung thư da. Việc nhận diện sớm trong điều kiện chăm sóc sức khỏe ban đầu (primary-care) như thế có thể cải thiện chẩn đoán ung thư và giảm đáng kể chi phí điều trị.

Tuy nhiên, nhanh chóng tìm và ưu tiên SPL là một việc làm khó khăn do một số lượng lớn các thương tổn cần được đánh giá để cân nhắc xem có cần lấy mẫu sinh thiết hay không. Để giải quyết vấn đề đó, các nhà nghiên cứu từ MIT và nhiều nơi khác đã sử dụng mạng neuron tích chập sâu và ứng dụng chúng để phân tích SPL qua việc chụp ảnh wide-field phổ biến ở hầu hết điện thoại thông minh và camera cá nhân.

Cách hoạt động sẽ là: Một bức ảnh wide-field, chụp từ camera của điện thoại thông minh, cho thấy các vùng da của bệnh nhân trong điều kiện Chăm sóc sức khỏe ban đầu. Một hệ thống tự động sẽ nhận diện, trích xuất và phân tích các thương tổn sắc tố da được quan sát từ bức ảnh đó. Một mạng neuron tích chập sâu được huấn luyện từ trước sẽ quyết định độ đáng nghi của từng thương tổn trên và đánh dấu chúng (vàng = cân nhắc kiểm tra thêm, đỏ = cần kiểm tra thêm hoặc chuyển tiếp cho các bác sĩ da liễu). Những đặc tính hậu trích xuất sẽ được sử dụng cho các đánh giá về sau và hiển thị kết quả dưới dạng bản đồ nhiệt (heatmap).

Mạng neuron trên được huấn luyện bằng 20388 bức ảnh wide-field từ 133 bệnh nhân ở bệnh viện Gregorio Marañón ở Madrid, cũng như các bức ảnh có sẵn ở chế độ công khai. Những bức ảnh này được chụp bằng nhiều camera thông thường và luôn sẵn có với người tiêu dùng. Bác sĩ da liễu và các nhà nghiên cứu đã phân loại một cách thị giác các thương tổn trong ảnh để so sánh. Họ phát hiện ra rằng hệ thống đạt được "sensitivity" hơn 90.3% trong việc phân biệt SPL với các thương tổn lành tính khác, từ da và từ ảnh nền phức tạp.

Góc Distributed System

Tìm hiểu về Parallel Commit trong CockroachDB

Trong cockroachDB, các transaction được parse thành chuỗi các request bao gồm hai operation cơ bản là read và write. Trước khi được commit vào hệ thống, transaction phải trải qua giai đoạn serialization và evaluation để CRDB kiểm tra nó với các transaction khác trong hệ thống nhằm đảm bảo tính conflict serializable giữa các transaction với nhau. Đây là một đặc điểm thiết kế quan trọng giúp CRDB đảm bảo được mức isolation SERIALIZABLE. Sau khi transaction được quyết định là có thể commit, việc commit thực sự vào hệ thống cũng là một bài toán khó trong môi trường phân tán. Có hai vấn đề chính trong bài toán commit mà CRDB gặp phải:

Sử dụng two-phase commit (2PC): mỗi request write trong transaction được gửi đến node leaseholder (node master chứa range dữ liệu mà request đó cần thực thi) với bản tin writeIntent thể hiện mong muốn write dữ liệu. WriteIntent sẽ được leaseholder replicate tới các node replicas theo thuật toán Raft để lấy đồng thuận về việc write này (prepare phase) Node coordinator sẽ phải đợi toàn bộ kết quả writeIntent trước khi thực hiện lệnh commit (commit phase). Vấn đề của 2PC là blocking. Coordinator sẽ phải đợi toàn bộ kết quả ở bước prepare trước khi thực hiện bước commit. Đồng thời, node coordinator trở thành single point of failure. Đây là vấn đề thứ hai.
Single point of failure: nếu node coordinator bị crash, client không thể biết được kết quả cuối cùng của txn, và hệ thống sẽ bị fragmented với những writeIntent dư thừa. Để giải quyết, CRDB kế thừa thiết kế của Google Spanner để tạo thêm 1 vòng đồng thuận giữa các node coordinator. Như vậy mỗi txn cần tới hai round đồng thuận, dẫn tới bất lợi là latency trong hệ thống tăng lên.

Dựa trên một số kết quả nghiên cứu (xem bài viết), CRDB đưa ra giải pháp là Parallel Commit để giải quyết hai vấn đề trên. Một số điểm khác biệt của Parallel Commit:

Nó chỉ cần 1 vòng đồng thuận để quyết định commit hoặc abort txn.
Giảm blocking ở 2PC bằng cách coordinator không cần đợi kết quả của toàn bộ writeIntent trước khi thực hiện lệnh COMMIT. Thay vào đó CRDB đưa ra trạng thái STAGING cho txn và distribute trạng thái này theo raft, biến nó thành một điều kiện cho việc commit/abort tnx.
Không có single point of failure vì WriteIntent, Tnx status đều được replicate theo Raft và việc có commit hay abort tnx được biến thành một quyết định dựa theo distributed commit condition.
Toàn bộ quá trình trao đổi thông tin diễn ra parallel.
tnx được coi là COMMITED (thông báo cho client) ngay khi thoả mãn hai điều kiện 1) txn state là STAGING và 2) có hết kết quả đồng thuận của các WriteIntent. Không cần phải đợi cho tới khi commit thực sự.

Chi tiết bài viết: https://www.cockroachlabs.com/blog/parallel-commits/

Góc Lập Trình

Đề tuần này: Count Complete Tree Nodes

Lời giải tuần trước:

Đề bài: Path With Minimum Effort

Lời giải

Đây là một bài toán trong chủ đề tìm đường đi ngắn nhất như đã đề cập ở số trước, tuy nhiên thật sự không dễ dàng để nhận ra. Nếu ta gọi "chỉ số cố gắng" (effort) để đi tới điểm có tọa độ (r, c) là E(r, c), và "chỉ số cố gắng" để đi tới tọa độ bên cạnh (rr, cc) là E(rr, cc), ta có:

E(rr, cc) = min( max(E(r, c) + abs(height[rr][cc] - height[r][c]) ), E(rr, cc) )

Trong đó, abs(height[rr][cc] - height[r][c]) là "chỉ số cố gắng" để đi từ tọa độ (r, c) tới tọa độ (rr, cc). Bạn đọc có thấy quen không?

Trong các giải thuật tìm đường đi ngắn nhất từ nguồn đơn (single source shortest path) trên đồ thị có trọng số, ta đều thấy công thức:

if (d[u] + weight(u, v) < d[v]) { d[v] = d[u] + weight(u, v) }

Xét 2 cạnh (u, v) với độ dài hiện tại từ gốc tới u, v lần lượt là d[u], d[v]. Nếu đi từ u tới v cho ta đường đi có độ dài ngắn hơn độ dài hiện tại, ta cập nhật độ dài d[v] = d[u] + weight(u, v).

Áp dụng vào bài toán trên: Xét 2 cell (r, c) và (rr, cc) với chỉ số nỗ lực là d[r][c] và d[rr][cc]. Nếu đi từ (r, c) tới (rr, cc) cho ta đường đi với "chỉ số nỗ lực" nhỏ hơn hiện tại, ta cập nhật "chỉ số nỗ lực" mới tại (rr, cc). Công thức này được gọi là "path relaxation".

Ta thực hiện giải thuật như sau: https://pastebin.com/PHsa6V1F

Ta lựa chọn sử dụng giải thuật Dijkstra bởi đồ thị luôn chứa cạnh dương: "chỉ số nỗ lực" là hiệu tuyệt đối giữa độ cao của 2 cell, vì vậy đồ thị Dijkstra cho ta time complexity tối ưu là O(E*logV) với E, V là tổng số đỉnh, cạnh.

Giải thuật Bellman-Ford cũng cho ta kết quả tương tự nhưng với time complexity là O(EV).

Có thể bạn chưa biết

Trong ảnh trên là một chiếc bo mạch IBM modem, thuộc nhóm HGB.

Vào cuối những năm 1950, IBM đã giới thiệu thẻ Hệ thống Mô-đun Tiêu chuẩn hóa (Standardized Modular System card), các bảng mạch nhỏ chứa một mạch đơn giản và sử dụng các bảng này để chế tạo máy tính và thiết bị ngoại vi vào giữa những năm 1960. Ý tưởng ở đây là thiết kế một số lượng nhỏ bo mạch tiêu chuẩn thực hiện các chức năng logic và các mạch điện cơ bản khác. Tuy nhiên, số lượng các bảng mạch đã tăng vọt ngoài tầm kiểm soát, với hàng nghìn loại thẻ SMS khác nhau.

This is a typical SMS card, implementing a triple AND gate.

Mời các bạn cùng đọc bài viết sau, để cùng tác giả phân tích về một bảng mạch modem cổ điển đã được xây dựng cách đây 60 năm. Những phát minh này, dù đã trở thành một phần của lịch sử nhưng vẫn luôn còn đó những điều thú vị mà ta có thể học hỏi.

Tech Talks

Grokking Techtalk #42: Engineering challenges on building data platform for ML Application

Đến với Techtalk #42, các bạn sẽ được chia sẻ về cách thiết kế và hiện thực một platform phục vụ các bài toán về Machine learning thông qua một case study về việc phân tích các bình luận của người dùng.

Nội dung chủ đề lần này sẽ xoay quanh một số thách thức trong quá trình xây dựng bao gồm các khó khăn về mặt kỹ thuật và phân tích khi:

Cần phải thu thập lượng lớn bình luận của người dùng.
Tổ chức lưu trữ và xử lý dữ liệu để dễ dàng mở rộng, thuận tiện cho việc giám sát, vận hành.
Thiết kế các thành phần trong hệ thống đảm báo tính tái sử dụng cao, tránh lãng phí tài nguyên.

Thông tin sự kiện:

Thời gian: 09:00 - 11:00 Thứ 7, 27/11/2021
Địa điểm: Online qua Zoom & Livestream trên Youtube Grokking Vietnam
Link đăng ký: https://forms.gle/UnJVfMG5ER5y5zrPA

Code & Tools

Góc 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

"Those who cannot learn from history are doomed to repeat it."

- George Santayana