Ilmuwan Menemukan Keseimbangan Optimal Penyimpanan Data dan Waktu | Majalah Kuanta

Sekitar 70 tahun yang lalu, seorang insinyur di IBM bernama Hans Peter Luhn diam-diam mengubah arah ilmu komputer. Luhn sudah memegang beberapa paten, termasuk satu untuk alat yang bisa mengukur jumlah benang kain dan satu lagi untuk panduan menentukan minuman campuran apa yang bisa Anda buat dari bahan-bahan di dapur Anda. Namun dalam makalah internal IBM tahun 1953, ia mengusulkan teknik baru untuk menyimpan dan mengambil informasi yang kini dibangun di hampir semua sistem komputasi: tabel hash.

Tabel hash adalah kelas utama struktur data. Mereka menawarkan metode yang sangat nyaman untuk mengakses dan mengubah informasi dalam database besar. Namun teknologi ini hadir dengan trade-off yang tidak dapat dihindari.

Dalam 1957 kertas diterbitkan dalam Jurnal Penelitian dan Pengembangan IBM, W. Wesley Peterson mengidentifikasi tantangan teknis utama yang ditimbulkan oleh tabel hash: Tabel hash harus cepat, artinya tabel tersebut dapat dengan cepat mengambil informasi yang diperlukan. Namun mereka juga harus kompak, menggunakan memori sesedikit mungkin. Tujuan kembar ini pada dasarnya bertentangan. Mengakses dan memodifikasi database dapat dilakukan lebih cepat bila tabel hash memiliki lebih banyak memori; dan operasi menjadi lebih lambat pada tabel hash yang menggunakan lebih sedikit ruang. Sejak Peterson memaparkan tantangan ini, para peneliti telah mencoba menemukan keseimbangan terbaik antara waktu dan ruang.

Para ilmuwan komputer kini telah membuktikan secara matematis bahwa mereka telah menemukan trade-off yang optimal. Solusinya datang dari a pasangan terbaru dokumen yang saling melengkapi. “Makalah-makalah ini menjawab pertanyaan terbuka yang sudah lama ada tentang kemungkinan trade-off ruang-waktu terbaik, menghasilkan hasil yang sangat mengejutkan yang saya perkirakan akan berdampak signifikan selama bertahun-tahun yang akan datang,” kata Michael Mitzenmacher, seorang ilmuwan komputer di Universitas Harvard yang tidak terlibat dalam kedua penelitian tersebut.

“Saya pasti akan mengatakan ini adalah masalah besar,” tambahnya Rasmus Pagh, seorang ilmuwan komputer di Universitas Kopenhagen. “Banyak orang telah mengatasi masalah ini, mencoba melihat seberapa besar Anda dapat menekan ruang, sekaligus melakukan pengoperasian yang efisien waktu. Ini adalah masalah yang ingin sekali saya pecahkan.”

Membuat Hash darinya

Tabel hash adalah salah satu struktur data tertua, paling sederhana, tercepat, dan paling banyak digunakan saat ini. Mereka dirancang untuk melakukan tiga operasi dasar: penyisipan, yang menambahkan item baru ke database; pertanyaan, yang mengakses suatu item atau memeriksa untuk melihat apakah item tersebut ada; dan penghapusan. Tabel hash dapat bersifat sementara — hanya ada selama program tertentu dijalankan — atau dapat menjadi bagian permanen dari sistem operasi komputer Anda. Peramban web seperti Chrome atau Safari mungkin memiliki beberapa tabel hash bawaan yang dimaksudkan untuk melacak berbagai jenis data.

Entri dalam tabel hash disimpan berpasangan, dengan item — informasi itu sendiri — terhubung ke kunci yang mengidentifikasi informasi tersebut. Masukkan kunci ke dalam algoritme kueri tabel hash, dan Anda akan diarahkan langsung ke item tersebut. Ini mungkin kedengarannya tidak terlalu luar biasa, namun untuk database yang sangat besar, ini bisa sangat menghemat waktu.

