ให้บริการกลุ่มแผนที่เร็วขึ้น 50 เท่าโดยใช้แคชอัจฉริยะ

ส่วนประกอบแผนที่ที่มีเครื่องหมายระบุตำแหน่งนั้นพบได้ทั่วไปในแอพมือถือในปัจจุบัน ตัวอย่างเช่น แอพ Airbnb แสดงเครื่องหมายดังกล่าวอย่างเด่นชัด ซึ่งดึงมาจากบริการเว็บ เพื่อแสดงคุณสมบัติที่พร้อมใช้งานบนแผนที่

เพื่อให้แน่ใจว่าปริมาณข้อมูลที่ดึงมาจะไม่สามารถจัดการได้เมื่อจำนวนตัวทำเครื่องหมายเพิ่มขึ้น เซิร์ฟเวอร์จะจัดกลุ่มตัวทำเครื่องหมายเหล่านั้นไว้ด้วยกันก่อนที่จะส่งไปยังไคลเอนต์ คลัสเตอร์แผนที่ เป็นเครื่องหมายเฉพาะที่มีตำแหน่งเท่ากับตำแหน่งเฉลี่ยของเครื่องหมายที่มันอยู่ภายใต้ มีป้ายกำกับจำนวนเครื่องหมายที่แสดง

อย่างไรก็ตาม คลัสเตอร์ที่ให้บริการสามารถสร้างปัญหาคอขวดด้านประสิทธิภาพได้ เนื่องจากบริการเว็บต้องดึงข้อมูลทุกเครื่องหมายภายในพื้นที่ทางภูมิศาสตร์ที่กำหนดจากฐานข้อมูล โชคดีที่ปัญหานี้สามารถแก้ไขได้ด้วยกลยุทธ์การแคช เพื่อให้เข้าใจวิธีออกแบบและบำรุงรักษาแคชได้ดีขึ้น มาดูตัวอย่างตำแหน่งข้อมูล API ของแผนที่ที่ฉันสร้างสำหรับแอป Playsports

ปัญหาการปรับขนาดและวิธีแก้ปัญหาที่ไร้เดียงสา

ในแผนที่ Playsports เครื่องหมายแต่ละอันแสดงถึงสิ่งอำนวยความสะดวกด้านกีฬา ตำแหน่งข้อมูล API ของแผนที่จำเป็นต้องส่งคืนรายการของตัวทำเครื่องหมายและกลุ่มตัวทำเครื่องหมาย โดยกำหนดระดับการซูมและกรอบขอบเขต

หากจำนวนตัวทำเครื่องหมายมีน้อยเพียงพอ เราสามารถโหลดตัวทำเครื่องหมายทั้งหมดในกล่องขอบเขตจากฐานข้อมูล คลัสเตอร์ตามความจำเป็น และส่งคืนตัวทำเครื่องหมายผลลัพธ์และคลัสเตอร์ไปยังไคลเอ็นต์

ในตอนเริ่มต้น จำนวนเครื่องหมายสูงสุดในกล่องขอบเขตที่เข้าถึงได้ใน Playsports คือ ~400 ส่งผลให้ความเร็วจุดปลายอยู่ที่ ~0.5 วินาที การใช้วิธีแก้ปัญหาที่ไร้เดียงสาก็เพียงพอแล้วสำหรับกรณีการใช้งานนี้

เมื่อจำนวนเครื่องหมายเพิ่มขึ้น ความไร้ประสิทธิภาพของกลไกก็ชัดเจน หลังจากที่เราเพิ่มเครื่องหมายแสดงสิ่งอำนวยความสะดวกด้านกีฬาใหม่ประมาณ 10,000 รายการ ความเร็วจุดปลายลดลงเหลือ ~4.3 วินาทีภายใต้ระดับการซูมบางระดับ อัตรานี้ต่ำกว่าระยะเวลาหนึ่งวินาทีซึ่งโดยทั่วไปถือว่าเป็นความล่าช้าสูงสุดที่ยอมรับได้สำหรับการดำเนินการของผู้ใช้ในแอปบนอุปกรณ์เคลื่อนที่

เพื่อให้เข้าใจถึงความไร้ประสิทธิภาพของโซลูชันไร้เดียงสามากขึ้น มาวิเคราะห์กันในบริบทของการสืบค้นเครื่องหมาย:

