Bắt đầu với kỹ thuật sharding trong database

Một trong các bottleneck của hệ thống thường xảy ra ở lớp database. Bạn phát hiện ra hệ thống của mình cũng rơi vào trường hợp tương tụ như vậy, việc đọc và ghi dữ liêu vô database bị chậm với lượng dữ liệu ngày càng lớn. Khi đó bạn phải nghĩ tới việc mở rộng database của mình. 

Một bài viết hay về sharding.
https://medium.com/@jeeyoungk/how-sharding-works-b4dec46b3f6

Khi nói tới việc mở rộng databases có hai xu hướng chính:

 

- mở rộng theo chiều dọc (vertical scaling)

- mở rộng theo chiều ngang (horizontal scaling) 

Mở rộng theo chiều dọc: 

- thực hiện việc tạo thêm nhiều tables và lưu ở các databases riêng biệt. Công việc này thường sẽ thực hiện ở lớp ứng dụng, bạn sẽ cần phải phân chia các ứng dụng của mình, mỗi ứng dụng sẽ sử dụng một database tách biệt. Việc sử dụng micro services cùng với việc mỗi service sử dụng một ngôn ngữ lập trình và một hệ cơ sở dữ liệu khác nhau được xem là một phương thức áp dụng việc mở rộng database theo chiều dọc.

Mở rộng theo chiều ngang: 

- thực hiện lưu trữ các rows của một table ở trên các máy chủ database khác nhau (được gọi là kỹ thuật sharding). Sharding đã được áp dụng ở nhiều hệ cơ sở dữ liệu khác nhau, gần như các hệ cơ sở dữ liệu hiện đại đều đang dùng sharding như là một tính năng hiển nhiên phải có,  ví dụ Cassandra, MongoDB, HBase ... 

Sharding (mở rộng database theo chiều ngang) được sử dụng khi dữ liệu lưu trữ trong một table quá lớn dẫn tới việc lưu trữ các rows của table đó ở nhiều máy chủ khác nhau là cần thiết, nhằm đảm bảo hiệu năng và khả năng mở rộng cho hệ thống. 

Có nhiều phương pháp thực hiện sharding, các phương pháp được phân biệt và so sánh dựa trên: 

- cách dữ liệu được đọc lên từ database (reading data) 

- cách dữ liệu được ghi xuống database (writing data)

Một khái niệm quan trọng trong sharding là Partition Key, nó sẽ xác định việc dữ liệu sẽ được lưu trữ phân tán như thế nào, dựa trên Partition Key để truy cập và chỉnh sửa dữ liệu một cách hiệu quả thông qua việc điều hướng các thao tác với database vô đúng nơi mà dữ liệu đang được lưu. Các dữ liệu có cùng Partition Key sẽ được lưu trên cùng một nơi (máy chủ).


Sharding được phân theo 2 loại chính là Algorithmic và Dynamic. Với Algorithmic sharding thì client sẽ tự xác định được dữ liệu đang được lưu ở đâu, còn đối với Dynamic sharding cần có một locator service để giúp xác định dữ liệu đang được lưu ở đâu.

Algorithmic sharding

Kiểu sharding này sẽ sử dụng một hàm sharding nhận vô tham số partition_key và trả về database_id để xác định vị trí dữ liệu ở đâu. 

Một hàm sharding đơn giản có thể dùng đó là: hash(key) % number_of_db. 

Dữ liệu được lưu trữ phân tán chỉ dựa trên hàm sharding, không phụ thuộc vào độ lớn dữ liệu hay không gian lưu trữ. Do đó kiểu sharding này chỉ nên sử dụng cho loại dữ liệu key-value trong đó loại dữ liệu phải giống nhau (không quá khác biệt).

Dynamic sharding

Trong kiểu sharding này, cần có một locator service chạy riêng biệt giúp xác định việc lưu trữ dữ liệu ở đâu. Để đọc và ghi dữ liệu, client cần kết nối và truy vấn vô locator service trước tiên. Locator sẽ thực hiện việc điều phối các hoạt động lưu trữ dữ liệu trong cluster một cách linh động. HDFS, Apache HBase, MôngDB đều sử dụng kiểu sharding này.

---

Vitess là công cụ nguồn mở giúp việc mở rộng Mysql theo chiều ngang (horizontal scaling or sharding) được thực hiện dễ dàng, đây là một trong những core infrastructure của Youtube

Vitess: https://github.com/vitessio/vitess
Sharding thực hiện ở instagram: https://instagram-engineering.com/sharding-ids-at-instagram-1cf5a71e5a5c

Học Data Structures & Algorithms phỏng vấn xin việc

Hầu như các công ty công nghệ lớn làm sản phẩm khi tuyển nhân viên họ đều muốn tìm các ứng viên có kiến thức tốt về cấu trúc dữ liệu và thuật toán. Với những người mất gốc và tưởng lầm thời gian học đại học là để chơi game, tán gái như tôi thì việc tự học cấu trúc dữ liệu và thuật toán là một việc không dễ dàng.

Một trong những khoá tôi cảm thấy học dễ vô nhất về cấu trúc dữ liệu và thuật toán là khoá học Intro to Data Structures and Algorithms trên Udacity, ngoài việc cấu trúc khoá học được thiết kế chi tiết dễ theo dõi không yêu cầu các kiến thức chuyên sâu khác để theo được hết khoá học, còn có lẽ là do cô giảng viên xinh đẹp tóc vàng Brynn

Ngoài việc học được các kiến thức cơ bản nhất về cấu trúc dữ liệu và thuật toán, khoá học này còn giúp bạn một số kỹ năng để đi phỏng vấn ở các công ty công nghệ lớn như Google, Facebook ... nghe thế này cũng đáng để học rồi đấy.

Cấu trúc chính của khoá học sẽ nói về các hiệu quả của các chương trình và các đo hiệu quả các chương trình đó bằng Big O(). Tiếp sẽ giới thiệu về các cấu trúc dữ liệu, cách triển khai các cấu trúc này trong python như list, maps, trees, graphs ... các thuật toán chính trong searching và sorting như binary search, bubble sort, merge sort, quick sort ...

Phần cuối của khoá sẽ có một vài cách để trả lời các câu hỏi phỏng vấn về cấu trúc dữ liệu và thuật toán, có phần giả lập đi kèm xem rất giống thật.

1. Introduction and Efficiency
2. List-Based Collections
3. Searching and Sorting
4. Maps and Hashing
5. Trees
6. Graphs
7. Case Studies in Algorithms
8. Technical Interview Tip

Một điều hấp dẫn khác là  khoá học này miễn phí trên Udacity, bạn nào muốn tự mình khám phá thì nhào vô link ở đây để học ngay thôi, bạn nào muốn tìm bạn để trao đổi thảo luận về nội dung khoá học thì để lại còm men ở dưới bài này nhé.