خدمة مجموعات الخرائط 50x أسرع باستخدام التخزين المؤقت الأكثر ذكاءً

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

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

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

مشكلة تحجيم وحل ساذج

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

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

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

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

لفهم عدم كفاءة الحل الساذج بشكل أفضل ، دعنا نحللها في سياق استعلام العلامة:

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

مع زيادة عدد العلامات ، يتدهور الأداء في الخطوتين 1 و 2:

• عندما يكون المربع المحيط كبيرًا بدرجة كافية ، وعندما تتطلب أكثر من 10000 علامة بحثًا تفصيليًا عبر JOIN ، يتباطأ استعلام قاعدة البيانات بشكل كبير (من ثانية إلى ثانيتين).
• يستغرق تغذية 10000 عنصر إلى خوارزمية تجميع الخرائط 250 مللي ثانية أخرى.

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

هندسة الحل الأمثل

يستغرق الحل البسيط وقتًا أطول بكثير لإكمال استعلام أسوأ حالة: الحد الأقصى لمربع الإحاطة في منطقة كثيفة العلامات. في المقابل ، سيستغرق الحل الأمثل 73 مللي ثانية فقط ، وهو ما يمثل تسريعًا يبلغ 58x تقريبًا. من مستوى عالي يبدو كالتالي:

1. استراتيجية التخزين المؤقت. استرجع العلامات والمجموعات في مربع محيط من ذاكرة تخزين مؤقت خاصة بمستوى التكبير / التصغير.
2. تفاصيل العلامة الإضافية (اختياري). قم بتحسين العلامات بحمولة تم جلبها من قاعدة البيانات.
3. إرجاع النتيجة. إرجاع العلامات والمجموعات إلى العميل.

يكمن التعقيد الرئيسي في بنية ذاكرة التخزين المؤقت (أي الخطوة الأولى).

الخطوة 1: استراتيجية التخزين المؤقت

تتكون هذه الخطوة الرئيسية من ستة مكونات:

تقنية

Redis هي قاعدة بيانات سريعة في الذاكرة تُستخدم عادةً كذاكرة تخزين مؤقت. تستخدم الفهرسة الجغرافية المكانية المضمنة خوارزمية Geohash للتخزين الفعال واسترجاع نقاط خطوط الطول والعرض ، وهو بالضبط ما نحتاجه لعلاماتنا.

ذاكرة تخزين مؤقت لكل مستوى تكبير

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

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

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

لدعم جميع مستويات التكبير في خرائط Google - باستثناء المستوى صفر ، الذي تم تصغيره بعيدًا جدًا - سننشئ 20 ذاكرة تخزين مؤقت مميزة. ستخزن كل ذاكرة تخزين مؤقت جميع العلامات والعناقيد للخريطة بأكملها ، كما تم تجميعها لمستوى التكبير / التصغير الذي تمثله.

أنواع بيانات ذاكرة التخزين المؤقت

ستخزن كل ذاكرة تخزين مؤقت مجموعات وعلامات فردية. لأي نوع من الإدخال ، سنحتاج إلى ملء عدة حقول:

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

ملء المخابئ

لملء ذاكرات التخزين المؤقت ، نقوم باسترداد جميع العلامات من قاعدة البيانات. لكل مستوى تكبير / تصغير ، نقوم بتنفيذ خوارزمية تجميع الخرائط. نستخدم GEOADD من GEOADD لإدراج العلامات والمجموعات الناتجة في ذاكرة التخزين المؤقت لمستوى التكبير / التصغير المقابل ، وتمريرها على طول خط العرض وخط الطول ، بالإضافة إلى سلسلة JSON الموصوفة سابقًا.

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

جاري الاستعلام عن ذاكرة التخزين المؤقت

بالنسبة إلى الطلب الوارد ، نقوم بتمرير المربع المحيط المحدد إلى الأمر GEOSEARCH ، والذي يستعلم عن ذاكرة التخزين المؤقت لمستوى التكبير / التصغير المحدد لاسترداد المرشحات والمجموعة المرشحة في المنطقة.

تصميم خطة تحديث ذاكرة التخزين المؤقت