1. จากฐานข้อมูล ดึงเครื่องหมายทั้งหมดในกล่องขอบเขต สำหรับแอปส่วนใหญ่ ขั้นตอนนี้จำเป็นต้องมีการดึงรายละเอียดเครื่องหมายนอกเหนือจากตำแหน่งละติจูด/ลองจิจูด ตัวอย่างเช่น เครื่องหมายของ Airbnb จะระบุราคาว่าผู้ใช้ได้ดูที่พักแล้วหรือไม่และทำเครื่องหมายว่าเป็นรายการโปรดหรือไม่
2. บนตัวทำเครื่องหมายที่ดึงมา ให้ รันอัลกอริธึมการทำคลัสเตอร์แผนที่ ที่รวมระดับการซูมเข้าไว้ด้วย
3. ส่งคืน คลัสเตอร์และเครื่องหมาย (รายละเอียด) ไปยังไคลเอนต์

เมื่อจำนวนเครื่องหมายเพิ่มขึ้น ประสิทธิภาพการทำงานจะลดลงในขั้นตอนที่ 1 และ 2:

• เมื่อกรอบขอบเขตมีขนาดใหญ่เพียงพอ และเมื่อตัวทำเครื่องหมายมากกว่า 10,000 ตัวต้องการการค้นหารายละเอียดผ่าน JOIN การสืบค้นฐานข้อมูลจะช้าลงอย่างมาก (ประมาณ 1 ถึง 2 วินาที)
• การป้อน 10,000 รายการไปยังอัลกอริธึมการทำคลัสเตอร์แผนที่ใช้เวลาอีก ~ 250 มิลลิวินาที

สมมติว่าขนาดหน้าต่างคงที่ เมื่อกรอบขอบเขตค่อนข้างใหญ่ ระดับการซูมมักจะต่ำ (กล่าวคือ ซูมออกไกล) ภายใต้ระดับการซูมที่ต่ำ ผลลัพธ์มักจะชอบคลัสเตอร์เพื่อหลีกเลี่ยงภาพซ้อน ดังนั้น ศักยภาพสูงสุดสำหรับการเพิ่มประสิทธิภาพจึงอยู่ในขั้นตอนแรกของโซลูชัน ซึ่งจะมีการโหลดตัวทำเครื่องหมายแต่ละรายการนับพันรายการ เราไม่ต้องการเครื่องหมายเหล่านี้ส่วนใหญ่ในผลลัพธ์ เราต้องการเพียงแต่ละอันเพื่อนับรวมในคลัสเตอร์

การสร้างสถาปัตยกรรมโซลูชันที่เหมาะสมที่สุด

โซลูชันที่ไร้เดียงสาใช้เวลานานกว่ามากในการค้นหากรณีที่เลวร้ายที่สุด: กล่องที่มีขอบเขตสูงสุดในพื้นที่ที่มีเครื่องหมายหนาแน่น ในทางตรงกันข้าม โซลูชันที่ได้รับการเพิ่มประสิทธิภาพจะใช้เวลาเพียง 73 มิลลิวินาที ซึ่งคิดเป็นความเร็วประมาณ 58 เท่า จากระดับสูงดูเหมือนว่า:

1. กลยุทธ์การแคช ดึงเครื่องหมายและคลัสเตอร์ในกล่องขอบเขตจากแคชเฉพาะระดับการซูม
2. รายละเอียดเครื่องหมายเพิ่มเติม (ไม่บังคับ) ปรับปรุงเครื่องหมายด้วยเพย์โหลดที่ดึงมาจากฐานข้อมูล
3. ส่งคืนผลลัพธ์ ส่งคืนเครื่องหมายและคลัสเตอร์ให้กับลูกค้า

ความซับซ้อนหลักอยู่ในสถาปัตยกรรมของแคช (เช่น ขั้นตอนแรก)

ขั้นตอนที่ 1: กลยุทธ์แคช

ขั้นตอนหลักนี้ประกอบด้วยหกองค์ประกอบ:

เทคโนโลยี

Redis เป็นฐานข้อมูลในหน่วยความจำที่รวดเร็วซึ่งมักใช้เป็นแคช การทำดัชนีเชิงพื้นที่ในตัวของมันใช้อัลกอริทึม Geohash สำหรับการจัดเก็บและการดึงจุดละติจูด-ลองจิจูดอย่างมีประสิทธิภาพ ซึ่งเป็นสิ่งที่เราต้องการสำหรับเครื่องหมายของเราอย่างแม่นยำ