Untuk mengambil contoh yang sangat sederhana, pertimbangkan Kamus Bahasa Inggris Oxford, yang memiliki definisi lebih dari 600,000 kata. Jika edisi digital bergantung pada tabel hash, Anda cukup menggunakan kata tertentu sebagai kunci dan langsung menuju ke definisinya. Tanpa tabel hash, kamus kemungkinan besar akan mengandalkan mekanisme pencarian yang jauh lebih lambat, menggunakan proses eliminasi untuk akhirnya menyatu pada definisi yang diminta. Dan meskipun tabel hash dapat menemukan kata apa pun dalam jumlah waktu yang konstan (biasanya sepersekian detik), waktu pencarian untuk metode lain dapat meningkat seiring dengan bertambahnya jumlah kata dalam kamus. Tabel hash juga menawarkan keuntungan lain: Tabel hash dapat menjaga kamus tetap dinamis, membuatnya mudah untuk menyisipkan kata-kata baru dan menghapus kata-kata yang sudah ketinggalan zaman.

Para peneliti telah menghabiskan waktu puluhan tahun untuk membuat tabel hash yang berupaya memaksimalkan kecepatan dan meminimalkan memori. Pada abad ke-20, solusi cenderung memberikan manfaat yang signifikan hanya dalam satu aspek, waktu atau ruang. Kemudian pada tahun 2003, peneliti menunjukkan bahwa secara teoritis dimungkinkan untuk membuat lompatan efisiensi besar dalam ruang dan waktu secara bersamaan. Namun, dibutuhkan waktu dua dekade lagi bagi para peneliti untuk menemukan keseimbangan ideal antara keduanya.

Pengacakan Data

Langkah besar pertama menuju tujuan tersebut terjadi pada tahun 2022 di a konferensi ilmu komputer besar di Roma. Di sana, sebuah tim mengusulkan tabel hash dengan fitur-fitur baru yang dapat memberikan kombinasi efisiensi waktu dan ruang terbaik yang pernah ada. Penulis pertama makalah ini (diurutkan berdasarkan abjad) adalah Michael Bender dari Stony Brook University, sehingga sering disebut sebagai Bender dkk. tabel hash. Meskipun tim tidak mencoba membuat tabel hash yang berfungsi, mereka membuktikan bahwa pada prinsipnya tabel tersebut dapat dibuat dengan fitur yang mereka jelaskan.

Untuk mengevaluasi tabel hash yang mereka buat, kelompok tersebut membuat kurva trade-off — grafik yang memplot waktu per operasi (penyisipan atau penghapusan) pada satu sumbu dan ruang yang digunakan oleh memori di sumbu lainnya. Namun grafik ini mendefinisikan ruang dengan cara yang khusus: Karena cara pembuatannya, tabel hash memerlukan lebih banyak memori daripada sekadar jumlah minimum yang diperlukan untuk menyimpan sekumpulan item tertentu. Ilmuwan komputer menyebut ruang ekstra ini sebagai “bagian yang terbuang”, meskipun sebenarnya ruang tersebut tidak terbuang dan, sampai batas tertentu, diperlukan. Sumbu spasi pada kurva trade-off mengukur jumlah bit yang terbuang per kunci.

Dengan menganalisis kurva trade-off, peneliti dapat mengetahui waktu tercepat untuk tabel hash yang menggunakan sejumlah ruang tertentu. Mereka juga dapat membalik pertanyaan untuk mengetahui ruang sekecil mungkin untuk waktu pengoperasian tertentu. Biasanya, perubahan kecil pada satu variabel akan menyebabkan perubahan kecil pada variabel lainnya, katanya William Kuszmaul, seorang ilmuwan komputer teoretis di Harvard dan salah satu penulis makalah tahun 2022. “Jika Anda menggandakan waktu, mungkin Anda akan mengurangi separuh jumlah bit yang terbuang per kunci.”

