ديسكان

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

نظرة عامة

يجمعDISKANN بين تقنيتين رئيسيتين للبحث المتجه الفعال:

• الرسم البياني Vamana Graph - فهرس قائم على القرص قائم على الرسم البياني يربط نقاط البيانات (أو المتجهات) للتنقل الفعال أثناء البحث.

• تكميم المنتج (PQ) - طريقة ضغط داخل الذاكرة تقلل من حجم المتجهات، مما يتيح إجراء حسابات تقريبية سريعة للمسافة بين المتجهات.

بناء الفهرس

الرسم البياني فامانا

يُعدّ الرسم البياني Vamana محوريًا في استراتيجية DISKANN القائمة على القرص. ويمكنه التعامل مع مجموعات البيانات الكبيرة جدًا لأنه لا يحتاج إلى التواجد بشكل كامل في الذاكرة أثناء الإنشاء أو بعده.

يوضح الشكل التالي كيف يتم بناء الرسم البياني لـ Vamana.

ديسكان

1. الاتصالات العشوائية الأولية: يتم تمثيل كل نقطة بيانات (متجه) كعقدة في الرسم البياني. يتم توصيل هذه العقد في البداية بشكل عشوائي، مما يشكل شبكة كثيفة. وعادةً ما تبدأ العقدة بحوالي 500 حافة (أو وصلات) للاتصال الواسع.

2. التنقيح من أجل الكفاءة: يخضع الرسم البياني العشوائي الأولي لعملية تحسين لجعله أكثر كفاءة للبحث. ويتضمن ذلك خطوتين رئيسيتين:

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

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

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

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

لمعرفة المزيد حول ضبط البارامترات، راجع بارامترات DISKANN.

PQ

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

تدير المعلمة pq_code_budget_gb_ratio بصمة الذاكرة المخصصة لتخزين رموز PQ هذه. وهي تمثل النسبة بين الحجم الإجمالي للمتجهات (بالجيجابايت) والمساحة المخصصة لتخزين رموز PQ. يمكنك حساب ميزانية رمز PQ الفعلية (بالجيجابايت) باستخدام هذه الصيغة:

PQ Code Budget (GB) = vec_field_size_gb * pq_code_budget_gb_ratio

حيث

• vec_field_size_gb هو الحجم الإجمالي للمتجهات (بالجيجابايت).

• pq_code_budget_gb_ratio هي نسبة يحددها المستخدم، تمثل جزءًا من إجمالي حجم البيانات المحجوزة لرموز PQ. تسمح هذه المعلمة بالمفاضلة بين دقة البحث وموارد الذاكرة. لمزيد من المعلومات حول ضبط المعلمة، راجع تكوينات DISKANN.

للحصول على التفاصيل الفنية حول طريقة PQ الأساسية، راجع IVF_PQ.

عملية البحث

بمجرد إنشاء الفهرس (الرسم البياني Vamana على القرص ورموز PQ في الذاكرة)، يقوم DISKANN بإجراء عمليات بحث ANN على النحو التالي:

ديسكان 2

1. الاستعلام ونقطة الدخول: يتم توفير متجه استعلام لتحديد موقع أقرب جيرانه. يبدأ DISKANN من نقطة دخول مختارة في الرسم البياني لـ Vamana، وغالبًا ما تكون عقدة بالقرب من النقطة المركزية العالمية لمجموعة البيانات. يمثّل المتجه المركزي العالمي متوسط جميع المتجهات، مما يساعد على تقليل مسافة العبور عبر الرسم البياني للعثور على الجيران المطلوبين.

2. استكشاف الجوار: تجمع الخوارزمية الجيران المرشحين المحتملين (دوائر باللون الأحمر في الشكل) من حواف العقدة الحالية، مستفيدةً من رموز PQ في الذاكرة لتقريب المسافات بين هؤلاء المرشحين ومتجه الاستعلام. هؤلاء الجيران المرشحون المحتملون هم العقد المتصلة مباشرةً بنقطة الدخول المحددة من خلال الحواف في الرسم البياني ل Vamana.

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

   • beam_width_ratio: الحصة التي تتحكم في اتساع نطاق البحث، وتحدد عدد الجيران المرشحين الذين يتم اختيارهم بالتوازي لاستكشاف جيرانهم. يؤدي وجود beam_width_ratio أكبر إلى استكشاف أوسع، مما قد يؤدي إلى دقة أعلى ولكن أيضًا زيادة التكلفة الحسابية وإدخال/إخراج القرص. يتم تحديد عرض الشعاع، أو عدد العقد المختارة، باستخدام المعادلة: Beam width = Number of CPU cores * beam_width_ratio.

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

   لمعرفة المزيد حول ضبط المعلمات، راجع تكوينات DISKANN.

