شرح الفهرس

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

نظرة عامة

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

يسرد الجدول التالي علاقة التعيين بين أنواع بيانات الحقل وأنواع الفهرس القابلة للتطبيق.

نوع بيانات الحقل	أنواع الفهرس القابلة للتطبيق
FLOAT_VECTOR FLOAT16_VECTOR بfloat16_vector INT8_VECTOR	مسطح IVF_FLAT IVF_SQ8 IVF_PQ IVF_RABITQ HNSW HNSW_SQ HNSW_PQ HNSW_PRQ DISKANN SCANN AISAQ GPU_CAGRA GPU_IVF_FLAT GPU_IVF_PQ gpU_brute_brute_force
BINARY_VECTOR	BIN_FLAT BIN_IVF_FLAT MINHASH_LSH
متناثر_متجه_مقلوب_متفرق	فهرس_مُتَفَرِّق_مقلوب_مُتَفَرِّق
VARCHAR	مقلوب (موصى به) BITMAP تري
BITMAP	BITMAP (موصى به) مقلوب
INT8 INT16 INT32 INT64	مقلوب STL_SORT
مسطح مزدوج	مقلوب
ARRAY (عناصر من أنواع BOOL و INT8/16/32/64 و VARCHAR)	BITMAP (موصى به)
ARRAY (عناصر من أنواع BOOL و INT8/16/32/64 و FLOAT و DOUBLE و VARCHAR)	مقلوب
JSON	مقلوب

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

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

تشريح الفهرس المتجه

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

تشريح الفهرس الكمي

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

بنية البيانات

تشكل بنية البيانات الطبقة الأساسية للفهرس. تشمل الأنواع الشائعة ما يلي:

• الملف المقلوب (IVF)

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

  يُعد هذا النوع من بنية بيانات الفهرس مثاليًا لمجموعات البيانات واسعة النطاق التي تتطلب إنتاجية سريعة.

• بنية قائمة على الرسم البياني

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

  ويتفوق هذا النوع من بنية بيانات الفهرس في المساحات عالية الأبعاد والسيناريوهات التي تتطلب استعلامات ذات زمن انتقال منخفض.

التكميم

يقلل التكميم الكمي من بصمة الذاكرة والتكاليف الحسابية من خلال تمثيل أكثر خشونة:

• يُمكّنالتكميم الكمي (على سبيل المثال SQ8) Milvus من ضغط كل بُعد متجه في بايت واحد (8 بت)، مما يقلل من استخدام الذاكرة بنسبة 75% مقارنةً بالعوامة 32 بت مع الحفاظ على دقة معقولة.

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

التنقيح

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

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

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

الملخص

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

مفاضلات الأداء

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

• عادةً ما تتفوقأنواع الفهارس القائمة على الرسم البياني على متغيرات IVF من حيث QPS.

• تتناسبمتغيرات IVF بشكل خاص مع السيناريوهات ذات القمة K الكبيرة (على سبيل المثال، أكثر من 2,000).

• عادةً ما توفرPQ معدل استرجاع أفضل بمعدلات ضغط مماثلة عند مقارنتها بـ SQ، على الرغم من أن الأخيرة توفر أداءً أسرع.

• يساعد استخدام محركات الأقراص الصلبة لجزء من الفهرس (كما هو الحال في DiskANN) في إدارة مجموعات البيانات الكبيرة، ولكنه يقدم أيضًا اختناقات محتملة في عدد وحدات IOPS.

السعة

تتضمن السعة عادةً العلاقة بين حجم البيانات وذاكرة الوصول العشوائي المتاحة. عند التعامل مع السعة، ضع في اعتبارك ما يلي:

• إذا كان ربع بياناتك الأولية يتناسب مع الذاكرة، ففكر في DiskANN لزمن الوصول المستقر.

• إذا كانت جميع بياناتك الأولية تتناسب مع الذاكرة، ففكر في أنواع الفهرس المستندة إلى الذاكرة و mmap.

• يمكنك استخدام أنواع الفهارس المطبقة على الكمية و mmap لمقايضة الدقة بالسعة القصوى.

الاستدعاء

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