يعد تحديث ذاكرة التخزين المؤقت المكون من 20 مستوى أمرًا مكلفًا ، لذا فمن الأفضل تحديثه بشكل غير متكرر كما تسمح به متطلبات مشروعك. على سبيل المثال ، تؤدي إضافة أو إزالة منشأة رياضية في Playsports فقط إلى وضع علامة على ذاكرة التخزين المؤقت على أنها قديمة ؛ وظيفة cron كل ساعة ثم تحديث ذاكرة التخزين المؤقت ، إذا لزم الأمر. المزيد عن هذا في قسم Staleness Cache.

الخطوة 2: تفاصيل العلامة الإضافية (اختياري)

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

يأخذ الحل الأمثل لدينا معرفات العلامات الفردية من نتيجة ذاكرة التخزين المؤقت ويجلب تفاصيلها من قاعدة البيانات. نحن الآن نبحث فقط عن العلامات الفردية المتبقية بعد التجميع. لن يكون هناك الكثير منها عند تصغير الخريطة (لأن لدينا مجموعات في الغالب) ولا عند التكبير (لأن المنطقة ستكون صغيرة).

في المقابل ، يبحث الحل الساذج عن جميع العلامات في المربع المحيط (وتفاصيلها) قبل التجميع. وبالتالي ، فإن هذه الخطوة - اختيارية ، ولكنها مهمة للعديد من التطبيقات - تعمل الآن بشكل أسرع.

الخطوة 3: إعادة النتيجة

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

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

الآن دعونا نلقي نظرة على عاملين إضافيين:

احتياجات الموارد

لنفترض أن خريطة التطبيق تحتوي على إجمالي عدد N من العلامات. نظرًا لوجود ما يصل إلى 20 مستوى من مستويات التكبير / التصغير ، فسنحتاج إلى تخزين عناصر ذاكرة التخزين المؤقت 20N على الأكثر. ومع ذلك ، من الناحية العملية ، غالبًا ما يكون العدد الفعلي لعناصر ذاكرة التخزين المؤقت أقل بكثير بسبب التجميع ، خاصة في مستويات التكبير / التصغير المنخفضة. في الواقع ، إجمالي عدد عناصر ذاكرة التخزين المؤقت الموزعة بين جميع ذاكرات التخزين المؤقت لـ Playsports هو 2N فقط.

علاوة على ذلك ، إذا افترضنا أن طول قيمة ذاكرة التخزين المؤقت (JSON المشروط) هو 250 حرفًا تقريبًا (افتراض معقول ، على الأقل لألعاب Playsports) وحجم السلسلة هو 1 بايت لكل حرف ، فإن مقدار التخزين المؤقت المطلوب لـ ستكون قيم JSON تقريبًا 2 * N * 250 بايت.

نضيف إلى هذا الشكل هياكل البيانات الداخلية لـ Redis للمجموعات المصنفة التي يستخدمها GEOADD . يستخدم Redis 85 ميغابايت من الذاكرة لمليون زوج صغير من قيم المفاتيح ، لذا يمكننا افتراض أن حساب Redis الداخلي أقل من 100 بايت لكل عنصر ذاكرة تخزين مؤقت. هذا يعني أنه يمكننا استخدام مثيل Redis سعة 1 غيغابايت من ذاكرة الوصول العشوائي لدعم ما يصل إلى 1.4 مليون علامة. حتى في السيناريو غير المحتمل المتمثل في انتشار العلامات بالتساوي عبر الخريطة بأكملها ، مما يؤدي إلى اقتراب عدد عناصر ذاكرة التخزين المؤقت من 20 نيوتن ، لا يزال من الممكن أن يرتفع N إلى 140.000. نظرًا لأن مثيل Redis يمكنه التعامل مع أكثر من 4 مليارات مفتاح (2 ³² ، على وجه الدقة) ، فهذا ليس عاملاً مقيدًا.

فساد مخبأ

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

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

تفوق استراتيجيات التخزين المؤقت خوارزميات تجميع الخرائط

الحل الأمثل لـ Playsports - أسرع من الحل البسيط بأكثر من 50 مرة - يعمل بشكل جيد. يجب أن تستمر في العمل بشكل جيد ، حتى نصل إلى 1.4 مليون علامة أو أكثر من 100 ضعف البيانات الموجودة.

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

مزيد من القراءة على مدونة Toptal Engineering:

• مسح لأفضل أدوات رسم الخرائط عبر الإنترنت لمطوري الويب: خارطة الطريق إلى خارطة الطريق
• مغامرات في برمجة وتطوير نظام تحديد المواقع العالمي (GPS): برنامج تعليمي جغرافي مكاني