#187 - Điều ta không thể nghĩ trong lập trình

Sep 06, 2021

Những bài viết hay

Building a dynamic and responsive Pinterest — medium.com

Vào năm 2015, phần lớn content trên Pinterest được tạo sẵn bất đồng bộ cho người dùng trước khi đăng nhập, nhờ vậy giúp Pinterest phát triển lên 100 triệu người dùng hoạt động hằng tháng. Tuy vậy, kiến trúc này có nhiều điểm yếu lớn, và Pinterest muốn sản phẩm dynamic, responsive và realtime hơn. Điều này áp đặt các yêu cầu rất khắc khe cho hệ thống backend, đội ngũ đã xây dựng 9 hệ thống khác nhau, hỗ trợ Pinterest cho tới ngày nay. Mặc dù hệ thống này được xây dựng riêng cho Pinterest, chúng cũng giải quyết nhiều vấn đề thường gặp cho các ứng dụng khác chuyên phân phối content hướng tới người dùng cuối.

Các vấn đề gặp phải:

Mapping Owner-to-Board và Board-to-Pin cần lưu trữ và update real time, tuy nhiên giải pháp hiện tại bằng MySQL và HBase tốn quá lâu để query
Hệ thống xếp hạng bằng machine learning cần hiệu suất cao để xếp hạng hàng nghìn mảnh content trong 1 request với độ trễ P99 thấp cỡ vài chục ms
Cần hệ thống tạo candidate để cung cấp tập candidate chất lượng cao real-time cho phần Picked For You ( content recommendation)

Để giải quyết, đội ngũ Pinterest đã cấu trúc lại phần lớn kiến trúc hiện tại cho Following Feed, Interested Feed, Picked For You với nhiều giải pháp tối ưu như:

Áp dụng C++, FBThrift, Folly và RocksDB để đáp ứng được độ trễ thấp và vài hệ thống đẩy mạnh về CPU.
Tự xây dựng thư viện về data replication cho RocksDB tên là Rockspicator. Thự viện còn tích hợp routing có nhận biết AZ ( Availability Zone) và hỗ trợ nhiều routing patterns ( single shard, multiple shard fanout, all shard fanout), giúp giảm chi phí lưu lượng liên vùng AZ của AWS. Thư viện đó được được opensource trên Github
Giảm overhead cho khâu operation bằng cách tích hợp Apache Helix (một framework opensource của Linkedin để quản lý cluster), chi tiết xem ở đây.
Một bộ cluster service đếm (counting) phải trả về hàng chục nghìn counts cho 1 request với độ trễ P99 ít hơn 20ms. Để làm được, đội ngũ đã chuyển sang RocksDB và config nó thành đại khái 1 hash table trong memory. Ngoài ra còn đổi sang float16 để giảm kích thước data, và encode tay kết quả thành chuỗi byte, sử dùng multithread cho 1 request
Tập trung tối ưu nhiều Scorpion( service chấm điểm bằng ML) để tăng tỉ lệ CPU cache hit, giải quyết vấn đề thundering herds, sử dụng zero-copy cho LRU cache trong memory.

Bài viết gốc có nói chi tiết hơn về kiến trúc trước và sau của Pinterest, các phương pháp tối ưu và lí do đưa ra quyết định, mời các bạn tham khảo ở đây.

Thinking the unthinkable: What we cannot think in programming

Suy nghĩ của chúng ta được định hình bởi những giả định cố hữu, những thứ mà ít khi chúng ta nghi ngờ. Những giả định này tồn tại ở các quy mô khác nhau. Sự nhận thức của Foucault mô tả về những giả định cơ bản về một thời đại (ví dụ như thời phục hưng), mô hình nghiên cứu của Kuhn xác định cách các nhà khoa học tiếp cận các vấn đề và phương pháp nghiên cứu khoa học của Lakatos được coi là không thể chối cãi được bởi rất nhiều các nhà khoa học.

Trong bài viết này tác giả cố gắng khám phá một số những giả định được giấu kỹ trong lĩnh vực nghiên cứu về ngôn ngữ lập trình (programming language theory). Những giả định mà chúng ta không bao giờ nghi vấn và việc không nghi vấn đó đã ảnh hưởng như thế nào đến việc thiết kế ngôn ngữ lập trình? Và thế giớí lập trình của chúng ta có thể thay đổi như thế nào nếu chúng ta thách thức những giả định đó.

Functional Domain Modeling in Kotlin

Kotlin là một ngôn ngữ mới trên nền JVM, hiện đại nhưng ổn định được phát triển với mục tiêu giúp lập trình viên viết code ngắn gọn, an toàn và có khả năng tương tác tốt với Java và các ngôn ngữ khác. Kotlin tuy bắt đầu với JVM nhưng hiện nay Kotlin đã có thể compiled, chạy trên nhiều runtime platform khác nhau, ví dụ như Ios, javascript, đặc biệt là Android(Kotlin là ngôn ngữ chính thức trên nền tảng này). Tương tự các ngôn ngữ hiện đại khác Kotlin hỗ trợ nhiều phong cách lập trình như lập trình hướng đối tượng và lập trình hàm.

Bài viết sau đây là bài viết đầu tiên trong một chuỗi bài viết về domain modelling với Kotlin. Domain modelling là phương pháp sử dụng types để mô tả business logics, và từ đó sẽ tận dụng tối đa khả năng của compiler để ngăn ngừa lỗi cũng như giảm nhu cầu về unit tests. Trong bài viết này, tác giả sử dụng Kotlin với những khái niệm như: data class, sealed class, enum class, value class. Thêm vào đó Arrow - một thư viện về lập trình hàm - bổ sung thêm một số kiểu dữ liệu thú vị như: Either, Validated, Ior.

