مقدمة موجزة عن مؤشر ScaNN

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

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

• FastScan عبارة عن مسار بحث PQ مُحسَّن مكون من 4 بت PQ مُحسَّن بـ SIMD يقلل من عنق الزجاجة التقليدي الذي يمثل عبء على الذاكرة من خلال الاحتفاظ بمزيد من العمل داخل سجلات وحدة المعالجة المركزية.

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

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

خلاصة IVFPPQ

تم اقتراح ScaNN من قِبل Google في عام 2020، وتشير الورقة البحثية إلى تحسن الأداء بمقدار 3 أضعاف مقارنةً ب HNSW على مجموعة بيانات GloVe. يمكنك الرجوع إلى الورقة البحث ية الأصلية والتنفيذ مفتوح المصدر للحصول على التفاصيل.

قبل تقديم ScaNN، سنلخص بإيجاز IVFPPQ، نظرًا لأن ScaNN مبنية على نفس الإطار العام.

يرمزIVFFPPQ إلى الملف المقلوب مع تحديد كمية المنتج، وهي خوارزمية تُستخدم للبحث الفعال والواسع النطاق عن أقرب جار تقريبي (ANN) في قواعد البيانات المتجهة عالية الأبعاد. وهو عبارة عن نهج هجين يجمع بين تقنيتين، فهرس الملف المقلوب (IVF) وتكميم المنتج (PQ)، لتحقيق التوازن بين سرعة البحث واستخدام الذاكرة والدقة.

كيف يعمل IVFPPQ

تتضمن العملية خطوتين رئيسيتين أثناء الفهرسة والبحث:

• طبقة IVF: يتم تجميع المتجهات في قوائم (مجموعات) مقلوبة nlist. في وقت الاستعلام، تقوم بزيارة مجموعة فرعية فقط من المجموعات (nprobe) لمقايضة الاستدعاء والكمون/الإنتاجية.

• طبقة PQ: داخل كل مجموعة تمت زيارتها، يتم تقسيم كل متجه ذي بُعد D إلى m متجهات فرعية، كل منها ذو بُعد (D/m). يتم تكميم كل متجه فرعي من خلال تعيينه إلى أقرب نقطة مركزية في دفتر الترميز الفرعي الخاص به. إذا كان دفتر الترميز الفرعي يحتوي على 256 مركزًا، فيمكن تمثيل كل متجه فرعي برمز uint8 (معرّف في [0، 255]).

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

D(q, X) = D(q, u0) + D(q, u1) + D(q, u2) + ... + D(q, un)

= L(q، id1) + L(q، id2) + L(q، id3) + ... + L(q، idn)

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

على سبيل المثال، بالنسبة إلى المتجهات ذات الـ 128 بُعدًا المقسمة إلى 32 متجهًا فرعيًا لكل منها 4 أبعاد، إذا تم ترميز كل متجه فرعي بمعرف uint8 ، تنخفض تكلفة التخزين لكل متجه من (128 × 4) بايت إلى (32 × 1) بايت - أي بتخفيض 1/16.

تحسينات ScaNN القائمة على IVFPPQ

باختصار، تعمل ScaNN على تحسين IVFPPQ في جانبين:

1. التحديد الكمي: تقترح ScaNN هدفاً يتجاوز مجرد استبدال كل متجه فرعي بأقرب نقطة مركزية له من k-means (أي تقليل خطأ إعادة البناء).

2. كفاءة البحث: تعمل ScaNN على تسريع البحث القائم على LUT، والذي غالبًا ما يكون مرتبطًا بالذاكرة، من خلال مسار FastScan سهل الاستخدام SIMD.

فقدان الكمية المدرك للنتيجة

نظرًا لأن التحليل يعتمد على مقياس IP، بعد أن تقوم ScaNN بتحليل خطأ التكميم إلى مكونات متوازية ومتعامدة، فإن المكون المتوازي فقط يؤثر على النتيجة، لذلك يجب تطبيق حد جزائي أكبر. وبالتالي، يمكن إعادة كتابة دالة الخسارة على النحو التالي:

