#182 - Hành trình của Uber hướng tới văn hóa dữ liệu tốt hơn

Aug 02, 2021

Bạn đọc thân mến,

HCM tiếp tục giãn cách thêm 2 tuần, tức là sẽ có thêm nhiều đồng bào của chúng ta rơi vào cảnh ngộ khó khăn, khốn cùng. Những sẻ chia dù là nhỏ cũng vô cùng cần thiết trong những lúc như thế này. Một hộp sữa có thể giúp một đứa bé khỏi phải uống nước gạo trong một vài ngày. Một kí rau, vài quả trứng sẽ giúp thêm một gia đình có thêm được một bữa no.

Ban biên tập Grokking hy vọng các bạn có điều kiện có thể đóng góp hỗ trợ cho các chương trình cộng đồng đã và đang diễn ra để góp phần hỗ trợ cho bà con bớt khổ hơn, cùng vượt qua đại dịch này.

Dưới đây là tổng hợp các chương trình cộng đồng hỗ trợ cho bà con nghèo ở HCM được LIN, một tổ chức uy tín chuyên kết nối và hỗ trợ các chương trình cộng đồng, đứng ra tổng hợp. Các bạn nào có nhu cầu đóng góp có thể tham khảo các chương trình ở đây.

Ngoài ra, các bạn cũng có thể tham khảo SOSMap, một bản đồ số giúp hiển thị thông tin những người đang cần hỗ trợ xung quanh mình. Cùng phát huy tinh thần tương thân tương ái cùng vượt qua đại dịch này các bạn nhé.

Chúc bạn đọc và gia đình luôn khoẻ mạnh và an toàn trong những ngày giãn cách sắp tới.

Thân,

Những bài viết hay

Time-series compression algorithms, explained — blog.timescale.com

Thời đại ngày nay, time-series data trở nên phổ biến, và vấn đề lớn của nó là khối lượng data lớn. Chúng ta insert data mới thay vì update mỗi khi data thay đổi, làm tập dữ liệu time-series data thường lên đến hàng terabyte hoặc hơn. Để duy trì hiệu năng cao và sử dụng hiệu quả resource, đội ngũ TimescaleDB đã tìm tòi và ứng dụng các thuật toán compression như Delta-of-delta encoding, Simple-8b, XOR-based compression, ... giúp tiết kiệm đến 90% chi phí lưu trữ và tăng tốc query.

Tác giả phân loại các thuật toán nén theo kiểu dữ liệu như sau:

Integer compression:

Delta encoding: thay vì lưu trữ một chuỗi các số, chỉ lưu chênh lệch giữa các con số đó kèm với 1 hoặc nhiều số tham chiếu. Thuật toán này này tận dụng việc hầu hết các time-series data không random mà là thay đổi từ từ theo thời gian. Nhờ vậy chúng ta có thể lượt bỏ phần lớn lượng dữ liệu dư thừa.
Delta-of-delta encoding: Giống delta encoding nhưng thêm 1 cấp độ nữa, áp dụng delta encoding lên tập dữ liệu đã được delta encoding.
Simple-8b: một trong những phương pháp đơn giản nhất lưu trữ chuỗi integer có độ dài thay đổi. Trong Simple-8b, tập hợp các số được lưu trữ dưới dạng một loạt các block có kích thước cố định (64-bit). Đối với 1 block integer như vậy, mỗi integer được biểu diễn với bit-length tối thiểu cần thiết để biểu diễn số integer lớn nhất trong cả block đó. Chúng ta chỉ cần lưu trữ bit-length 1 lần cho cả block, thay vì cho từng số trong block. Thêm nữa, vì block có size cố định, ta có thể suy ra số lượng integer trong mỗi block từ bit-length của block đó.
Run-length encoding: đối với tập dữ liệu nhiều giá trị lặp lại đứng cạnh nhau, chúng ta có thể lưu số lần lặp lại của giá trị kèm với bản thân giá trị đó, thành 1 pair.

Floating point compression:

XOR-based compression. Số float nói chung khó compress hơn số integer vì không có nhiều leading 0s và chỉ lưu giá trị gần đúng và phức tạp. Ví dụ: 93.9 được lưu thành 93.90000152587890625. Vì thế, nó khó có thể dùng delta encoding được. Thuật toán XOR-based compression cũng lưu sự khác nhau giữa các số giống delta encoding, nhưng dùng phép XOR thay vì phép trừ.

Data-agnostic compression:

Dictionary compression: thay vì lưu trực tiếp các giá trị, Dictionary compression tạo 1 tập các giá trị có thể xuất hiện và sau chỉ cần lưu index của giá trị đó.

Bài viết có miêu tả kĩ hơn các thuật toán compression cũng như cách chúng được kết hợp với nhau trong TimescaleDB, kèm với các kĩ thuật trong thực tế, mời các bạn tham khảo thêm.

Hit the Ground Running with Distributed Tracing Core Concepts

