Kendi Veritabanınızı Oluşturmak

• Anahtar-değer veritabanının temel ilkeleri ve uygulama süreci anlatılır
• Dosya sistemi ile kalıcı depolama ve arama yaklaşımından başlanır
• Veri ekleme, güncelleme ve silme işlemlerinde verimsizlik sorunları ortaya çıkar
• Eklemeli (append-only) dosya, dizin, sıralama, segment sıkıştırma (compaction) ile zamanla daha verimli bir yapıya evrilir
• Sonuç olarak modern bir yapı olan LSM ağacına bağlanır ve büyük ölçekli sistemlerde kullanılmaktadır

---

Giriş: Kendi Veritabanınızı Yapmaya Başlamak

Veritabanı kavramı yokmuş gibi varsayarak, kendi veritabanınızı adım adım nasıl kurabileceğinizi keşfediyoruz. En basit biçimde bir anahtar-değer veritabanının nasıl doğrudan uygulanacağını inceliyoruz.

Temel Fikir: Dosya ile Kalıcı Depolama

• Veritabanının amacı, verileri kalıcı olarak saklamak ve daha sonra etkili bir şekilde sorgulamaktır
• En yaygın yöntem, her bir anahtar-değer çiftini dosyaya yazmak için dosya sistemini kullanmaktır
• Veriler eklenirken örneğin $ db set 1 "Lorem ipsum" biçiminde dosyaya içerik eklenir
• Veriyi ararken, dosyadaki tüm anahtar-değer çiftleri sırasıyla taranır ve istenen anahtar bulunur
• Güncelleme sırasında ilgili anahtarın değeri dosya içinde doğrudan değiştirilir, silme sırasında ise kayıt dosyadan çıkarılır

Sorun: Yerinde (in-place) Düzenlemede Verimsizlik

• Dosya içindeki veriyi doğrudan düzenlemek veya silmek çok verimsizdir
• Dosya yalnızca basit bir bayt akışı olduğundan, ortadaki bir veriyi değiştirdiğinizde arkasındaki tüm verinin taşınması gerekir
• Örneğin bir kaydı yeni bir değerle değiştirirken uzunluk farklılaşırsa, ardından gelen tüm içerik yeniden konumlandırılmak zorunda kalır
• Veri arttıkça bu durum hız ve verimlilik üzerinde ciddi etki yaratır

İyileştirme 1: Append-Only Dosya Yapısı

• Güncelleme ve silmede, mevcut veriyi olduğu yerde tutup yalnızca dosyanın sonuna yeni kayıtlar eklenir
• Veri değiştiğinde yeni bir kayıt eklenir ve arama algoritması son eklenen anahtar değerini dönecek şekilde güncellenir
• Silme, özel bir "tombstone" değeri (null vb.) ile işaretlenir
• Avantajı: Mevcut veriyi taşımadan verimli kayıt işlemi yapılabilir
• Dezavantajı: Yinelenen veriler ve silme işaretleri nedeniyle dosya zamanla büyür
• Arama hızı yine yavaştır (tüm dosyayı tarama gerekir)

İyileştirme 2: Dosya Boyutu Yönetimi ve Compaction

• Dosyanın sınırsız büyümesini önlemek için belirli bir boyutu geçince yeni bir dosyaya (segment) geçilir ve önceki dosyadaki gereksiz veriler (yinelenenler/silinmiş olanlar) temizlenerek boyut küçültülür (compaction)
• Compaction sırasında yalnızca gerçekten gerekli veriler bırakılır; eski kayıtlar veya yalnızca silme işareti taşıyan kayıtlar atılır
• Birden fazla segment dosyasıyla yönetim yapılarak gerekirse bu dosyalar birleştirilir (merge)

İyileştirme 3: Dizin (Index) ile Hızlı Sorgulama

• Her anahtar için dosya içindeki konumu (offset) tutan bir in-memory (ön bellekte) hash table dizini oluşturularak hızlı sorgu sağlanır
• Sorgulamada önce dizin kontrol edilir ve doğrudan ilgili dosya konumundan okuma yapılır
• Trade-off: Sorgu hızı artar ancak dizin bellekte olduğu için anahtar sayısı arttıkça belleğin sınırına yaklaşılır
• Dizin yönetimi nedeniyle yazma performansı bir miktar düşer

İyileştirme 4: Sıralama (Sorted String Tables) ve Sparse Index

• Veriler her zaman anahtara göre sıralanmış saklanırsa aralıklı sorgularda (range query) yüksek verimlilik sağlanır
• Sıralama sayesinde dizini tüm anahtarlar yerine yalnızca bir kısmını (seyrek indeks - sparse index) tutmak mümkün olur
• Dizin yoğunluğu ayarlanarak bellek kullanımı ile sorgu verimliliği arasındaki denge kontrol edilir

Uygulama Biçimi: In-Memory ve Diskin Birleşimi ile Kalıcılık

• Yeni veriler önce sıralı in-memory listeye yazılır, ayrıca bir append-only dosyasıyla yedekleme işlevi de görür
• Bellek içi liste büyüdüğünde bunu diskte sıralı bir dosyaya (SST) yazıp dizin güncellenir
• Sorguda önce bellek kontrol edilir, yoksa dizin ile diskte arama yapılır
• Disk dosyaları değişmez (immutable) şekilde yönetilir; güncelleme ve silme yine yeni veri eklenerek yapılır
• Gereksiz yinelenen ve silinmiş veriler düzenli olarak compaction ile temizlenir

LSM Ağacının (Log-Structured Merge Tree) Ortaya Çıkışı

