العلماء يجدون التوازن الأمثل لتخزين البيانات والوقت | مجلة كوانتا

منذ حوالي 70 عامًا، قام مهندس في شركة IBM يُدعى هانز بيتر لون بتغيير مسار علوم الكمبيوتر بهدوء. حصل Luhn بالفعل على العديد من براءات الاختراع، بما في ذلك واحدة لجهاز يمكنه قياس عدد خيوط القماش وأخرى لدليل يحدد المشروبات المختلطة التي يمكنك صنعها من المكونات الموجودة في مطبخك. ولكن في بحث داخلي لشركة IBM عام 1953، اقترح تقنية جديدة لتخزين واسترجاع المعلومات التي تم دمجها الآن في جميع الأنظمة الحسابية تقريبًا: جدول التجزئة.

تعد جداول التجزئة فئة رئيسية من هياكل البيانات. إنها توفر طريقة ملائمة بشكل خاص للوصول إلى المعلومات وتعديلها في قواعد البيانات الضخمة. لكن هذه التكنولوجيا تأتي مع مقايضة لا مفر منها.

في 1957 ورقة نشرت في مجلة آي بي إم للبحث والتطوير، حدد دبليو ويسلي بيترسون التحدي الفني الرئيسي الذي تطرحه جداول التجزئة: يجب أن تكون سريعة، مما يعني أنها تستطيع استرجاع المعلومات الضرورية بسرعة. ولكنها تحتاج أيضًا إلى أن تكون مدمجة، بحيث تستخدم أقل قدر ممكن من الذاكرة. وهذان الهدفان التوأم متعارضان بشكل أساسي. يمكن الوصول إلى قاعدة البيانات وتعديلها بسرعة أكبر عندما يحتوي جدول التجزئة على ذاكرة أكبر؛ وتصبح العمليات أبطأ في جداول التجزئة التي تستخدم مساحة أقل. منذ أن طرح بيترسون هذا التحدي، حاول الباحثون إيجاد أفضل توازن بين الزمان والمكان.

لقد أثبت علماء الكمبيوتر الآن رياضيًا أنهم وجدوا المقايضة المثلى. الحل جاء من أ زوج الأخيرة أوراق التي تكمل بعضها البعض. وقال: "تحل هذه الأبحاث السؤال المفتوح طويل الأمد حول أفضل المفاضلات الممكنة بين الزمكان، مما يؤدي إلى نتائج مفاجئة للغاية أتوقع أن يكون لها تأثير كبير لسنوات عديدة قادمة". مايكل ميتسنماخر، عالم كمبيوتر في جامعة هارفارد ولم يشارك في أي من الدراستين.

وأضاف: "أود بالتأكيد أن أقول إنها صفقة كبيرة". راسموس باغ، عالم الكمبيوتر في جامعة كوبنهاجن. "لقد عمل الكثير من الأشخاص على هذه المشكلة، محاولين معرفة مقدار ما يمكنك ضغطه من مساحة، مع إجراء عمليات فعالة من حيث الوقت أيضًا. هذا هو الأمر الذي كنت أرغب في حله."

صنع تجزئة منه

تعد جداول التجزئة من بين أقدم وأبسط وأسرع هياكل البيانات وأكثرها استخدامًا اليوم. لقد تم تصميمها لتنفيذ ثلاث عمليات أساسية: عمليات الإدراج، التي تضيف عناصر جديدة إلى قاعدة البيانات؛ الاستعلامات، التي تصل إلى عنصر ما أو تتحقق لمعرفة ما إذا كان موجودًا؛ والحذف. يمكن أن يكون جدول التجزئة سريع الزوال — موجود فقط طالما كان برنامج معين قيد التشغيل — أو يمكن أن يكون جزءًا دائمًا من نظام تشغيل الكمبيوتر الخاص بك. قد يحتوي متصفح الويب مثل Chrome أو Safari على عدة جداول تجزئة مدمجة تهدف إلى تتبع أنواع مختلفة من البيانات.

يتم تخزين الإدخالات في جدول التجزئة كأزواج، مع توصيل العنصر - المعلومات نفسها - بمفتاح يحدد المعلومات. قم بتوصيل مفتاح في خوارزمية استعلام جدول التجزئة، وسيأخذك مباشرة إلى العنصر. قد لا يبدو هذا أمرًا استثنائيًا، لكنه يمكن أن يوفر الكثير من الوقت بالنسبة لقواعد البيانات الضخمة.