แคชสำหรับแต่ละระดับการซูม

ระดับของการจัดกลุ่มแผนที่ (ไม่ว่าจะส่งคืนเครื่องหมายเดี่ยวหรือคลัสเตอร์) กำหนดโดยระดับการซูมที่ส่งไปยังปลายทาง

• สำหรับระดับการซูมสูง (เช่น การซูมเข้าในระยะใกล้) ผลลัพธ์จะเหมาะกับเครื่องหมายแต่ละอัน ยกเว้นในบริเวณที่มีเครื่องหมายหนาแน่น
• สำหรับระดับการซูมต่ำ (เช่น การซูมออกไกล) ผลลัพธ์จะชอบคลัสเตอร์ ยกเว้นในบริเวณที่มีเครื่องหมายกระจัดกระจาย

Google Maps รองรับระดับการซูมจากศูนย์ถึงสูงสุด 20 ขึ้นอยู่กับพื้นที่ (ช่วงที่รองรับโดยบริการแผนที่อื่นๆ จะคล้ายกัน ตัวอย่างเช่น Mapbox ใช้ระดับการซูมจากศูนย์ถึงสูงสุด 23) เนื่องจากระดับการซูมเหล่านี้เป็นค่าจำนวนเต็ม เราจึงสามารถสร้างแคชแยกต่างหากสำหรับแต่ละระดับการซูมได้

เพื่อรองรับระดับการซูมทั้งหมดใน Google Maps—ยกเว้นระดับศูนย์ซึ่งซูมออกมากเกินไป—เราจะสร้างแคชที่แตกต่างกัน 20 รายการ แคชแต่ละรายการจะจัดเก็บเครื่องหมายและคลัสเตอร์ทั้งหมดสำหรับแผนที่ทั้งหมด ตามที่จัดกลุ่มไว้สำหรับระดับการซูมที่แสดง

ประเภทข้อมูลแคช

แต่ละแคชจะจัดเก็บคลัสเตอร์และตัวทำเครื่องหมายแต่ละรายการ สำหรับรายการประเภทใดประเภทหนึ่ง เราจะต้องกรอกข้อมูลหลายฟิลด์:

อย่างไรก็ตาม Redis อนุญาตให้ผู้ใช้จัดเก็บเฉพาะตำแหน่ง บวกกับสตริงเดียวเป็นค่าในชุดภูมิสารสนเทศ เพื่อหลีกเลี่ยงข้อจำกัดนี้ เราทำให้ฟิลด์ด้านบนเป็นอนุกรมในสตริง JSON จากนั้นเราใช้สตริงนี้เป็นค่าใน Redis ขนาดสูงสุดของทั้งคีย์และค่าใน Redis คือ 512 MB ซึ่งเพียงพอสำหรับกรณีการใช้งานนี้

เติมแคช

ในการเติมแคช เราดึงตัวทำเครื่องหมายทั้งหมดจากฐานข้อมูล สำหรับแต่ละระดับการซูม เราดำเนินการอัลกอริธึมการทำคลัสเตอร์แผนที่ เราใช้ GEOADD ของ Redis เพื่อแทรกเครื่องหมายและคลัสเตอร์ที่เป็นผลลัพธ์ลงในแคชของระดับการซูมที่เกี่ยวข้อง และส่งผ่านตามละติจูดและลองจิจูด บวกกับสตริง JSON ที่อธิบายไว้ก่อนหน้านี้

การรันอัลกอริธึมการทำคลัสเตอร์แผนที่บนทั้งแผนที่ในขั้นตอนนี้ (แทนที่จะเป็นบนกล่องขอบเขตจากผู้ใช้ ตามความต้องการ) ในทางทฤษฎีอาจสร้างความแตกต่างของขอบบางอย่างในการจัดวางคลัสเตอร์ แต่ประสบการณ์ผู้ใช้โดยรวมจะยังคงเหมือนเดิม

การสอบถามแคช

สำหรับคำขอที่เข้ามา เราส่งกล่องขอบเขตที่กำหนดไปยังคำสั่ง Redis GEOSEARCH ซึ่งจะค้นหาแคชของระดับการซูมที่กำหนดเพื่อดึงข้อมูลตัวทำเครื่องหมายและตัวเลือกคลัสเตอร์ในพื้นที่

