Satış ekibi 2019 sonbaharında yeni bir özellik sözü verdi (bize sormadan, klasik): müşteri haritada bir noktaya tıklayacak, "bu noktaya en yakın 10 boş araç" saniyeler içinde listelenecek. Nakliye dağıtım firmaları için cazip bir vaat. İlk prototipi bir öğleden sonra yazdım; 12.000 aracın son konumunu tutan tabloda her satır için Haversine mesafesi hesaplayıp sıralayan tek bir sorgu. Test ortamında 300 araçla 15 milisaniye. Canlıda 12.000 araçla 900 milisaniye — ve bu sorgu, dağıtım saatlerinde saniyede 40-50 kez çalışacaktı. Tek başına bir CPU çekirdeğini bitiriyordu.
"Yakınımdaki araçlar" masum görünen ama içi mayın dolu bir özelliktir. O sonbahar bunu adım adım öğrendik.
Enlem-Boylam İndeksinin Sessiz İflası
İlk iyileştirme herkesin aklına gelen: önce kaba bir dikdörtgenle ele, sonra kalanlara mesafe hesabı yap. WHERE lat BETWEEN ... AND ... AND lng BETWEEN ... Bileşik (lat, lng) indeksi de ekledik. Süre 900'den 210 milisaniyeye indi ama EXPLAIN can sıkıcıydı: indeks yalnızca enlem boyutunda işe yarıyordu. B-tree tek boyutlu bir yapıdır; lat aralığına giren binlerce satırın hepsini okuyup lng şartını tek tek eliyordu. İstanbul enlemindeki bir sorgu, aynı enlemdeki Ankara ve İzmir araçlarını da indeksten geçiriyordu. İki boyutlu bir soruyu tek boyutlu bir veri yapısına sorduğunuzda alacağınız cevap budur.
Doğru araçlar belliydi aslında: ya gerçek bir mekânsal indeks (R-tree) ya da mekânı tek boyuta akıllıca katlayan bir kodlama. İkinciden başladık, çünkü adı geohash olan şey mevcut altyapımıza sıfır ek bileşenle giriyordu.
Dünyayı Harf Harf Katlamak
Geohash'in fikri güzelliği şurada: dünyayı önce ikiye, sonra her parçayı tekrar ikiye bölerek gidiyorsunuz; her bölmede enlem ve boylam bitlerini dönüşümlü diziyorsunuz. Çıkan bit dizisini base32 harfleriyle yazınca "sxk9m" gibi bir metin elde ediyorsunuz. Kritik özellik şu: ortak önek, mekânsal yakınlık demek. sxk9m ile başlayan her nokta, aynı 5 karakterlik hücrenin (kabaca 5 km × 5 km) içindedir. Yani "yakınımdakiler" sorusu, sıradan bir B-tree'nin en sevdiği şeye dönüşüyor: LIKE 'sxk9m%' önek araması.
Uygulama tarafı basitti. Son konum tablosuna 8 karakterlik geohash sütunu ekledik (8 karakter ≈ 38 m × 19 m hücre), yazma katmanı her konum güncellemesinde hash'i hesaplayıp basıyor. Sorgu tarafında tıklanan noktanın 5 karakterlik hücresini buluyor, o önekle eşleşen araçları çekiyor, kalan 50-100 adaya gerçek Haversine hesabı yapıp sıralıyoruz. Kaba eleme indeksten, ince eleme matematikten. Süre: ortalama 6 milisaniye. 210'dan 6'ya.
Hücre Sınırında Kaybolan Kamyon
Sonra bir dağıtım müdürü aradı: "Depomun dibinde araç duruyor, sizin sistem 4 kilometre uzaktakini öneriyor." Kontrol ettik, haklıydı. Deponun konumu bir geohash hücresinin kenarına denk geliyordu; dipteki araç ise komşu hücredeydi. Önek araması yalnızca tek hücreye bakar; sınırın öteki yakası, alfabetik olarak bambaşka bir öneke sahip olabilir. Hatta geohash'in Z-eğrisi katlamasında, fiziksel olarak bitişik iki hücrenin kodları birbirinden alakasız görünebilir.
Standart çare, sorguyu merkez hücre artı 8 komşusuyla (kuzey, güney, doğu, batı ve dört çapraz) çalıştırmak. Komşu hücre hesabı hazır algoritma; dokuz öneki tek sorguda IN listesi gibi kullanıyoruz, dokuz önek taraması hâlâ birkaç milisaniye. Bu düzeltmeyle "dipteki aracı görmeme" şikâyeti bitti. Ama şunu da öğrendik: arama yarıçapınız hücre boyutunu aşıyorsa 9 hücre de yetmez. Biz yarıçapı önek uzunluğuna bağladık — 2 km'ye kadar aramalar 5 karakterlik, 500 metreye kadar olanlar 6 karakterlik hücrelerle dönüyor. Yarıçap-önek eşlemesini yanlış kuran, ya eksik sonuç alır ya da yarım şehri tarar.
Peki Neden R-tree Değil?
Dürüst cevap: kısmen tarihsel yük. Ana veritabanımız MySQL 5.6'dan devralınmış bir 5.7'ydi ve InnoDB'de SPATIAL indeks desteği 5.7 ile geldiğinde biz henüz taze göçmüştük; üretimde az sınanmış bir özelliğe kritik sorguyu emanet etmek istemedik. R-tree, dikdörtgenleri iç içe kutulayarak gerçek iki boyutlu arama yapar ve sınır problemi diye bir derdi yoktur; bugün sıfırdan başlayan birine PostGIS ya da MySQL 8 SPATIAL bakmadan geçme derim. Ama bizim vakamızda geohash'in iki ek kozu vardı. Birincisi taşınabilirlik: aynı hash değerini Redis'te anahtar öneki, uygulama içinde bellek haritası anahtarı olarak da kullandık; R-tree veritabanının içinde hapistir, geohash her yere sızar. İkincisi, canlı araç konumları saniyede yüzlerce kez güncellenir; o dönem okuduğumuz her şey, yoğun güncelleme altında R-tree bakımının B-tree'den pahalı olduğu yönündeydi ve bunu sınayacak vaktimiz yoktu.
Önek uzunluğu seçerken elimizin altında tuttuğumuz kaba cetveli de paylaşayım: 4 karakter kabaca 39 km × 19,5 km (şehir), 5 karakter 4,9 km × 4,9 km (ilçe), 6 karakter 1,2 km × 0,6 km (mahalle), 7 karakter 153 m × 153 m (sokak), 8 karakter 38 m × 19 m (bina). Her karakter 5 bit ekler ve bitler enlem-boylam arasında dönüşümlü dağıldığı için hücreler bir uzun bir kare gider. Bu cetveli ezberlemek yerine sorgu katmanına gömdük; yarıçap geliyor, önek uzunluğu fonksiyondan çıkıyor.
Sistemin bir sonraki evriminde aynı deseni Redis'e taşıdık. Canlı konumlar zaten bellekte tutuluyordu; anahtarları geohash önekiyle gruplayınca "hücredeki araçlar" sorusu Redis'ten mikrosaniyelerle cevaplanır oldu ve MySQL bu sorgu sınıfından tamamen kurtuldu. (Redis 3.2'nin GEORADIUS komutu da vardı ve içeride yine geohash kullanır; biz kendi önek şemamızı kurmuştuk bile, öyle kaldı.) Aynı fikrin üç ayrı katmanda — SQL LIKE, Redis anahtarı, bellek içi harita — aynen çalışması, geohash'in en az bilinen erdemi bence.
Bir yıl sonra aynı geohash sütunu beklemediğimiz bir işe daha yaradı: bölgesel yoğunluk ısı haritası. GROUP BY LEFT(geohash, 4) ile şehir ölçeğinde, LEFT(geohash, 6) ile mahalle ölçeğinde araç yoğunluğunu tek sorguda çıkarır olduk. Mekânsal veri için kurulan altyapının analitik tarafa bedava taşması, bu seçimin en tatlı yan geliriydi.
Ölçüm özetine dönersek: naif Haversine 900 ms, bounding box + bileşik indeks 210 ms, geohash öneki + 9 komşu + ince eleme 6-9 ms. Sorgu başına okunan satır 12.000'den ortalama 80'e indi. Ve en önemlisi, dağıtım saatlerindeki CPU tepeleri düzleşti; bu özellik artık kapasite planlamasında satır bile değil.
Sınır vakası bir uyarıyla kapatayım: geohash hücreleri kutuplara yaklaştıkça yamulur ve boylam sıkışması yüzünden hücre genişlikleri değişir. Türkiye enlemlerinde pratik sorun yaratmadı ama küresel çalışan bir sistem kuruyorsanız hücre boyutu varsayımlarınızı enleme göre sınayın. Mekânsal sorgu tasarımında benzer bir yol ayrımındaysanız — geohash mi, R-tree mi, yoksa ikisi birden mi — şuradan yazın; hangi ölçekte neyin battığını ilk elden anlatırım.