$$\begin{array}{r}{\displaystyle \mathrm{\ell }({\mathrm{xi}}_{},{\mathrm{x~i}}_{},{\stackrel{}{\mathrm{x~i}}}_{},w)}\end{array}$$$$بداية{محاذاة} \ll\left(x_i, \tilde{x}_i, w\right) &=h_{\|}\left(w,\left\|x_i\right\|\right)\left\|r_{\|}\left(x_i, \tilde{x}_i\right)\right\|^2 +h_{\perp}\left(w,\left\|x_i\right\|\right)\left\|r_{\perp}\left(x_i,$$ \tilde{e{x}_i_right$$)\right\\^2$$$$\نهاية$$ $$\begin{array}{r}(س\end{array}$$ط$$\begin{array}{r}،\end{array}$$ س ~ط$$\begin{array}{r}،\end{array}$$ =ح $$\begin{array}{l}(ث,\end{array}$$∥$$\begin{array}{l}\Vert \end{array}$$ $$\begin{array}{l}ص\end{array}$$ $$\begin{array}{l}(س\end{array}$$ط$$\begin{array}{l}،\end{array}$$ س~ط) 2 +ح $$\begin{array}{l}(ث،س\end{array}$$ط$$\begin{array}{l}){}_{}\end{array}$$ $$\begin{array}{l}(س\end{array}$$ط$$\begin{array}{l}،\end{array}$$

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

يُظهر الشكل الأيسر قياسًا كميًا ضعيفًا لأن الإزاحة المتوازية تؤثر على النتيجة النهائية، بينما يُظهر الشكل الأيمن قياسًا كميًا أفضل.

4 بت PQ FastScan 4 بت

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

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

أولًا، يتم تجميع كل متجه فرعي في 16 فئة، بحيث يمكن أن تمثل قيمة 4 بت مركزًا للمجموعة - وهذا هو أصل اسم "PQ 4 بت". بعد ذلك، يتم تحويل المسافات التي يتم تمثيلها عادةً على هيئة عوامات إلى uint8 باستخدام التكميم الكمي Scalar Quantization (SQ). بهذه الطريقة، يمكن تخزين جدول البحث لمتجه فرعي واحد في سجل باستخدام 16 × 8 = 128 بت.

أخيرًا، دعونا نفحص تخطيط تخزين السجل (باستخدام مجموعة تعليمات AVX2 كمثال): يتم وضع المتجهات الفرعية لـ 32 متجهًا في سجل 128 بت، مع جدول البحث. يمكن بعد ذلك إكمال عملية "البحث" بكفاءة باستخدام تعليمات وحدة المعالجة المركزية SIMD خلط SIMD واحدة.

تخطيط السجل

خلط SIMD Shuffle للبحث

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

النتائج التجريبية المقدمة في ورقة ScaNN.

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

النتائج التجريبية

باستخدام أداة قياس قاعدة البيانات المتجهة VectorDBBench، أجرينا اختبارًا بسيطًا. كانت ميزة أداء ScaNN على أداء IVFFLAT و IVF_PQ التقليدي واضحة تمامًا. بعد الدمج في Milvus، على مجموعة بيانات Cohere1M بنفس معدل الاسترجاع، يمكن أن تصل QPS إلى 5 أضعاف أداء IVFFLAT و6 أضعاف أداء IVF_PQ.

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

نوع_الفهرس	الحالة	QPS	زمن الوصول (p99)	الاستدعاء	الذاكرة
IVFFLAT	الأداء1م	266	0.0173s	0.9544	3G
HNSW	الأداء1م	1885	0.0054s	0.9438	3.24G
IVF_PQ	الأداء1م	208	0.0292s	0.928	0.375G
ScaNN （مع_البيانات_الخام: صحيح）	الأداء1م	1215	0.0069s	0.9389	3.186G
ScaNN （مع_البيانات_الأولية: خطأ）	الأداء1م	1265	0.0071s	0.7066	0.186G

الخلاصة

يعتمد ScaNN على إطار عمل IVFPPQ المألوف ولكنه يدفعه إلى أبعد من ذلك بكثير من خلال العمل الهندسي العميق في كل من التكميم وتسريع البحث منخفض المستوى. من خلال مواءمة هدف التكميم مع جودة الترتيب والتخلص من اختناقات الذاكرة في الحلقة الداخلية، تجمع ScaNN بين التكميم الواعي بالدرجات ومسار PQ FastScan رباعي البتات الذي يحول عملية تقليدية مرتبطة بالذاكرة إلى عملية حسابية فعالة وملائمة ل SIMD.

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

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