سائنسدانوں کو ڈیٹا سٹوریج اور وقت کا بہترین توازن ملتا ہے | کوانٹا میگزین

تقریباً 70 سال پہلے، ہینس پیٹر لوہن نامی IBM کے ایک انجینئر نے خاموشی سے کمپیوٹر سائنس کا کورس بدل دیا۔ لوہن کے پاس پہلے سے ہی کئی پیٹنٹ موجود ہیں، جن میں سے ایک ایسے آلے کے لیے ہے جو کپڑے کے دھاگے کی گنتی کی پیمائش کر سکتا ہے اور دوسرا ایک گائیڈ کے لیے جو یہ طے کرتا ہے کہ آپ اپنے باورچی خانے کے اجزاء سے کون سے مخلوط مشروبات بنا سکتے ہیں۔ لیکن 1953 کے ایک اندرونی IBM پیپر میں، اس نے معلومات کو ذخیرہ کرنے اور بازیافت کرنے کے لیے ایک نئی تکنیک کی تجویز پیش کی جو اب تقریباً تمام کمپیوٹیشنل سسٹمز میں بنی ہوئی ہے: ہیش ٹیبل۔

ہیش ٹیبل ڈیٹا ڈھانچے کی ایک بڑی کلاس ہیں۔ وہ بڑے پیمانے پر ڈیٹا بیس میں معلومات تک رسائی اور تبدیلی کے لیے خاص طور پر آسان طریقہ پیش کرتے ہیں۔ لیکن یہ ٹیکنالوجی ناگزیر تجارت کے ساتھ آتی ہے۔

ایک 1957 میں کاغذ میں شائع IBM جرنل آف ریسرچ اینڈ ڈویلپمنٹ, W. Wesley Peterson نے اہم تکنیکی چیلنج کی نشاندہی کی جو ہیش ٹیبلز کو لاحق ہے: انہیں تیز رفتار ہونے کی ضرورت ہے، مطلب یہ کہ وہ ضروری معلومات کو تیزی سے بازیافت کر سکتے ہیں۔ لیکن انہیں کم سے کم میموری کا استعمال کرتے ہوئے کمپیکٹ ہونے کی بھی ضرورت ہے۔ یہ جڑواں مقاصد بنیادی طور پر متضاد ہیں۔ جب ہیش ٹیبل میں زیادہ میموری ہو تو ڈیٹا بیس تک رسائی اور اس میں ترمیم کرنا زیادہ تیزی سے کیا جا سکتا ہے۔ اور کم جگہ استعمال کرنے والے ہیش ٹیبلز میں آپریشنز سست ہو جاتے ہیں۔ جب سے پیٹرسن نے یہ چیلنج پیش کیا ہے، محققین نے وقت اور جگہ کے درمیان بہترین توازن تلاش کرنے کی کوشش کی ہے۔

کمپیوٹر سائنس دانوں نے اب ریاضیاتی طور پر یہ ثابت کر دیا ہے کہ انہوں نے بہترین تجارت تلاش کر لی ہے۔ ایک سے حل نکلا۔ جوڑی حالیہ کاغذات جو ایک دوسرے کی تکمیل کرتا ہے۔ "یہ کاغذات بہترین ممکنہ اسپیس ٹائم ٹریڈ آف کے بارے میں دیرینہ کھلے سوال کو حل کرتے ہیں، جس سے گہرے حیران کن نتائج برآمد ہوتے ہیں جن کی مجھے امید ہے کہ آنے والے کئی سالوں تک اس کا اہم اثر پڑے گا،" کہا۔ مائیکل مٹزنماکر، ہارورڈ یونیورسٹی میں کمپیوٹر سائنسدان جو کسی بھی مطالعہ میں شامل نہیں تھا۔

"میں یقینی طور پر کہوں گا کہ یہ ایک بہت بڑی بات ہے۔" راسمس پاگکوپن ہیگن یونیورسٹی میں کمپیوٹر سائنس دان۔ "بہت سے لوگوں نے اس مسئلے پر کام کیا ہے، یہ دیکھنے کی کوشش کر رہے ہیں کہ آپ کتنی جگہ کو نچوڑ سکتے ہیں، اور وقت کے ساتھ آپریشن بھی کر رہے ہیں۔ یہ وہی ہے جسے میں حل کرنا پسند کروں گا۔"

