Konum Tabanlı Servis

Önceki vakada bir kaydı bulmak kolaydı: seri kimliği ile zaman aralığı verildiğinde okunacak satırlar tek bir yerde ve sıralı duruyordu. Bu vaka o kolaylığı kaldırır. Kayıtlar iki boyutlu bir düzlemde durur ve soru “şu noktaya yakın olanlar” biçiminde gelir. Yakınlığın sıralı bir anahtarı yoktur: iki boyutu tek bir eksende sıralamanın her yolu bazı komşuları birbirinden uzağa düşürür, çünkü bir eksende ardışık olan iki nokta düzlemde uzak, düzlemde komşu olan iki nokta eksende uzak olabilir.

Çözüm düzlemi hücrelere bölmek ve her kayda bir uzamsal anahtar (geohash) yazmaktır: aynı hücredeki kayıtlar aynı anahtarı taşır ve yakınlık sorgusu önce hücreleri, sonra hücre içindeki adayları tarar. Ölçülecek karar hücre boyudur ve iki yönlü bir ödünleşim taşır: hücre büyüdükçe taranan aday artar, hücre küçüldükçe sorgulanması gereken hücre sayısı artar.

Kısıtlar

İşlevsel gereksinim: yer kaydetme, hareketli nesnenin konumunu güncelleme, verilen bir noktanın belirli yarıçapı içindeki yerleri döndürme ve sonucu uzaklığa göre sıralama.

İşlevsel olmayan gereksinim, sayıyla: yakınlık sorgusu yarıçap içindeki kayıtların tamamını döndürür, kaçırma oranı sıfırdır; sorgu başına taranan aday 1000’i geçmez; tasarım tepe 1666,67 sorgu/s ve 24.000 konum güncellemesi/s taşır.

Kapsam daraltması: rota bulma, tahmini varış süresi, harita çizimi, yer sıralaması ve coğrafi projeksiyon dönüşümleri tasarlanmaz; bu vakada bölge küçük olduğu için düzlem yaklaşımı kullanılır ve bu bir model basitleştirmesidir.

Varsayımlar

Kod	Varsayım	Değer	Gerekçe
KT1	kayıtlı yer	40.000.000	hizmet alanındaki toplam nokta
KT2	günlük etkin kullanıcı	6.000.000	yakınlık sorgusu yapanlar
KT3	kullanıcı başına günlük sorgu	8	arama ve harita gezinmesi
KT4	tepe çarpanı	3	tepe saatin gün ortalamasına oranı
KT5	yer kaydı	320 bayt	ad, konum, kategori, çalışma saatleri
KT6	hareketli nesne	120.000	konumu sürekli değişen taşıyıcılar
KT7	konum güncelleme aralığı	15 s	taşıyıcının bildirim sıklığı
KT8	yerleşim bölgesinde yoğunluk	20 yer/km²	model bölgenin ortalaması
KT9	bir hücre aramasının bedeli	20 aday	dizin araması ile satır taramasının oranı
KT10	yakınlık yarıçapı	1 km	yürüme mesafesi sorgusu

KT9 bu vakanın karar verdiren varsayımıdır: hücre boyu seçimi bir dizin aramasının kaç satır taramasına denk olduğuna bağlıdır ve bu oran depo motoruna göre değişir.

Ölçek

// konum-olcek.mjs — KT tablosundan cikan olcek hesabi; hepsi aritmetiktir
const KT = { yer: 40_000_000, kullanici: 6_000_000, sorgu: 8, tepe: 3, yerBayt: 320,
  hareketli: 120_000, guncellemeSn: 15, yogunluk: 20, yaricapKm: 1, adayButce: 1000 };
const GUN = 86_400;
const sorguSn = (KT.kullanici * KT.sorgu) / GUN;
const guncellemeSn = KT.hareketli / KT.guncellemeSn;