Namun tidak demikian halnya dengan tabel hash yang mereka rancang. “Jika Anda menambah waktu sedikit, bit yang terbuang per kunci akan berkurang secara eksponensial,” kata Kuszmaul. Kurva trade-off sangat curam, sehingga benar-benar di luar grafik.

Tim membuat tabel hash mereka dalam dua bagian. Mereka memiliki struktur data primer, di mana item disimpan tanpa ada bagian yang terbuang sama sekali, dan struktur data sekunder, yang membantu permintaan kueri menemukan item yang dicarinya. Meskipun kelompok tersebut tidak menemukan gagasan tentang struktur data sekunder, mereka membuat penemuan penting yang memungkinkan tabel hash hiperefisien mereka: Efisiensi memori keseluruhan struktur bergantung pada bagaimana struktur utama mengatur item yang disimpan.

Ide dasarnya adalah bahwa setiap item dalam struktur utama memiliki lokasi penyimpanan pilihan — lokasi terbaik, terbaik kedua, terbaik ketiga, dan seterusnya. Jika suatu item berada pada posisi terbaiknya, nomor 1 ditempelkan padanya, dan nomor tersebut disimpan dalam struktur data sekunder. Menanggapi kueri, struktur sekunder hanya menyediakan angka 1, yang menguraikan lokasi pasti item di struktur utama.

Jika item berada di posisi terbaik ke-100, struktur data sekunder akan melampirkan angka 100. Dan karena sistem menggunakan biner, maka angka 100 direpresentasikan sebagai 1100100. Tentu saja, dibutuhkan lebih banyak memori untuk menyimpan angka 1100100 daripada 1 — nomor yang ditetapkan ke suatu item saat item tersebut berada di tempat terbaik. Perbedaan seperti itu menjadi signifikan jika Anda menyimpan, katakanlah, jutaan item.

Jadi tim menyadari bahwa jika Anda terus-menerus memindahkan item dalam struktur data primer ke lokasi yang lebih disukai, Anda dapat mengurangi secara signifikan memori yang digunakan oleh struktur sekunder tanpa harus menambah waktu kueri.

“Sebelum pekerjaan ini dilakukan, tidak ada yang menyadari bahwa Anda dapat memampatkan struktur data lebih lanjut dengan memindahkan informasi,” kata Pagh. “Itulah wawasan besar dari makalah Bender.”

Para penulis menunjukkan bahwa penemuan mereka menetapkan batas atas baru untuk tabel hash paling efisien, yang berarti bahwa ini adalah struktur data terbaik yang pernah dirancang dalam hal efisiensi waktu dan ruang. Namun masih ada kemungkinan bahwa orang lain mungkin akan melakukan yang lebih baik lagi.

Pasti Sukses

Tahun berikutnya, tim dipimpin oleh Huacheng Yu, seorang ilmuwan komputer di Universitas Princeton, mencoba memperbaiki tabel hash tim Bender. “Kami bekerja sangat keras dan tidak bisa melakukannya,” kata Renfei Zhou, seorang mahasiswa di Universitas Tsinghua di Beijing dan anggota tim Yu. “Saat itulah kami curiga bahwa batas atas mereka [juga] adalah batas bawah” – hal terbaik yang mungkin bisa dicapai. “Ketika batas atas sama dengan batas bawah, permainan berakhir, dan Anda sudah mendapatkan jawabannya.” Tidak peduli seberapa pintar Anda, tidak ada tabel hash yang lebih baik.

Tim Yu menggunakan strategi baru untuk mengetahui apakah firasat itu benar dengan menghitung batas bawah dari prinsip pertama. Pertama, mereka beralasan bahwa untuk melakukan penyisipan atau penghapusan, tabel hash — atau, struktur data apa pun — harus mengakses memori komputer beberapa kali. Jika mereka dapat mengetahui berapa kali minimum yang diperlukan untuk tabel hash yang hemat ruang, mereka dapat mengalikannya dengan waktu yang diperlukan untuk setiap akses (sebuah konstanta), sehingga memberikan batas bawah pada runtime.