اس کا ایک ہیش بنانا

ہیش ٹیبلز آج کے سب سے قدیم، آسان، تیز ترین اور سب سے زیادہ استعمال ہونے والے ڈیٹا ڈھانچے میں سے ہیں۔ وہ تین بنیادی کارروائیوں کو انجام دینے کے لیے ڈیزائن کیے گئے ہیں: اندراج، جو ڈیٹا بیس میں نئی ​​اشیاء شامل کرتے ہیں۔ سوالات، جو کسی شے تک رسائی حاصل کرتے ہیں یا یہ دیکھنے کے لیے چیک کرتے ہیں کہ آیا یہ موجود ہے؛ اور حذف ایک ہیش ٹیبل عارضی ہو سکتا ہے — صرف اس وقت تک موجود ہے جب تک کہ کوئی خاص پروگرام چلتا ہے — یا یہ آپ کے کمپیوٹر کے آپریٹنگ سسٹم کا مستقل حصہ ہو سکتا ہے۔ ایک ویب براؤزر جیسے کروم یا سفاری میں متعدد بلٹ ان ہیش ٹیبلز ہو سکتے ہیں جن کا مقصد مختلف قسم کے ڈیٹا کو ٹریک کرنا ہے۔

ہیش ٹیبل میں اندراجات کو جوڑے کے طور پر ذخیرہ کیا جاتا ہے، آئٹم کے ساتھ - معلومات خود - ایک کلید سے منسلک ہوتی ہے جو معلومات کی شناخت کرتی ہے۔ ایک کلید کو ہیش ٹیبل کے استفسار کے الگورتھم میں لگائیں، اور یہ آپ کو براہ راست آئٹم تک لے جاتا ہے۔ یہ اتنا غیر معمولی نہیں لگ سکتا ہے، لیکن بہت زیادہ ڈیٹا بیس کے لیے یہ ایک بہترین وقت بچانے والا ہو سکتا ہے۔

ایک انتہائی آسان مثال لینے کے لیے، آکسفورڈ انگلش ڈکشنری پر غور کریں، جس میں 600,000 سے زیادہ الفاظ کی تعریفیں ہیں۔ اگر ڈیجیٹل ایڈیشن ہیش ٹیبل پر انحصار کرتا ہے، تو آپ صرف ایک دیئے گئے لفظ کو کلید کے طور پر استعمال کر سکتے ہیں اور سیدھے تعریف کی طرف بڑھ سکتے ہیں۔ ہیش ٹیبل کے بغیر، لغت ممکنہ طور پر ایک بہت سست تلاش کے طریقہ کار پر انحصار کرے گی، جس کے خاتمے کے عمل کو استعمال کرتے ہوئے بالآخر مطلوبہ تعریف پر اکتفا کیا جائے گا۔ اور جب کہ ہیش ٹیبل کسی بھی لفظ کو مستقل وقت میں تلاش کر سکتا ہے (عام طور پر ایک سیکنڈ کا ایک چھوٹا سا حصہ)، دوسرے طریقوں کے لیے تلاش کا وقت بڑھ سکتا ہے جیسے جیسے لغت میں الفاظ کی تعداد بڑھ جاتی ہے۔ ایک ہیش ٹیبل ایک اور فائدہ بھی پیش کرتا ہے: یہ لغت کو متحرک رکھ سکتا ہے، جس سے نئے الفاظ داخل کرنا اور پرانے الفاظ کو حذف کرنا آسان ہو جاتا ہے۔