• إذا كانت نسبة التصفية أقل من 85%، تتفوق أنواع الفهرس المستندة إلى الرسم البياني على متغيرات IVF.

• إذا كانت نسبة التصفية بين 85% و95%، فاستخدم متغيرات IVF.

• إذا كانت نسبة التصفية أكثر من 98%، فاستخدم متغيرات (FLAT) للحصول على نتائج بحث أكثر دقة.

الأداء

عادةً ما يتضمن أداء البحث عادةً أعلى K، والذي يشير إلى عدد السجلات التي يُرجعها البحث. عند التعامل مع الأداء، ضع في اعتبارك ما يلي:

• بالنسبة للبحث الذي يحتوي على أعلى K صغير (على سبيل المثال، 2,000) يتطلب معدل استدعاء مرتفع، تتفوق أنواع الفهارس المستندة إلى الرسم البياني على متغيرات IVF.

• بالنسبة للبحث الذي يحتوي على أعلى K كبير (مقارنةً بالعدد الإجمالي لتضمينات المتجهات)، تعد متغيرات IVF خيارًا أفضل من أنواع الفهرس المستندة إلى الرسم البياني.

• بالنسبة للبحث الذي يحتوي على أعلى K متوسط الحجم ونسبة تصفية عالية، فإن متغيرات IVF هي الخيارات الأفضل.

مصفوفة القرار: اختيار نوع الفهرس الأنسب

الجدول التالي هو مصفوفة قرارات يمكنك الرجوع إليها عند اختيار نوع الفهرس المناسب.

السيناريو	الفهرس الموصى به	الملاحظات
بيانات أولية تناسب الذاكرة	HNSW، IVF + التنقيح	استخدم HNSW للاستدعاء المنخفضk/عالي الاستدعاء.
البيانات الأولية على القرص، SSD	DiskANN	الأمثل للاستعلامات الحساسة لوقت الاستجابة.
بيانات أولية على القرص، ذاكرة وصول عشوائي محدودة	IVFPQ/SQ + mmap	يوازن بين الوصول إلى الذاكرة والقرص.
نسبة تصفية عالية (>95%)	القوة الغاشمة (FLAT)	يتجنب النفقات العامة للفهرس للمجموعات المرشحة الصغيرة.
كبير k (≥1% من مجموعة البيانات)	IVF	يقلل التقليم العنقودي من العمليات الحسابية.
معدل استرجاع مرتفع للغاية (>99%)	القوة الغاشمة (FLAT) + وحدات معالجة الرسوميات	--

تقدير استخدام الذاكرة

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

على وجه التحديد، يمكن حساب استخدام ذاكرة الفهرس على النحو التالي:

استخدام ذاكرة فهرس IVF

توازن فهارس IVF بين كفاءة الذاكرة وأداء البحث من خلال تقسيم البيانات إلى مجموعات. فيما يلي تفصيل للذاكرة المستخدمة من قبل مليون متجه ذي 128 بُعدًا مفهرسًا باستخدام متغيرات IVF.

1. حساب الذاكرة المستخدمة من قبل المتجهات المركزية.

   تمكّن أنواع الفهرس من سلسلة IVF Milvus من تجميع المتجهات في مجموعات باستخدام التقسيم القائم على النقط المركزية. يتم تضمين كل مركزية في الفهرس في تضمين المتجهات الخام. عند تقسيم المتجهات إلى 2000 مجموعة، يمكن حساب استخدام الذاكرة على النحو التالي:

   2,000 clusters × 128 dimensions × 4 bytes = 1.0 MB
   

2. حساب الذاكرة المستخدمة بواسطة تعيينات المجموعات.

   يتم تعيين كل تضمين متجه إلى مجموعة وتخزينها كمعرّفات أعداد صحيحة. بالنسبة إلى 2,000 مجموعة، يكفي عدد صحيح بحجم 2 بايت. يمكن حساب استخدام الذاكرة على النحو التالي:

   1,000,000 vectors × 2 bytes = 2.0 MB
   