Namun jika mereka tidak mengetahui apa pun tentang tabel hash (kecuali tabel hash yang hemat ruang), bagaimana para peneliti dapat mengetahui jumlah minimum waktu yang diperlukan untuk mengakses memori? Mereka memperolehnya murni dari teori, dengan menggunakan bidang yang tampaknya tidak berhubungan yang disebut teori kompleksitas komunikasi, yang mempelajari berapa banyak bit yang diperlukan untuk menyampaikan informasi antara dua pihak. Pada akhirnya, tim tersebut berhasil: Mereka mengetahui berapa kali struktur data harus mengakses memorinya per operasi.

Ini adalah pencapaian utama mereka. Mereka kemudian dapat menetapkan batas bawah runtime untuk tabel hash yang hemat ruang. Dan mereka melihat bahwa tabel tersebut sama persis dengan tabel hash Bender. “Kami pikir [pada awalnya] hal ini dapat ditingkatkan,” kata Zhou. “Ternyata kami salah.” Hal ini berarti masalah Peterson akhirnya terselesaikan.

Selain menjawab pertanyaan yang sudah berumur puluhan tahun, Kuszmaul mengatakan, hal yang menakjubkan tentang bukti Yu adalah sifatnya yang bersifat umum. “Batas bawahnya berlaku untuk semua kemungkinan struktur data, termasuk struktur data yang belum ditemukan.” Artinya, tidak ada metode penyimpanan data yang dapat mengalahkan tabel hash Bender dalam hal memori dan kecepatan.

Hashing Ke Masa Depan

Meskipun tabel hash baru memiliki efisiensi yang belum pernah terjadi sebelumnya, kemungkinan besar tidak akan ada yang mencoba membuatnya dalam waktu dekat. Itu terlalu rumit untuk dibangun. “Algoritme yang cepat secara teori belum tentu cepat dalam praktiknya,” kata Zhou.

Bukan hal yang aneh jika kesenjangan antara teori dan praktik bertahan dalam jangka waktu lama, kata Kuszmaul, karena para ahli teori cenderung mengabaikan faktor-faktor yang konstan. Waktu yang diperlukan untuk melakukan suatu operasi biasanya dikalikan dengan suatu angka, suatu konstanta yang nilai pastinya mungkin tidak penting dari sudut pandang teoritis. “Namun dalam praktiknya, konstanta sangat penting,” katanya. “Di dunia nyata, faktor 10 adalah akhir dari permainan.”

Tabel hash yang sebenarnya masih mengalami peningkatan secara material, meskipun masih jauh dari ideal teoritis. Misalnya, tabel hash baru disebut gunung esHT, yang dibangun oleh Bender, Kuszmaul dan lainnya, jauh lebih baik dari pendahulunya. Menurut Kuszmaul, tabel ini dua kali lebih cepat dari tabel hash paling hemat ruang yang tersedia saat ini, dan menggunakan ruang tiga kali lebih sedikit dibandingkan tabel hash tercepat.

Mitzenmacher berharap bahwa hasil tahun 2023 akan segera memberikan manfaat lain: “Setiap kali Anda mendapatkan batas bawah baru – terutama yang melibatkan beberapa teknik baru – selalu ada harapan bahwa Anda dapat menggunakannya … untuk masalah terkait.”

Ada juga kepuasan intelektual yang didapat karena mengetahui bahwa Anda telah memecahkan masalah yang sulit dan sudah berlangsung lama, kata ilmuwan komputer tersebut Piotr Indyk dari Institut Teknologi Massachusetts. “Setelah Anda yakin bahwa struktur data tertentu tidak dapat diperbaiki, hal itu dapat membantu memfokuskan upaya penelitian.” Terakhir, peneliti data dapat mengalihkan perhatian mereka dari tantangan Peterson dan fokus pada masalah baru dalam ilmu komputer teoretis, yang tidak ada kekurangannya.