4. الاستكشاف التكراري: يقوم البحث بشكل متكرر بتنقيح مجموعة المرشحين بشكل متكرر، مع إجراء تقييمات تقريبية (باستخدام PQ) بشكل متكرر متبوعة بفحوصات دقيقة (باستخدام المتجهات الأصلية من القرص) حتى يتم العثور على عدد كافٍ من الجيران.

تمكين DISKANN في ميلفوس

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

إليك كيفية تمكين DISKANN في ميلفوس:

1. تحديث ملف تهيئة ميلفوس

   1. حدد موقع ملف تكوين Milvus الخاص بك. (راجع وثائق Milvus حول التكوين للحصول على تفاصيل حول العثور على هذا الملف).

   2. ابحث عن المعلمة queryNode.enableDisk وقم بتعيين قيمتها إلى true:

       queryNode:
           enableDisk: true # Enables query nodes to load and search using the on-disk index
      

2. تحسين التخزين لـ DISKANN

لضمان أفضل أداء مع DISKANN، يوصى بتخزين بيانات Milvus على محرك أقراص NVMe SSD سريع. إليك كيفية القيام بذلك لكل من عمليات نشر Milvus Standalone و Cluster:

• ميلفوس مستقل

  • قم بتركيب دليل بيانات Milvus على قرص NVMe SSD داخل حاوية Milvus. يمكنك القيام بذلك في الملف docker-compose.yml أو باستخدام أدوات إدارة الحاويات الأخرى.

  • على سبيل المثال، إذا تم تركيب قرص NVMe SSD الخاص بك على /mnt/nvme ، يمكنك تحديث قسم volumesمن docker-compose.yml الخاص بك على هذا النحو:

   volumes:
        - /mnt/nvme/volumes/milvus:/var/lib/milvus
  

• مجموعة ميلفوس العنقودية

  • قم بتحميل دليل بيانات Milvus على محرك أقراص NVMe SSD في كل من حاويات QueryNode و IndexNode. يمكنك تحقيق ذلك من خلال إعداد تزامن الحاوية الخاصة بك.

  • من خلال تركيب البيانات على محرك أقراص NVMe SSD في كلا النوعين من العقد، فإنك تضمن سرعات قراءة وكتابة عالية لكل من عمليات البحث والفهرسة.

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

تكوين DISKANN

لا يمكن تكوين المعلمات المتعلقة بـ DISKANN إلا من خلال ملف تكوين Milvus (milvus.yaml):

# milvus.yaml
common:
  DiskIndex:
    MaxDegree: 56  # Maximum degree of the Vamana graph
    SearchListSize: 100  # Size of the candidate list during building graph
    PQCodeBudgetGBRatio: 0.125  # Size limit on the PQ code (compared with raw data)
    SearchCacheBudgetGBRatio: 0.1 # Ratio of cached node numbers to raw data
    BeamWidthRatio: 4 # Ratio between the maximum number of IO requests per search iteration and CPU number

للحصول على تفاصيل حول أوصاف المعلمات، راجع بارامز DISKANN.

بارامترات DISKANN

يسمح لك الضبط الدقيق لمعلمات DISKANN بتكييف سلوكها مع مجموعة البيانات الخاصة بك وعبء عمل البحث، وتحقيق التوازن الصحيح بين السرعة والدقة واستخدام الذاكرة.

بارامترات بناء الفهرس

تؤثر هذه المعلمات على كيفية إنشاء فهرس DISKANN. يمكن أن يؤثر تعديلها على حجم الفهرس ووقت إنشائه وجودة البحث.

	المعلمة	الوصف	نطاق القيمة	اقتراح الضبط
