Các nhà khoa học tìm ra sự cân bằng tối ưu về lưu trữ dữ liệu và thời gian | Tạp chí Quanta

Khoảng 70 năm trước, một kỹ sư tại IBM tên là Hans Peter Luhn đã âm thầm thay đổi tiến trình khoa học máy tính. Luhn đã nắm giữ một số bằng sáng chế, bao gồm một bằng sáng chế cho thiết bị có thể đo số lượng sợi vải và một bằng sáng chế khác cho hướng dẫn xác định loại đồ uống hỗn hợp nào bạn có thể làm từ các nguyên liệu trong nhà bếp của mình. Nhưng trong một bài báo nội bộ của IBM năm 1953, ông đã đề xuất một kỹ thuật mới để lưu trữ và truy xuất thông tin hiện đã được tích hợp trong hầu hết các hệ thống tính toán: bảng băm.

Bảng băm là một lớp cấu trúc dữ liệu chính. Họ cung cấp một phương pháp đặc biệt thuận tiện để truy cập và thay đổi thông tin trong cơ sở dữ liệu lớn. Nhưng công nghệ này đi kèm với sự đánh đổi không thể tránh khỏi.

Trong 1 1957 giấy công bố trên Tạp chí Nghiên cứu và Phát triển của IBM, W. Wesley Peterson đã xác định thách thức kỹ thuật chính mà bảng băm đặt ra: Chúng cần tốc độ nhanh, nghĩa là chúng có thể nhanh chóng truy xuất thông tin cần thiết. Nhưng chúng cũng cần phải nhỏ gọn, sử dụng càng ít bộ nhớ càng tốt. Hai mục tiêu song sinh này về cơ bản là mâu thuẫn với nhau. Việc truy cập và sửa đổi cơ sở dữ liệu có thể được thực hiện nhanh hơn khi bảng băm có nhiều bộ nhớ hơn; và các hoạt động trở nên chậm hơn trong các bảng băm sử dụng ít không gian hơn. Kể từ khi Peterson đặt ra thách thức này, các nhà nghiên cứu đã cố gắng tìm ra sự cân bằng tốt nhất giữa thời gian và không gian.

Các nhà khoa học máy tính giờ đây đã chứng minh được bằng toán học rằng họ đã tìm ra sự cân bằng tối ưu. Giải pháp đến từ một đôi của gần đây giấy tờ đó bổ sung cho nhau. “Những bài báo này giải quyết câu hỏi bỏ ngỏ bấy lâu nay về sự đánh đổi không-thời gian tốt nhất có thể, mang lại những kết quả vô cùng đáng ngạc nhiên mà tôi kỳ vọng sẽ có tác động đáng kể trong nhiều năm tới”, ông nói. Michael Mitzenmacher, một nhà khoa học máy tính tại Đại học Harvard, người không tham gia vào cả hai nghiên cứu.

“Tôi chắc chắn sẽ nói rằng đó là một vấn đề lớn,” nói thêm Rasmus Pagh, một nhà khoa học máy tính tại Đại học Copenhagen. “Rất nhiều người đã giải quyết vấn đề này, cố gắng xem bạn có thể thu hẹp không gian đến mức nào mà vẫn có thể thực hiện các hoạt động hiệu quả về thời gian. Đây chính là vấn đề mà tôi rất muốn giải quyết.”

Thực hiện một băm của nó

Bảng băm là một trong những cấu trúc dữ liệu lâu đời nhất, đơn giản nhất, nhanh nhất và được sử dụng rộng rãi nhất hiện nay. Chúng được thiết kế để thực hiện ba thao tác cơ bản: chèn, thêm các mục mới vào cơ sở dữ liệu; các truy vấn truy cập vào một mục hoặc kiểm tra xem nó có tồn tại hay không; và xóa. Bảng băm có thể là tạm thời — chỉ tồn tại khi một chương trình cụ thể chạy — hoặc nó có thể là một phần vĩnh viễn trong hệ điều hành máy tính của bạn. Trình duyệt web như Chrome hoặc Safari có thể có nhiều bảng băm tích hợp nhằm theo dõi các loại dữ liệu khác nhau.

Các mục trong bảng băm được lưu trữ dưới dạng cặp, với mục — chính thông tin — được kết nối với khóa xác định thông tin. Cắm một khóa vào thuật toán truy vấn của bảng băm và nó sẽ đưa bạn trực tiếp đến mục đó. Điều này nghe có vẻ không quá đặc biệt nhưng đối với cơ sở dữ liệu khổng lồ thì đây có thể là một cách tiết kiệm thời gian tuyệt vời.