لنأخذ مثالاً مبسطًا للغاية، لنأخذ قاموس أكسفورد الإنجليزي، الذي يحتوي على تعريفات لأكثر من 600,000 ألف كلمة. إذا كان الإصدار الرقمي يعتمد على جدول التجزئة، فيمكنك ببساطة استخدام كلمة معينة كمفتاح والمتابعة مباشرة إلى التعريف. بدون جدول التجزئة، من المرجح أن يعتمد القاموس على آلية بحث أبطأ بكثير، وذلك باستخدام عملية الحذف للتقارب في النهاية مع التعريف المطلوب. وبينما يمكن لجدول التجزئة العثور على أي كلمة في فترة زمنية ثابتة (عادةً جزء صغير من الثانية)، فإن وقت البحث عن طرق أخرى يمكن أن يرتفع مع زيادة عدد الكلمات في القاموس. يوفر جدول التجزئة أيضًا ميزة أخرى: يمكنه الحفاظ على ديناميكية القاموس، مما يجعل من السهل إدراج كلمات جديدة وحذف الكلمات القديمة.

لقد أمضى الباحثون عقودًا من الزمن في بناء جداول التجزئة التي تحاول زيادة السرعة وتقليل الذاكرة. في القرن العشرين، كانت الحلول تميل إلى تقديم مكاسب كبيرة في جانب واحد فقط، أو الزمان أو المكان. ثم في عام 20، الباحثون أظهرت أنه كان من الممكن نظريًا تحقيق قفزة كبيرة في الكفاءة في الزمان والمكان في وقت واحد. ومع ذلك، سيستغرق الأمر عقدين آخرين حتى يتمكن الباحثون من اكتشاف التوازن المثالي بين الاثنين.

خلط البيانات

جاءت الخطوة الرئيسية الأولى نحو هذا الهدف في عام 2022 عند أ المؤتمر الرئيسي لعلوم الكمبيوتر في روما. هناك، اقترح الفريق جدول تجزئة بميزات جديدة يمكن أن توفر أفضل مزيج من كفاءة الوقت والمساحة على الإطلاق. المؤلف الأول لهذه الورقة (المدرجة أبجديًا) هو مايكل بندر من جامعة ستوني بروك، لذلك يشار إليها عادة باسم بندر وآخرون. جدول التجزئة. على الرغم من أن الفريق لم يحاول بناء جدول تجزئة فعال، إلا أنه أثبت أنه من الممكن، من حيث المبدأ، أن يتم إنشاؤه بالميزات التي وصفوها.

ولتقييم جدول التجزئة الذي توصلوا إليه، أنتجت المجموعة منحنى مقايضة - رسم بياني يرسم الوقت لكل عملية (الإدراج أو الحذف) على محور واحد والمساحة التي تشغلها الذاكرة على المحور الآخر. لكن هذا الرسم البياني يحدد المساحة بطريقة خاصة: نظرًا لكيفية إنشائها، تحتاج جداول التجزئة إلى ذاكرة أكبر من مجرد الحد الأدنى المطلوب لتخزين مجموعة معينة من العناصر. يطلق علماء الكمبيوتر على هذه المساحة الإضافية اسم "البتات الضائعة"، على الرغم من أنها ليست مهدرة بالفعل، بل إنها ضرورية إلى حد ما. يقيس المحور الفضائي على منحنى المقايضة عدد البتات الضائعة لكل مفتاح.

من خلال تحليل منحنى المقايضة، يمكن للباحثين معرفة أسرع وقت ممكن لجدول التجزئة الذي يستخدم مقدارًا معينًا من المساحة. يمكنهم أيضًا قلب السؤال لمعرفة أصغر مساحة ممكنة لفترة تشغيل معينة. وقال عادة، تغيير بسيط في أحد المتغيرات يؤدي إلى تغيير صغير في الآخر وليام كوزمول، عالم كمبيوتر نظري في جامعة هارفارد ومؤلف مشارك لورقة 2022. "إذا قمت بمضاعفة الوقت، فربما ستخفض عدد البتات الضائعة لكل مفتاح إلى النصف."