محققین نے ہیش ٹیبل بنانے میں دہائیاں گزاری ہیں جو رفتار کو زیادہ سے زیادہ کرنے اور میموری کو کم سے کم کرنے کی کوشش کرتی ہیں۔ 20 ویں صدی میں، حل صرف ایک پہلو، وقت یا جگہ میں اہم فوائد پیش کرتے تھے۔ پھر 2003 میں، محققین سے ظاہر ہوا کہ نظریاتی طور پر وقت اور جگہ دونوں میں ایک ساتھ ایک بڑی کارکردگی کی چھلانگ لگانا ممکن تھا۔ تاہم، محققین کو دونوں کے درمیان مثالی توازن معلوم کرنے میں مزید دو دہائیاں لگیں گی۔

ڈیٹا شفل

اس مقصد کی طرف پہلا بڑا قدم 2022 میں آیا اہم کمپیوٹر سائنس کانفرنس روم میں. وہاں، ایک ٹیم نے نئی خصوصیات کے ساتھ ایک ہیش ٹیبل تجویز کیا جو وقت اور جگہ کی کارکردگی کا ابھی تک تصور کیا گیا بہترین امتزاج فراہم کر سکتا ہے۔ اس مقالے کے پہلے مصنف (حروف تہجی کے لحاظ سے درج) اسٹونی بروک یونیورسٹی کے مائیکل بینڈر تھے، لہذا اسے عام طور پر بینڈر ایٹ ال کہا جاتا ہے۔ ہیش ٹیبل. اگرچہ ٹیم نے کام کرنے والی ہیش ٹیبل بنانے کی کوشش نہیں کی، لیکن انہوں نے ثابت کیا کہ یہ اصولی طور پر، ان کی بیان کردہ خصوصیات کے ساتھ تعمیر کیا جا سکتا ہے۔

وہ جس ہیش ٹیبل کے ساتھ آئے تھے اس کا اندازہ کرنے کے لیے، گروپ نے ایک تجارتی بند وکر تیار کیا - ایک گراف جو ایک محور پر فی آپریشن (اندراج یا حذف کرنے) کا وقت اور دوسری طرف میموری کے ذریعے لی گئی جگہ کا نقشہ بناتا ہے۔ لیکن یہ گراف ایک خاص طریقے سے جگہ کی وضاحت کرتا ہے: اس کی وجہ سے کہ وہ کیسے بنائے گئے ہیں، ہیش ٹیبلز کو اشیاء کے دیئے گئے سیٹ کو ذخیرہ کرنے کے لیے درکار کم از کم میموری سے زیادہ میموری کی ضرورت ہوتی ہے۔ کمپیوٹر سائنس دان اس اضافی جگہ کو "ضائع شدہ بٹس" کہتے ہیں، حالانکہ وہ واقعی ضائع نہیں ہوئے ہیں اور کسی حد تک ضروری ہیں۔ تجارتی بند وکر پر خلائی محور فی کلید ضائع شدہ بٹس کی تعداد کی پیمائش کرتا ہے۔

ٹریڈ آف وکر کا تجزیہ کرکے، محققین ہیش ٹیبل کے لیے ممکنہ تیز ترین وقت کا اندازہ لگا سکتے ہیں جو ایک دی گئی جگہ استعمال کرتی ہے۔ وہ ایک دیے گئے آپریشن کے وقت کے لیے سب سے چھوٹی ممکنہ جگہ کا پتہ لگانے کے لیے سوال کو ادھر ادھر بھی پلٹ سکتے ہیں۔ عام طور پر، ایک متغیر میں ایک چھوٹی سی تبدیلی دوسرے میں ایک چھوٹی تبدیلی کا باعث بنے گی۔ ولیم کزمول، ہارورڈ میں ایک نظریاتی کمپیوٹر سائنس دان اور 2022 کے مقالے کے شریک مصنف۔ "اگر آپ وقت کو دوگنا کرتے ہیں، تو شاید آپ فی کلید ضائع ہونے والے بٹس کی تعداد کو نصف کر دیں گے۔"

لیکن ان کے ڈیزائن کردہ ہیش ٹیبل کا معاملہ ایسا نہیں ہے۔ Kuszmaul نے کہا، "اگر آپ وقت میں تھوڑا سا اضافہ کرتے ہیں، تو فی کلید کے ضائع ہونے والے بٹس تیزی سے کم ہو جاتے ہیں۔" تجارتی بند وکر بہت کھڑا تھا، یہ لفظی طور پر چارٹ سے دور تھا۔