Để lấy một ví dụ cực kỳ đơn giản, hãy xem xét Từ điển tiếng Anh Oxford, có định nghĩa cho hơn 600,000 từ. Nếu ấn bản kỹ thuật số dựa trên bảng băm, bạn chỉ cần sử dụng một từ nhất định làm khóa và tiến thẳng đến định nghĩa. Nếu không có bảng băm, từ điển có thể sẽ dựa vào cơ chế tìm kiếm chậm hơn nhiều, sử dụng quy trình loại bỏ để cuối cùng hội tụ về định nghĩa được yêu cầu. Và trong khi bảng băm có thể tìm thấy bất kỳ từ nào trong một khoảng thời gian không đổi (thường là một phần rất nhỏ của một giây), thời gian tìm kiếm cho các phương pháp khác có thể tăng lên khi số lượng từ trong từ điển tăng lên. Bảng băm cũng mang lại một lợi thế khác: Nó có thể giữ cho từ điển luôn hoạt động, giúp dễ dàng chèn các từ mới và xóa những từ lỗi thời.

Các nhà nghiên cứu đã dành nhiều thập kỷ để xây dựng các bảng băm nhằm tối đa hóa tốc độ và giảm thiểu bộ nhớ. Trong thế kỷ 20, các giải pháp có xu hướng mang lại những lợi ích đáng kể chỉ ở một khía cạnh, thời gian hoặc không gian. Sau đó vào năm 2003, các nhà nghiên cứu cho thấy rằng về mặt lý thuyết có thể tạo ra bước nhảy vọt lớn về hiệu quả cả về thời gian và không gian. Tuy nhiên, phải mất thêm hai thập kỷ nữa, các nhà nghiên cứu mới tìm ra được sự cân bằng lý tưởng giữa hai điều này.

Xáo trộn dữ liệu

Bước quan trọng đầu tiên hướng tới mục tiêu đó diễn ra vào năm 2022 với tốc độ hội nghị khoa học máy tính lớn Ở Rome. Ở đó, một nhóm đã đề xuất một bảng băm với các tính năng mới có thể mang lại sự kết hợp tốt nhất giữa hiệu quả về thời gian và không gian. Tác giả đầu tiên của bài báo (được liệt kê theo thứ tự bảng chữ cái) là Michael Bender của Đại học Stony Brook, vì vậy nó thường được gọi là Bender et al. bảng băm. Mặc dù nhóm không cố gắng xây dựng một bảng băm hoạt động nhưng họ đã chứng minh rằng về nguyên tắc, nó có thể được xây dựng với các tính năng mà họ mô tả.

Để đánh giá bảng băm mà họ nghĩ ra, nhóm đã tạo ra một đường cong cân bằng - một biểu đồ vẽ thời gian cho mỗi thao tác (chèn hoặc xóa) trên một trục và không gian được chiếm bởi bộ nhớ trên trục kia. Nhưng biểu đồ này xác định không gian theo một cách đặc biệt: Do cách chúng được xây dựng, các bảng băm cần nhiều bộ nhớ hơn mức tối thiểu cần thiết để lưu trữ một tập hợp các mục nhất định. Các nhà khoa học máy tính gọi không gian thừa này là “bit lãng phí”, mặc dù chúng không thực sự lãng phí và ở một mức độ nào đó là cần thiết. Trục không gian trên đường cong đánh đổi đo số bit bị lãng phí trên mỗi khóa.

Bằng cách phân tích đường cong đánh đổi, các nhà nghiên cứu có thể tìm ra thời gian nhanh nhất có thể cho một bảng băm sử dụng một lượng không gian nhất định. Họ cũng có thể lật ngược câu hỏi để tìm ra không gian nhỏ nhất có thể trong một thời gian thực hiện nhất định. Thông thường, một sự thay đổi nhỏ ở một biến sẽ dẫn đến một sự thay đổi nhỏ ở biến kia. William Kuszmaul, một nhà khoa học máy tính lý thuyết tại Harvard và là đồng tác giả của bài báo năm 2022. “Nếu bạn tăng gấp đôi thời gian, có lẽ bạn sẽ giảm được một nửa số bit bị lãng phí trên mỗi khóa.”

