การสัมภาษณ์การออกแบบระบบ: ออกแบบ Uber

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

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

1. ชี้แจงความต้องการ

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

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

2. ประมาณสเกล

ตัวเลขประมาณคร่าว ๆ ช่วยสนับสนุนการตัดสินใจในขั้นต่อไป สมมติว่ามีคนขับที่ใช้งานรายวันประมาณ 10 ล้านคน ส่งสัญญาณตำแหน่งทุก 4 วินาที — นั่นคือประมาณ 2.5 ล้านครั้งการเขียนต่อวินาทีสำหรับข้อมูลตำแหน่ง ซึ่งเป็นภาระงานที่เน้นการเขียนเป็นหลัก และตัดตารางเชิงสัมพันธ์แบบธรรมดาออกไปทันทีในฐานะ hot path

3. องค์ประกอบหลักและ API

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

บริการตำแหน่ง: รับสัญญาณจากคนขับ เก็บตำแหน่งปัจจุบันไว้ในดัชนีเชิงภูมิศาสตร์แบบอยู่ในหน่วยความจำ
บริการจับคู่: เมื่อมีคำขอเรียกรถ จะค้นหาคนขับที่ออนไลน์อยู่ใกล้เคียงและกำหนดให้หนึ่งคน
บริการการเดินทาง: บันทึกถาวรของวงจรชีวิตการเดินทาง (ขอแล้ว → จับคู่แล้ว → กำลังดำเนินการ → เสร็จสมบูรณ์)
การแจ้งเตือน/สตรีมมิง: ส่งตำแหน่งสดของคนขับไปยังผู้โดยสาร (WebSocket/long-poll)

4. การจับคู่เชิงภูมิศาสตร์ — หัวใจของปัญหา

นี่คือสิ่งที่ผู้สัมภาษณ์ต้องการฟังมากที่สุด การเก็บละติจูด/ลองจิจูดแบบดิบแล้วสแกนคือ O(n) คุณต้องมีดัชนีเชิงพื้นที่ อธิบาย quadtree หรือ geohashing: แบ่งแผนที่ออกเป็นเซลล์ เพื่อให้ 'หาคนขับที่อยู่ใกล้จุดนี้' กลายเป็นการค้นหาเพียงไม่กี่เซลล์ ไม่ใช่การสแกนทั้งหมด

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

5. การขยายขนาดและจุดคอขวด

ระบุจุดที่มีความดันและวิธีที่คุณจะบรรเทามัน การไหลของการเขียนตำแหน่ง 2.5 ล้านครั้งต่อวินาทีคือจุดที่โดดเด่นที่สุด

ทำ sharding ดัชนีตำแหน่งตามภูมิศาสตร์ — คนขับและผู้โดยสารของเมืองหนึ่งจะถูกจัดการโดย shard เดียวกัน ทำให้การจับคู่ยังคงเป็นแบบโลคัล
ดูดซับการเขียนที่พุ่งสูงด้วยที่เก็บข้อมูลในหน่วยความจำและการเขียนถาวรแบบอะซิงโครนัส คุณไม่จำเป็นต้องให้ทุกสัญญาณเข้าสู่ฐานข้อมูลถาวร
รับประกันคนขับหนึ่งคน-ผู้โดยสารหนึ่งคนด้วยการกำหนดแบบอะตอมมิก (ล็อกหรืออัปเดตแบบมีเงื่อนไข) เพื่อหลีกเลี่ยงการจองซ้ำ
ใช้ message queue (Kafka) ระหว่างการรับข้อมูลตำแหน่งและผู้บริโภคปลายทาง เพื่อแยกช่วงที่มีการพุ่งสูงออกจากกัน

6. ข้อแลกเปลี่ยนที่ควรพูดออกมา

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

ฝึกการออกแบบระบบของ Uber พร้อมความช่วยเหลือแบบเรียลไทม์

ผู้ช่วยสัมภาษณ์การออกแบบระบบของ Nativelyสามารถช่วยให้คุณมีโครงสร้างที่ชัดเจนระหว่างรอบสัมภาษณ์แบบสด — เสนอมิติต่อไปที่ควรครอบคลุมและแสดงข้อแลกเปลี่ยนแบบเรียลไทม์ ทั้งหมดบนอุปกรณ์ของคุณเอง