DiskANN Explorer: بحث متجهي على نطاق المليارات من SSD
DiskANN يحتفظ بنسخة صغيرة مضغوطة بتنسيقPQ من كل متجه في RAM والمتجهات الكاملة + الرسم البياني على SSD. يقوم البحث بالتنقل عبر الرسم البياني باستخدام مقارنات RAM منخفضة التكلفة، ثم يعيد ترتيب المرشحين الأوائل باستخدام عدد قليل من عمليات قراءة القرص المكلفة.
سبب وجود « DiskANN »: حاجز الذاكرة
يمكن لـ« SSD » (محرك أقراص صلبة) واحد استيعاب جانب القرص بسهولة. أما جانب « RAM » (الذاكرة) فيتناسب مع أي كمبيوتر محمول. وبدون حيلة « PQ » (التخزين المؤقت)، ستحتاج إلى خادم بسعة مئات الجيجابايت من « RAM » (الذاكرة) لمجرد تحميل مجموعة البيانات.
التكلفة حتى الآن
PQ ≈ 1 µs، SSD ≈ 100 µs. تعتمد الأرقام الحقيقية على الأجهزة.إحصائيات البحث
كيف يعمل كتاب « DiskANN »
- قم ببناء الرسم البياني « Vamana »: رسم بياني kNN أحادي الطبقة (درجة
R) مُحسَّن لتخطيط القرص التسلسلي. لا توجد هرمية — مجرد رسم بياني واحد كبير. - تخزين التكمية والتقسيم: يحصل كل متجه على رمز صغير من نوع « PQ » (على سبيل المثال، 32 بايت). توجد رموز « PQ » في RAM. وتوجد المتجهات الكاملة وحواف الرسم البياني في SSD.
- «Beam-walk» مع مسافات « PQ »: من نقطة دخول ثابتة (المديود)، احتفظ بمجموعة مرشحة بحجم
L. اختر الأفضل، وقم بتوسيع جيرانه، وقم بتقدير المسافات باستخدام رموز «in-RAM » و« PQ » فقط. لا توجد عمليات إدخال/إخراج للقرص أثناء عملية «walk». - أعد ترتيب المتأهلين للتصفيات النهائية على القرص: تم تقدير المسافات بين أفضل العناصر في مجموعة المرشحين تقريبياً باستخدام PQ. اقرأ متجهاتهم الكاملة من القرص وأعد حساب المسافات الدقيقة لتصحيح الترتيب.
- Return top-K. Total disk I/O = عدد صغير من عمليات القراءة العشوائية، وعادةً ما يكون أقل من 20.
المهنة
- لماذا يتسم هذا النظام بالقابلية للتوسع: لا يحتوي « RAM » إلا على أكواد مضغوطة. تحتاج مجموعة بيانات مكونة من 1 مليار متجه مع « PQ » بحجم 32 بايت إلى حوالي 32 جيجابايت RAM — وهو ما يتسع على محطة عمل واحدة.
- لماذا هو أبطأ من HNSW: SSD عمليات القراءة العشوائية أبطأ بحوالي 100 مرة من RAM. حتى مع وجود حوالي 10 عمليات قراءة فقط، فإن زمن استجابة الاستعلام يتأثر بشكل كبير بالقرص.
- لماذا لا يزال يتفوق على « IVF_PQ » من حيث دقة الاسترجاع: خطوة إعادة الترتيب تعالج أخطاء التكمية التي لا تستطيع الطرق القائمة على « PQ » وحدها إصلاحها.
النموذج الذهني: « PQ » هو الاختبار البسيط «هل هذا الحي واعد؟». عمليات قراءة القرص هي الفحص المكلف «دعني أتحقق فعليًّا». يقوم « DiskANN » بإنجاز معظم عمله باستخدام الاختبار البسيط.
ما هو « DiskANN »؟
DiskANN هو فهرس تقريبي لأقرب الجيران قائم على الرسم البياني ومصمم لمجموعات البيانات التي لا تتناسب مع RAM. يقوم ببناء رسم بياني أحادي الطبقة Vamana مصمم للوصول الفعال إلى القرص، ويحتفظ برمز صغير مُكمَّل (PQ) لكل متجه في الذاكرة، ويخزن المتجهات ذات الدقة الكاملة وحواف الرسم البياني على SSD. تتنقل عمليات البحث في الرسم البياني باستخدام مقارنات منخفضة التكلفة داخلRAM PQ ولا تلمس القرص إلا لإعادة ترتيب عدد قليل من المرشحين النهائيين.
في « Milvus »، تعمل « DiskANN » على تشغيل خيار الفهرس على القرص: تصبح المجموعات التي تبلغ حجمها المليارات قابلة للبحث على أجهزة ذات سعة تصل إلى عشرات — وليس مئات — الجيجابايت من « RAM »، بينما تحافظ خطوة إعادة الترتيب على القرص على دقة الاسترجاع قريبة من فهارس الرسوم البيانية الموجودة في الذاكرة.
ما الذي تتحكم فيه المقابض
R(درجة الرسم البياني، وقت الإنشاء): العدد الأقصى للحواف لكل عقدة في الرسم البياني « Vamana ». كلما زادت قيمة R، تحسنت الاتصال ودقة الاسترجاع، على حساب حجم أكبر للرسم البياني على القرص وبطء في عملية الإنشاء.L/search_list(وقت الاستعلام): مجموعة المرشحين التي يتم الاحتفاظ بها أثناء البحث الشعاعي — مفتاح التحكم الرئيسي في الاسترجاع/الكمون، وهو ما يعادل ef في HNSW. يجب أن يكون على الأقل top-K الخاص بك.- ميزانية إعادة الترتيب (Re-rank budget): عدد المتأهلين للتصفيات النهائية الذين يتم استرداد متجهاتهم الكاملة من «الملفات المجمعة» ( SSD ) من أجل التقييم الدقيق. كل عملية من هذه العمليات تمثل قراءة عشوائية للقرص، لذا فإن هذا هو المكان الذي يحدث فيه تأخر الاستجابة للاستعلام — وأيضًا المكان الذي يتم فيه تصحيح أخطاء التقريب الناتجة عن «التقدير المسبق» ( PQ ).
DiskANN vs HNSW vs IVF
اختر « DiskANN » عندما تتجاوز مجموعة البيانات (أو استهلاك الذاكرة) سعة « RAM »: فهي تخدم الاستعلامات ذات الاسترجاع العالي باستخدام جزء بسيط من الذاكرة، مقابل زمن انتقال على مستوى الميلي ثانية يهيمن عليه قراءات « SSD ». إذا كان كل شيء يتسع بسهولة في الذاكرة، فإن « HNSW » يقدم إجابات أسرع. إذا كنت بحاجة إلى إنشاء فهارس سريع أو توفير معتدل في الذاكرة دون استخدام القرص، فإن متغيرات « IVF » تقع في الوسط.
الأسئلة المتكررة
متى يجب عليّ استخدام « DiskANN » بدلاً من « HNSW »؟
عندما لا تتسع متجهاتك في RAM — أو عندما تكون تكلفة RAM لتخزينها أعلى مما ترغب في دفعه. يحتاج مليار متجه عائم ذي 768 بُعدًا إلى ~3 تيرابايت في الذاكرة لـ HNSW ، ولكنه لا يحتاج سوى عشرات الجيجابايت من RAM بالإضافة إلى SSD مع DiskANN. إذا كانت مجموعة البيانات تتسع في الذاكرة بسهولة، فإن HNSW يظل الخيار الأقل تأخيرًا.
ما هي الأجهزة التي يحتاجها برنامج « DiskANN »؟
يُعد «البحث السريع عن المتجهات» ( NVMe ) SSD هو المطلب الرئيسي، حيث إن زمن استجابة الاستعلام يتأثر بشكل كبير بعدد قليل من عمليات القراءة العشوائية للقرص (تستغرق كل منها حوالي 100 ميكروثانية). متطلبات «الذاكرة المخصصة» ( RAM ) متواضعة: تقريبًا رموز «الذاكرة المخصصة» ( PQ ) (على سبيل المثال، 32–64 بايت لكل متجه) بالإضافة إلى المخازن المؤقتة العاملة.
هل « DiskANN » أبطأ من الفهارس الموجودة في الذاكرة مثل « HNSW »؟
لكل استعلام، نعم — عادةً ما تكون الميلي ثانية منخفضة من رقم واحد مقابل أقل من الميلي ثانية لـ « HNSW » داخل الذاكرة، لأن كل إعادة ترتيب على القرص تكون أبطأ بحوالي 100× من الوصول إلى « RAM ». المقايضة هي التكلفة: « DiskANN » يخدم نفس مجموعة البيانات بـ RAM أقل بمقدار عشرة أضعاف مع الحفاظ على دقة الاسترجاع فوق 90–95%.
كيف يحافظ « DiskANN » على دقة الاسترجاع (Recall) عاليةً على الرغم من ضغط « PQ »؟
PQ تُستخدم الرموز فقط لتوجيه مسار الرسم البياني، وليس لإنتاج النتائج النهائية. قبل إرجاع النتائج، يقرأ « DiskANN » المتجهات ذات الدقة الكاملة لأفضل المرشحين من « SSD » ويعيد ترتيبها بدقة، مصححًا خطأ التكمية الذي لا تستطيع الفهارس القائمة على « PQ » البحتة مثل « IVF_PQ » إصلاحه.
لمزيد من التفاصيل: اقرأ وثائق «DiskANN » لمعرفة متطلبات الإعداد، أو راجع «شرح الفهرس» للحصول على دليل القرار الكامل.
استمر في الاستكشاف
مستكشف HNSW
شاهد البحث في الرسم البياني متعدد الطبقات خطوة بخطوة — بدءًا من القفزات السريعة وصولًا إلى التنقلات المحلية.
FLAT vs IVF
مقارنة جنبًا إلى جنب بين البحث بالقوة الغاشمة والبحث المجمَّع. قم بضبط « nprobe » في الوقت الفعلي.
مختبر مقاييس التشابه
اسحب نقطة استعلام وقم بالتبديل بين « L2 » و«Cosine» و« IP » لترى كيف يتغير «الأقرب».