for (const [ad, d] of [
  ["tepe yakinlik sorgusu/s", sorguSn * KT.tepe],
  ["tepe konum guncellemesi/s", guncellemeSn * KT.tepe],
  ["guncelleme / sorgu orani", guncellemeSn / sorguSn],
  ["yer verisi GB", (KT.yer * KT.yerBayt) / 1e9],
  ["yaricap alani km2", Math.PI * KT.yaricapKm ** 2],
  ["alandaki beklenen yer", Math.PI * KT.yaricapKm ** 2 * KT.yogunluk],
]) console.log(ad.padEnd(26) + d.toFixed(2).padStart(14));

const duz = sorguSn * KT.tepe * KT.yer;
console.log(`\nduz tarama: sorgu basina ${KT.yer.toLocaleString("tr-TR")} kayit -> tepede ` +
  `${duz.toExponential(2)} kayit/s`);
console.log(`aday butcesi ${KT.adayButce} olursa tepede ${(sorguSn * KT.tepe * KT.adayButce)
  .toLocaleString("tr-TR", { maximumFractionDigits: 0 })} kayit/s (duz taramanin 1/${KT.yer / KT.adayButce}'i)`);

tepe yakinlik sorgusu/s          1666.67
tepe konum guncellemesi/s       24000.00
guncelleme / sorgu orani           14.40
yer verisi GB                      12.80
yaricap alani km2                   3.14
alandaki beklenen yer              62.83

