นักวิทยาศาสตร์พบความสมดุลที่เหมาะสมของการจัดเก็บข้อมูลและเวลา | นิตยสารควอนต้า

ประมาณ 70 ปีที่แล้ว วิศวกรของ IBM ชื่อ Hans Peter Luhn ได้เปลี่ยนหลักสูตรวิทยาการคอมพิวเตอร์อย่างเงียบๆ Luhn ถือสิทธิบัตรหลายฉบับแล้ว ซึ่งรวมถึงสิทธิบัตรสำหรับอุปกรณ์ที่สามารถวัดจำนวนเส้นด้ายของผ้าได้ และอีกสิทธิบัตรหนึ่งสำหรับแนวทางที่กำหนดว่าเครื่องดื่มผสมชนิดใดที่คุณสามารถผลิตได้จากส่วนผสมในห้องครัวของคุณ แต่ในรายงานภายในของ IBM เมื่อปี 1953 เขาเสนอเทคนิคใหม่ในการจัดเก็บและเรียกค้นข้อมูลที่ปัจจุบันรวมอยู่ในระบบคอมพิวเตอร์แทบทุกระบบ นั่นก็คือ ตารางแฮช

ตารางแฮชเป็นคลาสหลักของโครงสร้างข้อมูล พวกเขาเสนอวิธีที่สะดวกเป็นพิเศษในการเข้าถึงและแก้ไขข้อมูลในฐานข้อมูลขนาดใหญ่ แต่เทคโนโลยีนี้มาพร้อมกับการแลกเปลี่ยนที่หลีกเลี่ยงไม่ได้

ใน 1957 กระดาษ ตีพิมพ์ใน วารสารวิจัยและพัฒนาไอบีเอ็มW. Wesley Peterson ระบุความท้าทายทางเทคนิคหลักที่ทำให้เกิดตารางแฮช นั่นคือ ตารางแฮชต้องรวดเร็ว ซึ่งหมายความว่าสามารถดึงข้อมูลที่จำเป็นได้อย่างรวดเร็ว แต่ต้องมีขนาดกะทัดรัดด้วย โดยใช้หน่วยความจำน้อยที่สุดเท่าที่จะเป็นไปได้ วัตถุประสงค์แฝดเหล่านี้โดยพื้นฐานแล้วขัดแย้งกัน การเข้าถึงและแก้ไขฐานข้อมูลสามารถทำได้รวดเร็วยิ่งขึ้นเมื่อตารางแฮชมีหน่วยความจำมากขึ้น และการดำเนินการจะช้าลงในตารางแฮชที่ใช้พื้นที่น้อยลง นับตั้งแต่ปีเตอร์สันวางความท้าทายนี้ นักวิจัยได้พยายามค้นหาสมดุลที่ดีที่สุดระหว่างเวลาและสถานที่

ในปัจจุบัน นักวิทยาศาสตร์คอมพิวเตอร์ได้พิสูจน์ทางคณิตศาสตร์แล้วว่า พวกเขาพบข้อแลกเปลี่ยนที่เหมาะสมที่สุดแล้ว วิธีแก้ปัญหามาจากก คู่ ล่าสุด เอกสาร ที่เติมเต็มซึ่งกันและกัน “เอกสารเหล่านี้ช่วยตอบคำถามเปิดที่มีมายาวนานเกี่ยวกับการแลกเปลี่ยนกาล-อวกาศที่ดีที่สุดเท่าที่จะเป็นไปได้ ซึ่งให้ผลลัพธ์ที่น่าประหลาดใจอย่างยิ่งซึ่งผมคาดว่าจะส่งผลกระทบอย่างมีนัยสำคัญในหลายปีต่อจากนี้” กล่าว ไมเคิล มิทเซนมาเคอร์นักวิทยาศาสตร์คอมพิวเตอร์แห่งมหาวิทยาลัยฮาร์วาร์ดซึ่งไม่ได้เกี่ยวข้องกับการศึกษาทั้งสองเรื่อง