3. حساب الضغط الناجم عن التكميم.

   تستخدم متغيرات IVF عادةً PQ و SQ8، ويمكن تقدير استخدام الذاكرة على النحو التالي:

   • باستخدام PQ مع 8 وحدات تكميم فرعية

     1,000,000 vectors × 8 bytes = 8.0 MB
     

   • باستخدام SQ8

     1,000,000 vectors × 128 dimensions × 1 byte = 128 MB 
     

   يسرد الجدول التالي الاستخدام التقديري للذاكرة مع تكوينات مختلفة:

   التكوين	تقدير الذاكرة	إجمالي الذاكرة
   IVF-PQ (بدون تنقيح)	1.0 ميجا بايت + 2.0 ميجا بايت + 8.0 ميجا بايت	11.0 ميغابايت
   IVF-PQ + 10٪ تنقيح أولي	1.0 ميجا بايت + 2.0 ميجا بايت + 8.0 ميجا بايت + 51.2 ميجا بايت	62.2 ميغابايت
   IVF-SQ8 (بدون تنقيح)	1.0 ميجا بايت + 2.0 ميجا بايت + 128 ميجا بايت	131.0 ميغابايت
   IVF-FLAT (متجهات خام كاملة)	1.0 ميجا بايت + 2.0 ميجا بايت + 512 ميجا بايت	515.0 ميغابايت

4. حساب النفقات العامة للتنقية.

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

   10 (topK) x 5 (expansion rate) = 50 candidates
   50 candidates x 128 dimensions x 4 bytes = 25.6 KB
   

استخدام ذاكرة الفهرس القائم على الرسم البياني

تتطلب أنواع الفهارس المستندة إلى الرسم البياني مثل HNSW ذاكرة كبيرة لتخزين كل من بنية الرسم البياني والتضمينات المتجهة الخام. فيما يلي تحليل مفصل للذاكرة التي يستهلكها مليون متجه ذي 128 بُعدًا مفهرسًا باستخدام نوع فهرس HNSW.

1. احسب الذاكرة التي تستخدمها بنية الرسم البياني.

   يحتفظ كل متجه في HNSW باتصالات مع جيرانه. مع درجة رسم بياني (حواف لكل عقدة) تبلغ 32، يمكن حساب الذاكرة المستهلكة على النحو التالي:

   1,000,000 vectors × 32 links × 4 bytes (for 32-bit integer storage) = 128 MB  
   

2. حساب الذاكرة المستخدمة بواسطة تضمينات المتجهات الخام.

   يمكن حساب الذاكرة المستهلكة من خلال تخزين متجهات FP32 غير المضغوطة على النحو التالي:

   1,000,000 vectors × 128 dimensions × 4 bytes = 512 MB  
   

   عند استخدام HNSW لفهرسة مليون تضمين متجه ذي 128 بُعدًا، سيكون إجمالي الذاكرة المستخدمة 128 ميغابايت (رسم بياني) + 512 ميغابايت (متجهات) = 640 ميغابايت.

3. احسب الضغط الناتج عن التكميم.

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

   1,000,000 vectors × 8 bytes = 8 MB
   

   يحقق ذلك معدل ضغط يبلغ 64 ضعفًا عند مقارنته بتضمينات المتجهات الخام، ويكون إجمالي الذاكرة المستخدمة بواسطة نوع فهرس HNSWPQ 128 ميغابايت (رسم بياني) + 8 ميغابايت (متجه مضغوط) = 136 ميغابايت.

4. حساب النفقات العامة للتنقيح.

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

   10 (topK) x 5 (expansion rate) = 50 candidates
   50 candidates x 128 dimensions x 4 bytes = 25.6 KB
   

اعتبارات أخرى

بينما تعمل فهارس IVF والفهارس المستندة إلى الرسم البياني على تحسين استخدام الذاكرة من خلال التكميم، فإن الملفات المعينة بالذاكرة (mmap) وDiskANN تعالج سيناريوهات معالجة مجموعات البيانات التي تتجاوز ذاكرة الوصول العشوائي (RAM) المتاحة.

DiskANN

DiskANN عبارة عن فهرس قائم على الرسم البياني Vamana الذي يربط نقاط البيانات للتنقل الفعال أثناء البحث مع تطبيق PQ لتقليل حجم المتجهات وتمكين حساب المسافة التقريبية السريعة بين المتجهات.

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

ملفات تعيين الذاكرة (mmap)

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

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