Yolculuk Paylaşımı Sistem Tasarımı: Konum Güncellemeleri, Eşleştirme ve Görevlendirme

Bir yolcu “Talep et” düğmesine dokunur ve saniyeler içinde bir araç bekler. O dokunuşun arkasında sistemin, hareket hâlindeki yüz binlerce sürücünün şu anda nerede olduğunu bilmesi, iyi bir sürücü seçmesi, aynı sürücünün başka bir yolcuya verilmemesini sağlaması ve ardından ödemeyle biten bir yolculuğu izlemesi gerekir. Yüksek hacimli gerçek zamanlı bir akışı küçük ve katı bir işlemsel çekirdekle birleştirdiği için gözde bir sistem tasarımı mülakat sorusudur.

Bu yazı altyapıyı adım adım tasarlıyor: gereksinimler ve kapasite rakamları, konum toplama, geohash, S2 ve H3 ile coğrafi indeksleme, eşleştirme ve görevlendirme, yolculuk durum makinesi ve plan yapmanız gereken arızalar; kopyalayabileceğiniz bir mimari diyagramıyla.

Gereksinimler

İşlevsel:

• Sürücüler çevrim içi olur ve konumlarını akış hâlinde gönderir.
• Yolcular yolculuk talep eder, yakındaki araçları ve tahmini alınma süresini görür.
• Sistem yolcuyu, kabul ya da reddedebilecek bir sürücüyle eşleştirir.
• İki uygulama da yolculuğu canlı izler; yolculuk bir ücret ve ödemeyle biter.

İşlevsel olmayan:

• Birkaç saniye içinde eşleşme.
• Sürücü konumları en fazla birkaç saniye eski.
• Bir sürücüyü asla iki yolcuya atamamak.
• Bir şehrin sorunları diğer şehirleri çökertmemeli.

Kapasite: tasarımı şekillendiren rakamlar

Büyük bir kurulum için, zirvede çevrim içi bir milyon sürücü, her birinin 4 saniyede bir konum gönderdiğini ve dakikada 20.000 yolculuk talebi olduğunu varsayın:

Birbirinden çok farklı iki iş yükü ortaya çıkar. Konum güncellemelerinin hacmi muazzamdır, ama her biri küçüktür, atılabilir ve 4 saniye sonra yenisiyle değişir. Yolculuk talepleri üç büyüklük mertebesi daha seyrektir, ama her biri tam olarak bir kez işlenmeli ve paraya bağlanmalıdır. Mimari bu ikisini ayırır.

Konum toplama: yalnızca güncel olanı tutun

