Kasım ayının izleme grafiklerinde tuhaf bir merdiven vardı: coğrafi çit servisimizin CPU kullanımı her büyük müşteri geldikçe bir basamak zıplıyordu. Eylülde yüzde 34, ekimde 52, kasım sonunda 85. Aralıkta gelecek yeni müşterinin 4 bin aracı ve 900 çit tanımı vardı. Basit bir çarpma işlemi, ocak ayında bu servisin duvara toslayacağını söylüyordu. Kimse gece alarmıyla uyanmadı; bu kez felaketi grafikte önceden gördük ve bu, nadir yaşanan bir lüks.
Coğrafi çit işi kâğıt üzerinde basit: müşteri haritaya bir poligon çizer, "aracım buraya girince/çıkınca haber ver" der. Motorun işi, akan her konum için bu sorunun cevabını bilmek. Bizim akışta saniyede ortalama 1.200 konum vardı ve sistemde 21 bin aktif çit tanımı birikmişti.
Naif Motorun Anatomisi
İlk sürüm, dürüst olmak gerekirse, herkesin ilk yazacağı şeydi: her konum geldiğinde, o aracın müşterisine ait bütün çitler için nokta-poligon testi koş. Ortalama müşteri 40 çite sahipti; yani saniyede 1.200 × 40 = 48 bin poligon testi. Test başına maliyet de masum değildi: ray casting algoritması, poligonun her kenarı için bir kesişim hesabı yapar. Müşteriler haritada il sınırı gibi ayrıntılı şekiller çizmeyi seviyordu; 200-400 köşeli poligonlar sıradandı. Kabaca hesap: saniyede 48 bin test × ortalama 250 kenar = 12 milyon kesişim hesabı. CPU'nun nereye gittiği belliydi.
Ucuz Hayır Demenin Sanatı
Optimizasyonun ilk kuralı: pahalı sorunun cevabı çoğunlukla hayırsa, hayırı ucuza demenin yolunu bul. Konumların ezici çoğunluğu herhangi bir çitin yakınında bile değil. Her çit için bir kez hesaplanıp saklanan bounding box — poligonu içine alan en küçük dikdörtgen — dört karşılaştırmayla "bu nokta bu çitin semtinde bile değil" diyebiliyor. Bu ön filtre tek başına ray casting çağrılarının yüzde 97'sini eledi ve CPU 85'ten 31'e indi.
Bounding box'ın bir inceliği de tampon payı: GPS hatasını hesaba katmak için dikdörtgeni her yönde 20 metre genişlettik. Böylece sınıra çok yakın noktalar ön filtreye takılıp asıl teste girmeden elenmiyor; ucuz hayırın hiçbir zaman yanlış hayır olmaması gerekiyor.
Ama ölçek büyüdükçe bounding box taraması da lineer kalıyordu: 900 çitli müşteride her konum için 900 dikdörtgen kontrolü. İkinci katman olarak dünyayı hücrelere bölen bir grid indeksi kurduk. Her çit, kapladığı hücrelere kaydediliyor; konum geldiğinde önce noktanın hücresi hesaplanıyor (iki bölme işlemi), sonra yalnızca o hücreye kayıtlı çitler aday listesine giriyor. Ortalama aday sayısı 40'tan 1.3'e düştü. R-tree ile de denedik; sorgu performansı benzerdi ama grid'in kodu yarım günde yazılıp okunabiliyor ve çit ekleme/silme sırasında güncellenmesi çok daha basit. Kütüphane parlaklığı yerine hata ayıklanabilirliği seçtik.
Köşe sayısıyla da ayrıca uğraştık. Kullanıcıların çizdiği 400 köşeli poligonların çoğu, o ayrıntıyı hak etmeyen şekillerdi; harita aracı fare hareketini olduğu gibi köşeye çeviriyordu. Kayıt sırasında Douglas-Peucker sadeleştirmesi ekledik: 5 metrelik toleransla, şeklin görsel bütünlüğünü bozmadan köşe sayısını ortalama 4'te 1'e indiriyor. Kullanıcıya sadeleştirilmiş hâli önizletip onaylatıyoruz ki "benim çizdiğim şekil değişti" sürprizi olmasın. Dairesel çitleri de poligona çevirmeyi bıraktık; merkez ve yarıçapla saklanan daire için içeride-mi testi tek bir mesafe karşılaştırması ve dairelerin toplam içindeki payı yüzde 30. Girdiyi olduğu gibi kabul etmek nezaket, olduğu gibi işlemek savurganlık.
Ray Casting'in Kendisini de Törpüledik
Aday sayısı düşünce test başına maliyet öne çıktı. İki düzeltme yaptık. Poligon kenarlarını her testte yeniden hesaplamak yerine, çit kaydedilirken kenar listesini önceden çıkarıp bellekte tuttuk. Ve koordinatları double derece yerine 1e7 ile çarpılmış tamsayılara çevirdik; hem kesişim aritmetiği hızlandı hem de kayan nokta hassasiyet sürprizleri bitti. Bu ikisiyle tekil test süresi ortalama 4.1 mikrosaniyeden 0.9'a indi. Toplam tablo: eski motor saniyede 48 bin testte yüzde 85 CPU yiyordu; yeni motor aynı yükü tek çekirdeğin yüzde 6'sıyla karşılıyor ve sentetik testte saniyede 50 bin nokta-poligon testini 4 milisaniyelik p99 gecikmeyle işliyor.
Yeni motoru üretime çıkarma şeklimiz de hikâyenin önemli parçası, çünkü coğrafi çit alarmları müşterilerin operasyonel süreçlerine bağlı; yanlış alarm da, kaçan alarm da gerçek para. Yeni motoru üç hafta gölge modda çalıştırdık: her konum hem eski hem yeni motordan geçti, kullanıcıya yalnızca eskinin sonucu gitti, ikisinin farkları loglandı. İlk hafta farklar bize iki gerçek bug yakalattı. Biri sınır üstü noktalarda yatıyordu: eski motor sınırın tam üzerindeki noktayı içeride, yenisi dışarıda sayıyordu; kural olarak "sınır içeridedir" deyip iki tarafı eşitledik. Diğeri ise ekvator kadar egzotik değil ama bizim için önemliydi: kendini kesen, hatalı çizilmiş poligonlarda iki motor farklı telden çalıyordu. Bunun kalıcı çözümü motorda değil giriş kapısında oldu; çit kaydedilirken geometri doğrulaması yapıp kendini kesen poligonu kullanıcıya anında geri bildiriyoruz.
Asıl Zor Kısım: Titreyen GPS ve Çırpınan Alarmlar
Motor hızlanınca ortaya daha sinsi bir problem çıktı: doğruluk. GPS noktaları 5-15 metre oynar; çit sınırına park etmiş bir araç, art arda gelen noktalarla dakikada üç kez "girdi/çıktı" üretebiliyordu. Bir müşteri tek gecede 74 SMS almıştı. Çözüm histerezis: durum değişikliğini tek noktayla değil, üst üste iki tutarlı nokta veya sınırın en az 25 metre içine/dışına taşan tek nokta ile ilan ediyoruz. Alarm sayısı düzeldi, kimse gerçek bir girişi kaçırmadı ve o müşteriyle ilişkimiz kurtuldu.
Bellek tarafı da düşünülmeye değerdi. 21 bin çitin önceden hesaplanmış kenar listeleri, bounding box'ları ve grid hücre kayıtları toplam 380 MB tutuyor ve tamamı süreç belleğinde. Veritabanına gitmek yok; çit ekleme ve silmelerde küçük bir değişiklik akışıyla bellek kopyası güncelleniyor. Burada başlangıçta gereksiz bir mühendislik hevesiyle Redis'e koymayı tartışmıştık; hesap basit çıktı — ağ üzerinden gidip gelen bir sorgu, ne kadar hızlı olursa olsun, yerel bellekteki birkaç yüz nanosaniyelik erişimle yarışamaz ve 380 MB, bir sunucu için hiçbir şey. Her veri yapısının doğal yaşadığı yer var; bu motorunki süreç belleğiydi.
Kapasite planlaması da artık kâğıt üzerinde: motor tek çekirdekte saniyede 50 bin testi kaldırdığına ve araç başına test sayısı grid sayesinde sabite yakın olduğuna göre, önümüzdeki iki yılın müşteri projeksiyonu tek sunucunun konforlu bölgesinde kalıyor. O merdiven grafiği artık düz bir çizgi; ayda bir bakıp basamak arıyorum, bulamıyorum.
Bu üç aylık çalışmadan aklımda kalan özet şu: performans problemlerinde donanım büyütmek meşru bir araç ama sıra ondaysa genellikle algoritma katmanında alınacak 10-50 katlık kazançlar hâlâ masadadır. Biz sunucu eklemeden, veri yapısı değiştirerek 14 kat kapasite kazandık. Mekânsal veriyle uğraşıyorsanız ve motorunuzun içini birlikte kurcalamak isterseniz buradan yazabilirsiniz; poligon hikâyesi dinlemekten yorulmam.