التخزين الأمثل لهيكل البيانات للبحث السريع والمثابرة

Question

سيناريو

لدي الطرق التالية:

public void AddItemSecurity(int itemId, int[] userIds)
public int[] GetValidItemIds(int userId)

في البداية أفكر في التخزين في النموذج:

itemId -> userId, userId, userId

و

userId -> itemId, itemId, itemId

AddItemSecurity يعتمد على كيفية الحصول على بيانات من واجهة برمجة تطبيقات طرف ثالث ، GetValidItemIds هو كيف أريد استخدامه في وقت التشغيل.

يحتمل أن يكون هناك 2000 مستخدم و 10 ملايين عنصر. معرف العنصر في النموذج: 2007123456 ، 2010001234 (10 أرقام حيث تمثل الأربعة الأولى العام).

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

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

إذا كان معرف العنصر قد بدأ في 0 ، فكرت في إنشاء صفيف بايت بطول MaxItemId / 8 لكل مستخدم ، وتعيين بت صحيح/خطأ إذا كان العنصر موجودًا أم لا. من شأن ذلك أن يحد من طول الصفيف إلى ما يزيد قليلاً عن 1 ميجابايت لكل مستخدم ويعطي بحثًا سريعًا بالإضافة إلى طريقة سهلة لتحديث القائمة لكل مستخدم. من خلال استمرار هذا الملفات المعينة الذاكرة مع إطار .NET 4 ، أعتقد أنني سأحصل على تخزين مؤقت لائق أيضًا (إذا كان لدى الجهاز ذاكرة الوصول العشوائي كافية) دون تنفيذ منطق التخزين المؤقت بنفسي. قد يكون تحليل الهوية ، وتجريد العام ، وتخزين صفيف سنويًا حلاً.

يمكن تسلسل قائمة itemId -> userId [] مباشرة إلى القرص وقراءة/الكتابة باستخدام عادي FileStream من أجل الاستمرار في القائمة والاختلاف عندما تكون هناك تغييرات.

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

سؤال

هل يجب أن أستمر في تجربة هذا النهج ، أم أن هناك مسارات أخرى يجب استكشافها أيضًا؟ أفكر في أن SQL Server لن يؤدي بسرعة كافية ، وسيعطيه عاماً (على الأقل إذا تم استضافته على خادم مختلف) ، لكن افتراضاتي قد تكون خاطئة. أي فكرة أو رؤى حول هذه المسألة موضع تقدير. وأريد أن أحاول حلها دون إضافة الكثير من الأجهزة :)

تحديث 2010-03-31

لقد اختبرت الآن مع SQL Server 2008 في ظل الشروط التالية.

• جدول مع عمودين (userId ، itemId) كلاهما int
• فهرس مجموعات على العمودين
• تمت إضافة ~ 800.000 عنصر لـ 180 مستخدمًا - إجمالي 144 مليون صف
• تخصيص ذاكرة الوصول العشوائي 4 جيجابايت لخادم SQL
• كمبيوتر محمول مزدوج 2.66 جيجا هرتز
• قرص SSD
• استخدم sqldatareader لقراءة جميع العناصر في قائمة
• حلقة على جميع المستخدمين

إذا قمت بتشغيل موضوع واحد ، فسيبلغ متوسطه في 0.2 ثانية. عندما أضيف موضوعًا ثانيًا ، فإنه يصل إلى 0.4 ثانية ، وهو ما لا يزال على ما يرام. من هناك على النتائج تتناقص. إضافة موضوع ثالث يجلب الكثير من الاستعلامات حتى 2 seonds. خيط فورث ، حتى 4 ثوانٍ ، يمتد بعض الاستعلامات لمدة تصل إلى 50 ثانية.

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

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

تحديث 2010-03-31 #2

لقد أجريت اختبارًا سريعًا مع نفس البيانات التي وضعتها كبتات في الملفات المعينة للذاكرة. يؤدي أداء أفضل بكثير. ستة خيوط تعطي أوقات الوصول بين 0.02s و 0.06s. ذاكرة بحتة ملزمة. تم تعيين الملفات المعينة بواسطة عملية واحدة ، وتم الوصول إليها من قبل ستة آخرين في وقت واحد. وبينما استغرق قاعدة SQL 4 جيجابايت ، استغرقت الملفات على القرص 23 ميجابايت.

Answer 1

بعد الكثير من الاختبارات ، انتهى بي الأمر باستخدام الملفات المعينة للذاكرة ، ووضع علامات عليها مع البت المتفرق (NTFS) ، باستخدام التعليمات البرمجية من ملفات NTFS متناثرة مع C#.

ويكيبيديا لديها شرح لما أ ملف متفرق هو.

تتمثل فوائد استخدام ملف متناثر في أنه لا يتعين عليّ الاهتمام بمجموعة الهوية الخاصة بي. إذا كنت أكتب فقط معرفًا بين 2006000000 و 2010999999 ، فإن الملف سيخصص فقط 625،000 بايت من إزاحة 250،750،000 في الملف. جميع المساحة حتى هذا الإزاحة غير مخصصة في نظام الملفات. يتم تخزين كل معرّف على أنه مجموعة محددة في الملف. نوع من المعالجة كصفيف بت. وإذا تغير تسلسل المعرف فجأة ، فسيتم تخصيصه في جزء آخر من الملف.

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

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

والجزء الجيد هو أنه يمكن مشاركة الملفات المعينة للذاكرة مع Java أيضًا (والتي تبين أنها شيء مطلوب). لدى Java أيضًا دعمًا للملفات المعينة للذاكرة على Windows ، وتنفيذ منطق القراءة/الكتابة تافهة إلى حد ما.

Answer 2

أعتقد حقًا أنك يجب أن تجرب قاعدة بيانات لطيفة قبل اتخاذ قرارك. شيء من هذا القبيل سيكون تحديا للحفاظ على المدى الطويل. قاعدة المستخدم الخاصة بك هي في الواقع صغيرة جدا. يجب أن يكون SQL Server قادرًا على التعامل مع ما تحتاجه دون أي مشاكل.

Answer 3

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

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