Sürücü uygulamaları konumları WebSocket gibi kalıcı bir bağlantı üzerinden ya da küçük, periyodik HTTPS istekleriyle gönderir. Bir konum ağ geçidi sürücünün kimliğini doğrular, imkânsız noktaları (4 saniyede 50 km'lik bir sıçrama) atar ve her güncellemeyi Kafka gibi, şehre göre bölümlenmiş bir akışa yazar.

Akışı üç tüketici okur:

1. Canlı coğrafi indeks her müsait sürücünün yalnızca en son konumunu tutar; kısa bir sona erme süresiyle, telefonu sessizleşen bir sürücü örneğin 30 saniye sonra kaybolur.
2. Yolculuk takibi atanan sürücünün konumunu yolcunun uygulamasına iletir.
3. Soğuk depolama tüm geçmişi analitik, ETA modelleri ve anlaşmazlık çözümü için nesne depolamada saklar.

Kilit karar, sıcak indeksin güncelleme başına değil, sürücü başına bir satır tutmasıdır. Her biri kabaca yüz bayt olan bir milyon sürücü yaklaşık 100 MB eder; şehir başına bellekte tutulacak kadar küçüktür.

Coğrafi indeksleme

Eşleştirme sorusu şudur: “Bu noktanın yakınında hangi müsait sürücüler var?” Enlem ve boylam üzerindeki düz bir veritabanı indeksi bunu kötü yanıtlar; bu yüzden sistemler koordinatları hücrelere eşler.

Uber'in 2018'de açık kaynak yaptığı H3, yarıçap aramasını tekdüze hâle getirir: Yolcunun hücresini ve çevresindeki hücre halkasını alın, ardından içlerindeki sürücüleri toplayın. Çözünürlük önemlidir. H3 çözünürlük tablosundan:

Yoğun şehirlere 8 ya da 9 çözünürlüğü uyar; kırsal bölgeler daha geniş halkalar ya da daha kaba hücreler gerektirir.

Basit başlamak istiyorsanız, Redis'te yerleşik coğrafi komutlar vardır:

GEOADD drivers:sf -122.4194 37.7749 driver:8812
GEOSEARCH drivers:sf FROMLONLAT -122.4100 37.7800 BYRADIUS 2 km ASC COUNT 20 WITHDIST

Redis 6.2'den beri kullanılabilen GEOSEARCH, 2 km içindeki en yakın 20 sürücüyü mesafeye göre sıralı döndürür. Önce doğal sınır olan şehre göre shard'layın, havalimanları ya da stadyumlar gibi çok yoğun yerleri daha ince hücrelere bölün.

Eşleştirme ve görevlendirme

Kuş uçuşu mesafe, alınma süresi için kötü bir göstergedir: Nehrin karşı yakasında 500 m uzaktaki bir sürücü 15 dakika uzakta olabilir. Bu yüzden eşleştirme iki aşamada çalışır:

1. Aday üretimi. Alınma noktasının yakınındaki müsait sürücüleri, araç tipi ve diğer kısıtlara göre filtreleyerek coğrafi indeksten sorgulayın.
2. Sıralama. En iyi adaylar için bir ETA servisinden yol ağına göre alınma sürelerini isteyin ve ETA'ya, artı sürücünün yönü gibi etkenlere göre sıralayın.

Her talebi anında en yakın sürücüyle eşleştirmek açgözlü bir yaklaşımdır. Talepleri bir iki saniye boyunca toplayıp bir atama problemi olarak birlikte çözmek, yolcular genelinde toplam bekleme süresini en aza indirir. Ödünleşim, yoğun dönemlerde daha iyi eşleşmeler karşılığında kısa bir gecikmedir.

Ardından görevlendirme, yaklaşık 15 saniyelik bir zaman aşımıyla, teklifi her seferinde tek bir sürücüye gönderir. Ret ya da zaman aşımında teklif sıradaki adaya gider.

Bir sürücüyü asla iki kez atamayın

İki eşleştirme işçisi aynı saniye içinde aynı sürücüyü iki yolcu için seçebilir. Bunu eşleştirme mantığında değil, sürücünün durumunda önleyin:

• Her sürücünün durumunu (available, offered, on_trip) bir sürüm numarasıyla saklayın.
• Teklif koşullu bir güncellemedir: offered değerini yalnızca durum, okuduğunuz sürümde hâlâ available ise ayarlayın.
• Tam olarak bir işçi kazanır; diğeri sıradaki adayına geçer.
• Süresi dolan bir teklif sürücüyü, yine koşullu olarak, available durumuna geri taşır.

Aynı karşılaştır-ve-ayarla (compare-and-set) fikri yolcu tarafını da korur: yolcu başına tek etkin talep.

Yolculuk durum makinesi

Bir yolculuk requested, matching, driver_assigned, driver_arrived, in_progress, completed ve paid durumlarından geçer; birkaç durumdan iptal de mümkündür. Yolculuk servisi her yolculuğu Postgres gibi ilişkisel bir veritabanında saklar, geçişleri yalnızca mevcut durum izin verdiğinde uygular ve her değişikliği faturalama, bildirimler, makbuzlar ve analitik için bir olay olarak yayımlar.

Her geçişi yolculuk kimliği ve durum sürümüyle anahtarlanmış biçimde idempotent yapın. Mobil ağlar yeniden dener ve iki kez teslim edilen “sürücü geldi” hiçbir şeyi iki kez yapmamalıdır. Durum diyagramı örneği bu yaşam döngüsünü tek başına nasıl çizeceğinizi gösteriyor.

Canlı güncellemeler, ETA'lar ve fiyatlandırma

Bir yolculuk sürerken yolcunun uygulaması, sürücünün konumunu birkaç saniyede bire kısılmış ve istemcide yumuşatılmış olarak bir push bağlantısı üzerinden alır. Aynı konum akışı, canlı trafiğe ihtiyaç duyan ETA servisini ve kayan bir pencere boyunca hücre başına talepleri müsait sürücülerle karşılaştıran dinamik fiyatlandırmayı besler. Ödeme, yolculuktan sonra bir ödeme sağlayıcısı üzerinden gerçekleşir; bu kısmı ödeme ağ geçidi entegrasyonu diyagramı ele alıyor.

Plan yapılması gereken arızalar

• Sürücülerin bağlantısı kopar. Uygulama yeniden bağlandığında yalnızca en son noktayı gönderir ve indeks sessizleşen sürücüleri süresi dolmuş sayar.
• Bir eşleştirme işçisi teklifin ortasında çöker. Tekliflerin sona erme zamanları vardır; teklifin süresi dolduğunda sürücü available durumuna döner.
• Bir şehrin kümesi çöker. Her şey şehre göre bölümlendiği için arıza yerel kalır. Süren yolculuklar durumlarını kalıcı yolculuk deposunda korur.
• Sahte GPS. Ağ geçidindeki hız ve rota makullük kontrolleri kaba vakaları yakalar.

Yolculuk paylaşımı diyagramı

Nasıl okunur:

• Çerçeve tek bir şehirdir; içindeki her şey için bölümleme sınırıdır.
• Konum yolu üstten geçer: sürücü uygulaması, konum ağ geçidi, Kafka ve oradan Redis coğrafi indeksi ile geçmiş için nesne deposu.
• Talep yolu alttan geçer: Yolcu uygulaması eşleştirmeyi çağırır; eşleştirme adayları coğrafi indeksten okur, ETA servisinden alınma sürelerini ister ve teklifi sürücüye gönderir.
• Yolculuk servisi durum makinesinin sahibidir ve onu Postgres'te saklar.
• Markdown bloğu kapasite rakamlarını gösterir.

Gerçek zamanlı sistemler için sistem tasarımı diyagramları çizmek

• Sıcak yolu işlemsel yoldan ayırın. Burada konum akışı ile yolculuk yaşam döngüsünün hacimleri, garantileri ve arıza biçimleri farklıdır; onları ayrı şeritler olarak çizin.
• Bölümleme anahtarını diyagrama yazın. “Şehre göre bölümlenmiş” ifadesi, ölçeklemeyi ve arıza izolasyonunu üç kelimeyle açıklar.
• Neyin güncel, neyin geçmiş olduğunu gösterin. En son konum indeksi ile geçmiş deposu farklı sorulara yanıt verir.
• Kenarları hızlarla etiketleyin: Tek bir okun üzerindeki saniyede 250.000 güncelleme, inceleyenlere yükün nerede olduğunu söyler.

Bu diyagramlara genel bir yaklaşım için sistem tasarımı diyagramı örneğine bakın. Push bağlantıları sohbet uygulaması mimari diyagramında, akışın kendisi ise Kafka mimari diyagramında ele alınıyor.

Archboard'da oluşturun

1. Google ya da GitHub ile giriş yapın ve bir diyagram oluşturun.
2. Şehrin adını taşıyan bir Temel Çerçeve ekleyin.
3. Sürücü uygulaması ve yolcu uygulaması için Ağ paketinden iki Cihaz düğümü ekleyin.
4. Konum ağ geçidi için Bulut paketinden bir API ağ geçidi, akış için Veri paketinden bir Kafka düğümü, coğrafi indeks için bir Redis düğümü ve geçmiş için bir Nesne deposu ekleyin.
5. Eşleştirme, ETA ve yolculuk servisleri için Bulut paketinden üç Hesaplama düğümü, yolculuklar için de Veri paketinden bir Postgres düğümü ekleyin.
6. Konum yolunu üstte, talep yolunu onun altında bağlayın ve kenarları taşıdıkları şeyle ve ne sıklıkla taşıdıklarıyla etiketleyin.
7. Temel paketinden kapasite rakamlarını içeren bir Markdown bloğu ekleyin.

Örnek 12 diyagram düğümü kullanıyor ve Free planın sınırları içinde kalıyor.

SSS

Sürücüler konumlarını ne sıklıkla göndermeli? Birkaç saniyede bir yaygın bir aralıktır. Daha sık güncellemeler konumları daha taze kılar ama alım hacmini katlar: Aralığı 4 saniyeden 2 saniyeye yarıya indirmek trafiği iki katına çıkarır.

Geohash mi, S2 mi, H3 mü kullanmalıyım? Hangisi olsa çalışır. Geohash en basitidir ve Redis'te yerleşiktir; H3 komşu uzaklıklarını tekdüze kılar, bu da yarıçap aramalarını ve hücre başına fiyatlandırmayı daha temiz hâle getirir. Birini seçin ve tutarlı biçimde kullanın.

Bir sürücüyü iki yolcuya atamaktan nasıl kaçınılır? Teklifi sürücünün durumu üzerinde koşullu bir güncelleme yapın; böylece yalnızca sürücü, eşleştiricinin okuduğu sürümde hâlâ müsaitse başarılı olur. Yalnızca bir eşleştirici kazanabilir.

Neden her yolcuyu hemen en yakın sürücüyle eşleştirmiyoruz? Açgözlü eşleştirme, sonraki yolcuları uzun beklemelerle baş başa bırakabilir. Talepleri bir iki saniye toplayıp birlikte çözmek, kısa bir gecikme pahasına toplam bekleme süresini düşürür.

Yolculukları hangi veritabanı saklar? İlişkisel bir veritabanı iyi uyar: Yolculuklar işlemseldir, katı durum geçişleri gerektirir ve faturalamayı besler. Yüksek hacimli konum verisi başka yerde, bellekte ve nesne depolamada durur.

Ücretsiz başlayın — tek kullanıcı, kredi kartı gerekmez.