การออกแบบแผนรีเฟรชแคช

การรีเฟรชแคช 20 ระดับมีราคาแพง ดังนั้นจึงเป็นการดีที่สุดที่จะรีเฟรชบ่อย ๆ ตามความต้องการของโปรเจ็กต์ของคุณ ตัวอย่างเช่น การเพิ่มหรือลบสิ่งอำนวยความสะดวกด้านกีฬาใน Playsports จะทำเครื่องหมายว่าแคชค้างเท่านั้น งาน cron รายชั่วโมงจะรีเฟรชแคช หากจำเป็น เพิ่มเติมเกี่ยวกับเรื่องนี้ในส่วน Cache Staleness

ขั้นตอนที่ 2: รายละเอียดเครื่องหมายเพิ่มเติม (ไม่บังคับ)

ณ จุดนี้ แอปส่วนใหญ่จะต้องดึงรายละเอียดตามรหัสเครื่องหมายแต่ละรายการ เราสามารถทำให้รายละเอียดนี้เป็นส่วนหนึ่งของค่า JSON ที่ถูกทำให้เป็นสตริงในแคชได้ แต่ในหลายๆ แอป รายละเอียดเครื่องหมายจะระบุเฉพาะผู้ใช้ เนื่องจากมีแคชที่ใช้ร่วมกันเพียงรายการเดียวสำหรับผู้ใช้ทั้งหมด จึงเป็นไปไม่ได้ที่จะจัดเก็บฟิลด์เพิ่มเติมเหล่านี้ไว้ที่นั่น

โซลูชันที่ปรับให้เหมาะสมที่สุดของเราใช้ ID ของตัวทำเครื่องหมายแต่ละตัวจากผลลัพธ์แคชและดึงรายละเอียดจากฐานข้อมูล ตอนนี้เรากำลังค้นหาเฉพาะตัวทำเครื่องหมายที่เหลืออยู่หลังจากจัดกลุ่มแล้ว จะไม่มีสิ่งเหล่านี้มากเกินไปเมื่อย่อแผนที่ (เพราะเราจะมีกลุ่มเป็นส่วนใหญ่) หรือเมื่อซูมเข้า (เพราะพื้นที่จะเล็ก)

ในทางตรงกันข้าม โซลูชันที่ไร้เดียงสาจะค้นหาเครื่องหมาย ทั้งหมด ในกล่องขอบเขต (และรายละเอียด) ก่อนจัดกลุ่ม ดังนั้น ขั้นตอนนี้—ไม่บังคับ แต่สำหรับหลาย ๆ แอพ สิ่งสำคัญ—ตอนนี้ทำงานเร็วขึ้นมาก

ขั้นตอนที่ 3: การส่งคืนผลลัพธ์

ด้วยคลัสเตอร์ที่สร้างขึ้นและเครื่องหมายแต่ละตัวได้รับการปรับปรุง เราจึงสามารถส่งมอบสิ่งเหล่านี้ให้กับลูกค้าได้ นอกเหนือจากกรณี Edge ที่ไม่สำคัญบางกรณี ข้อมูลที่ได้นั้นเกือบจะเหมือนกับโซลูชันที่ไร้เดียงสา—แต่เราสามารถส่งมอบได้เร็วกว่ามาก

ข้อควรพิจารณาเพิ่มเติม

ทีนี้มาดูปัจจัยเพิ่มเติมสองประการ:

ความต้องการทรัพยากร

สมมติว่าแผนที่ของแอปมีทั้งหมด N เครื่องหมาย เนื่องจากมีระดับการซูมสูงสุด 20 ระดับ เราจึงต้องจัดเก็บรายการแคชสูงสุด 20N รายการ อย่างไรก็ตาม ในทางปฏิบัติ จำนวนรายการแคชที่แท้จริงมักจะต่ำกว่ามากเนื่องจากการจัดกลุ่ม โดยเฉพาะอย่างยิ่งในระดับการซูมที่ต่ำกว่า อันที่จริง จำนวนรายการแคชทั้งหมดที่แจกจ่ายระหว่างแคชของ Playsports ทั้งหมดนั้นอยู่ที่ ~2N เท่านั้น