ٹیم نے اپنی ہیش ٹیبل کو دو حصوں میں بنایا۔ ان کے پاس ڈیٹا کا بنیادی ڈھانچہ تھا، جس میں آئٹمز کو بغیر کسی ضائع شدہ بٹس کے ذخیرہ کیا جاتا ہے، اور ایک ثانوی ڈیٹا ڈھانچہ، جو استفسار کی درخواست کو اس آئٹم کو تلاش کرنے میں مدد کرتا ہے جسے وہ تلاش کر رہا ہے۔ اگرچہ اس گروپ نے ثانوی ڈیٹا ڈھانچے کا تصور ایجاد نہیں کیا، لیکن انہوں نے ایک اہم دریافت کی جس نے ان کی انتہائی موثر ہیش ٹیبل کو ممکن بنایا: ساخت کی مجموعی میموری کی کارکردگی اس بات پر منحصر ہے کہ بنیادی ڈھانچہ اپنی ذخیرہ شدہ اشیاء کو کس طرح ترتیب دیتا ہے۔

بنیادی خیال یہ ہے کہ بنیادی ڈھانچے میں ہر آئٹم نے ذخیرہ کرنے کی جگہوں کو ترجیح دی ہے - ایک بہترین مقام، دوسرا بہترین، تیسرا بہترین وغیرہ۔ اگر کوئی آئٹم اپنی بہترین جگہ پر ہے، تو نمبر 1 اس پر چسپاں ہوتا ہے، اور وہ نمبر سیکنڈری ڈیٹا ڈھانچے میں محفوظ ہوتا ہے۔ ایک سوال کے جواب میں، ثانوی ڈھانچہ صرف نمبر 1 فراہم کرتا ہے، جو بنیادی ڈھانچے میں آئٹم کے صحیح مقام کو ظاہر کرتا ہے۔

اگر آئٹم اپنی 100 ویں بہترین جگہ پر ہے تو، ثانوی ڈیٹا ڈھانچہ نمبر 100 کو منسلک کرتا ہے۔ اور چونکہ سسٹم بائنری استعمال کرتا ہے، اس لیے یہ 100 کے نمبر کو 1100100 کے طور پر ظاہر کرتا ہے۔ یقیناً، 1100100 کے مقابلے 1 نمبر کو ذخیرہ کرنے میں زیادہ میموری درکار ہوتی ہے۔ - کسی شے کو تفویض کردہ نمبر جب وہ بہترین جگہ پر ہو۔ اگر آپ ایک ملین اشیاء کو ذخیرہ کر رہے ہیں تو اس طرح کے اختلافات اہم ہو جاتے ہیں۔

لہذا ٹیم نے محسوس کیا کہ اگر آپ بنیادی ڈیٹا سٹرکچر میں آئٹمز کو ان کے زیادہ ترجیحی مقامات پر مسلسل شفٹ کرتے ہیں، تو آپ استفسار کے اوقات میں اضافہ کیے بغیر ثانوی ڈھانچے کے ذریعے استعمال ہونے والی میموری کو نمایاں طور پر کم کر سکتے ہیں۔

پگ نے کہا، "اس کام سے پہلے، کسی کو یہ احساس نہیں تھا کہ آپ معلومات کو ادھر ادھر منتقل کر کے ڈیٹا کے ڈھانچے کو مزید سکیڑ سکتے ہیں۔" "یہ بینڈر پیپر کی بڑی بصیرت تھی۔"

مصنفین نے ظاہر کیا کہ ان کی ایجاد نے سب سے زیادہ موثر ہیش ٹیبلز کے لیے ایک نئی اوپری حد قائم کی ہے، مطلب یہ ہے کہ یہ ڈیٹا کا بہترین ڈھانچہ تھا جسے وقت اور جگہ کی کارکردگی دونوں کے لحاظ سے ابھی تک وضع کیا گیا ہے۔ لیکن امکان باقی رہا کہ کوئی اور اس سے بھی بہتر کام کر سکتا ہے۔

