50 برابر سریعتر داده های نقشه: استراتژی ذخیره سازی خوشه نقشه

اجزای نقشه که دارای نشانگرهای مکان هستند امروزه در برنامه های تلفن همراه رایج هستند. به عنوان مثال، برنامه Airbnb به طور برجسته چنین نشانگرهایی را دارد که از یک سرویس وب واکشی شده اند تا ویژگی های موجود را روی نقشه نشان دهند.

برای اطمینان از اینکه حجم داده‌های واکشی شده با افزایش تعداد نشانگرها غیرقابل مدیریت نمی‌شود، سرور آن نشانگرها را قبل از ارسال به مشتری با هم گروه‌بندی می‌کند. آ خوشه نقشه یک نشانگر تخصصی است که موقعیت آن برابر با میانگین موقعیت نشانگرهایی است که زیرمجموعه آن قرار می گیرد. با تعداد نشانگرهایی که نشان می دهد برچسب گذاری شده است.

با این حال، خوشه‌های سرویس‌دهی می‌توانند گلوگاه‌های عملکردی ایجاد کنند، زیرا یک وب سرویس باید هر نشانگر را در یک منطقه جغرافیایی معین از پایگاه داده بازیابی کند. خوشبختانه، این مشکل را می توان با یک استراتژی کش حل کرد. برای درک بهتر نحوه طراحی و نگهداری یک کش، اجازه دهید به مثالی از نقشه پایانی API که برای اپلیکیشن Playsports.

یک مشکل مقیاس پذیری و یک راه حل ساده لوحانه

در نقشه Playsports، هر نشانگر نشان دهنده یک مرکز ورزشی است. نقطه پایانی API نقشه باید فهرستی از نشانگرها و خوشه‌های نشانگر را با توجه به سطح بزرگنمایی و یک کادر محدود ارائه دهد.

اگر تعداد نشانگرها به اندازه کافی کم باشد، می‌توانیم همه نشانگرها را در کادر محدود از پایگاه داده بارگذاری کنیم، در صورت لزوم خوشه‌بندی کنیم و نشانگرها و خوشه‌های حاصل را به مشتری برگردانیم.

در ابتدا، حداکثر تعداد نشانگرها در هر جعبه مرزی قابل دسترسی در Playsports 400 بود که منجر به سرعت نقطه پایانی ~0.5 ثانیه شد. اجرای راه حل ساده لوحانه برای این مورد کافی بود.

با افزایش تعداد نشانگرها، ناکارآمدی مکانیسم آشکار شد. پس از افزودن 10000 نشانگر جدید برای امکانات ورزشی، سرعت نقطه پایانی در برخی از سطوح زوم به 4.3 ثانیه کاهش یافت. این نرخ بسیار کمتر از مدت زمان یک ثانیه ای است که معمولاً در نظر گرفته می شود حداکثر تاخیر قابل قبول برای یک اقدام کاربر در یک برنامه تلفن همراه.

برای درک بهتر ناکارآمدی راه حل ساده، بیایید آن را در زمینه پرس و جو نشانگر تحلیل کنیم:

1. از پایگاه داده، همه نشانگرها را در کادر محدود بازیابی کنید. برای اکثر برنامه ها، این مرحله باید شامل واکشی جزئیات نشانگر فراتر از موقعیت جغرافیایی/طولایی باشد. به عنوان مثال، نشانگرهای Airbnb شامل قیمت است، اینکه آیا کاربر قبلاً ملک را مشاهده کرده است یا خیر و آیا آن را به عنوان مورد علاقه علامت گذاری کرده است.
2. روی نشانگرهای بازیابی شده، یک الگوریتم خوشه بندی نقشه را اجرا کنید که سطح زوم را در خود جای داده است.
3. برگشت خوشه ها و نشانگرها (جزئیات) به مشتری.

با افزایش تعداد نشانگرها، عملکرد در مراحل 1 و 2 بدتر می شود:

• زمانی که کادر محدود کننده به اندازه کافی بزرگ باشد، و زمانی که بیش از 10000 نشانگر نیاز به جستجوی جزئیات از طریق JOIN دارند، سرعت جستجوی پایگاه داده به طور چشمگیری کاهش می یابد (1 تا 2 ثانیه).
• تغذیه 10000 مورد به الگوریتم خوشه بندی نقشه 250 میلی ثانیه دیگر طول می کشد.