duz tarama: sorgu basina 40.000.000 kayit -> tepede 6.67e+10 kayit/s
aday butcesi 1000 olursa tepede 1.666.667 kayit/s (duz taramanin 1/40000'i)

Bu sayılar hesap sınıfındadır ve üçü tasarımı belirliyor. Birincisi, bu vakada veri hacmi küçük: 40.000.000 yer kaydı 12,80 GB tutuyor, önceki üç vakanın terabaytlarının yanında hiç. Yoğunluk buradaki veri hacminde değil, sorgu başına dokunulan kayıt sayısında. Düz tarama tepede saniyede 66,7 milyar kayıt okumak demek; aday sayısı 1000’de tutulursa aynı yük 1.666.667 kayıt/s’ye, yani kırk binde birine iniyor. İkincisi, yazma okumadan baskın: konum güncellemesi sorgunun 14,40 katı ve tepede saniyede 24.000. Üçüncüsü, bir sorgunun gerçek yanıtı ortalama 62,83 kayıt; aday bütçesi bu sayının on altı katı, yani tasarım baştan bir israfa razı oluyor.

Aday Sayısı

Hücre boyu ancak gerçek bir dağılım üzerinde savunulabilir, çünkü noktalar düzgün dağılmaz. Aşağıdaki model 100 × 100 km’lik bir düzleme kümelenmiş 200.000 nokta koyar, beş hücre boyu için uzamsal anahtarı bir dizine yazar ve aynı 200 sorguyu hepsine birden sorar.

// uzamsal.mjs — node:sqlite ile gercek veri uzerinde uzamsal anahtarin taradigi aday sayisi.
// Bolge 100x100 km'lik bir duzlem olarak modellenir (kucuk bolgede duzlem yaklasimi); noktalar
// kumelenmis, uretec kendi yazilmis ve tohum gorunur. Model oldugu yazilir.
import { DatabaseSync } from "node:sqlite";

const N = 200_000, KENAR = 100, R = 1, SORGU = 200, TOHUM = 20260802, KUME = 20, ARAMA = 20;
const HUCRE = [0.5, 1, 2, 4, 8];                     // hucre kenar uzunlugu, km
let durum = TOHUM;
const rast = () => { durum = (durum * 1103515245 + 12345) % 2147483648; return durum / 2147483648; };
const merkez = Array.from({ length: KUME }, () => [rast() * KENAR, rast() * KENAR]);
function nokta() {                                    // %60 kume cevresinde, %40 duzgun dagilim
  if (rast() < 0.4) return [rast() * KENAR, rast() * KENAR];
  const [mx, my] = merkez[Math.floor(rast() * KUME)];
  const a = rast() * 2 * Math.PI, d = -Math.log(1 - rast()) * 3;
  return [Math.min(KENAR, Math.max(0, mx + d * Math.cos(a))), Math.min(KENAR, Math.max(0, my + d * Math.sin(a)))];
}
const kod = (x, y, c) => Math.floor(y / c) * 10_000 + Math.floor(x / c);

const db = new DatabaseSync(":memory:");
db.exec(`CREATE TABLE yer(id INTEGER PRIMARY KEY, x REAL, y REAL, ${HUCRE.map((_, i) => `h${i} INTEGER`).join(", ")});
${HUCRE.map((_, i) => `CREATE INDEX yer_h${i} ON yer(h${i});`).join("\n")}`);
db.exec("BEGIN");
const ekle = db.prepare(`INSERT INTO yer VALUES(?,?,?,${HUCRE.map(() => "?").join(",")})`);
const noktalar = [];
for (let i = 0; i < N; i += 1) {
  const [x, y] = nokta();
  noktalar.push([x, y]);
  ekle.run(i, x, y, ...HUCRE.map((c) => kod(x, y, c)));
}
db.exec("COMMIT");
const sorgular = Array.from({ length: SORGU }, nokta);
const yakin = (q, x, y) => (x - q[0]) ** 2 + (y - q[1]) ** 2 <= R * R;

let duzEslesen = 0;                                   // duz tarama: dogrulugun olcusu
for (const q of sorgular) duzEslesen += noktalar.filter(([x, y]) => yakin(q, x, y)).length;

console.log(`model: ${N} yer, ${KENAR}x${KENAR} km, ${KUME} kume, yaricap ${R} km, ` +
  `${SORGU} sorgu, tohum ${TOHUM}`);
console.log(`duz tarama: sorgu basina ${N} aday, ${(duzEslesen / SORGU).toFixed(2)} eslesme\n`);
console.log("hucre km".padEnd(10) + "sorgulanan".padStart(12) + "aday".padStart(10) +
  "isabet".padStart(9) + "esdeger is".padStart(12) + "kendi hucresi".padStart(15) +
  "kacirilan".padStart(11));
const IS = {};
for (const c of HUCRE) {
  const i = HUCRE.indexOf(c), k = Math.ceil(R / c);
  let aday = 0, eslesen = 0, hucre = 0, kendi = 0;
  for (const q of sorgular) {
    const cx = Math.floor(q[0] / c), cy = Math.floor(q[1] / c), liste = [];
    for (let dy = -k; dy <= k; dy += 1) for (let dx = -k; dx <= k; dx += 1) liste.push((cy + dy) * 10_000 + cx + dx);
    hucre += liste.length;
    const s = db.prepare(`SELECT x, y FROM yer WHERE h${i} IN (${liste.map(() => "?").join(",")})`).all(...liste);
    aday += s.length;
    for (const r of s) if (yakin(q, r.x, r.y)) {
      eslesen += 1;
      if (Math.floor(r.y / c) === cy && Math.floor(r.x / c) === cx) kendi += 1;
    }
  }
  IS[c] = [aday / SORGU, hucre / SORGU];
  console.log(`${c}`.padEnd(10) + (hucre / SORGU).toFixed(0).padStart(12) + (aday / SORGU).toFixed(0).padStart(10) +
    `%${((eslesen / aday) * 100).toFixed(1)}`.padStart(9) +
    (aday / SORGU + (hucre / SORGU) * ARAMA).toFixed(0).padStart(12) +
    (kendi / SORGU).toFixed(2).padStart(15) +
    `%${(((eslesen - kendi) / eslesen) * 100).toFixed(1)}`.padStart(11));
}
console.log(`\neslesme her hucre boyunda duz taramayla ayni (${(duzEslesen / SORGU).toFixed(2)}): ` +
  `komsu hucreler sorgulandigi icin kacirma yok`);
console.log(`esdeger is = aday + sorgulanan hucre x ${ARAMA} (KT9: bir hucre aramasinin bedeli)`);
const [a1, h1] = IS[0.5], [a2, h2] = IS[1];
console.log(`0.5 km ile 1 km esitlendigi nokta: hucre aramasi = ${((a2 - a1) / (h1 - h2)).toFixed(2)} ` +
  `aday taramasi; bunun altinda 0.5 km, ustunde 1 km kazanir`);

model: 200000 yer, 100x100 km, 20 kume, yaricap 1 km, 200 sorgu, tohum 20260802
duz tarama: sorgu basina 200000 aday, 443.95 eslesme

hucre km    sorgulanan      aday   isabet  esdeger is  kendi hucresi  kacirilan
0.5                 25       700    %63.4        1200         105.33      %76.3
1                    9       864    %51.4        1044         181.41      %59.1
2                    9      2123    %20.9        2303         322.27      %27.4
4                    9      5251     %8.5        5431         381.24      %14.1
8                    9     13611     %3.3       13791         415.85       %6.3

eslesme her hucre boyunda duz taramayla ayni (443.95): komsu hucreler sorgulandigi icin kacirma yok
esdeger is = aday + sorgulanan hucre x 20 (KT9: bir hucre aramasinin bedeli)
0.5 km ile 1 km esitlendigi nokta: hucre aramasi = 10.25 aday taramasi; bunun altinda 0.5 km, ustunde 1 km kazanir

Bu sayılar ölçüm sınıfındadır; değerler bu koşumun tohumuna ve kümelenme parametrelerine bağlı, sütunlar arasındaki eğilim bağlı değil. Model kümelenmiş olduğu için sorgu başına 443,95 eşleşme çıkıyor — ölçek hesabındaki 62,83’ün yedi katı, çünkü sorgular da noktalarla aynı dağılımdan çekiliyor ve yoğun bölgelerde toplanıyor.

Üç şey okunuyor. Birincisi dizin doğruluğu bozmuyor: her hücre boyunda eşleşme sayısı düz taramanınkiyle aynı, 443,95. Uzamsal anahtar bir yaklaşıklık değil, bir ön elemedir; kesin uzaklık her adayda ayrıca hesaplanır. İkincisi isabet hücre boyuyla çöküyor: 0,5 km’de taranan adayın yüzde 63,4’ü gerçek eşleşme, 8 km’de yalnız yüzde 3,3. Sekiz kilometrelik hücrede 13.611 aday taranıyor; aday bütçesi 1000 olan kısıt 2 km ve üstünü doğrudan eliyor.

Üçüncüsü ödünleşimin şekli. Hücre küçüldükçe aday azalıyor ama sorgulanan hücre sayısı artıyor: 0,5 km’de 25 hücre ve 700 aday, 1 km’de 9 hücre ve 864 aday. KT9’un oranıyla eşdeğer iş 1200’e karşı 1044 çıkıyor ve 1 km kazanıyor. Kazanan tarafın oranı da yazılabilir: iki boy tam olarak bir hücre araması 10,25 aday taramasına denk geldiğinde eşitleniyor. Bir dizin araması bundan ucuzsa 0,5 km, pahalıysa 1 km doğru seçimdir — yani karar depo motorunun bir özelliğine bağlıdır, coğrafyaya değil.

Tasarım

Uzamsal anahtar kayda denormalize edilerek yazılır (Veri Katmanı Ölçekleme kursunun Veri Dağıtımı konusu) ve üzerine bir dizin konur (Veritabanları müfredatının Veritabanı Yönetimi kursu, Dizin Türleri); ikisi birlikte uzamsal dizini oluşturur. Dizin mekaniği orada kuruldu, burada seçilen tek şey anahtarın taneciğidir — 1 km. Kategori süzgeci gerektiğinde anahtar bir bileşik dizine girer (aynı kurs, Bileşik ve Kısmi Dizinler): sıralama (hücre, kategori) olur, çünkü hücre her sorguda eşitlikle verilir.

Parçalama anahtarı uzamsal anahtarın kendisi değil, karmasıdır (Veri Dağıtımı konusu, Parçalama). Uzamsal anahtara göre parçalanırsa yoğun bir bölgenin bütün hücreleri aynı parçaya düşer ve modeldeki kümelenme doğrudan sıcak parçaya dönüşür; karma parçalamada bir sorgunun 9 hücresi farklı parçalara dağılır ve dokuz paralel arama olur. Bu, gecikme için ödenen bir bedeldir ve tercih edilmesinin nedeni tepe 1666,67 sorgunun tek parçada toplanmamasıdır.

Hareketli nesnelerin konumu ayrı bir anahtar–değer deposunda tutulur (aynı konu, Depo Türleri): anahtar nesne kimliği, değer son konum ve hücre. Saniyede 24.000 güncelleme yer tablosuna yazılmaz, çünkü yer kayıtları neredeyse hiç değişmez ve iki iş yükünün aynı dizini paylaşması dizin bakımını güncelleme hızına bağlardı. Yer sorgusu için hücre sonucu yanında okuma ile önbelleğe alınır (Önbellek Mimarisi konusu); bayatlık penceresi burada güvenlidir çünkü yerler değişmez, hareketli nesneler ise önbelleğe hiç girmez.

Bilerek kullanılmayan kalıp: somutlaştırılmış görünüm. Her hücre için komşularıyla birlikte önceden hesaplanmış bir aday listesi tutmak sorguyu tek okumaya indirirdi, ama her kaydın dokuz hücrede birden görünmesi demektir; hareketli nesnelerin saniyede 8000 güncellemesi 72.000 yazmaya çıkar ve tepe yazma hızı üç katına çıkarken kazanç bir dizin aramasıdır. İkincisi talep fişi kalıbıdır (Dayanıklılık ve Güvenilirlik kursunun Dağıtık Doğruluk konusu): en kötü durumda yanıt gövdesi 1000 adayın süzülmüş halidir ve 320 baytlık kayıtlarla yüz kilobaytın altında kalır — gövdeyi bir depoya koyup fiş döndürmek yanıta bir tur daha ekler.

Elenen Alternatifler

Düz tarama kaçırma kısıtını kusursuz karşılar ve hiçbir dizin bakımı istemez; sorgu başına 40.000.000 kayıt okur ve tepede saniyede 66,7 milyar kayda çıkar — aday bütçesinin kırk bin katı. Kaba hücre, örneğin 8 km, dizin aramasını en aza indirir (9 hücre) ama 13.611 aday tarar ve 1000 kısıtını on üç kat aşar; 2 km bile 2123 adayla kısıtın iki katındadır.

Tek hücre sorgusu üçüncü alternatiftir ve dokuz arama yerine bir arama ister. Onu tablonun son iki sütunu eliyor: yalnız sorgu noktasının kendi hücresi taransaydı 1 km hücrede 443,95 eşleşmenin yalnız 181,41’i bulunurdu, yani yüzde 59,1 kaçırma. Oran hücre büyüdükçe düşüyor (8 km’de yüzde 6,3) ama sıfıra inmiyor, çünkü sorgu noktası hücrenin kenarına ne kadar yakınsa daire o kadar dışarı taşar.

Tek hücre sorgusu hiçbir hücre boyunda kaçırma kısıtını karşılamıyor; komşu hücrelerin taranması bir iyileştirme değil, bir gerekliliktir. Hangi kısıt değişirse alternatif kazanır: kaçırma kısıtı gevşetilip “sonuçların yüzde 90’ı yeter” denseydi 8 km hücrede tek hücre sorgusu yüzde 93,7 ile geçerdi ve dokuz arama bire inerdi.

Arıza Davranışı ve Feda Edilen

Bir parça düğümü düştüğünde sorgunun dokuz hücresinden bir kısmı yanıtsız kalır. Burada iki seçenek vardır ve tasarım ikincisini seçer: eksik yanıtı hata saymak ya da elde olan hücrelerle yanıt verip sonucun kısmi olduğunu belirtmek. İkincisi zarif bozulmadır (Dayanıklılık ve Güvenilirlik kursunun Arıza Yalıtımı konusu) ve bedeli ölçülmüştür: bir hücre eksik kalırsa kaçırma oranı sıfır kısıtı çiğnenir, ama tek hücre sorgusunun yüzde 59,1’lik kaçırmasının yanında dokuzda bir eksik tarama çok daha küçük bir bozulmadır. Önbellek düştüğünde yük doğrudan dizine biner ve tepe 1666,67 sorgu tamamen depoya ulaşır; bu, aday bütçesinin neden yanıt boyutuna değil tepe hıza göre seçildiğinin gerekçesidir.

Feda edilen: sorgu başına 864 aday taranıyor, gerçek yanıt ise 443,95 kayıt — isabet yüzde 51,4 ve tasarım her sorguda yaklaşık yarısı boşa giden bir tarama kabul ediyor. Bu israfın karşılığı, kaçırma oranının sıfır kalması ve hücre boyunun tek bir sayıya sabitlenebilmesidir.

Özet

• Bu vakada hacim küçük (12,80 GB) ama sorgu pahalı: düz tarama tepede saniyede 66,7 milyar kayıt okumak demek, aday bütçesi 1000 olduğunda aynı yük kırk binde birine iniyor.
• Uzamsal anahtar doğruluğu bozmuyor: her hücre boyunda eşleşme sayısı düz taramayla aynı (443,95), çünkü hücre bir ön elemedir ve kesin uzaklık her adayda ayrıca hesaplanır.
• Aday sayısı hücre boyuyla hızla büyüyor: 0,5 km’de 700, 1 km’de 864, 8 km’de 13.611; isabet yüzde 63,4’ten yüzde 3,3’e düşüyor ve 1000 aday kısıtı 2 km ve üstünü eliyor.
• Küçük hücre adayı azaltır ama hücre sayısını artırır: 0,5 km 25 hücre ve 700 aday, 1 km 9 hücre ve 864 aday; eşdeğer iş 1200’e karşı 1044 ve iki boy bir hücre araması 10,25 aday taramasına denk geldiğinde eşitlenir.
• Komşu hücre sorgulamak bir iyileştirme değil zorunluluktur: yalnız kendi hücresi taransa 1 km’de kaçırma yüzde 59,1, 8 km’de yüzde 6,3 olur ve hiçbir boyda sıfıra inmez.

Sonraki Adım

Bu konudaki dört vaka aynı ayrımın iki yakasında durdu. Nesne deposu ile video servisi işi yazıldığı anda yaptı: parça yerleştirildi, kalite basamakları üretildi ve okuma yalnız hazır olanı aldı. Ölçüt sistemi ile konum servisi işin bir kısmını sorulduğu anda yaptı: toplulaştırma önceden hesaplansa da yüzdelik sorusu okuma anında yanıtlandı, uzamsal anahtar önceden yazılsa da yakınlık sorgusu her seferinde yeniden tarandı. Hiçbir vakada ikisinin aynı sistemde birlikte gerekmesi ele alınmadı: aynı veri hem geriye dönük olarak eksiksiz işlenmek hem de geldiği anda saniyeler içinde yanıtlanmak zorunda kalsaydı, iki işleme biçiminin ürettiği sonuçların birbirini tutması ayrı bir tasarım problemi olurdu. Sonraki ders o problemi ele alır.