Tác giả bắt đầu với một ví dụ đơn giản, giải thích các nhược điểm của nó sau đó hướng dẫn người đọc cách tích hợp những công cụ có sẵn với Kotlin (và sau đó là Arrow) để giải quyết các nhược điểm đó. Với cách diễn giải dễ hiểu và thực tế, chúng ta có thể dễ dàng áp dụng các kỹ thuật được giới thiệu trong bài vào công việc hàng ngày, viết code an toàn hơn, ít lỗi hơn.

Góc Distributed System

Enabling Seamless Kafka Async Queuing with Consumer Proxy — eng.uber.com

Apache Kafka là một message queue được sử dụng nhiều trong các hệ thống phân tán lớn do các đặc điểm nổi bật: high availability / resilience / và hỗ trợ nhiều programming pattern.Ở phía consumer, để đạt được high throughput, chúng ta thường sử dụng consumer group - một khái niệm như worker pool: nhiều consumer cùng join vào một group để xử lí message trên cùng một topic. Tuy nhiên, do thiết kế của Kafka, một partition chỉ có thể xử lí bởi một và chỉ một consumer trong cùng một consumer group. Do vậy, một số bài toán phát sinh:

head-of-line blocking: khi có một message bị xử lí quá lâu, các message sau đó trên cùng partition sau đó buộc phải chờ với thời gian lớn. Ảnh hưởng này sẽ cộng gộp nếu toàn bộ message trong partition/topic đều cần thời gian lớn để xử lí.
partition number: tăng số partition là một cách để tăng throughput, và/hoặc xử lí bài toán phía trên. Tuy nhiên, con số này phải được configure lúc khởi tạo topic, và đồng thời có những giới hạn nhất định.

Với các thách thức như vậy, một chiến thuật là tìm cách xử lí song song các message trên cùng một partition. Từ đó, Uber giới thiệu một thiết kế - mà trung tâm là Consumer Proxy - thay thế vai trò consumer group trong việc điều hướng và xử lí message. Chúng ta có thể tham khảo kĩ hơn qua bài viết sau.

Góc Lập Trình

Đề ra tuần này:

Cho hai mảng số nguyên inorder và postorder lần lượt là inorder traversal và postorder traversal của một binary tree. Hãy xây dựng và trả về binary tree nói trên.

Ví dụ 1:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]

Output: [3,9,20,null,null,15,7]

Ví dụ 2:

Input: inorder = [-1], postorder = [-1]

Output: [-1]

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

Đề bài

https://leetcode.com/problems/merge-k-sorted-lists/

Lời giải

Đề bài yêu cầu gộp `k` linked-list đã được sắp xếp lại thành một linked-list, linked-list sau khi gộp cũng phải được sắp xếp. Có rất nhiều phương pháp để giải bài này, mình xin được giới thiệu 2 hướng tiếp cận sau đây:

1. Chọn lần lượt node có giá trị nhỏ nhất từ `k` linked-list

Ý tưởng của hướng tiếp cận này là ta lần lượt chọn node có giá trị nhỏ nhất từ `k` linked-list, thêm vào list kết quả, sau đó tăng con trỏ của node được chọn tới node tiếp theo.

Lặp lại bước trên cho tới khi tất cả các node đều đã được chọn.

Độ phức tạp của giải thuật time complexity là O(kN) với k là số lượng linked-list, N là tổng số node, bởi tại mỗi bước ta cần so sánh `k` node để chọn node có giá trị nhỏ nhất. Space complexity là O(1).Với thuật toán trên ta có thể tối ưu bước chọn phần tử nhỏ nhất bằng min heap có size là k. time complexity sẽ là O(logk * N), space complexity là O(k).2. Gộp từng cặp 2 linked-list cho tới khi có kết quả cuối cùng

Hướng tiếp cận này mượn ý tưởng của hàm gộp trong merge sort. Ta lần lượt gộp 2 cặp list lại thành 1, và lặp lại quá trình cho tới khi chỉ còn 1 list duy nhất. Thuật toán được thực hiện như sau:<TODO: paste link to code>Độ phức tạp của giải thuật trên có time complexity là O(logk * N), space complexity là O(N) cho mảng `tmp`.

Ta có thể tối ưu space complexity xuống O(1) bằng cách sử dụng mảng đầu vào `ListNode[] lists` để lưu trữ kết quả gộp tạm thời. Bạn đọc hãy thử tối ưu nhé.

Code & Tools

Glean - System for collecting, deriving and working with facts about source code.

This Week Sponsors

Database documentation tự động với dbdocs.io

[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

"I very frequently get the question: “What’s going to change in the next 10 years?” That’s a very interesting question.

I almost never get the question: “What’s not going to change in the next 10 years?” And I submit to you that that second question is actually the more important of the two.

You can build a business strategy around the things that are stable in time. In our retail business, we know that customers want low prices, and I know that’s going to be true 10 years from now. They want fast delivery; they want vast selection. It’s impossible to imagine a future 10 years from now where a customer comes up and says, “Jeff I love Amazon, I just wish the prices were a little higher.” Or, “I love Amazon, I just wish you’d deliver a little slower.” Impossible.

So we know the energy we put into these things today will still be paying off dividends for our customers 10 years from now. When you have something that you know is true, even over the long term, you can afford to put a lot of energy into it."

— Jeff Bezos