ولكن هذا ليس هو الحال مع جدول التجزئة الذي صمموه. وقال كوزماول: "إذا قمت بزيادة الوقت قليلاً، فإن البتات الضائعة لكل مفتاح تنخفض بشكل كبير". كان منحنى المقايضة حادًا للغاية، وكان حرفيًا خارج المخططات.

قام الفريق ببناء جدول التجزئة الخاص بهم في جزأين. كان لديهم بنية بيانات أساسية، حيث يتم تخزين العناصر دون أي بتات ضائعة على الإطلاق، وبنية بيانات ثانوية، مما يساعد طلب الاستعلام في العثور على العنصر الذي يبحث عنه. على الرغم من أن المجموعة لم تخترع فكرة بنية البيانات الثانوية، إلا أنهم توصلوا إلى اكتشاف مهم جعل جدول التجزئة عالي الكفاءة ممكنًا: تعتمد كفاءة الذاكرة الإجمالية للبنية على كيفية ترتيب البنية الأساسية لعناصرها المخزنة.

الفكرة الأساسية هي أن كل عنصر في البنية الأساسية له مواقع تخزين مفضلة - موقع أفضل، وثاني أفضل موقع، وثالث أفضل، وما إلى ذلك. إذا كان العنصر في أفضل مكان له، فسيتم لصق الرقم 1 عليه، ويتم تخزين هذا الرقم في بنية البيانات الثانوية. ردًا على استعلام، توفر البنية الثانوية الرقم 1 فقط، والذي يوضح الموقع الدقيق للعنصر في البنية الأساسية.

إذا كان العنصر في أفضل 100 مكان له، فإن بنية البيانات الثانوية تقوم بإرفاق الرقم 100. ولأن النظام يستخدم النظام الثنائي، فإنه يمثل الرقم 100 كـ 1100100. ويتطلب الأمر ذاكرة أكبر، بالطبع، لتخزين الرقم 1100100 أكثر من 1 — الرقم المخصص للعنصر عندما يكون في أفضل مكان. تصبح الاختلافات من هذا القبيل كبيرة إذا كنت تقوم بتخزين مليون عنصر على سبيل المثال.

لذلك أدرك الفريق أنه إذا قمت باستمرار بنقل العناصر الموجودة في بنية البيانات الأساسية إلى مواقعها المفضلة، فيمكنك تقليل الذاكرة التي تستهلكها البنية الثانوية بشكل كبير دون الحاجة إلى زيادة أوقات الاستعلام.

وقال باغ: "قبل هذا العمل، لم يكن أحد يدرك أنه يمكنك زيادة ضغط بنية البيانات عن طريق نقل المعلومات". "كانت تلك هي الفكرة الرئيسية لورقة بندر."

أظهر المؤلفون أن اختراعهم أنشأ حدًا أعلى جديدًا لجداول التجزئة الأكثر كفاءة، مما يعني أنه كان أفضل بنية بيانات تم ابتكارها حتى الآن من حيث كفاءة الزمان والمكان. ولكن يظل هناك احتمال أن يقوم شخص آخر بأداء أفضل.

ملزمة بالنجاح

وفي العام التالي، فريق بقيادة هواتشنغ يوحاول عالم الكمبيوتر في جامعة برينستون تحسين جدول التجزئة الخاص بفريق بندر. وقال: "لقد عملنا بجد ولم نتمكن من القيام بذلك". رينفي تشو، طالب في جامعة تسينغهوا في بكين وعضو في فريق يو. "وعندها شككنا في أن الحد الأعلى كان [أيضًا] الحد الأدنى" - وهو أفضل ما يمكن تحقيقه. "عندما يساوي الحد الأعلى الحد الأدنى، تنتهي اللعبة، ولديك إجابتك." بغض النظر عن مدى ذكائك، لا يمكن لأي جدول تجزئة أن يقوم بعمل أفضل.

استخدم فريق يو استراتيجية جديدة لمعرفة ما إذا كان هذا الحدس صحيحًا عن طريق حساب الحد الأدنى من المبادئ الأولى. أولاً، اعتقدوا أنه لإجراء عملية إدراج أو حذف، يجب أن يصل جدول التجزئة - أو أي بنية بيانات - إلى ذاكرة الكمبيوتر عدة مرات. إذا تمكنوا من معرفة الحد الأدنى لعدد المرات اللازمة لجدول التجزئة الموفر للمساحة، فيمكنهم مضاعفة ذلك في الوقت المطلوب لكل وصول (ثابت)، مما يمنحهم حدًا أدنى في وقت التشغيل.

