#199 - Cơ chế kiểm soát tắc nghẽn trong giao thức TCP
Chào các bạn.
Trong số này, chúng tôi gửi tới các bạn các bài viết sau:
Cơ chế kiểm soát tắc nghẽn trong giao thức TCP.
Ứng dụng gRPC trong thực tế.
Thiết kế ELT tại Scentbird.
Raft trong RabbitMQ.
Columnar datastore lưu trữ data như thế nào.
Lời giải của bài toán Count Complete Tree Node.
Những bài viết hay
Cơ chế kiểm soát tắc nghẽn mạng (Congestion Control) của TCP được Van Jacobson đưa vào Internet vào cuối những năm 1980, khoảng tám năm sau khi giao thức TCP/IP đi vào hoạt động. Vào thời điểm trên, Internet đang chịu sự ảnh hưởng từ nhiều sự cố tắc nghẽn - thiết bị nguồn (máy chủ) liên tục gửi các gói tin vào Internet khiến tắc nghẽn sẽ xảy ra ở một số bộ định tuyến dẫn đến mất gói tin xảy ra.
Kiểm soát tắc nghẽn TCP là cơ chế để thiết bị nguồn xác định lưu lượng có thể truyền trong mạng. Nói một cách đơn giản, cơ chế này sử dụng sự xuất hiện của cờ ACK trong gói tin (mà thiết bị nguồn nhận được từ thiết bị đích) như một tín hiệu để chắc chắn rằng một trong các gói tin của nó đã được truyền thành công và do đó có thể gửi một gói tin mới vào mạng mà không làm tăng thêm mức tắc nghẽn. Tất nhiên, đây không phải là một công việc dễ dàng khi mà thực tế luôn luôn có rất nhiều kết nối được tạo ra/ngắt bỏ trong mạng, băng thông khả dụng của mạng liên tục thay đổi theo thời gian, có nghĩa là bất kỳ thiết bị nguồn nhất định nào cũng phải có khả năng điều chỉnh số lượng gói mà nó nên gửi đi.
Bài viết mô tả 3 thuật toán chính được TCP sử dụng để giải quyết vấn đề này bào gồm:
- Additive Increase/Multiplicative Decrease: tăng lượng gói tin gửi theo cấp số cộng và giảm theo cấp số nhân dựa vào một biến số thể hiện độ tắc nghẽn mạng Congestion Window.
- Slow Start: tăng lượng gói tin gửi theo cấp số nhân cho đến khi tìm thấy dung lượng mang tối đa của mạng.
- Fast Retransmit and Fast Recovery: thực hiện gửi lại gói tin sớm hơn thời gian timeout dựa vào tín hiệu ACK nhận được.
Ngoài ra hiện tại có khá nhiều biến thể của cơ chế kiểm soát tắc nghẽn TCP đang được các nhà nghiên cứu tiếp tục khám phá để giải quyết vấn đề này. Một cách tiếp cận mới cũng được nêu lên trong bài viết là TCP CUBIC.
Bài viết là một phần của cuốn sách về Mạng máy tính: Computer Networks: A Systems Approach. Mời bạn đọc bài viết gốc để hiểu hơn về cơ chế kiểm soát tắc nghẽn trong giao thức TCP/IP.
4 cách ứng dụng gRPC trong doanh nghiệp thực tế — www.redhat.com
gRPC là một công nghệ hấp dẫn được Google phát hành từ 2015,. Nó nhanh chóng, hiệu quả và bởi vì chạy trên HTTP/ 2, gRPC hỗ trợ cả giao tiếp request/response điển hình và giao tiếp streaming với thời gian dài. Nhiều công ty đang ứng dụng gRPC với nhiều cách thú vị bao gồm 4 ví dụ sau:
- Sử dụng gRPC cho Kubernetes CRI. Cụ thể là giao tiếp giữa kubelet và CRI trong nội bộ một worker node để quản lí container (xem hình) Trong thực tế, mỗi node có thể hỗ trợ hàng trăm tới hàng nghìn container, với mức độ hoạt động rất cao. Tất cả hoạt động này được điều phối bằng cách gửi và nhận tin nhắn qua gRPC. Dựa vào tính nhanh chóng và hiệu quả của gRPC ở giao tiếp quy mô lớn. Có thể nói Kubernetes không thể chạy mà thiếu gRPC.
- Đồng nhất nhiều ngôn ngữ lập trình khác nhau với Temporal. Temporal là một nền tảng mã nguồn mở cho phép các kĩ sư doanh nghiệp phục hồi và tiếp tục thực thi các tiến trình đang chạy trong trường hợp cơ sở hạ tầng bị fail. Theo CEO của Temporal, một kĩ sư có thể định nghĩa một tiến trình (Temporal activity) bằng PHP, trong khi một kĩ sư khác định nghĩa một activity bằng Go. Mỗi activity này gửi data của chúng tới một gRPC client sau đó forward cho một gRPC server, sau đó được gửi tới chung Temporal backend service, nơi thực sự thực hiện các activity. Nhờ gRPC, việc giao tiếp dữ liệu có thể được thực hiện bởi nhiều ngôn ngữ khác nhau (xem hình)
- Sử dụng gRPC streaming để thông báo vị trí xe cộ. gRPC hỗ trợ streaming hai chiều nhờ HTTP/2. Các kĩ sư iOS ở Lyft đã tận dụng điều này để thông báo vị trí của chiếc xe tới điện thoại của người đặt xe trong thời gian thật (xem hình)
- Sử dụng gRPC trong web client ở frontend thông qua proxy. Sử dụng gRPC trên Front-end trong browser là một việc rất khó. gRPC giao tiếp bằng dữ liệu binary đã được serialized, trong khi các web client trên browser thích dữ liệu dạng chữ hơn. Công ty Torq đã sử dụng giải pháp dùng một web proxy đứng giữa browser và gRPC server (xem hình)
Các ứng dụng của gRPC trong các doanh nghiệp lớn có thể dụng như một lộ trình hướng dẫn cho các kĩ sư muốn bắt đầu cho doanh nghiệp của mình. Bài viết gốc có mô tả chi tiết hơn các ứng dụng của gRPC, mời các bạn tham khảo.
Migrate from Redshift to Snowflake. Redesign ETL process. — medium.com
Tại Scentbird, họ đã quyết định chuyển đổi từ Redshift đến Snowflake và thiết kế lại việc xử lý ETL(Extract, transform, load).
Kiến trúc dữ liệu của họ vào đầu năm 2019
Sử dụng AWS Glue để xử lý ETL: chiết xuất dữ liệu từ Postgres(chỉ đọc) sau đó tải vào bộ nhớ của cụm Spark để xử lý và tải vào kho dữ liệu đích.
Sử dụng công cụ DBT để chuyển đổi dữ liệu nhưng họ phải sử dụng thêm AWS Glue để chuyển đổi JSON (bởi vì sự giới hạn về lưu trữ JSON của Redshift)
Tự xây dựng Analytics Portal nhưng sau khi dùng Looker (1 công cụ để phân tích và trực quan hoá dữ liệu) nó bao phủ hết tất cả nhu cầu kinh doanh.
Tuy nhiên, sau 1 thời gian họ gặp phải 1 số vấn đề trong kiến trúc dữ liệu do nhu cầu tăng trưởng về số lượng người dùng và khoảng dữ liệu thu thập
Redshift
Sức mạnh tính toán và không gian lưu trữ ràng buộc nhau: khi tạo 1 node Redshift, nó sẽ có 1 khoảng lưu trữ cố định và không có cơ hội để tăng sức mạnh tính toán và ngược lại. Để mở rộng thêm không gian lưu trữ, họ phải thêm 1 node khác hoặc tìm cách để chuyển dữ liệu của vào vùng lưu trữ cold của Amazon Spectrum. Nhu cầu tính toán của họ thì thấp hơn nhu cầu lưu trữ(30-40% so với trên 85%) vì thế họ tốn chi phí cho nhu cầu lưu trữ khá cao.
Mở rộng và nhân bản của cụm cố định thì khá chậm: khá mất thời gian để nhân bản dữ liệu từ môi trường product đến staging.
Khó để phát triển mô hình dữ liệu song song: vì hạn chế thứ nhất, họ khá khó khăn để tạo 1 bản sao từ dữ liêu. Việc tạo bảng sao phải thêm không gian lưu trữ và họ phải thêm 1 node.
Khả năng xử lý JSON quá tệ: Redshift thì không tốt trong việc xử lý JSON và họ sử dụng AWS Glue để giải quyết việc này.
AWS Glue
Glue là 1 công cụ giao diện. Tạo ra những mã dư thừa lặp lại trong mỗi công việc. Việc này khá là bình thường khi số lượng công việc ít. Nhưng với việc tăng về số lượng công việc > 60, họ đã tạo 1 đóng gói của Glue SDK để tối ưu mã và loại bỏ những mã dư thừa.
Khó để tích hợp với CI/CD: Để có thể tự động tạo 1 công việc mới từ mã, chỉnh sửa 1 thứ đã tồn tại, loại bỏ những thứ ít sử dụng hoặc cập nhật thư viện họ phải viết lại mã của họ qua AWS SDK. Một lần nữa họ lại sử dụng mã Python để đóng gói.
Khá khó để phát triển và tìm lỗi của công việc mới: Không có cách để tách biệt môi trường product và development trừ khi họ tạo thêm 1 thể hiện của AWS Glue để phát triển và trả tiền cho nó.
Thời gian khởi động khá lâu: Thời gian để cấp phát tài nguyên và khởi động cụm Spark khoảng 7 phút trên môi trường production. Tuy nhiên vào đầu năm 2021, AWS đã giới thiệu AWS Glue 2.0 với thời gian khởi động dưới 1 phút.
Choáng ngợp với sức mạnh tính toán của cụm Spark cho hoạt động chiết xuất và tải: Mỗi công việc AWS Glue có Spark chạy bên dưới để thực hiện những tính toán phức tạp. Tuy nhiên họ chỉ sử dụng nó để chuyển đổi JSON.
Khó khăn trong việc kết hợp những dữ liệu/sự kiện đến trễ: việc sử dụng AWS Glue để kết hợp dữ liệu khá tốn kém về mặt thời gian, chi phí, tiền bạc vì thế họ sử dụng DBT để kết hợp dữ liệu.
Glue không phù hợp cho luồng dữ liệu: giới hạn về mặt chức năng. Bạn phải tạo 1 ràng buộc để bắt đầu công việc B khi công việc A thành công. Việc chạy lại những công việc lỗi(từ 1 điểm, hay toàn bộ luồng dữ liệu) rất thủ công và khá khó khăn.
AWS Glue có thể thường không ổn định do vấn đề nội bộ của AWS: thỉnh thoảng họ phải nhận những công việc thất bại và họ được sự hỗ trợ từ nội bộ AWS nhưng họ được khuyên là chạy lại công việc hoặc thỉnh thoảng phải khởi động lại toàn bộ luồng dữ liệu điều này khá mất thời gian và làm chậm quá trình chuyển đổi dữ liệu cho người dùng.
Kiến trúc đầu năm 2021 (Scentbird Analytics 2.0)
Snowflake:
Cú pháp SQL thì giống hoàn toàn so với Redshift (90%).
Sức mạnh tính toán và lưu trữ hoàn toàn độc lập với nhau.
Các thể hiện tính toán có thể tự động tạm ngưng nếu không có yêu cầu nào đến.
Tự động mở rộng với zero downtime.
Không nhân bản bản sao của dữ liệu: chỉ cần bộ nhớ để lưu trữ “con trỏ” để tăng dần dữ liệu.
Có thể snapshot dữ liệu của 1 bảng tại bất kì thời điểm trong tối đa 90 ngày.
Có thể khôi phục thao tác drop (bảng, lược đồ).
Hỗ trợ JSON.
Snowflake có thể tích hợp với bất kì công cụ ngoài trừ AWS Glue.
Quá trình chạy thử nghiệm khá nhanh và dữ liệu được tạo ra nhanh hơn 4 lần với Snowflake’s instance Small(Redshift’s DC2.Large trong cùng giá)
Singer
Họ sử dụng Singer để ETL dữ liệu thay thế cho AWS Glue. Họ đã so sánh với AWS Glue về thời gian để xử lý với 3 bảng khác nhau về số dòng và họ nhận thấy rằng Singer có thời gian xử lý nhanh gần 2x so với AWS Glue.
Job orchestration. Argo PoC
Mỗi công việc trong luồng dữ liệu chạy trên những pod Kubernetes tách biệt, nó độc lập, tài nguyên hiệu quả và để dàng khởi động lại
mỗi công việc là 1 docker container, có thể đóng gói bất kì công nghệ vào bên trong
dễ dàng để xây dựng DAG bởi việc dùng những cấu hình
Luồng dữ liệu có thể được bắt đầu với crontab hoặc gọi API
Rất gọn và có UI nhanh
Mời các bạn đọc bài viết gốc để có thêm thông tin chi tiết
Góc Distributed System
Thực hiện Raft ở RabbitMQ
Quorum queue (QQ) là một kiểu hàng đợi của RabbitMQ triển khai FIFO queue dựa trên thuật toán đồng thuận Raft. QQ được giới thiệu từ RabbitMQ phiên bản 3.8.0.
Trước QQ, cách duy nhất để replica dữ liệu trong RabbitMQ là queue mirroring (QM).
QM hoạt động dựa trên cơ chế chain replication với nguyên tắc: Writer viết vào HEAD, sau đó được replicate đến node tiếp theo, cuối cùng đến đến TAIL của chain. Reader đọc từ TAIL. Ở RabbitMQ TAIL cũng chính là HEAD, chain lúc này là một hình tròn. Độc giả muốn biết rõ hơn về chain replication có thể đọc thêm ở bài báo
Chain Replication for Supporting High Throughput and Availability (Robbert van Renesse, Fred B. Schneider 2004).
QM hoạt động tốt trong hầu hết thời gian. Tuy nhiên QM yêu cầu thuật toán failure detection tốt để phát hiên không chỉ failure của master mà cả các node thành viên khác. Ở QM, việc thay đổi thành viên trong cluster khá đắt đỏ (yêu cầu queue sync). Đồng thời thuật toán bầu chọn master được chỉ định một cách không chính thức.
Các tác giả của RabbitMQ tìm kiếm sự thay thế tốt hơn cho QM. Có thể kể đến như Paxos, Viewstamped Replication (VR), và Raft. Với Paxos, các tác giả thấy có sự phân mảnh trong các implementation từ bài báo của Lamport. VR thì gần giống Raft; nhưng ngược lại với Paxos, VR có quá ít implementation và ít được sử dụng trong thực tế. Cuối cùng họ lựa chọn Raft, vì bài báo đưa ra hướng implement cụ thể, và được chứng minh trong các chương trình như etcd, Consul, CockroachDB.
Việc sử dụng thuật toán đồng thuận tuy vậy cũng phải đánh đổi một số yêu tố khác. Kể đến như (1) Raft yêu cầu một stable storage cho log và sử dụng fsync, điều này dẫn đến tăng độ trễ khi public một message vào queue. (2) Giảm availability vì quorum (tính quá bán). (3) Mỗi Raft chỉ có một leader. Việc tất cả operation đều qua leader này ảnh hưởng đến tính mở rộng của hệ thống.
Trong video, tác giả đề cập đến một số hướng giải quyết khi implement thư viện Raft cho RabbitMQ như:
1. Sử dụng một Raft cluster cho một queue. RabbitMQ có thể hỗ trợ rất nhiều, đến hàng ngàn queue, nên có thể có rất nhiều Raft cluster. Hệ quả là có thể có hàng ngàn fsync đồng thời. Raft là thuật toán khá ồn ào (khi idle, leader phải giữ liên lạc với các follower), nên sử dụng khá nhiều băng thông ngay cả khi hệ thống idle.
2. Chia xẻ write ahead log (WAL) giữa các Raft cluster. fsync từng cụm (batch)
3. Sử dụng storage engine giống LSM tree và append-oriented store
4. Dùng RabbitMQ heartbeat thay cho Raft heartbeat để giảm backgrond traffic.
Thông tin cụ thể hơn, mời độc giả xem video tại: https://www.youtube.com/watch?v=w-_1Wwymk58
Thư viện Raft viết bằng Erlang tại: https://github.com/rabbitmq/ra
Góc Database
Các bạn nào đã dùng qua các hệ thống OLAP (Online Analytical Processing) hẳn cũng sẽ nghe qua thuật ngữ columnar datastore, hoặc column-store.
Dành cho các bạn nào chưa biết thì Column-store là thuật ngữ chỉ các công nghệ lưu trữ dữ liệu theo cột, nhằm phân biệt với các công nghệ lưu trữ dữ liệu truyền thống theo hàng (row-store, row-based datastore). Ví dụ như chúng ta có một bảng dữ liệu học sinh như bên dưới:
Nếu lưu trữ theo dạng hàng thông thường thì dữ liệu sẽ được nhóm thành từng dòng ví dụ như:
Tuy nhiên nếu lưu trữ theo dạng cột thì dữ liệu sẽ được lưu dưới dạng như sau
(Lưu ý, các record có thể được lưu trữ trên cùng file hoặc khác file, thường đối với column-store thì mỗi column sẽ được lưu thành file riêng)
Cách lưu trữ theo cột này lợi gì? Hãy xét thử một câu query có dạng
Nếu lưu theo dạng cột thì rõ ràng việc thực thi câu query như trên sẽ dễ dàng hơn nhiều vì chỉ cần đọc 1 record thay vì phải đọc hết n record để lọc ra như cách lưu dạng hàng.
Rõ ràng, một trong các ưu điểm của việc lưu trữ dạng cột là tính hiệu quả về mặt I/O cho các câu query dạng analytics, vì các bộ xử lý truy vấn chỉ cần đọc ra các cột cần thiết để thực hiện thao tác tính toán thay vì phải đọc hết dữ liệu các cột không liên quan.
Tuy nhiên một câu hỏi đặt ra là, nếu chúng ta lưu trữ dạng hàng, nhưng đánh index tất cả các cột trong bảng thì sao? Liệu có đạt được hiệu quả tương tự như khi lưu trữ dạng cột hay không?
Để trả lời câu hỏi này, một nhóm tác giả đã làm một thử nghiệm nho nhỏ để so sánh performance của hai cách làm này và rút ra kết luận. Mời các bạn cùng đọc bài báo để xem kết luận rút ra là như thế nào nhé.
Góc Lập Trình
Đề tuần này: Product of Array Except Self
Lời giải tuần trước:
Đề bài: Count Complete Tree Nodes
Lời giải:
Chúng ta có thể bắt đầu với một giải pháp đệ quy tương đối cơ bản như sau:
return root == nullptr? 0 : 1 + countNodes(root->left) + countNodes(root->right);
Phương án này đòi hỏi độ phức tạp như sau:
Time complexity : O(N)
Space complexity: O(d) = O(logN) với d là độ sâu của cây (do ta sử dụng đệ quy).
Với đề ra là một "complete binary tree", có nghĩa là ở mỗi cấp (level) của cây sẽ đều được lấp đầy bởi các node, ngoại trừ cấp cuối cùng. Tức là ở kth-level, sẽ có 2^k node.
Như với ta có thể tính tổng số node trong cây, ngoại trừ cấp cuối cùng theo công thức (2^0 + 2^1 + 2^2 + ... + 2^(d-1)) = 2^d -1 , với d là độ sâu của cây.
Do đó ta có thể rút gọn bài toán về việc tìm số node ở cấp cuối cùng của cây.
Vậy làm thế nào để tìm số node này một cách hiệu quả nhất?
Do đây là một "complete binary tree", do đó các node ở cấp cuối cùng sẽ nằm từ bên trái qua phải. Do đó, ta không cần phải tìm toàn bộ các node, mà chỉ cần tìm node ngoài cùng bên phải của cấp cuối cùng, nên ta có thể sử dụng binary search. Vậy làm sao để kiểm tra một node ở vị trí idx có tồn tại hay không, với giả sử các node ở cấp cuối cùng được đánh số từ 0 đến 2^d -1. Ta lại sử dụng binary search thêm một lần nữa.
Ví dụ ta cần tìm node ở vị trí idx = 4, trong số các node được đánh số từ 0 -> 7. Vì 4 nằm ở nửa sau, nên ta có thể đi qua phải (từ node root). idx 4 lại nằm trong nửa trước của các node 4 -> 7 do đó ta đi tiếp qua trái. Từ đây, idx 4 nằm trong nửa trước của các node 4 và 5. Do đó ta đi tiếp qua trái. Time complexity cho thao tác này là O(d).
Tổng toàn bộ thời gian sẽ là cần là O(d^2) (Do có tối đa 2^d node ở cấp cuối cùng).
Ta có giải thuật như sau:
- Return 0 nếu cây rỗng
- Tính độ sâu d của cây
- Return 1 nếu d == 0
- Tổng số node của các tầng ngoại trừ tầng cuối cùng là 2^d-1
- Thực hiện binary search để tìm số node ở tầng cuối cùng
- Sử dụng function exist(idx, d, root) để kiểm tra node với index idx có tồn tại hay không.
- Trả về kết quả
Phương án này đòi hỏi độ phức tạp như sau:
Time Complexity: O(d^2)
Space Complexity: O(1)
Các bạn có thể tham khảo source code mẫu tại đây: https://pastebin.com/enJzj0SC
Code & Tools
Amundsen - A data discovery and metadata engine
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.
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
“You've baked a really lovely cake, but then you've used dog shit for frosting.”
Steve Jobs