“ฉันจะบอกว่ามันเป็นเรื่องใหญ่อย่างแน่นอน” กล่าวเสริม ราสมุส ปาห์นักวิทยาศาสตร์คอมพิวเตอร์แห่งมหาวิทยาลัยโคเปนเฮเกน “ผู้คนจำนวนมากได้แก้ไขปัญหานี้แล้ว โดยพยายามดูว่าคุณสามารถบีบพื้นที่ได้มากเพียงใด ขณะเดียวกันก็มีการดำเนินงานที่ประหยัดเวลาด้วย นี่คือสิ่งที่ฉันอยากจะแก้ไข”

ทำแฮชของมัน

ตารางแฮชเป็นหนึ่งในโครงสร้างข้อมูลที่เก่าแก่ ง่ายที่สุด เร็วที่สุด และใช้กันอย่างแพร่หลายที่สุดในปัจจุบัน ได้รับการออกแบบมาเพื่อดำเนินการพื้นฐานสามประการ ได้แก่ การแทรกซึ่งเพิ่มรายการใหม่ลงในฐานข้อมูล แบบสอบถามซึ่งเข้าถึงรายการหรือตรวจสอบเพื่อดูว่ามีอยู่หรือไม่ และการลบ ตารางแฮชอาจเป็นเพียงชั่วคราว โดยจะมีอยู่ตราบใดที่โปรแกรมใดรันอยู่ หรืออาจเป็นส่วนถาวรของระบบปฏิบัติการของคอมพิวเตอร์ของคุณ เว็บเบราว์เซอร์ เช่น Chrome หรือ Safari อาจมีตารางแฮชในตัวหลายตารางซึ่งมีจุดประสงค์เพื่อติดตามข้อมูลประเภทต่างๆ

รายการในตารางแฮชจะถูกจัดเก็บเป็นคู่ โดยรายการซึ่งเป็นตัวข้อมูลเองจะเชื่อมต่อกับคีย์ที่ระบุข้อมูล เสียบคีย์เข้ากับอัลกอริทึมการสืบค้นของตารางแฮช แล้วระบบจะนำคุณไปยังรายการโดยตรง สิ่งนี้อาจฟังดูไม่พิเศษนัก แต่สำหรับฐานข้อมูลขนาดใหญ่ อาจช่วยประหยัดเวลาได้มาก

หากต้องการยกตัวอย่างที่ง่ายมาก ลองพิจารณา Oxford English Dictionary ซึ่งมีคำจำกัดความมากกว่า 600,000 คำ หากฉบับดิจิทัลอาศัยตารางแฮช คุณสามารถใช้คำที่กำหนดเป็นคีย์และดำเนินการตรงไปยังคำจำกัดความได้ หากไม่มีตารางแฮช พจนานุกรมก็น่าจะอาศัยกลไกการค้นหาที่ช้ากว่ามาก โดยใช้กระบวนการตัดออกเพื่อมาบรรจบกันในคำจำกัดความที่ร้องขอในที่สุด และในขณะที่ตารางแฮชสามารถค้นหาคำใดๆ ในระยะเวลาคงที่ (โดยปกติจะเป็นเสี้ยววินาที) แต่เวลาในการค้นหาสำหรับวิธีอื่นๆ ก็สามารถเพิ่มขึ้นได้เมื่อจำนวนคำในพจนานุกรมเพิ่มขึ้น ตารางแฮชยังมีข้อดีอีกประการหนึ่ง นั่นคือ สามารถทำให้พจนานุกรมมีความเคลื่อนไหว ทำให้ง่ายต่อการแทรกคำใหม่และลบคำที่ล้าสมัย