Nhưng bảng băm họ thiết kế lại không như vậy. Kuszmaul cho biết: “Nếu bạn tăng thời gian lên một chút, số bit lãng phí trên mỗi khóa sẽ giảm theo cấp số nhân”. Đường cong đánh đổi quá dốc, nó thực sự nằm ngoài bảng xếp hạng.

Nhóm đã xây dựng bảng băm của họ thành hai phần. Chúng có cấu trúc dữ liệu chính, trong đó các mục được lưu trữ mà không có bất kỳ bit lãng phí nào và cấu trúc dữ liệu thứ cấp giúp yêu cầu truy vấn tìm thấy mục mà nó đang tìm kiếm. Mặc dù nhóm không phát minh ra khái niệm về cấu trúc dữ liệu thứ cấp nhưng họ đã có một khám phá quan trọng giúp bảng băm siêu hiệu quả của họ có thể thực hiện được: Hiệu suất bộ nhớ tổng thể của cấu trúc phụ thuộc vào cách cấu trúc chính sắp xếp các mục được lưu trữ của nó.

Ý tưởng cơ bản là mọi mục trong cấu trúc chính đều có vị trí lưu trữ ưu tiên - vị trí tốt nhất, vị trí tốt thứ hai, vị trí tốt thứ ba, v.v. Nếu một mục ở vị trí tốt nhất, số 1 sẽ được gắn vào nó và số đó được lưu trữ trong cấu trúc dữ liệu thứ cấp. Để trả lời một truy vấn, cấu trúc phụ chỉ cung cấp số 1, cho biết vị trí chính xác của mục trong cấu trúc chính.

Nếu mục ở vị trí tốt nhất thứ 100 thì cấu trúc dữ liệu thứ cấp sẽ gắn số 100. Và vì hệ thống sử dụng hệ nhị phân nên nó biểu thị số 100 là 1100100. Tất nhiên, để lưu trữ số 1100100 sẽ cần nhiều bộ nhớ hơn 1 — số được gán cho một hạng mục khi nó ở vị trí tốt nhất. Những khác biệt như thế sẽ trở nên quan trọng nếu bạn đang lưu trữ một triệu món đồ.

Vì vậy, nhóm nhận ra rằng nếu bạn liên tục chuyển các mục trong cấu trúc dữ liệu chính sang các vị trí ưa thích hơn, thì bạn có thể giảm đáng kể mức tiêu thụ bộ nhớ mà cấu trúc phụ mà không cần phải tăng thời gian truy vấn.

Pagh nói: “Trước công việc này, không ai nhận ra rằng bạn có thể nén thêm cấu trúc dữ liệu bằng cách di chuyển thông tin xung quanh”. “Đó là cái nhìn sâu sắc lớn của bài báo Bender.”

Các tác giả đã chỉ ra rằng phát minh của họ đã thiết lập một giới hạn trên mới cho các bảng băm hiệu quả nhất, nghĩa là đây là cấu trúc dữ liệu tốt nhất được phát minh ra cả về hiệu quả về thời gian và không gian. Nhưng vẫn có khả năng là người khác có thể làm tốt hơn.

Chắc chắn thành công

Năm tiếp theo, một nhóm do Hoa Thành Vũ, một nhà khoa học máy tính tại Đại học Princeton, đã cố gắng cải thiện bảng băm của nhóm Bender. “Chúng tôi đã làm việc rất chăm chỉ và không thể làm được,” nói Chu Nhâm Phi, sinh viên tại Đại học Thanh Hoa ở Bắc Kinh và là thành viên trong nhóm của Yu. “Đó là khi chúng tôi nghi ngờ rằng giới hạn trên của họ [cũng] là giới hạn dưới” - điều tốt nhất có thể đạt được. “Khi giới hạn trên bằng giới hạn dưới, trò chơi kết thúc và bạn có câu trả lời của mình.” Dù bạn có thông minh đến đâu thì cũng không có bảng băm nào có thể làm tốt hơn được.

Nhóm của Yu đã sử dụng một chiến lược mới để tìm hiểu xem linh cảm đó có đúng hay không bằng cách tính toán giới hạn dưới theo các nguyên tắc đầu tiên. Đầu tiên, họ lý giải rằng để thực hiện thao tác chèn hoặc xóa, bảng băm - hay thực tế là bất kỳ cấu trúc dữ liệu nào - đều phải truy cập vào bộ nhớ máy tính một số lần. Nếu họ có thể tìm ra số lần tối thiểu cần thiết cho một bảng băm tiết kiệm không gian, thì họ có thể nhân số đó với thời gian cần thiết cho mỗi lần truy cập (một hằng số), mang lại cho họ giới hạn dưới trong thời gian chạy.