ولكن إذا لم يكونوا يعرفون أي شيء عن جدول التجزئة (باستثناء أنه موفر للمساحة)، فكيف يمكن للباحثين معرفة الحد الأدنى لعدد المرات المطلوبة للوصول إلى الذاكرة؟ لقد اشتقوها من النظرية بحتة، باستخدام مجال يبدو غير ذي صلة يسمى نظرية تعقيد الاتصالات، والذي يدرس عدد البتات المطلوبة لنقل المعلومات بين طرفين. في النهاية، نجح الفريق: فقد اكتشفوا عدد المرات التي يجب أن تصل فيها بنية البيانات إلى ذاكرتها في كل عملية.

وكان هذا إنجازهم الرئيسي. وتمكنوا بعد ذلك من إنشاء حد أدنى في وقت التشغيل لأي جدول تجزئة موفر للمساحة. ورأوا أنه يطابق جدول تجزئة بندر تمامًا. قال تشو: "اعتقدنا [في البداية] أنه يمكن تحسين الأمر". "اتضح أننا كنا مخطئين." وهذا بدوره يعني أن مشكلة بيترسون قد تم حلها أخيرًا.

وقال كوسزماول إنه إلى جانب الإجابة على السؤال المستمر منذ عقود، فإن الشيء المدهش في دليل يو هو عموميته. "ينطبق الحد الأدنى على جميع هياكل البيانات الممكنة، بما في ذلك تلك التي لم يتم اختراعها بعد." وهذا يعني أنه لا توجد طريقة لتخزين البيانات يمكنها التغلب على جدول تجزئة Bender من حيث الذاكرة والسرعة.

التجزئة في المستقبل

على الرغم من الكفاءة غير المسبوقة لجدول التجزئة الجديد، فمن غير المرجح أن يحاول أحد بنائه في أي وقت قريب. إنها معقدة للغاية في البناء. قال تشو: "إن الخوارزمية السريعة من الناحية النظرية ليست بالضرورة سريعة من الناحية العملية".

وقال كوزمول إنه ليس من غير المألوف أن تستمر مثل هذه الفجوات بين النظرية والتطبيق لفترة طويلة، لأن المنظرين يميلون إلى تجاهل العوامل الثابتة. عادةً ما يتم ضرب الوقت الذي يستغرقه إجراء عملية ما برقم، وقد تكون قيمته الدقيقة غير مهمة من وجهة النظر النظرية. وأضاف: "لكن من الناحية العملية، الثوابت مهمة حقًا". "في العالم الحقيقي، العامل 10 هو نهاية اللعبة."

لا تزال جداول التجزئة الفعلية تتحسن بطرق مادية، حتى لو كانت أقل بكثير من المثالية النظرية. على سبيل المثال، يسمى جدول التجزئة الجديد جبل الجليدHT، التي بناها بندر وكوزماول وآخرون، أفضل بكثير من سابقاتها. وفقًا لكوسزماول، فهو أسرع بمرتين من جدول التجزئة الأكثر كفاءة في المساحة المتاح اليوم، ويستخدم مساحة أقل بثلاث مرات من أسرع جدول تجزئة.

ويأمل ميتزنماخر أن تسفر نتيجة 2023 قريبا عن نوع آخر من الفوائد: "كلما حصلت على حد أدنى جديد ــ وخاصة ذلك الذي يتضمن بعض التقنيات الجديدة ــ هناك دائما أمل في أن تتمكن من استخدامها ... في مشاكل ذات صلة".

وقال عالم الكمبيوتر إن هناك أيضًا الرضا الفكري الذي يأتي من معرفة أنك قمت بحل مشكلة صعبة وطويلة الأمد بيوتر إنديك من معهد ماساتشوستس للتكنولوجيا. "بمجرد التأكد من عدم إمكانية تحسين بعض هياكل البيانات، يمكن أن يساعد ذلك في تركيز جهود البحث." وأخيرا، يمكن للباحثين في مجال البيانات تحويل انتباههم بعيدا عن التحدي الذي طرحه بيترسون والتركيز على المشاكل الجديدة في علوم الكمبيوتر النظرية، والتي لا يوجد نقص فيها.