นักวิจัยใช้เวลาหลายทศวรรษในการสร้างตารางแฮชที่พยายามเพิ่มความเร็วและลดหน่วยความจำ ในศตวรรษที่ 20 แนวทางแก้ไขมีแนวโน้มที่จะให้ประโยชน์อย่างมากในแง่ เวลา หรือพื้นที่เพียงด้านเดียว จากนั้นในปี พ.ศ. 2003 นักวิจัย แสดงให้เห็นว่า ในทางทฤษฎีแล้วมันเป็นไปได้ที่จะเพิ่มประสิทธิภาพอย่างก้าวกระโดดครั้งใหญ่ทั้งในเวลาและสถานที่พร้อมกัน อย่างไรก็ตาม อาจต้องใช้เวลาอีกสองทศวรรษก่อนที่นักวิจัยจะค้นพบความสมดุลในอุดมคติระหว่างทั้งสอง

การสับเปลี่ยนข้อมูล

ก้าวสำคัญก้าวแรกสู่เป้าหมายนั้นเกิดขึ้นในปี 2022 ด้วยเวลาเฉลี่ย การประชุมใหญ่ด้านวิทยาการคอมพิวเตอร์ ในโรม. ที่นั่น ทีมงานได้เสนอตารางแฮชพร้อมฟีเจอร์ใหม่ๆ ที่สามารถผสมผสานเวลาและพื้นที่ได้อย่างมีประสิทธิภาพที่สุดเท่าที่เคยมีมา ผู้เขียนบทความคนแรก (เรียงตามตัวอักษร) คือ Michael Bender จาก Stony Brook University ดังนั้นจึงมักเรียกกันว่า Bender และคณะ ตารางแฮช แม้ว่าทีมงานไม่ได้พยายามสร้างตารางแฮชที่ใช้งานได้ แต่พวกเขาก็พิสูจน์ว่าตามหลักการแล้ว สามารถสร้างตารางแฮชตามคุณสมบัติที่พวกเขาอธิบายไว้ได้

เพื่อประเมินตารางแฮชที่พวกเขาคิดขึ้น กลุ่มได้สร้างเส้นโค้งการแลกเปลี่ยน ซึ่งเป็นกราฟที่วางแผนเวลาต่อการดำเนินการ (การแทรกหรือการลบ) บนแกนหนึ่ง และพื้นที่ที่หน่วยความจำใช้ในอีกแกนหนึ่ง แต่กราฟนี้กำหนดพื้นที่ด้วยวิธีพิเศษ: เนื่องจากวิธีการสร้างตารางแฮชจึงจำเป็นต้องมีหน่วยความจำมากกว่าพื้นที่ขั้นต่ำเปล่าที่จำเป็นในการจัดเก็บชุดรายการที่กำหนด นักวิทยาศาสตร์คอมพิวเตอร์เรียกพื้นที่พิเศษนี้ว่า "เศษขยะ" แม้ว่าจะไม่สูญเปล่าจริงๆ และจำเป็นบ้างก็ตาม แกนช่องว่างบนเส้นโค้งการแลกเปลี่ยนจะวัดจำนวนบิตที่เสียไปต่อคีย์

ด้วยการวิเคราะห์เส้นโค้งการแลกเปลี่ยน นักวิจัยสามารถคำนวณเวลาที่เร็วที่สุดเท่าที่จะเป็นไปได้สำหรับตารางแฮชที่ใช้พื้นที่ตามที่กำหนด พวกเขายังสามารถพลิกคำถามเพื่อหาพื้นที่ที่เล็กที่สุดเท่าที่จะเป็นไปได้สำหรับเวลาดำเนินการที่กำหนด โดยปกติแล้วการเปลี่ยนแปลงเล็กน้อยในตัวแปรตัวหนึ่งจะนำไปสู่การเปลี่ยนแปลงเล็กน้อยในอีกตัวแปรหนึ่ง กล่าว วิลเลียม คุสซ์มอลนักวิทยาศาสตร์คอมพิวเตอร์เชิงทฤษฎีที่ Harvard และเป็นผู้ร่วมเขียนรายงานประจำปี 2022 “ถ้าคุณเพิ่มเวลาเป็นสองเท่า บางทีคุณอาจลดจำนวนบิตที่เสียไปต่อคีย์ลงครึ่งหนึ่ง”