Nhưng nếu họ không biết gì về bảng băm (ngoại trừ việc nó tiết kiệm không gian), làm sao các nhà nghiên cứu có thể tìm ra số lần tối thiểu cần thiết để truy cập bộ nhớ? Họ rút ra nó hoàn toàn từ lý thuyết, sử dụng một lĩnh vực dường như không liên quan được gọi là lý thuyết về độ phức tạp của giao tiếp, nghiên cứu xem cần bao nhiêu bit để truyền tải thông tin giữa hai bên. Cuối cùng, nhóm đã thành công: Họ đã tìm ra số lần cấu trúc dữ liệu phải truy cập vào bộ nhớ của nó trong mỗi thao tác.

Đây là thành tựu quan trọng của họ. Sau đó, họ có thể thiết lập giới hạn dưới về thời gian chạy cho bất kỳ bảng băm nào tiết kiệm không gian. Và họ thấy rằng nó khớp chính xác với bảng băm Bender. “Lúc đầu, chúng tôi nghĩ rằng nó có thể được cải thiện,” Chu nói. “Hóa ra chúng tôi đã sai.” Điều đó có nghĩa là vấn đề của Peterson cuối cùng đã được giải quyết.

Kuszmaul cho biết, bên cạnh việc trả lời câu hỏi đã tồn tại hàng thập kỷ này, điều đáng kinh ngạc về bằng chứng Yu là tính tổng quát của nó. “Giới hạn dưới của chúng áp dụng cho tất cả các cấu trúc dữ liệu có thể có, bao gồm cả những cấu trúc chưa được phát minh.” Điều đó có nghĩa là không có phương pháp lưu trữ dữ liệu nào có thể đánh bại bảng băm Bender về bộ nhớ và tốc độ.

Băm vào tương lai

Bất chấp hiệu quả chưa từng có của bảng băm mới, không ai có thể thử xây dựng nó sớm. Nó quá phức tạp để xây dựng. “Một thuật toán nhanh về mặt lý thuyết không nhất thiết phải nhanh trong thực tế”, Chu nói.

Kuszmaul nói, không có gì lạ khi những khoảng cách như vậy giữa lý thuyết và thực tiễn tồn tại trong một thời gian dài bởi vì các nhà lý thuyết có xu hướng bỏ qua các yếu tố không đổi. Thời gian cần thiết để thực hiện một thao tác thường được nhân với một số, một hằng số nào đó có giá trị chính xác có thể không quan trọng theo quan điểm lý thuyết. “Nhưng trong thực tế, các hằng số thực sự quan trọng,” ông nói. “Trong thế giới thực, hệ số 10 là kết thúc trò chơi.”

Các bảng băm thực tế vẫn đang được cải thiện về mặt vật chất, ngay cả khi chúng còn kém xa so với lý tưởng về mặt lý thuyết. Ví dụ: một bảng băm mới có tên tảng băng trôiHT, được xây dựng bởi Bender, Kuszmaul và những người khác, tốt hơn nhiều so với những người tiền nhiệm của nó. Theo Kuszmaul, nó nhanh gấp đôi so với bảng băm tiết kiệm không gian nhất hiện nay và sử dụng không gian ít hơn ba lần so với bảng băm nhanh nhất.

Mitzenmacher hy vọng rằng kết quả năm 2023 có thể sớm mang lại một loại lợi ích khác: “Bất cứ khi nào bạn nhận được giới hạn dưới mới - đặc biệt là giới hạn liên quan đến một số kỹ thuật mới - luôn có hy vọng rằng bạn có thể sử dụng chúng… cho các vấn đề liên quan”.

Nhà khoa học máy tính cho biết còn có sự hài lòng về mặt trí tuệ khi biết rằng bạn đã giải quyết được một vấn đề khó khăn và tồn tại lâu dài. Piotr Indyk của Viện Công nghệ Massachusetts. “Khi bạn chắc chắn rằng không thể cải thiện một số cấu trúc dữ liệu nhất định, điều đó có thể giúp bạn tập trung nỗ lực nghiên cứu.” Cuối cùng, các nhà nghiên cứu dữ liệu có thể chuyển sự chú ý của họ khỏi thách thức của Peterson và tập trung vào các vấn đề mới trong khoa học máy tính lý thuyết, trong đó không thiếu.