Thế giới công nghệ có một mô hình thú vị về việc khám phá song song, khi cùng một đột phá xảy ra độc lập giữa các nhóm và thời kỳ khác nhau. Trong khi hầu hết mọi người đều biết về những trường hợp nổi tiếng như Newton và Leibniz cùng phát minh ra phép tính vi tích phân, một câu chuyện tương tự đã âm thầm diễn ra trong thế giới cấu trúc dữ liệu với thứ gọi là prolly trees.
Các cuộc thảo luận gần đây trong cộng đồng lập trình viên đã tiết lộ rằng cấu trúc dữ liệu chuyên biệt này đã được phát minh độc lập ít nhất bốn lần kể từ năm 2009, với mỗi nhóm đặt cho nó một tên khác nhau và sử dụng cho các mục đích khác nhau. Mô hình này cho thấy prolly trees đại diện cho một sự tiến hóa tự nhiên trong cách chúng ta xử lý dữ liệu có kiểm soát phiên bản.
Dòng thời gian các phát minh về Prolly Tree
| Năm | Người tạo ra | Tên được sử dụng | Trường hợp sử dụng chính |
|---|---|---|---|
| 2009 | Bup ( Avery Pennarun ) | Không có tên chính thức | Sao lưu hệ thống tập tin |
| 2015 | Noms | Prolly Trees | Cơ sở dữ liệu có kiểm soát phiên bản |
| 2019 | Viện Pháp ( INRIA ) | Merkle Search Trees | Hệ thống phân tán/ CRDTs |
| 2020 | Đại học DePaul | Content-Defined Merkle Trees | Nén image Docker |
Bí Ẩn Của Việc Thiếu Ghi Nhận
Khám phá đáng ngạc nhiên nhất đến từ các thành viên cộng đồng đã đào sâu vào dòng thời gian. Trong khi nhiều người ghi nhận Noms vào năm 2015 là người phát minh ban đầu, các lập trình viên đã tìm thấy bằng chứng rằng cùng một khái niệm đã xuất hiện sớm hơn nhiều. Một người bình luận đã chỉ ra Bup, một công cụ sao lưu từ năm 2009, đã sử dụng chính xác cùng một kỹ thuật nhưng không bao giờ đặt cho nó một tên chính thức.
Các ranh giới chunk nên được xác định một cách xác định từ các thuộc tính cục bộ của dữ liệu. Sử dụng rolling checksum trên một cửa sổ nhỏ nào đó và chia tệp nếu nó đạt đến một giá trị đặc biệt (0).
Thậm chí còn hấp dẫn hơn, các cuộc thảo luận trên danh sách gửi thư Git từ năm 2005 cho thấy các lập trình viên đã mô tả một cách bình thường cùng một cách tiếp cận, cho thấy họ không coi nó là điều đặc biệt mới lạ vào thời điểm đó. Điều này làm nổi bật một vấn đề phổ biến trong đổi mới công nghệ - đôi khi những đột phá quan trọng nhất lại không được chú ý vì chúng có vẻ hiển nhiên đối với những người tạo ra chúng.
Tại Sao Mọi Người Cứ Tiếp Tục Phát Minh Lại Cùng Một Bánh Xe
Cuộc thảo luận cộng đồng tiết lộ lý do tại sao prolly trees cứ tiếp tục được khám phá lại. Chúng kết hợp ba khái niệm đã được thiết lập từ lâu và đã tồn tại hàng thập kỷ: Merkle trees (1979), rolling hash functions (1981), và content-defined chunking (1996). Điều kỳ diệu xảy ra khi bạn kết hợp cả ba theo một cách cụ thể.
Các nhóm khác nhau đã tình cờ khám phá ra sự kết hợp này trong khi giải quyết những vấn đề hoàn toàn khác nhau. Bup cần sao lưu tệp tốt hơn, Noms muốn cơ sở dữ liệu có kiểm soát phiên bản, các nhà nghiên cứu Pháp đang xây dựng hệ thống phân tán, và Đại học DePaul đang cố gắng tối ưu hóa Docker images. Mỗi nhóm đều độc lập nhận ra rằng việc kết hợp ba kỹ thuật này đã tạo ra thứ gì đó mạnh mẽ.
Cấu trúc dữ liệu này cung cấp một số thuộc tính có giá trị khiến nó trở nên hấp dẫn đối với các ứng dụng hiện đại: nó có thể lưu trữ hiệu quả nhiều phiên bản dữ liệu trong khi chia sẻ các phần chung, nhanh chóng xác định sự khác biệt giữa các phiên bản, và duy trì hiệu suất tốt ngay cả với các tập dữ liệu lớn.
Các Công Nghệ Nền Tảng
| Công Nghệ | Năm Ra Đời | Mục Đích Trong Prolly Trees |
|---|---|---|
| Merkle Trees | 1979 | Xác minh mật mã và tính toàn vẹn cấu trúc |
| Rabin Fingerprint (Rolling Hash) | 1981 | Ranh giới phân đoạn được định nghĩa bởi nội dung |
| Content Defined Chunking (CDC) | 1996 (rsync) | Phân đoạn dữ liệu có kích thước biến đổi |
Vấn Đề Đặt Tên
Một khía cạnh thú vị của việc phát minh lặp đi lặp lại này là sự nhầm lẫn trong việc đặt tên. Cùng một cấu trúc dữ liệu đã được gọi là prolly trees, Merkle search trees, content-defined Merkle trees, và đôi khi chỉ được mô tả mà không có bất kỳ tên đặc biệt nào. Điều này tạo ra thách thức cho các lập trình viên đang cố gắng nghiên cứu chủ đề này hoặc xây dựng dựa trên công việc hiện có.
Cộng đồng có vẻ chia rẽ về tên nào cuối cùng sẽ trở thành tiêu chuẩn. Một số người ủng hộ prolly trees vì nó có vẻ là tên chính thức sớm nhất, trong khi những người khác thích các thuật ngữ mô tả hơn như Merkle search trees. Việc thiếu một trang Wikipedia cho bất kỳ tên nào trong số này không giúp ích gì cho tình hình.
Các Thuộc Tính Chính của Prolly Trees
- Có thể tìm kiếm: Lưu trữ dữ liệu có thứ tự với khả năng tra cứu key/offset hiệu quả
- Độc lập với lịch sử: Biểu diễn duy nhất bất kể trình tự các thao tác
- Tự cân bằng: Cấu trúc cây cân bằng theo xác suất
- Chia sẻ cấu trúc: Nhiều phiên bản chia sẻ dữ liệu chung, giảm dung lượng lưu trữ
- So sánh hiệu quả: So sánh các phiên bản với độ phức tạp thời gian logarit
- Biến đổi hiệu quả: Áp dụng các thay đổi với chi phí tính toán tối thiểu
Nhìn Về Phía Trước
Việc phát minh lặp đi lặp lại prolly trees cho thấy chúng đáp ứng một nhu cầu thực sự trong điện toán hiện đại. Khi ngày càng nhiều ứng dụng yêu cầu kiểm soát phiên bản hiệu quả và đồng bộ hóa dữ liệu, chúng ta có thể sẽ thấy mô hình này tiếp tục. Cuộc thảo luận cộng đồng chỉ ra rằng các cấu trúc tương tự đang được phát triển cho các trường hợp sử dụng khác, với các nhà nghiên cứu đang làm việc trên các biến thể sử dụng các loại cây cơ bản khác nhau.
Câu chuyện này phục vụ như một lời nhắc nhở rằng đổi mới thường xảy ra song song, được thúc đẩy bởi những nhu cầu tương tự và các công cụ có sẵn. Mặc dù có vẻ không hiệu quả khi phát minh lại cùng một thứ nhiều lần, mỗi lần lặp lại đã mang lại những hiểu biết và cải tiến mới có lợi cho toàn bộ lĩnh vực.
Tham khảo: People Keep Inventing Prolly Trees