فامانا	MaxDegree	يتحكم في الحد الأقصى لعدد الاتصالات (الحواف) التي يمكن أن تحتويها كل نقطة بيانات في الرسم البياني فامانا.	النوع: عدد صحيح المدى: [1, 512] القيمة الافتراضية: 56	تنشئ القيم الأعلى رسومات بيانية أكثر كثافة، مما قد يزيد من الاستدعاء (العثور على المزيد من النتائج ذات الصلة) ولكن أيضًا يزيد من استخدام الذاكرة ووقت الإنشاء. في معظم الحالات، نوصي بتعيين قيمة ضمن هذا النطاق: [10, 100].
	SearchListSize	أثناء إنشاء الفهرس، تحدد هذه المعلمة حجم مجموعة المرشحين المستخدمة عند البحث عن أقرب الجيران لكل عقدة. لكل عقدة تتم إضافتها إلى الرسم البياني، تحتفظ الخوارزمية بقائمة بأفضل search_list_size المرشحين الذين تم العثور عليهم حتى الآن. يتوقف البحث عن الجيران عندما لا يمكن تحسين هذه القائمة. من مجموعة المرشحين النهائيين هذه، يتم اختيار أفضل max_degree عقدة لتكوين الحواف النهائية.	النوع: عدد صحيح المدى: [1، int_max] القيمة الافتراضية: 100	تزيد القيمة الأكبر search_list_size من احتمالية العثور على أقرب الجيران الحقيقيين لكل عقدة، مما قد يؤدي إلى رسم بياني أعلى جودة وأداء بحث أفضل (استرجاع). ومع ذلك، يأتي ذلك على حساب وقت إنشاء فهرس أطول بكثير. يجب تعيينه دائمًا على قيمة أكبر من أو تساوي max_degree.
	SearchCacheBudgetGBRatio	يتحكم في مقدار الذاكرة المخصصة للتخزين المؤقت للأجزاء التي يتم الوصول إليها بشكل متكرر من الرسم البياني أثناء إنشاء الفهرس.	النوع: عائم المدى: [0.0, 0.3) القيمة الافتراضية: 0.10	تؤدي القيمة الأعلى إلى تخصيص ذاكرة أكبر للتخزين المؤقت، مما يقلل بشكل كبير من إدخال/إخراج القرص ولكن يستهلك المزيد من ذاكرة النظام. تستخدم القيمة المنخفضة ذاكرة أقل للتخزين المؤقت، مما قد يزيد من الحاجة إلى الوصول إلى القرص. في معظم الحالات، نوصي بتعيين قيمة ضمن هذا النطاق: [0.0, 0.3).
PQ	PQCodeBudgetGBRatio	يتحكم في حجم رموز PQ (تمثيلات مضغوطة لنقاط البيانات) مقارنة بحجم البيانات غير المضغوطة.	النوع: عائم النطاق: (0.0، 0.25] القيمة الافتراضية: 0.125	تؤدي النسبة الأعلى إلى نتائج بحث أكثر دقة من خلال تخصيص نسبة أكبر من الذاكرة لرموز PQ، مما يؤدي فعليًا إلى تخزين المزيد من المعلومات حول المتجهات الأصلية. ومع ذلك، يتطلب ذلك ذاكرة أكبر، مما يحد من القدرة على التعامل مع مجموعات البيانات الكبيرة. تقلل النسبة الأقل من استخدام الذاكرة ولكن من المحتمل أن تضحي بالدقة، حيث تحتفظ رموز PQ الأصغر بمعلومات أقل. هذا النهج مناسب للسيناريوهات التي تكون فيها قيود الذاكرة مصدر قلق، مما قد يتيح فهرسة مجموعات بيانات أكبر. في معظم الحالات، نوصيك بتعيين قيمة ضمن هذا النطاق: (0.0625، 0.25]

بارامترات البحث الخاصة بالفهرس

تؤثر هذه المعلمات على كيفية إجراء DISKANN لعمليات البحث. يمكن أن يؤثر ضبطها على سرعة البحث، والكمون واستخدام الموارد.

	المعلمة	الوصف	نطاق القيمة	اقتراح الضبط
فامانا	BeamWidthRatio	يتحكم في درجة التوازي أثناء البحث عن طريق تحديد الحد الأقصى لعدد طلبات الإدخال/الإخراج المتوازي للقرص بالنسبة لعدد أنوية وحدة المعالجة المركزية المتوفرة.	النوع: نطاق عائم: [1، الحد الأقصى (128/رقم وحدة المعالجة المركزية، 16)] القيمة الافتراضية: 4.0	تعمل القيم الأعلى على زيادة التوازي، مما قد يؤدي إلى تسريع البحث على الأنظمة ذات وحدات المعالجة المركزية القوية ومحركات أقراص الحالة الصلبة. ومع ذلك، قد يؤدي تعيينها أعلى من اللازم إلى تنافس مفرط على الموارد. في معظم الحالات، نوصي بتعيين قيمة ضمن هذا النطاق: [1.0, 4.0].
	search_list	أثناء عملية البحث، تحدد هذه المعلمة حجم مخزن التخزين المرشح الذي تحتفظ به الخوارزمية أثناء اجتيازها للرسم البياني. تزيد القيمة الأكبر من فرص العثور على الجيران الأقرب الحقيقيين (استدعاء أعلى) ولكنها تزيد أيضًا من زمن انتقال البحث.	النوع: عدد صحيح المدى: [1، int_max] القيمة الافتراضية: 100	لتحقيق توازن جيد بين الأداء والدقة، يوصى بتعيين هذه القيمة لتكون مساوية لعدد النتائج التي تريد استرجاعها (top_k) أو أكبر قليلاً من عدد النتائج التي تريد استرجاعها.