کامیابی کا پابند

اگلے سال، ایک ٹیم کی قیادت میں ہواچینگ یوپرنسٹن یونیورسٹی کے کمپیوٹر سائنسدان نے بینڈر ٹیم کی ہیش ٹیبل کو بہتر بنانے کی کوشش کی۔ "ہم نے واقعی بہت محنت کی اور ایسا نہیں کر سکے،" کہا رینفی چاؤ، بیجنگ میں سنگھوا یونیورسٹی کا ایک طالب علم اور یو کی ٹیم کا ایک رکن۔ "اس وقت جب ہمیں شبہ ہوا کہ ان کی اوپری باؤنڈ [بھی] ایک نچلی حد ہے" - بہترین جو ممکنہ طور پر حاصل کیا جاسکتا ہے۔ "جب اوپری باؤنڈ لوئر باؤنڈ کے برابر ہو جاتی ہے، تو گیم ختم ہو جاتی ہے، اور آپ کے پاس آپ کا جواب ہوتا ہے۔" اس سے کوئی فرق نہیں پڑتا ہے کہ آپ کتنے ہی ہوشیار ہیں، کوئی ہیش ٹیبل اس سے بہتر کام نہیں کر سکتا۔

یو کی ٹیم نے پہلے اصولوں سے کم حد کا حساب لگا کر یہ معلوم کرنے کے لیے ایک نئی حکمت عملی استعمال کی۔ سب سے پہلے، انہوں نے یہ استدلال کیا کہ اندراج یا حذف کرنے کے لیے، ایک ہیش ٹیبل — یا، واقعی، کسی بھی ڈیٹا ڈھانچے — کو کمپیوٹر کی میموری تک کئی بار رسائی حاصل کرنی چاہیے۔ اگر وہ خلائی موثر ہیش ٹیبل کے لیے درکار وقت کی کم از کم تعداد کا پتہ لگاسکتے ہیں، تو وہ اسے فی رسائی (ایک مستقل) کے لیے درکار وقت سے ضرب دے سکتے ہیں، جس سے انھیں رن ٹائم پر کم حد ملتی ہے۔

لیکن اگر وہ ہیش ٹیبل کے بارے میں کچھ نہیں جانتے تھے (سوائے اس کے کہ یہ اسپیس ایفیئنٹ تھا)، تو محققین میموری تک رسائی کے لیے درکار اوقات کی کم از کم تعداد کا کیسے پتہ لگا سکتے ہیں؟ انہوں نے اسے خالصتاً نظریہ سے اخذ کیا، بظاہر غیر متعلقہ فیلڈ کا استعمال کرتے ہوئے جسے تھیوری آف کمیونیکیشن پیچیدگی کہا جاتا ہے، جو اس بات کا مطالعہ کرتا ہے کہ دو فریقوں کے درمیان معلومات پہنچانے کے لیے کتنے بٹس کی ضرورت ہوتی ہے۔ آخر کار، ٹیم کامیاب ہوئی: انہوں نے اندازہ لگایا کہ ڈیٹا ڈھانچے کو ہر آپریشن کے لیے کتنی بار اس کی میموری تک رسائی حاصل کرنی چاہیے۔

یہ ان کی اہم کامیابی تھی۔ اس کے بعد وہ کسی بھی خلائی موثر ہیش ٹیبل کے لیے رن ٹائم پر کم حد قائم کرنے کے قابل تھے۔ اور انہوں نے دیکھا کہ یہ بینڈر ہیش ٹیبل سے بالکل مماثل ہے۔ "ہم نے سوچا کہ [پہلے] اسے بہتر بنایا جا سکتا ہے،" زو نے کہا۔ "یہ پتہ چلا کہ ہم غلط تھے." اس کے نتیجے میں، مطلب یہ تھا کہ پیٹرسن کا مسئلہ بالآخر حل ہو گیا تھا۔

