View profile

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

Grokking Vietnam
Grokking Vietnam
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
Góc Distributed System
DBMS Musings: It’s Time to Move on from Two Phase Commit
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)
Độ 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
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