แต่นั่นไม่ใช่กรณีของตารางแฮชที่พวกเขาออกแบบ “ถ้าคุณเพิ่มเวลาอีกสักหน่อย บิตที่เสียไปต่อคีย์จะลดลงแบบทวีคูณ” Kuszmaul กล่าว เส้นโค้งการแลกเปลี่ยนนั้นชันมากจนไม่อยู่ในแผนภูมิเลย

ทีมงานสร้างตารางแฮชเป็นสองส่วน พวกเขามีโครงสร้างข้อมูลหลักซึ่งรายการต่างๆ จะถูกจัดเก็บโดยไม่มีบิตที่สูญเปล่าเลย และโครงสร้างข้อมูลรองซึ่งช่วยให้คำขอสืบค้นค้นหารายการที่ต้องการได้ แม้ว่ากลุ่มนี้จะไม่ได้คิดค้นแนวคิดเกี่ยวกับโครงสร้างข้อมูลรอง แต่พวกเขาก็ได้ค้นพบที่สำคัญซึ่งทำให้ตารางแฮชที่มีประสิทธิภาพสูงเป็นไปได้: ประสิทธิภาพหน่วยความจำโดยรวมของโครงสร้างขึ้นอยู่กับวิธีที่โครงสร้างหลักจัดเรียงรายการที่เก็บไว้

แนวคิดพื้นฐานคือทุกรายการในโครงสร้างหลักมีสถานที่จัดเก็บที่ต้องการ เช่น ตำแหน่งที่ดีที่สุด ตำแหน่งที่ดีที่สุดอันดับสอง อันดับสามที่ดีที่สุด และอื่นๆ หากรายการอยู่ในจุดที่ดีที่สุด หมายเลข 1 จะติดอยู่กับรายการนั้น และหมายเลขนั้นจะถูกจัดเก็บไว้ในโครงสร้างข้อมูลรอง เพื่อตอบแบบสอบถาม โครงสร้างรองจะให้เพียงหมายเลข 1 ซึ่งสะกดตำแหน่งที่แน่นอนของรายการในโครงสร้างหลัก

หากรายการอยู่ในจุดที่ดีที่สุดอันดับที่ 100 โครงสร้างข้อมูลรองจะแนบหมายเลข 100 และเนื่องจากระบบใช้ไบนารี จึงแทนหมายเลข 100 เป็น 1100100 แน่นอนว่าต้องใช้หน่วยความจำมากกว่าในการจัดเก็บหมายเลข 1100100 มากกว่า 1 — หมายเลขที่กำหนดให้กับรายการเมื่ออยู่ในจุดที่ดีที่สุด ความแตกต่างดังกล่าวจะมีความสำคัญหากคุณจัดเก็บสิ่งของนับล้านรายการ

ทีมงานจึงตระหนักว่าหากคุณย้ายรายการในโครงสร้างข้อมูลหลักไปยังตำแหน่งที่ต้องการมากขึ้นอย่างต่อเนื่อง คุณสามารถลดหน่วยความจำที่ใช้โดยโครงสร้างรองได้อย่างมากโดยไม่ต้องเพิ่มเวลาในการสืบค้น

“ก่อนงานนี้ ไม่มีใครรู้ว่าคุณสามารถบีบอัดโครงสร้างข้อมูลเพิ่มเติมได้โดยการย้ายข้อมูลไปรอบๆ” Pagh กล่าว “นั่นคือข้อมูลเชิงลึกที่สำคัญของรายงานของ Bender”

ผู้เขียนแสดงให้เห็นว่าสิ่งประดิษฐ์ของพวกเขาได้สร้างขอบเขตบนใหม่สำหรับตารางแฮชที่มีประสิทธิภาพสูงสุด ซึ่งหมายความว่ามันเป็นโครงสร้างข้อมูลที่ดีที่สุดที่คิดค้นขึ้นทั้งในด้านเวลาและพื้นที่อย่างมีประสิทธิภาพ แต่ความเป็นไปได้ยังคงอยู่ที่คนอื่นอาจทำได้ดีกว่านี้