Chắc hẳn các bạn cũng không mấy gì xa lạ với các kiến trúc microservices phổ biến hiện nay. Một trong những vấn đề các hệ thống microservices thường gặp phải là một microservice sẽ ngày càng phụ thuộc nhiều microservices khác khi mà hệ thống của bạn cần phải mở rộng các chức năng. Do đó, việc debug và sửa lỗi sẽ trở nên khó hơn khi mà dependency graph của bạn ngày càng lớn và phức tạp hơn.

Distributed tracing là phương pháp thông dụng hiện nay để giải quyết vấn đề này. Các phần mềm distributed tracing nổi tiếng như là Zipkin, Jaeger, … sẽ giúp bạn truy tìm các nguyên nhân làm hệ thống bị lỗi hay xử lý chậm hơn. Bài viết sau đây được Nic Munroe, một principle engineer ở Nike, nói về cách họ đã áp dụng các ý tưởng cốt lõi của distributed tracing vào hệ thống của họ như thế nào. Đồng thời, bài viết cũng nói về một vài bài học họ đã rút ra trong quá trình tích hợp distributed tracing. Một vài ý chính của bài được đề cập như là:

Các khái niệm về Trace và Span được hiểu như thế nào trong mô hình hệ thống Dapper của Google? Mối quan hệ giữa Trace và Span là gì?
Cần nên làm gì khi xử lý incoming request?
Tuyên truyền dữ liệu về Trace và Span như thế nào cho các outbound calls?

Hành trình của Uber hướng tới văn hóa dữ liệu tốt hơn từ những nguyên tắc đầu tiên

Uber đã cách mạng hóa cách thế giới di chuyển qua việc tạo ra hàng tỷ chuyến đi và giao hàng bằng cách kết nối hàng triệu hành khách, doanh nghiệp, nhà hàng, tài xế và người giao hàng. Trung tâm của nền tảng vận tải khổng lồ này là Dữ liệu lớn (Big Data) và Khoa học dữ liệu (Data Science) để cung cấp năng lượng cho mọi thứ mà Uber thực hiện, chẳng hạn như là định giá và matching các chuyến đi tốt hơn, phát hiện gian lận, giảm ETA, hay thử nghiệm. Hàng petabyte dữ liệu được thu thập và xử lý mỗi ngày, giúp đưa ra các quyết định để xây dựng, cải thiện các sản phẩm này.

Mặc dù Uber có thể mở rộng quy mô hệ thống dữ liệu của mình, nhưng trước đây họ đã không tập trung đủ vào một số vấn đề dữ liệu quan trọng đặc biệt trên quy mô lớn. Một số vấn đề cụ thể nổi lên bao gồm: Data Duplication, Discovery Issues, Disconnected Tools, Logging Inconsistencies, Lack of Process, Lack of Ownership và SLAs. Những vấn đề này không phải chỉ có ở Uber. Chúng là những vấn đề phổ biến, đặc biệt đối với những công ty phát triển rất nhanh.

Không giống như các services luôn cố gắng ẩn dữ liệu và để lộ các giao diện hẹp bên ngoài các services, offline data trong data warehouse thường hiển thị dữ liệu từ các services và domain liên quan được phân tích cùng nhau. Một nhận thức quan trọng mà Uber có được là để làm tốt điều này, họ không chỉ nên giải quyết các công cụ cho dữ liệu, mà còn cả con người và các khía cạnh xử lý của dữ liệu. Vì vậy, Uber đã đưa ra một số nguyên tắc quan trọng về dữ liệu và được áp dụng xuyên suốt như: Data as code, Data is owned, Data quality is known, Accelerate data productivity, Organize for data. Qua đó, bằng việc xây dựng các công cụ, định hình các quy chuẩn, quy ước, ... Uber đã giải quyết được rất nhiều vấn đề quan trọng, giúp scale hệ thống data của mình tốt hơn.

Đây là một bài phân tích rất chi tiết cách mà Uber đã đặt ra các vấn đề họ gặp phải khi scale hệ thống data của họ. Từ đây Uber đã xây dựng ra các quy tắc, quy chuẩn và từ đó phát triển các công cụ, process để giúp họ giải quyết các vấn đề dữ liệu quan trọng và hoạch định cho việc phát triển trong tương lai.

Góc Distributed System

DBMS Musings: It’s Time to Move on from Two Phase Commit — dbmsmusings.blogspot.com

2PC - 2 phase commit, là một khái niệm ra đời từ lâu trong khoa học máy tính, được ứng dụng nhiều trong nhiều lĩnh vực khoa học máy tính như là: database; networking; … Trong lĩnh vực database, 2PC đảm bảo tính atomic cho một transaction . 2PC được biết, và sử dụng nhiều hơn trong hệ thống phân tán thông qua những database thuộc thế hệ NewSQL như Spanner; CockRoachDB; YugabyteDB …

Tuy nhiên, 2PC vẫn có những nhược điểm như độ trễ cao, scalability, availability, … Một lí do xuất phất từ một giả định căn bản: Để đảm bảo tính atomic, một transaction có thể phải abort tại bất cứ lúc nào; và cho bất cứ lí do gì. Bài viết sau đưa ra góc nhìn mới về 2PC - nhìn lại giả định trên ở lăng kính mới, và từ đó đưa ra hướng thiết kế một cơ sở dữ liệu vẫn đảm bảo được tính atomic, nhưng đồng thời có thể khắc phục được những nhược điểm của 2PC.

Góc Database

Compaction Strategy

Trong những kỳ newsletter trước, Góc Database đã từng đề cập đến Log-Structure Merge tree, còn gọi tắt là LSM, một trong những kỹ thuật đang được sử dụng phổ biến hiện nay cho các dòng database phân tán. Và khi nói đến LSM, Compaction Strategy là một từ khoá quan trọng không thể không tìm hiểu.

Hiểu một cách nôm na thì khi sử dụng LSM, dữ liệu được ghi vào hệ thống DB sẽ được giữ trên bộ nhớ. Khi dữ liệu ghi đủ nhiều, hệ thống sẽ flush dữ liệu xuống đĩa thành các file gọi là Sorted String Table (SSTable). Các file này là immutable. Đối với các lệnh update, hệ thống sẽ không cần kiểm tra xem dữ liệu có khoá tương ứng đã tồn tại trước đó hay chưa, mà cứ tiếp tục ghi ra những SSTable mới. Nói cách khác, cùng một dòng dữ liệu có thể được ghi ở nhiều file SSTable khác nhau tuỳ vào số lần update.

Cơ chế này giúp việc ghi nhanh hơn do không phải kiểm tra sự tồn tại của dữ liệu trước đó. Tuy nhiên, khi đọc thì hệ thống sẽ phải đọc tất cả các phiên bản của cùng một dòng dữ liệu ở các SSTable khác nhau và tổng hợp lại trước khi trả ra kết quả cuối cùng. Điều này khiến việc đọc trở nên chậm nếu dữ liệu được update nhiều lần.

Để giải quyết vấn đề này, định kỳ các file SSTable khác nhau sẽ được chọn và merge lại để bỏ bớt sự trùng lặp và dư thừa dữ liệu này. Quá trình này được gọi là Compaction.

Có nhiều chiến lược Compaction (Compaction Strategy). Các chiến lược khác nhau sẽ khác biệt ở thời điểm và cách lựa chọn các file SSTable nào là nên được merge lại.

Mời các bạn đọc thêm bài viết này của ScyllaDB team để hiểu thêm về khác biệt của các chiến lược Compaction này.

Góc Lập Trình

Đề ra kỳ này:

Cho một mảng các số nguyên nums trong đó mỗi số nguyên sẽ xuất hiện ba lần, ngoại trừ một số duy nhất. Hãy tìm ra số đó nguyên duy nhất đó.

1 <= nums.length <= 3 * 10^4
-2^31 <= nums[i] <= 2^31 - 1

Ví dụ:

Input: nums = [2,2,3,2]

Output: 3

Các bạn có thể làm thử tại đây.

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

Lời giải 1:

Bài toán yêu cầu trả về k số gần với x nhất, ta có thể nhận thấy, nếu ta sắp xếp mảng arr theo thứ tự: số gần với x nhất liền trước số gần với x nhì… Ta có thể chọn được k số gần x nhất.

Cách thực hiện thuật toán này khá đơn giản với custom comparator.

Giải thuật này có độ phức tạp thời gian là O(Nlog(N) + klog(k)) với N là độ dài của mảng arr. Bởi ta phải thực hiện thuật toán sắp xếp 2 lần.

Lời giải 2:

Nếu ta có thể tìm được số gần với x nhất trong mảng arr, ta có thể dễ dàng tìm được k phần tử gần với x nhất bằng cách thực hiện một sliding window. Để tìm số gần với x nhất, ta có thể thực hiện binary search (bởi mảng đã được sắp xếp tăng dần).

Độ phức tạp thời gian sẽ là O(logN + k).

Lời giải 3:

Ta cũng có thể thực hiện binary search bằng cách đi tìm cận trái của mảng kết quả. Ý tưởng của binary search là tại mỗi bước tìm kiếm, ta phải thu gọn không gian tìm kiếm. Với bài toán này, ta có thể thực hiện như sau:

- Chọn phần tử trung gian mid → giả sử mảng cần tìm là [arr(mid) ... arr(mid+k)]

- Nếu arr(mid) gần x hơn arr(mid+k), ta cần một số mid nhỏ hơn, vì vậy ta cần giảm không gian tìm kiếm về bên trái.

arr(mid) … x … … arr(mid+k)

- Nếu arr(mid+k) gần với x hơn, ta cần một số mid lớn hơn.

Độ phức tạp thời gian của giải thuật này là O(log(N-k) + k)

Các bạn có thể thử sức tại đây.

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

The best programs are the ones written when the programmer is supposed to be working on something else.

- Melinda Varian