นอกจากนี้ หากเราคิดว่าความยาวของค่าแคช (JSON แบบสตริง) คือ ~250 อักขระ (สมมติฐานที่สมเหตุสมผล อย่างน้อยสำหรับ Playsports) และขนาดสตริงคือ 1 ไบต์ต่ออักขระ จำนวนพื้นที่จัดเก็บแคชที่จำเป็นสำหรับ ค่า JSON จะอยู่ที่ประมาณ 2 * N * 250 ไบต์

ในรูปนี้ เราได้เพิ่มโครงสร้างข้อมูลภายในของ Redis สำหรับชุดที่จัดเรียงซึ่งใช้โดย GEOADD Redis ใช้หน่วยความจำ 85 MB สำหรับคู่คีย์-ค่าขนาดเล็ก 1 ล้านคู่ ดังนั้นเราจึงสามารถถือว่าบัญชีภายในของ Redis น้อยกว่า 100 ไบต์ต่อรายการแคช ซึ่งหมายความว่าเราสามารถใช้อินสแตนซ์ Redis ขนาด 1 GB-RAM เพื่อรองรับเครื่องหมายได้มากถึง 1.4 ล้านตัว แม้ในสถานการณ์ที่ไม่น่าจะเป็นไปได้ของมาร์กเกอร์จะกระจายอย่างเท่าเทียมกันทั่วทั้งแผนที่ ส่งผลให้จำนวนรายการแคชใกล้จะถึง 20N แล้ว N ก็ยังสามารถเพิ่มได้ถึง ~140,000 เนื่องจากอินสแตนซ์ Redis สามารถจัดการคีย์ได้มากกว่า 4 พันล้านคีย์ (2 ³² ถ้าใช่) นี่จึงไม่ใช่ปัจจัยจำกัด

แคชค้าง

ขึ้นอยู่กับกรณีการใช้งาน การรีเฟรชแคชเป็นระยะ ๆ อาจไม่เพียงพอ ในกรณีเช่นนี้ เราสามารถใช้คิวงานที่จำกัดอัตราได้ มันจะลดความค้างของแคช ในขณะที่ยังคงจำกัดจำนวนการรีเฟรชแคช และทำให้โหลดบนระบบ

หลังจากการอัพเดตฐานข้อมูลแต่ละครั้ง เราจะจัดคิวงานรีเฟรชแคช คิวนี้จะจำกัดจำนวนของงานเป็น M ต่อชั่วโมง การประนีประนอมนี้ช่วยให้สามารถอัปเดตได้เร็วกว่ารายชั่วโมงในขณะที่ยังคงโหลดระบบค่อนข้างต่ำ (ขึ้นอยู่กับ M)

กลยุทธ์การแคชมีค่ามากกว่าอัลกอริทึมการทำคลัสเตอร์แผนที่

โซลูชันที่ปรับให้เหมาะสมที่สุดสำหรับ Playsports ซึ่งเร็วกว่าโซลูชันไร้เดียงสามากกว่า 50 เท่า ทำงานได้ดี มันควรจะทำงานได้ดีต่อไป จนกว่าเราจะมีเครื่องหมาย 1.4 ล้านตัวหรือมากกว่า 100 เท่าของข้อมูลที่มีอยู่

สำหรับคำขอบริการเว็บตามแผนที่ส่วนใหญ่ จำเป็นต้องมีรูปแบบการคำนวณล่วงหน้าบางรูปแบบเพื่อให้สามารถปรับขนาดได้ ประเภทของเทคโนโลยีที่จะใช้ ตลอดจนการออกแบบเฉพาะ จะขึ้นอยู่กับความต้องการของธุรกิจ ความต้องการแคชที่คงอยู่ การเสริมเครื่องหมาย และจำนวนมาร์กเกอร์เป็นคุณลักษณะที่สำคัญที่ควรพิจารณาเมื่อออกแบบโซลูชัน

อ่านเพิ่มเติมในบล็อก Toptal Engineering:

• แบบสำรวจเครื่องมือสร้างแผนที่ออนไลน์ที่ดีที่สุดสำหรับนักพัฒนาเว็บ: แผนงานสู่แผนงาน
• การผจญภัยในการเขียนโปรแกรมและการพัฒนา GPS: บทช่วยสอนเกี่ยวกับภูมิสารสนเทศ