دہائیوں پرانے سوال کا جواب دینے کے علاوہ، Kuszmaul نے کہا، Yu ثبوت کے بارے میں حیرت انگیز چیز اس کی عمومیت ہے۔ "ان کی کم حد تمام ممکنہ ڈیٹا ڈھانچے پر لاگو ہوتی ہے، بشمول وہ جو ابھی تک ایجاد نہیں ہوئے ہیں۔" اس کا مطلب ہے کہ ڈیٹا اسٹوریج کا کوئی بھی طریقہ میموری اور رفتار کے لحاظ سے بینڈر ہیش ٹیبل کو ہرا نہیں سکتا۔

مستقبل میں ہیشنگ

نئے ہیش ٹیبل کی بے مثال کارکردگی کے باوجود، کوئی بھی جلد ہی اسے بنانے کی کوشش نہیں کرے گا۔ یہ تعمیر کرنا بہت پیچیدہ ہے۔ "ایک الگورتھم جو نظریہ میں تیز ہے ضروری نہیں کہ عملی طور پر تیز ہو،" زو نے کہا۔

Kuszmaul نے کہا کہ تھیوری اور پریکٹس کے درمیان اس طرح کے فاصلوں کا طویل عرصے تک برقرار رہنا کوئی غیر معمولی بات نہیں ہے، کیونکہ تھیوریسٹ مستقل عوامل کو نظر انداز کرتے ہیں۔ کسی آپریشن کو انجام دینے میں جو وقت لگتا ہے اسے عام طور پر ایک عدد سے ضرب دیا جاتا ہے، کچھ مستقل جن کی صحیح قدر نظریاتی نقطہ نظر سے غیر اہم ہو سکتی ہے۔ "لیکن عملی طور پر، مستقل اہمیت رکھتا ہے،" انہوں نے کہا۔ "حقیقی دنیا میں، 10 کا عنصر گیم اینڈر ہے۔"

اصل ہیش ٹیبلز ابھی بھی مادی طریقوں سے بہتر ہو رہی ہیں، چاہے وہ نظریاتی آئیڈیل سے بہت کم کیوں نہ ہوں۔ مثال کے طور پر، ایک نیا ہیش ٹیبل کہا جاتا ہے آئس برگ ایچ ٹیBender، Kuszmaul اور دوسروں کی طرف سے بنایا گیا، اپنے پیشروؤں سے کہیں بہتر ہے۔ Kuszmaul کے مطابق، یہ آج دستیاب سب سے زیادہ خلائی موثر ہیش ٹیبل سے دوگنا تیز ہے، اور یہ تیز ترین ہیش ٹیبل سے تین گنا کم جگہ استعمال کرتا ہے۔

Mitzenmacher امید کرتا ہے کہ 2023 کا نتیجہ جلد ہی ایک اور قسم کا فائدہ دے سکتا ہے: "جب بھی آپ کو کوئی نئی نچلی حد ملتی ہے - خاص طور پر ایک جس میں کچھ نئی تکنیکیں شامل ہوتی ہیں - ہمیشہ امید رہتی ہے کہ آپ انہیں استعمال کر سکتے ہیں … متعلقہ مسائل کے لیے۔"

کمپیوٹر سائنس دان نے کہا کہ ایک فکری اطمینان بھی ہے جو یہ جان کر حاصل ہوتا ہے کہ آپ نے ایک مشکل اور دیرینہ مسئلہ حل کر لیا ہے۔ پیوٹر انڈیک میساچوسٹس انسٹی ٹیوٹ آف ٹیکنالوجی کے۔ "ایک بار جب آپ کو یقین ہو جائے کہ ڈیٹا کے کچھ ڈھانچے کو بہتر نہیں بنایا جا سکتا، تو اس سے تحقیقی کوششوں پر توجہ مرکوز کرنے میں مدد مل سکتی ہے۔" آخر میں، ڈیٹا محققین پیٹرسن کے چیلنج سے اپنی توجہ ہٹا سکتے ہیں اور نظریاتی کمپیوٹر سائنس میں نئے مسائل پر توجہ مرکوز کر سکتے ہیں، جن میں کوئی کمی نہیں ہے۔