ผูกพันกับความสำเร็จ

ปีหน้ามีทีมนำโดย หัวเฉิง หยูนักวิทยาศาสตร์คอมพิวเตอร์จากมหาวิทยาลัยพรินซ์ตัน พยายามปรับปรุงตารางแฮชของทีมเบนเดอร์ “เราทำงานหนักมากและไม่สามารถทำได้” กล่าว เหรินเฟย โจวนักศึกษาจากมหาวิทยาลัย Tsinghua ในกรุงปักกิ่ง และเป็นสมาชิกในทีมของ Yu “นั่นคือตอนที่เราสงสัยว่าขอบเขตบนของพวกเขาคือ [ด้วย] ขอบเขตล่าง” ซึ่งเป็นสิ่งที่ดีที่สุดที่สามารถทำได้ “เมื่อขอบเขตบนเท่ากับขอบเขตล่าง เกมจะจบลง และคุณจะได้คำตอบ” ไม่ว่าคุณจะฉลาดแค่ไหน ไม่มีตารางแฮชใดที่ทำได้ดีกว่านี้อีกแล้ว

ทีมงานของ Yu ใช้กลยุทธ์ใหม่เพื่อค้นหาว่าลางสังหรณ์นั้นถูกต้องหรือไม่โดยการคำนวณขอบเขตล่างจากหลักการแรก ประการแรก พวกเขาให้เหตุผลว่าในการแทรกหรือลบ ตารางแฮช หรือโครงสร้างข้อมูลใดๆ จะต้องเข้าถึงหน่วยความจำของคอมพิวเตอร์หลายครั้ง หากพวกเขาสามารถทราบจำนวนครั้งขั้นต่ำที่จำเป็นสำหรับตารางแฮชที่มีประสิทธิภาพด้านพื้นที่ พวกเขาสามารถคูณด้วยเวลาที่ต้องการต่อการเข้าถึง (ค่าคงที่) ทำให้มีขอบเขตล่างของรันไทม์

แต่ถ้าพวกเขาไม่รู้อะไรเกี่ยวกับตารางแฮช (ยกเว้นว่ามันประหยัดพื้นที่) นักวิจัยจะทราบจำนวนครั้งขั้นต่ำที่จำเป็นในการเข้าถึงหน่วยความจำได้อย่างไร พวกเขาได้มาจากทฤษฎีล้วนๆ โดยใช้สาขาที่ดูเหมือนไม่เกี่ยวข้องกันที่เรียกว่าทฤษฎีความซับซ้อนของการสื่อสาร ซึ่งศึกษาจำนวนบิตที่ต้องใช้ในการถ่ายทอดข้อมูลระหว่างทั้งสองฝ่าย ในที่สุด ทีมงานก็ประสบความสำเร็จ: พวกเขาค้นพบว่าโครงสร้างข้อมูลต้องเข้าถึงหน่วยความจำกี่ครั้งต่อการดำเนินการ

นี่คือความสำเร็จที่สำคัญของพวกเขา จากนั้นพวกเขาก็สามารถสร้างขอบเขตล่างของรันไทม์สำหรับตารางแฮชที่ประหยัดพื้นที่ได้ และพวกเขาเห็นว่ามันตรงกับตารางแฮชของ Bender ทุกประการ “เราคิดว่า [ตอนแรก] มันสามารถปรับปรุงได้” โจวกล่าว “ปรากฎว่าเราคิดผิด” นั่นหมายความว่าในที่สุดปัญหาของ Peterson ก็ได้รับการแก้ไขแล้ว