با فرض یک اندازه پنجره ثابت، زمانی که یک جعبه مرزی نسبتاً بزرگ است، سطح بزرگنمایی معمولاً پایین است (یعنی بسیار کوچک‌نمایی شده است). در سطوح کم زوم، نتایج به نفع خوشه‌هاست تا از شلوغی بصری جلوگیری شود. بنابراین، بیشترین پتانسیل برای بهینه سازی در مرحله اول راه حل نهفته است، جایی که هزاران نشانگر جداگانه بارگذاری می شوند. ما در نتیجه به اکثر این نشانگرها نیاز نداریم. ما فقط به هر یک از آنها نیاز داریم تا در یک خوشه حساب شوند.

معماری راه حل بهینه شده

راه حل ساده لوحانه برای تکمیل یک پرس و جو در بدترین حالت به طور قابل توجهی بیشتر طول می کشد: یک کادر حد اکثر در یک منطقه متراکم نشانگر. در مقابل، راه حل بهینه شده فقط 73 میلی ثانیه طول می کشد که نشان دهنده سرعت 58 برابری است. از یک سطح بالا، به نظر می رسد این است:

1. استراتژی ذخیره سازی نشانگرها و خوشه‌ها را در یک جعبه محدود از یک حافظه پنهان سطح زوم خاص بازیابی کنید.
2. جزئیات نشانگر اضافی (اختیاری). نشانگرها را با باری که از پایگاه داده واکشی شده است، تقویت کنید.
3. برگرداندن نتیجه نشانگرها و خوشه ها را به مشتری برگردانید.

پیچیدگی اصلی در معماری کش (یعنی مرحله اول) نهفته است.

مرحله 1: استراتژی ذخیره سازی

این مرحله اصلی از شش جزء تشکیل شده است:

فن آوری

Redis یک پایگاه داده سریع و درون حافظه است که معمولاً به عنوان کش استفاده می شود. نمایه سازی مکانی داخلی آن از الگوریتم Geohash استفاده می کند برای ذخیره سازی و بازیابی کارآمد نقاط طول و عرض جغرافیایی، که دقیقاً همان چیزی است که ما برای نشانگرهای خود نیاز داریم.

کش برای هر سطح زوم

درجه خوشه‌بندی نقشه (اعم از اینکه نشانگرهای منفرد یا خوشه‌ها برگردانده شوند) با سطح بزرگنمایی ارسال شده به نقطه پایانی تعیین می‌شود.

• برای سطوح بزرگنمایی بالا (یعنی بزرگنمایی نزدیک)، نتیجه به نفع نشانگرهای جداگانه خواهد بود، به جز در مناطق متراکم نشانگر.
• برای سطوح بزرگنمایی کم (یعنی بزرگنمایی بسیار زیاد)، نتیجه به نفع خوشه ها خواهد بود، به جز در مناطق پراکنده نشانگر.

نقشه های گوگل بسته به منطقه از سطوح بزرگنمایی از صفر تا حداکثر 20 پشتیبانی می کند. (محدوده های پشتیبانی شده توسط سایر خدمات نقشه مشابه هستند. به عنوان مثال، Mapbox از سطوح بزرگنمایی از صفر تا حداکثر 23 استفاده می کند.) از آنجایی که این سطوح بزرگنمایی نیز مقادیر صحیح هستند، می توانیم به سادگی یک کش جداگانه برای هر سطح بزرگنمایی ایجاد کنیم.

برای پشتیبانی از تمام سطوح بزرگ‌نمایی در Google Maps – به جز سطح صفر، که خیلی کوچک‌نمایی شده است – ما 20 کش مجزا ایجاد خواهیم کرد. هر کش همه نشانگرها و خوشه‌ها را برای کل نقشه ذخیره می‌کند، همانطور که برای سطح بزرگنمایی که نشان‌دهنده آن است.

انواع داده های کش

هر کش می تواند خوشه ها و نشانگرهای جداگانه را ذخیره کند. برای هر نوع ورودی، باید چندین فیلد را پر کنیم:

با این حال، Redis به کاربران این امکان را می دهد که فقط مکان، به اضافه یک رشته، را به عنوان مقدار در یک مجموعه جغرافیایی ذخیره کنند. برای دور زدن این محدودیت، فیلدهای بالا را در یک رشته JSON سریال می کنیم. سپس از این رشته به عنوان مقدار در Redis استفاده می کنیم. حداکثر اندازه کلیدها و مقادیر در Redis 512 مگابایت است که برای این مورد کافی است.

پر کردن کش ها

برای پر کردن کش ها، همه نشانگرها را از پایگاه داده بازیابی می کنیم. برای هر سطح بزرگنمایی، الگوریتم خوشه بندی نقشه را اجرا می کنیم. ما از Redis استفاده می کنیم GEOADD برای قرار دادن نشانگرها و خوشه های به دست آمده در حافظه پنهان سطح بزرگنمایی مربوطه، و عبور از طول و عرض جغرافیایی، به علاوه رشته JSON که قبلاً توضیح داده شد.

اجرای الگوریتم خوشه‌بندی نقشه بر روی کل نقشه در این مرحله (به جای یک جعبه محدود از کاربر، در صورت تقاضا) ممکن است از نظر تئوری تفاوت‌هایی در لبه‌ها در قرارگیری خوشه ایجاد کند، اما تجربه کلی کاربر یکسان خواهد ماند.

پرس و جو از کش

برای یک درخواست ورودی، کادر محدود داده شده را به Redis منتقل می کنیم 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 مگابایت حافظه برای 1 میلیون جفت کلید-مقدار کوچک، بنابراین می‌توانیم فرض کنیم که داخلی‌های Redis کمتر از 100 بایت در هر آیتم کش دارند. این بدان معناست که ما می‌توانیم از یک نمونه 1 گیگابایت رم Redis برای پشتیبانی از 1.4 میلیون نشانگر استفاده کنیم. حتی در سناریوی بعید که نشانگرها به طور یکنواخت در کل نقشه پخش شده باشند، که منجر به تعداد آیتم های حافظه پنهان نزدیک به 20N می شود، N همچنان می تواند تا 140000 افزایش یابد. از آنجایی که یک نمونه Redis می تواند بیش از 4 میلیارد کلید را مدیریت کند (2³²به طور دقیق)، این یک عامل محدود کننده نیست.

کهنگی کش

بسته به مورد استفاده، ممکن است تنها به‌صورت دوره‌ای حافظه پنهان را بازخوانی نکنید. در چنین مواردی، می‌توانیم از صف کار با نرخ محدود استفاده کنیم. این امر باعث کاهش کهنگی حافظه نهان می‌شود، در حالی که همچنان تعداد بازخوانی‌های حافظه پنهان و در نتیجه بارگذاری روی سیستم را محدود می‌کند.

پس از هر به روز رسانی پایگاه داده، ما یک کار به روز رسانی کش را در صف قرار می دهیم. این صف تعداد کارها را به M در ساعت محدود می کند. این مصالحه امکان به‌روزرسانی‌های سریع‌تر از ساعتی را فراهم می‌کند و در عین حال بار نسبتاً کم را روی سیستم (بسته به M) حفظ می‌کند.

استراتژی های ذخیره سازی از الگوریتم های خوشه بندی نقشه بیشتر است

راه حل بهینه شده برای Playsports – بیش از 50 برابر سریعتر از راه حل ساده – به خوبی کار کرده است. باید به خوبی به کار خود ادامه دهد، تا زمانی که به 1.4 میلیون نشانگر یا بیش از 100 برابر داده های موجود برسیم.

برای اکثر درخواست‌های خدمات وب مبتنی بر نقشه، نوعی پیش‌محاسبه برای امکان مقیاس‌پذیری لازم است. نوع فناوری مورد استفاده، و همچنین طراحی خاص، به نیازهای تجاری بستگی دارد. نیازهای کهنه بودن حافظه پنهان، افزایش نشانگر و تعداد نشانگرها ویژگی های مهمی هستند که باید در طراحی راه حل مورد توجه قرار گیرند.

ادامه مطلب در وبلاگ مهندسی تاپتال: