View profile

#202 - Những điều học được ở vị trí Software Architect

Grokking Vietnam
Grokking Vietnam
Trong số này, chúng ta sẽ cùng tìm hiểu về:
  • Lý do tại sao CockroachDB sử dụng RocksDB
  • Những lý do tại sao Python được sử dụng rộng rãi ngày nay hơn so với Perl
  • Tìm hiểu về thuật toán đồng thuận Tendermint
  • Tìm hiểu về MinHash
  • Lời giải bài toán Maximal Square
  • Techtalk về cách tối ưu Spark 3.0 và Delta Lake

Những bài viết hay
Góc Distributed System
Tendermint thuộc dòng consensus Practical Byzantine Fault Tolerance (PBFT) hoạt động hiệu quả trong hệ thống tính tới lỗi Byzantine, được sử dụng phổ biến trong các mạng lưới blockchain. Đặc điểm của PBFT nói chung và Tendermint nói riêng là việc đồng thuận xảy ra dựa vào quá trình trao đổi các bản tin giữa các node được chia làm 3 phase chính: Propose - Vote - Commit. Điều kiện tiên quyết để đạt được đồng thuận là 2/3 tổng số node cùng đồng ý với giá trị đề xuất. Tendermint thực hiện việc đồng thuận theo từng vòng, ở mỗi vòng các node phải trải qua 3 giai đoạn kể trên. Ứng với mỗi giai đoạn, mỗi node sẽ phải đợi nhận đủ 2/3 số bản tin của giai đoạn đó hoặc là đạt thời gian timeout trước khi chuyển sang giai đoạn tiếp theo. Cũng như các thuật toán đồng thuận khác, các tính chất của Tendermint cũng bao gồm:
  • Agreement: không có hai correct node nào đồng thuận trên hai giá trị khác nhau tại cùng một bước đồng thuận.
  • Termination: toàn bộ correct node sẽ dần hội tụ về giá trị đồng thuận.
  • Validity: giá trị đồng thuận phải là một giá trị hợp lệ.
Để hiểu rõ hơn cơ chế hoạt động của Tendermint, mời bạn xem bài viết gốc: https://arxiv.org/pdf/1807.04938.pdf
Góc Database
Ở chuyên mục Góc Database kỳ trước, chúng ta đã được biết đến HyperLogLog, thuật toán giúp ước tính được số lượng phần tử duy nhất trong một tập hợp lên đến vài trăm triệu phần tử mà chỉ cần một lượng bộ nhớ rất nhỏ.
HyperLogLog có một đặc tính khá đặc biệt đó là có thể dùng để ước tính kết quả hợp (union) của hai tập hợp một cách dễ dàng. Ví dụ như bạn có hai tập hợp A và tập hợp B lần lượt được biểu diễn bởi hai bộ thanh ghi (registers) Ra và Rb được xây dựng dựa theo HyperLogLog, bằng cách kết hợp hai bộ thanh ghi Ra và Rb với nhau thành một bộ thanh ghi mới Rab, bạn có thể dùng để ước tính được A hợp B (A union B).
Tuy nhiên, để ước tính kết quả A giao B (A intersect B) thì HyperLogLog lại không phù hợp. Đến với góc Database kỳ này, mời bạn cùng tìm hiểu về kỹ thuật MinHash, một kỹ thuật giúp ước tính được “độ tương đồng” (similarity) của hai tập hợp. 
MinHash sẽ dựa trên một chỉ số gọi là chỉ số Jaccard (Jaccard index, hay còn gọi là Jaccard similarity coefficient). Chỉ số Jaccard của hai tập hợp A và B sẽ được tính như sau:
Theo định nghĩa này thì J(A,B) sẽ nằm trong khoảng từ 0 đến 1 (0<=J<=1). Khi hai tập A và B giống hoàn toàn với nhau thì J=1, còn khi hai tập A và B khác hoàn toàn nhau thì J=0.
Bằng cách chỉ lưu trữ k phần tử nhỏ nhất của hai tập hợp A và B, thuật toán MinHash sẽ giúp chúng ta tính được chỉ số Jaccard của hai tập hợp, từ đó sẽ ước tính được kích thước của phép giao giữa hai tập A và B.
Kết hợp HyperLogLog và MinHash, chúng ta sẽ có được một phương pháp đầy đủ hơn giúp ước tính được kích thước của các tập hợp cùng kết quả các phép toán hợp (union), giao (intersect) của hai tập hợp, từ đó có thể ứng dụng cho các bài toán như ước tính lưu lượng, ước tính tập hợp người dùng cho quảng cáo, …
Mời các bạn cùng xem clip này để hiểu thêm về MinHash.
Góc Lập Trình
Đề tuần này: Making A Large Island
Lời giải tuần trước:
Đề bài: Maximal Square
Lời giải
Đề bài yêu cầu tìm diện tích của ma trận vuông lớn nhất chỉ chứa số “1”. Cách đầu tiên ta có thể thử là tại mỗi ô “1”, ta mở rộng độ dài của của cạnh lên 1 đơn vị và kiểm tra xem ma trận vuông mới có chứa toàn số “1” hay không? Cách thực hiện có thể mô tả như sau:
1. Duyệt toàn bộ các ô, nếu ô chứa số “1”, ta thực hiện bước 2
2. Tăng độ dài của cạnh lên 1 đơn vị và tiến hành kiểm tra
 a. Nếu ma trận vuông mới chứa toàn số “1”, ta cập nhật diện tích lớn nhất và tiếp tục bước 2 để tìm kiếm ma trận vuông lớn hơn.
 b. Nếu ma trận vuông mới có chứa số “0”, ta di chuyển sang ô tiếp theo, lặp lại từ bước 1
Giải thuật trên có độ phức tạp time complexity là O(m^2 * n^2), với m, n là số dòng, cột của ma trận đầu vào.
Để tối ưu time complexity của bài toán này, trước hết ta cần một quan sát như sau:
  • Nếu ô [i][j] hiện tại chứa số “1”, ta có thể tạo được một ma trận vuông mới bằng cách thêm nó vào 3 ma trận vuông trước đó.
  • 3 ma trận vuông trước đó là các ma trận có cạnh dưới cùng bên trái (bottom right) lần lượt là: [i - 1][j], [i][j - 1], [i - 1][j - 1].
Để dễ hiểu, mời bạn đọc xem công thức sau:
Gọi L(i, j) là độ dài của ma trận vuông lớn nhất tại ô [i][j], L[i][j] được tính bằng:
L[i][j] = min{ L[i - 1][j], L[i][j - 1], L[i - 1][j - 1] } + 1
Với công thức đệ quy như trên ta có thể dễ dàng giải bài toán này theo quy hoạch động (Dynamic Programming) như sau: https://pastebin.com/LPGizKUd
Độ phức tạp time complexity, space complexity của giải thuật là O(m*n).
Ta hoàn toàn có thể tối ưu space complexity của giải thuật xuống O(m) (hoặc O(n)), mời bạn đọc thử thực hiện.
Tech Talks
Code & Tools
Góc Sponsors
One Mount là tập đoàn kiến tạo hệ sinh thái công nghệ lớn nhất Việt Nam, cung cấp các giải pháp và dịch vụ xuyên suốt chuỗi giá trị, từ lĩnh vực dịch vụ tài chính, phân phối, bất động sản và bán lẻ, với ba sản phẩm chủ lực: VinShop, VinID, OneHousing.
Với trụ sở tại Hà Nội, Hồ Chí Minh và quy tụ hơn 1.500 nhân sự xuất sắc, One Mount tâm huyết xây dựng môi trường làm việc:
  • Đề cao “Giá trị của công việc ý nghĩa”
  • Quy tụ nhân tài Việt trên toàn cầu
  • Văn hóa thành công cùng nhau vươn tới đỉnh cao
Các vị trí hấp dẫn đang mở tuyển: 
  • Back-end Engineer (Java/Golang), Front-end Engineer (ReactJS, Angular), Mobile Developer (iOS, Android)
  • Data Analysis, Data Engineer, Data Scientist
  • Business Analysis, QC Engineer
Tham khảo các thông tin về văn hóa, môi trường làm việc, cơ hội nghề nghiệp tại One Mount:
Quotes
When your hammer is C++, everything begins to look like a thumb.
— Steve Haflich
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

In order to unsubscribe, click here.
If you were forwarded this newsletter and you like it, you can subscribe here.
Created with Revue by Twitter.
Viet Nam