• Bu geliştirilmiş yapı pratikte LSM ağacı adıyla geniş ölçekte kullanılmaktadır
• In-memory (memtable) ile diskteki sıralı dize tabloları (sorted string table, SST) birleşiminden oluşur ve hızlı, büyük ölçekli ortamlara uygundur
• LevelDB, Amazon DynamoDB gibi büyük ölçekli anahtar-değer veritabanlarında temel veri yapısıdır
• B-Tree tabanlı ilişkisel veritabanlarıyla farkları ve bazı dezavantajları olmakla birlikte, yüksek trafikte genişleme konusunda güçlü performans gösterir

Sonuç

• Basit dosya tabanlı yaklaşımdan başlayıp append-only, dizin, sıralama, segment-compaction ve in-memory-disk birleşimi ile daha iyi bir veritabanı tasarımına doğru evrilir
• Geliştirme süreci üzerinden veritabanı iç işleyişi ve mimari düşünce yapısı doğrudan öğrenilebilir
• LSM ağacı günümüzün büyük ölçekli veri sistemlerinde standart bir rol üstlenir
• İleride ilişkisel veritabanlarındaki B-Tree gibi farklı mimarileri keşfetmek için alan bulunmaktadır

[GN⁺]

Hacker News Yorumları

• Bu yazının tasarımı ve örnekleri gerçekten çok hoşuma gitti; okunması kolay bir düzeni var ve böyle bir alıştırma çok eğlenceli. Hiçbir şeyden başlamaya kalkınca gerçekten ne kadar bildiğini test etme imkânı doğuyor.
  • Ben de eskiden, "kendi veritabanını kendin yapma, KV veritabanı da kullanma, sadece SQL yaz" şeklinde aceleci bir tutumdaydım. Ama bu düşünce bile, doğrudan DB tasarlamaya çalışıp KV veritabanını tek başına kullanarak SQL’den kaçınmaya uğraştığımda ve sonunda SQL’i kaba bir şekilde yeniden icat ettikten sonra edinilmişti. Pratikte yaşayarak öğrenmenin kesin bir değeri var.
  • Tek bir eksiği var: örnek olarak lorem ipsum kullanılmış olması, dikkatini daha çok dağıtmıştı; bu yüzden meseleye tam odaklanıp geçmeden geçilmiş. Gerçek veri örnekleri çok daha fazla ilgi çekerdi. Bunun dışında gerçekten müthiş bir yazı.
• “LSM ağaçları, DynamoDB gibi sistemlerde temel olarak kullanılan bir veri yapısıdır ve büyük ölçeklerde de çok iyi performans verir; saniyede 8 milyon değil de 80 milyon isteğe kadar çıkabilir” deniyor ama burada biraz yanıltıcı bir durum var. LSM yalnızca düğüm seviyesindeki depolama motorunda kullanılır; dağıtık sistemin tamamının 80M RPS ile ölçeklenmesi süreci anlatılmıyor. Bildiğim kadarıyla orijinal Dynamo makalesinde BerkeleyDB (b-tree veya LSM) kullanılıyordu ve 2012’de tamamen LSM tabanlı bir motora geçilmiştir.
• Yazı listesindeki bazı makaleleri tıkladım, tasarım ve animasyon gerçekten çok güzeldi.
• “Sorting in Practice” kısmındaki ilk örnek bozulmuş gibi görünüyor. Açıklama metni bellekte sıraladıktan sonra sıralanmış biçimde diske yazılması gerektiğini söylüyor ama örnekte diske yazılırken sıralama bozuluyor. Recap kısmındaki flush örneğinde (2.) de aynı şey var, metinde ise dosyaya sıralı şekilde yazıldığı yazıyor.
• İlginç bir yazıydı. Son zamanlarda geliştirici etkinliğini zaman serisi anahtar-değer sistemine modellemeye çalışıyorum; her geliştiriciyi anahtar, commit’leri değer alıyorum. Benzer bir sorunu yaşıyorum: log hızla büyüyor, indeks ağırlaşıyor ve aralık sorguları yavaşlıyor. Segment compacting yaparken hangi verinin atılacağına nasıl karar vereceğim konusunda merakım var; tazelik ile saklama süresi arasındaki dengeyi tutturmanın zor olduğunu hissediyorum.
• Son 4 haftadır triple store yazmakla meşgulüm. Bu yazı biraz daha erken yayımlansaydı daha erken kavrayacağım birkaç içgörü bulurdum, hayal kırıklığı.
• Eğer yazar bu yazıyı görürse, siteye bir RSS feed ekleyip ekleyemeyeceğini merak ediyorum; Feedly’de ekleyip okumak isterim.
• Kendi veritabanınızı yapmayı denemek istiyorsanız bu ücretsiz çevrimiçi kitap *’ı kesinlikle öneririm
  • Daha önce birinin bash örneğiyle bir veritabanının temel kavramlarını anlattığı bir yazıyı (ör. "bash ile DB oluşturma") burada gördüğümü hatırlıyorum ama bulamıyorum. Bunu bilen varsa, lütfen paylaşsın.
• Site şu an zaten çok yüksek trafik yüzünden erişilemez durumda.
  • Daha hızlı bir veritabanına ihtiyaç olacak.
• Bu "First Principles"ten başlamak ve adım adım ilerlemek gerçekten çok hoşuma gidiyor. Bu yazıyı takip ettiğinizde her adımda hangi sorunun ortaya çıktığını ve onu çözerken hangi yeni sorunların doğduğunu net bir şekilde görebiliyor, bu da gerçekten tatmin edici bir yaklaşım haline geliyor.