นอกเหนือจากการตอบคำถามที่มีมานานหลายทศวรรษแล้ว Kuszmaul ยังกล่าวอีกว่า สิ่งที่น่าทึ่งเกี่ยวกับการพิสูจน์ Yu ก็คือลักษณะทั่วไปของมัน “ขอบเขตล่างใช้กับโครงสร้างข้อมูลที่เป็นไปได้ทั้งหมด รวมถึงโครงสร้างที่ยังไม่ได้ถูกประดิษฐ์ขึ้นด้วย” นั่นหมายความว่าไม่มีวิธีการจัดเก็บข้อมูลใดที่สามารถเอาชนะตารางแฮชของ Bender ในแง่ของหน่วยความจำและความเร็วได้

ก้าวไปสู่อนาคต

แม้ว่าตารางแฮชใหม่จะมีประสิทธิภาพอย่างที่ไม่เคยมีมาก่อน แต่ก็ไม่มีใครมีแนวโน้มที่จะลองสร้างมันขึ้นมาในเร็วๆ นี้ มันซับซ้อนเกินไปที่จะสร้าง “อัลกอริทึมที่เร็วในทางทฤษฎีไม่จำเป็นต้องเร็วในทางปฏิบัติ” โจวกล่าว

ไม่ใช่เรื่องแปลกที่ช่องว่างระหว่างทฤษฎีและการปฏิบัติจะคงอยู่เป็นเวลานาน Kuszmaul กล่าว เนื่องจากนักทฤษฎีมักจะเพิกเฉยต่อปัจจัยคงที่ โดยทั่วไปเวลาที่ใช้ในการดำเนินการจะคูณด้วยตัวเลข ค่าคงที่บางตัวซึ่งค่าที่แน่นอนอาจไม่มีความหมายจากมุมมองทางทฤษฎี “แต่ในทางปฏิบัติ ค่าคงที่มีความสำคัญจริงๆ” เขากล่าว “ในโลกแห่งความเป็นจริง ปัจจัย 10 คือการสิ้นสุดเกม”

ตารางแฮชที่แท้จริงยังคงมีการปรับปรุงในด้านวัตถุ แม้ว่าจะยังขาดอุดมคติทางทฤษฎีก็ตาม ตัวอย่างเช่นตารางแฮชใหม่ที่เรียกว่า ภูเขาน้ำแข็งHTซึ่งสร้างโดย Bender, Kuszmaul และคนอื่นๆ นั้นดีกว่ารุ่นก่อนมาก จากข้อมูลของ Kuszmaul มันเร็วเป็นสองเท่าของตารางแฮชที่ประหยัดพื้นที่มากที่สุดในปัจจุบัน และใช้พื้นที่น้อยกว่าตารางแฮชที่เร็วที่สุดถึงสามเท่า

Mitzenmacher หวังว่าผลลัพธ์ในปี 2023 อาจให้ประโยชน์อีกประเภทหนึ่งในไม่ช้า: “เมื่อใดก็ตามที่คุณได้รับขอบเขตล่างใหม่ — โดยเฉพาะอย่างยิ่งที่เกี่ยวข้องกับเทคนิคใหม่ — มีความหวังอยู่เสมอว่าคุณจะใช้มัน … สำหรับปัญหาที่เกี่ยวข้อง”

นอกจากนี้ยังมีความพึงพอใจทางปัญญาที่มาจากการรู้ว่าคุณได้แก้ไขปัญหาที่ยากและยาวนานแล้ว นักวิทยาศาสตร์คอมพิวเตอร์กล่าว ปิโอเตอร์ อินดี้ ของสถาบันเทคโนโลยีแมสซาชูเซตส์ “เมื่อคุณแน่ใจว่าโครงสร้างข้อมูลบางอย่างไม่สามารถปรับปรุงได้ นั่นสามารถช่วยมุ่งเน้นความพยายามในการวิจัยได้” ในที่สุด นักวิจัยข้อมูลสามารถหันเหความสนใจไปจากความท้าทายของ Peterson และมุ่งเน้นไปที่ปัญหาใหม่ในวิทยาการคอมพิวเตอร์เชิงทฤษฎี ซึ่งไม่มีปัญหาการขาดแคลน