#216 - Happy Birthday, Git!
Xin chào các bạn,
Sau 1 tuần mở bán ấn phẩm Dijkstra tập 2, chúng tôi đã nhận được sự ủng hộ nhiệt tình từ đông đảo bạn đọc Grokking Newsletter ❤️
Với rất nhiều thành viên trong Ban Biên soạn Dijkstra, đây là lần đầu tiên chúng tôi cùng thực hiện một ấn phẩm như thế, do đó không tránh khỏi một số thiếu sót như khâu dàn trang hay chất lượng hình ảnh chưa tốt. Để cải thiện lần xuất bản sau này, rất mong bạn đọc gửi ý kiến đóng góp tại đây.
Ngoài ra, nếu ấn phẩm của bạn chẳng may có lỗi trong khâu sản xuất như thiếu trang, bạn có thể gửi ảnh chụp sản phẩm bị lỗi và thông tin đơn hàng về dijkstra@grokking.org. Chúng tôi sẽ gửi tặng bạn một cuốn khác.
Xin cảm ơn,
Ban Biên soạn Dijkstra
Những bài viết hay
Scalability concepts: distributed ID generation
ID là một khái niệm rất quen thuộc đối với developer, được sử dụng để định danh một đối tượng cụ thể. Thao tác với ID nghe có vẻ đơn giản nhưng khi nhúng tay vào các hệ thống có khả năng scale lớn sẽ phát sinh khá nhiều bài toán hóc búa.
ID tự động tăng
- Với những bạn làm việc với database nhiều, khái niệm auto-increment primary key sẽ không còn xa lạ. Lấy ví dụ xây dựng chức năng đăng bài đơn giản, cách phổ biến để thiết kế database là tạo một table posts gồm các column:
- id: unique id cho mỗi bài post
- author: khóa ngoại trỏ tới bảng users
- và những field content, ...
Nếu chỉ có một server database và một luồng ghi vào CSDL thì việc sẽ nhẹ nhàng, khởi tạo id chạy từ 0, khi có bài viết mới được đăng thì cho id tăng dần lên. Bài toán sẽ khó hơn bạn có nhiều hơn một luồng ghi, bạn phải đảm bảo không xảy ra hai bài viết khác nhau nhưng lại có cùng một id. May mắn là database hiện tại có các cơ chế về locking để đảm bảo tính Atomic (nhất quán) cho dữ liệu.
Scale nhiều data stores
Bài toán ID tự động tăng sẽ hoạt động trơn tru khi bạn có một server duy nhất. Trong tương lai, sản phẩm của bạn ngày càng phát triển, traffic tăng và database phình to, bạn chọn cách scale database ra nhiều servers. Vấn đề phát sinh khi mỗi server lại có một bộ ID riêng và bạn cần đảm bảo tất cả các bài viết trên hệ thống databases phân tán là duy nhất. Có một vài cách giải quyết như sau:
1. Ghi tập trung (Centralized writes)
Bạn chỉ định một database làm leader đảm nhận các request ghi (write) dữ liệu, các database còn lại sẽ đóng vai trò replica từ leader và phục vụ nhu cầu đọc dữ liệu (read). Mô hình trên còn được gọi là master-slave (hoặc primary-replica). Tuy nhiên, nhược điểm ở mô hình này chính là nút thắt cổ chai (bottleneck) xảy ra ở database master nếu hệ thống của bạn cần phục vụ việc ghi nhiều hơn là đọc dữ liệu nên cần phải cân nhắc.
2. Tạo ID tập trung (Centralized ID generation)
Ngoài cách trên, hệ thống của bạn được phép ghi vào bất kì database nào, nhưng trước đó, cần một thao tác Gen-ID để đảm bảo id của bài viết là duy nhất. Dù phương pháp này cho phép chúng ta ghi vào nhiều database, nhưng vẫn phát sinh bottleneck tại thao tác Gen-ID.
3. Chọn ngẫu nhiên từ tập hợp lớn (Pick randomly from a large range)
Thay vì sử dụng ID tăng dần, bạn còn một giải pháp khác là chọn ngẫu nhiên ID từ một tập hợp số thật lớn, phổ biến như UUID để đảm bảo tính duy nhất của nó. Nhược điểm của phương pháp này nằm ở việc ID chọn có thể thể lớn và không theo trình tự.
4. Mã hóa phân vùng ID (Encode the partition in the ID)
Thay thế cho giải pháp chọn ID từ tập số lớn bên trên, bạn có tạo ID bằng cách đính kèm với tiền tố của partition chẳng hạn như 01-123, 02-123. Giải pháp này cho phép bạn sử dụng ID tự tăng mà vẫn đảm bảo không bị trùng ID giữa các database server.
Tóm lại còn nhiều giải pháp khác, tùy vào từng trường hợp mà bạn cần chọn cách giải quyết hợp lý, việc đảm bảo tính duy nhất cho ID trên hệ thống cần mở rộng cao cũng sẽ là một thách thức cho bạn.
Mời các bạn cùng đọc bài viết sau.
(by duyquang)
Góc Data
Revisiting B+-tree vs. LSM-tree
Có thể nói B+-tree và LSM-tree là hai cấu trúc dữ liệu được sử dụng rộng rãi nhất trong các hệ thống Database hiện đại.
Được thiết kế với những định hướng khác nhau, tuy nhiên B+-tree và LSM-tree đều dựa trên đặc tính của HDD như lưu dữ liệu theo từng block (tận dụng bởi B+-tree) và tối ưu hơn cho dữ liệu ghi một cách tuần tự (sequential write - tận dụng bởi LSM-tree).
Câu hỏi được đặt ra là khi SSD đang trở thành phần cứng phổ biến và thay thế HDD, các ưu thế của B+-tree và LSM-tree có còn giữ nguyên? Đặc biệt là những đặc tính đã từng được xem là ưu thế của LSM-tree so với B+-tree?
Trong bài báo sau, các tác giả chia sẻ những khảo sát của mình về tính hiệu quả của LSM so với B+-tree trên SSD. Đồng thời các tác giả cũng đề xuất B- tree, một phiên bản điều chỉnh của B+ tree có performance không kém hơn so với LSM trong các bài test phổ biến.
(by n^4)
Góc Lập Trình
Đề ra tuần này: Longest String Chain
Lời giải đề bài tuần trước: Count and Say
Lời giải:
Nếu đã biết tới kỹ thuật nén dữ liệu Run-length encoding, bạn sẽ nhận thấy ngay rằng xâu kết quả của n = i chính là kết quả run-length encode từ xâu kết quả của n = (i - 1).
Ta có thể định nghĩa một hàm đệ quy bằng giả mã như sau:
String countAndSay(int n)
// base case
if (n == 1)
return "1"
// get result of n - 1
String prev = countAndSay(n - 1)
return runLengthEncode(prev)
Ghi chú: Run-length encoding là một trong những kỹ thuật nén dữ liệu không mất mát (lossless data compression). Kỹ thuật này dựa trên ý tưởng thay thế chuỗi ký tự liên tiếp giống nhau bằng chuỗi "số lượng ký tự, ký tự".
Ví dụ: nếu ta có chuỗi nguyên gốc là "AAAABBB", thì chuỗi sau khi thực hiện run-length encoding là "4A3B". Bằng cách này, ta giảm được 3 ký tự so với so với chuỗi nguyên gốc.
Với ý tưởng trên, ta thực hiện giải thuật như sau: https://pastebin.com/uztiPiTg
Với n đủ lớn, chiều dài của chuỗi (n + 1) sẽ tăng khoảng 30% so với chuỗi n. Mời bạn đọc tham khảo thêm tại Look-and-say sequence.
(by nhphuc)
History
Chúc mừng sinh nhật Git!
Vào ngày 06/4/2005, Linus Torvalds đã thông báo tới cộng đồng Linux về Git, một revision-control system ông vừa tạo ra vào cuối tuần trước. Đằng sau sự ra đời của Git là một câu chuyện khá dài.
Trước khi có Git, lập trình viên Linux sử dụng BitKeeper, một công cụ do BitMover phát triển. Mặc dù BitMover có một phiên bản miễn phí cho lập trình viên Linux phát triển kernel, nhưng khi cộng đồng tự phát triển open-source trên đó thì BitMover lại không thoải mái. Open-source đó là BitKeeper client, do Andrew Tridgell viết vào tháng 2/2005, cho phép làm việc với source code được lưu trữ trong BitKeeper. Xung quanh công cụ này cũng có nhiều tranh cãi:
Những người ủng hộ cho rằng công cụ này chỉ đơn giản là cung cấp một phương thức khác để đóng góp cho Linux kernel mà không cần bản quyền phần mềm của BitKeeper. Tridgell client chỉ có thể truy cập tới dữ liệu của BitKeeper và không thay thế cho toàn bộ hệ thống.
Cha đẻ của Git là Torvalds lại không đánh giá cao client do Tridgell tạo ra. Theo ông, phần mềm của Tridgell không có mục đích hữu ích. Ngoài ra, giao thức reverse-engineering của Tridgell đã phần nào vi phạm quy định sử dụng của BitKeeper. (Bản thân Tridgell lại khẳng định công cụ của mình là hoàn toàn hợp lệ cả về đạo đức lẫn pháp luật.)
Chính Torvalds cũng đã dành nhiều thời gian để hòa giải giữa Tridgel và BitMover nhưng không thành công. Sau vài tháng thảo luận, BitMover đã quyết định thu hồi luôn quyền sử dụng BitKeeper.
Kết quả là Torvalds không thể sử dụng BitKeeper nữa, nhưng các sản phẩm tương tự trên thị trường thời điểm đó cũng không đáp ứng được các yêu cầu về performance. Theo Torvalds, "không thể chấp nhận được việc phải bỏ ra 10 giây chỉ để apply 1 patch bởi vì source code quá lớn", nên cuối cùng ông đã tự viết ra một công cụ đáp ứng được đúng yêu cầu của mình.
Khi được hỏi tại sao lại gọi phần mềm mới này là "git" (từ lóng trong tiếng Anh, nghĩa là "kẻ thối nát"), ông giải thích: "Vì tôi là một kẻ tự cao tự đại, nên tôi đặt tên cho tất cả các dự án của mình theo tên bản thân. Trước tiên là Linux, và bây giờ là git".
(by lpv)
Code & Tools
pre-commit: Một framework để quản lý và duy trì các hook trước khi commit, hỗ trợ nhiều ngôn ngữ.
Lapce: Một code editor được viết bằng Rust.
Góc Sponsors
Là một trong những siêu ứng dụng hàng đầu ở khu vực Đông Nam Á, Grab cung cấp đa dạng dịch vụ cho hơn 187 triệu người dùng tại 428 thành phố ở tám quốc gia. Tại Grab, chúng tôi tin rằng nhân tài chính là trái tim của công ty, vì vậy chúng tôi luôn cố gắng tạo ra một môi trường tuyệt vời để tối ưu hoá tiềm năng của các Grabbers.
Những lý do bạn sẽ thích làm việc ở Grab:
Đồng nghiệp thân thiện, chuyên môn cao.
Môi trường làm việc đa quốc gia, cân bằng giữa cuộc sống và công việc (work-life balance)
Được tham gia giải quyết các bài toán khó (high scale, high traffic), với nhiều impact (vài trăm triệu người dùng)
Lương tháng 13 + lương thưởng bonus theo hiệu quả công việc.
Rất nhiều khoá học training đào tạo nội bộ cũng như đào tạo được cung cấp bởi các đối tác như Microsoft, Amazon, ..
Hiện văn phòng R&D của Grab đang tuyển nhiều vị trí như: Backend Developer, Frontend Developer, DevOps Engineer, Lead Software Engineer, ... Bạn có thể tham khảo tại Jobs - Grab Careers để biết thêm chi tiết.
Quotes
"Git, to some degree, was designed on the principle that everything you ever do on a daily basis should take less than a second" - Linus
Bạn đánh giá nội dung số newsletter này thế nào?
(1 = Rất tệ / 5 = Rất tốt)
Đánh giá của các bạn sẽ giúp chúng tôi liên tục cải thiện nội dung Newsletter!