Veritabanı Temelleri

 (tontinton.com)
5 puan yazan GN⁺ 2023-12-16 | 1 yorum | WhatsApp'ta paylaş
  • Basit bir Bash anahtar-değer deposundan başlayarak, gerçek veritabanlarının dayanıklılık, atomiklik, izolasyon ve performansı neden ayrı tasarım sorunları olarak ele alması gerektiğini adım adım gösterir
  • fsync/fdatasync, flock ve WAL; arıza ve eşzamanlılık durumlarında veriyi koruyan temel araçlardır, ancak garanti düzeyi yükseldikçe performans maliyeti artar
  • Depolama motorları, disk I/O ve arama maliyetini azaltmak için B-tree ve LSM tree gibi yapılar kullanır; her birinin ardından vacuum ve compaction gibi bakım işleri gelir
  • Dağıtık veritabanları, erişilebilirlik ve yatay ölçekleme kazanırken CAP teoremi, ağ bölünmesi, tutarlılık ayarı ve çakışma çözümü gibi dağıtık sistem karmaşıklıklarını üstlenir
  • Bir veritabanı seçerken veya uygularken ACID garantileri, izolasyon düzeyi, depolama yapısı, replikasyon yöntemi ve tutarlılık gereksinimleri iş yüküne göre ayarlanmalıdır

bashdb ile ortaya çıkan veritabanlarının temel sorunu

  • bashdb, iki Bash fonksiyonuyla yapılmış basit bir anahtar-değer deposudur
    • db_set, dosyaya key,value biçiminde append eder
    • db_get, son değeri okumak için grep, sed ve tail kombinasyonunu kullanır
  • Öğrenme amaçlı olarak basittir; ancak yalnızca bu uygulama bile üretim veritabanlarının çözmesi gereken sorunları ortaya çıkarır
    • Durability: db_set başarılı olduktan sonra makine çökerse, diske flush edilmemiş veri kaybolabilir
    • Atomicity: Yazma sırasında çökme olursa veri yalnızca kısmen kaydedilip bozulabilir
    • Isolation: Okuma ve yazma aynı anda aynı öğeye erişirse, okuma tarafı verinin yalnızca bir kısmını görebilir
    • Performance: db_get, tüm dosyayı satır satır aradığı için O(n)’dir

ACID ve bashdb iyileştirme denemeleri

  • ACID, birçok veritabanının garanti etmeye çalıştığı özellikleri bir araya getiren bir kısaltmadır
    • Atomicity: Yazma sırasında arıza olursa, kısmi yazma durumu bırakmadan işlemin tamamını iptal eder veya geri alır
    • Consistency: Geçersiz işlemler veritabanını bozmamalıdır
    • Isolation: Aynı veriye eşzamanlı erişimde race condition olmamalıdır
    • Durability: Başarılı yazmalar, güç kesintisi gibi durumlardan sonra da korunmalıdır
  • Tüm veritabanı işlemlerinin mutlaka ACID garantisi sağlaması gerekmez; bazı kullanım durumlarında performans için garantiler düşürülebilir

  • Dayanıklılık ve fsync

    • write sistem çağrısı tamponu dosyaya yazar, ancak bu hemen kalıcı depolama aygıtına kaydedildiği anlamına gelmez
    • Çekirdek, tamponu page cache içinde dirty page olarak saklayıp daha sonra diske flush edebilir
    • Disk aygıtı veya RAID sistemi de ayrı bir write cache’e sahip olabilir
    • fsync ve fdatasync, dirty page’leri kalıcı depolamaya flush etmek için kullanılan sistem çağrılarıdır
    • fdatasync, write ile geçirilen raw buffer’ı flush eder
    • fsync, verinin yanı sıra mtime gibi dosya metadatasını da flush eder
    • db_set sonuna sync -d database eklemek, fdatasync’e yakın bir davranışla dayanıklılığı artırabilir; ancak sync genellikle write’ın kendisinden daha yavaş olduğu için performansı düşürür
    • fsync() başarısı, “son fsync’ten bu yana yapılan tüm write’lar diske ulaştı” anlamına gelir; yalnızca “son başarılı fsync’ten sonraki write’lar” anlamına gelmez
    • PostgreSQL 2018’de bu sorunu yaşadı ve fsync hatasında yeniden denemek yerine panic edecek şekilde davranışını değiştirdi
    • Bu olay fsyncgate olarak bilinir ve ilgili kaynak olarak fsync failures makalesi bağlantısı verilir
    • MongoDB’de yazmalar varsayılan olarak her 100 ms’de bir sync edildiğinden %100 dayanıklı değildir

  • İzolasyon ve flock

    • bashdb’de en basit çok süreçli izolasyon yöntemi, depolama dosyasını okumadan veya yazmadan önce lock almaktır
    • Linux’taki flock dosyayı kilitler; -s bayrağı kullanılırsa shared lock ile birden fazla reader aynı anda okuyabilir
    • İyileştirilmiş bashdb, yazma için exclusive lock, okuma için shared lock kullanır
    • Dezavantajı, her yazmada tüm veritabanını kilitlemesidir
    • Yalnızca Bash ile atomikliği basitçe garanti etmek zordur; mv -T veya rename kullanma olasılığı vardır, ancak tamamlanmamıştır
    • bashdb, O(n) sorgulama sorununu hâlâ çözemez

Depolama motorunun rolü ve darboğazlar

  • Depolama motoru, kalıcı depolamada veri okuma ve yazma için bir soyutlama sağlar; başlıca hedefleri yüksek throughput ve düşük gecikmedir
  • En büyük kısıt, diskin kendi hız farklarından kaynaklanır
    • Örnek gecikme tablosunda L1 cache referansı yaklaşık 0.5ns, SSD’den 4KB random read 150,000ns, disk seek ise 10,000,000ns olarak verilmiştir
    • L1 cache referansını yaklaşık 0,5 saniyelik bir kalp atışı olarak düşünürsek, SSD’den 1MB sıralı okuma yaklaşık 12 güne, diskten 1MB sıralı okuma ise yaklaşık 8 aya karşılık gelir
  • Bu yüzden depolama motoru tasarımı, disk I/O ve disk seek’i olabildiğince azaltma yönünde gelişmiştir
  • Yaygın depolama motoru tasarım öğeleri şunlardır
    • Öğeleri diskte saklayan temel veri yapısı
    • ACID işlemleri
    • Disk okumalarını azaltmak için cache
    • SQL, document, graph gibi API katmanları
  • Depolama motoru veri yapıları genel olarak değiştirilebilir yapılar ve değişmez yapılar olarak ikiye ayrılabilir
    • Değiştirilebilir yapılar, dosyaya yazılmış verinin daha sonra üzerine yazılmasına izin verir
    • Değişmez yapılar, dosyaya yazılmış veriyi yalnızca tekrar okur

Değiştirilebilir B-tree

  • Veri artsa bile iyi performansı korumak için, bashdb gibi doğrusal arama yapmak yerine öğeleri en fazla logaritmik zamanda bulabilmek gerekir
  • BST ile O(log n) sorgulama mümkündür; ancak düğümler disk üzerinde birbirinden uzaksa arama sırasında çok sayıda disk seek oluşabilir
  • B-tree, bir düğümün ikiden fazla çocuğa sahip olabildiği BST genellemesidir ve spatial locality’den yararlanır
    • Diskten genellikle 4KB veya 8KB page okunduktan sonra, içindeki birden fazla düğüm bellek ve CPU cache’inde sıralı olarak karşılaştırılır
    • Bellek ve CPU cache erişimi diskten katbekat hızlı olduğu için, diskten okunan baytları olabildiğince çok kullanmak önemlidir
  • Sıralı bellek erişimi; SIMD, instruction pipelining ve prefetching sayesinde çok güçlü olabilir
  • B+ tree yalnızca leaf node’larda değer saklar, diğer düğümlerde ise yalnızca key saklayarak tek bir disk page’inde daha fazla key’in karşılaştırılmasını sağlar

  • Alan geri kazanımı ve vacuum

    • B-tree, alan optimizasyonu için veri parçalanmasıyla oluşan boş alanları geri kazanmalıdır
    • Büyük bir değerle güncelleme yapıldığında bir sonraki düğümün verisinin üzerine yazılabileceği için öğe başka bir konuma taşınır ve özgün page’de bir boşluk oluşur
    • Küçük bir değerle güncelleme yapıldığında sonda bir boşluk kalır
    • Silme işlemi, silinen değerin bulunduğu yerde bir boşluk oluşturur
    • Bu tür alan geri kazanımı ve page yeniden yazma süreci vacuum, compaction, page defragmentation, maintenance vb. adlarla anılabilir
    • Genellikle kullanıcı isteklerinde gecikme spike’ını önlemek için arka planda yürütülür
    • PostgreSQL’de auto vacuum daemon yapılandırılabilir
    • B-tree, PostgreSQL’in varsayılan index’i gibi index’lerin temel veri yapısı olarak yaygın şekilde kullanılır; DynamoDB’nin şaka yollu “distributed B-tree” diye anıldığı bir örnek de vardır

Değişmez LSM tree

  • LSM tree, disk seek işlemlerinin pahalı olması fikrinden yola çıkan append-only bir veri yapısıdır
  • Veriler yalnızca dosyanın sonuna eklendiğinde disk kafasının bir sonraki yazma konumuna büyük ölçüde hareket etmesi gerekmez; bu da yazma ağırlıklı iş yükleri için avantaj sağlar
  • Log Structured Merge tree, kısaca LSM tree, RocksDB, Cassandra, ScyllaDB gibi modern veritabanı depolama motorlarında kullanılır
  • Temel çalışma şekli şöyledir
    • Yazmalar, bellekte sıralanabilir bir veri yapısında tamponlanır
    • Örnekler AVL tree, Red Black tree, Skip Listtir
    • Belirli bir kapasiteye ulaşıldığında sıralı bir dosya olan Sorted String Table, yani SSTable olarak flush edilir
  • SSTable, sıralanmış verileri sakladığı için binary search ve sparse index ile disk I/O’sunu azaltabilir
  • Dayanıklılık için belleğe yazılan işlemler Write-Ahead Log, yani WAL’a kaydedilir
    • Program başlarken WAL okunarak kapanma veya crash öncesindeki duruma geri yüklenir
  • Silme işlemleri de normal yazma gibi append edilir; değer yerine tombstone saklanır
    • tombstone, compaction sürecinde kaldırılır

  • LSM tree’de okuma ve compaction

    • LSM tree’de okuma önce bellekteki veri yapısını arar; bulunamazsa diskteki SSTable’ları en yeni dosyadan en eski dosyaya doğru tarar
    • Yazmalar arttıkça kontrol edilmesi gereken SSTable sayısı artar
    • Her dosya sıralı olsa bile çok sayıda küçük dosyayı taramak, tek bir büyük dosyaya bakmaktan daha yavaş olabilir
    • Karşılaştırma ifadesi log(num_files * table_size) < num_files * log(table_size) şeklindedir
    • compaction, birden fazla küçük SSTable’ı tek bir büyük SSTable’da birleştiren ve tombstone’ları kaldıran arka plan işlemidir
    • RocksDB, Leveled Compaction uygular
    • Yeni flush edilmiş SSTable level 0’da yer alır
    • Bir level’da ayarlanan sayıda dosya biriktiğinde, compaction sonrasında yeni dosya bir sonraki level’a yükseltilir
    • tombstone kaldırma dikkatli yapılmalıdır
    • Silinen bir öğenin daha eski dosyalarla yapılan compaction sırasında yeniden ortaya çıkması şeklinde data resurrection sorunu oluşabilir
    • RocksDB, son level’a yükselten compaction’a kadar tombstone’u korur
    • Rust ile yazılmış gerçek bir örnek için dbeel’in LSM tree kodu bağlantı verilmiştir

  • Bloom filter

    • Bloom filter, bir öğenin bir kümede bulunmadığını verimli biçimde doğrulamaya yarayan olasılıksal bir küme veri yapısıdır
    • Sorgu sonucu iki türlüdür
      • false: öğe kesinlikle kümede yoktur
      • true: öğe kümede olabilir
    • Bloom filter, birden fazla hash function sonucunu bitmap’teki bit konumlarına eşleyip 1 olarak ayarlar
    • Alan karmaşıklığı, sıradan set’lerdeki O(n)den farklı olarak O(log n) şeklinde sunulur
    • Daha fazla bitmap belleği ayırarak ve hash function sayısını artırarak “yok olduğundan emin olma olasılığı” ayarlanabilir; bunun için bir hesaplayıcı da vardır
    • LSM tree, her SSTable için Bloom filter saklayarak belirli bir key’in bulunmadığı doğrulanmış SSTable aramalarını atlayabilir

WAL ve transaction garantileri

  • WAL, ani crash’lerden sağ çıkmak için tüm transaction işlemlerini özel bir dosyaya kaydetme yöntemidir
  • Veritabanı süreci başladığında WAL dosyasını okur ve veri durumunu yeniden oluşturur
    • commit log’u olmayan transaction’lar atlandığı için atomiklik elde edilir
  • Kullanıcıya yanıt vermeden önce yazma isteğinin verisi WAL’a kaydedilip flush edilirse, başlangıçta mutlaka okunabildiği için dayanıklılık elde edilir
  • WAL, transaction event’leri için event sourcing’in bir biçimi olarak görülebilir

İzolasyon seviyeleri ve eşzamanlılık kontrolü

  • İzolasyonu sağlamanın yolları genel olarak üçe ayrılır
    • Kötümser lock: Şu anda yazılmakta olan verilere erişimi engeller
    • İyimser lock: Verinin bir kopyasını değiştirir; transaction sırasında orijinal değişmemişse commit eder, aksi halde retry yapar
    • MVCC: Verinin üzerine yazmak yerine yeni bir version oluşturur; her kullanıcının belirli bir zamandaki snapshot’ı görmesini sağlar
  • Tüm uygulamaların tam izolasyona, yani serializable isolation’a ihtiyacı yoktur
  • ANSI/ISO SQL 92, bir transaction sırasında başka bir transaction aynı veriyi değiştirdiğinde ortaya çıkabilecek sonuçları üçe ayırır
    • Dirty read: Henüz commit edilmemiş başka bir transaction’ın güncellemesini okuma
    • Non-repeatable read: Aynı row iki kez okunurken arada başka bir transaction commit ettiği için değerin değişmesi
    • Phantom read: Aynı koşuldaki row kümesi iki kez okunurken arada row eklenmesi veya kaldırılması
  • ANSI/SQL 92 izolasyon seviyeleri yüksekten düşüğe şöyledir
    • Serializable: Yalnızca commit edilmiş verileri okur; aralık tabanlı çoklu row yazmaları da dahil olmak üzere phantom read’i önler
    • Repeatable reads: phantom read’e izin verilir
    • Read committed: non-repeatable read’e izin verilir
    • Read uncommitted: dirty read’e izin verilir
  • Daha yüksek izolasyon seviyeleri genellikle performans fedakârlığıyla birlikte gelir
  • ANSI/SQL 92 izolasyon seviyeleri eksik olmakla eleştirilir
    • Birçok MVCC uygulaması serializable isolation değil, snapshot isolation sağlar
    • Hızlı bir serializable MVCC algoritması olarak HyPer önerilir

Dağıtık sistemlere neden ihtiyaç duyulur ve CAP

  • Dağıtık sistemler çok fazla karmaşıklık eklediğinden, dağıtık olmayan çözümler yeterliyken bunlardan kaçınılmalıdır
  • Veriyi birden fazla makineye dağıtmanın yaygın iki nedeni vardır
    • Kullanılabilirlik(Availability): Veritabanı makinesi crash olsa veya kullanıcıyla bağlantısı kesilse bile istekler başka bir makineye gönderilebilir
    • Yatay ölçekleme(Horizontal Scaling): Daha büyük tek bir makineye ölçeklemek olan vertical scaling yerine, ağa bağlı birden fazla makinenin tek bir makine gibi davranmasını sağlar
  • Dağıtık sistemler operasyonel karmaşıklık ve network partition sorunlarını beraberinde getirir
  • CAP teoremi, bir sistemin aşağıdaki üç özellikten yalnızca ikisini garanti edebileceğini söyler
    • Consistency: Okumalar en son yazmayı alır
    • Availability: Arızalardan bağımsız olarak tüm istekler başarılı olur
    • Partition Tolerance: Düğümler arası mesaj kaybı veya gecikme olsa bile sistem çalışmaya devam eder
  • Tek makineli veritabanında network partition yoktur ve tutarlıdır; ancak makine arızasında yeni istekler başarısız olduğu için availability ihlal edilir
  • İki makinenin ayrı CPU, bellek ve disklere sahip olup bir kabloyla bağlı olduğu durumda, arıza anında seçenekler ayrışır
    • İstekler iptal edilirse availability’den feragat edilip consistency korunur
    • Yalnızca çalışan makinede istekler işlenmeye devam edilirse consistency’den feragat edilip availability korunur
  • consistency’den feragat edip daha sonra uzlaştıran sistemlere eventually consistent denir
  • Network partition, kümeye dağılmış verilerin toplanmasını gerektirdiği için verimli JOIN işlemlerini de zorlaştırır; NoSQL çevresi bunu hafifletmek için denormalization önerir

Replikasyon ve Amazon Dynamo Örneği

  • Amazon'un orijinal Dynamo makalesi, amazon.com alışveriş sepetinde availability'nin consistency'den daha önemli görüldüğü bir örnek olarak sunulur
    • Kullanıcı alışveriş sepetinde aynı üründen iki tane görürse birini silebilir
    • Bunun, satın almanın hiç mümkün olmadığı bir durumdan daha iyi olduğu değerlendirilmiştir
  • Availability elde etmek için birden çok node'un veriyi paylaşması tek başına yeterli değildir; her öğenin en az bir kopyası bulunmalıdır
  • Bir öğenin kopyalarını saklayan node replica, kopyalama süreci ise replication olarak adlandırılır
  • Replica sayısını artırmak availability'yi yükseltir, ancak kopyaları saklamak için daha fazla kaynak gerekir
  • Veri kopyaları bütün olarak saklanmak yerine erasure coding ile parçalara ayrılıp birden çok node'a dağıtılabilir; ilgili gecikme özellikleri için erasure coding yazısı bağlantılıdır

Consistent Hashing ve Veri Yerleşimi

  • Birden çok node olduğunda, saklama isteğini hangi node'un işleyeceğini belirleyen bir load balancing veya veri partitioning yöntemi gerekir
  • Basit bir yöntem, primary key'i hash'leyip node sayısına göre modulo almaktır
    • Bir node eklendiğinde veya kaldırıldığında len(nodes) değişir ve aynı key farklı bir node'u işaret eder
    • Bu durumda neredeyse tüm öğeleri migrate etmek gerekir; maliyeti yüksektir
  • Consistent Hashing, node'ları bir diziye değil bir ring'e yerleştirerek node ekleme/kaldırma sırasında taşınması gereken öğe sayısını azaltır
    • Dynamo ve Cassandra gibi veritabanlarında kullanılır
  • Consistent hashing'de node adının hash'i ring'e yerleştirilir; istek key'inin hash'inden sonra karşılaşılan node sahip olur
  • Replica seçimi, ring üzerinde saat yönünün tersine ilerleyip kopyayı sonraki node'a kaydetme şeklinde yapılabilir
    • Sahip node ölürse replica node isteği işleyerek availability'yi korur
    • Bu yöntem Leaderless Replication olarak adlandırılır ve Cassandra gibi Dynamo tarzı veritabanlarında kullanılır
  • Node eklenirken taşınması gereken ortalama key sayısı num_keys / num_nodes değeridir
  • Virtual node, tek bir fiziksel node'u ring'e birden çok kez yerleştirerek bazı node'ların daha fazla öğeye sahip olma olasılığını azaltır
    • Örnek, node adına "half-0", "half-1" gibi index'i suffix olarak ekleme yöntemidir
  • Leader node ve replica node seçmenin başka bir yöntemi leader election'dır, ancak burada ele alınmaz

Leaderless Replication ve Tutarlılık Ayarı

  • Leaderless yapı, yüksek availability elde ederken consistency'den ödün verir
  • Sahip node write isteği sırasında down durumundaysa replica'ya yazılır; sahip node yeniden ayağa kalktıktan sonra read isteğinde eski veri okunabilir
  • Belirli bir istekte consistency gerekiyorsa read isteği birden çok replica'ya ve sahip node'a paralel gönderilir, istemci en güncel veriyi seçer
  • Write isteği genellikle tüm replica'lara paralel gönderilir, ancak yalnızca bazı node'lardan acknowledgement beklenir
  • İstek düzeyinde consistency ayarlamak için R + W > N/2 + 1 doğrulanır
    • N: Veri kopyasına sahip node sayısı
    • W: Write'ın başarılı olması için acknowledgement vermesi gereken node sayısı
    • R: Read'in başarılı olması için yanıt vermesi gereken node sayısı
  • W veya R değeri N/2 + 1 olan çoğunluk node istekleri quorum olarak adlandırılır

  • Çakışma Çözümü

    • En güncel write'ı seçme süreci Conflict Resolution'dır
    • Yalnızca timestamp karşılaştırmak dağıtık sistemlerde güvenilir değildir
    • Her makinenin kendi hardware clock'u vardır ve clock'lar tamamen doğru olmadığından drift oluşur
    • NTP daha doğru bir zaman kaynağından zaman alır, ancak isteğin kendisi ağdan geçtiği için yanıta kadar geçen süre tam olarak bilinemez
    • Cassandra timestamp kullanır; ilgili doküman Cassandra data versioning bağlantılıdır
    • Google Spanner, özel yüksek hassasiyetli zaman donanımı ve timestamp belirsizlik aralığını açığa çıkaran bir API ile clock tabanlı consistency garantisi sağlamıştır; ilgili makale Spanner paper'dır
    • Dynamo gibi sistemler Version Vectors ile bazı çakışmaları azaltır
    • Her öğe version'ına (node, counter) çifti eklenerek version'lar arasındaki nedensel ilişki bulunur
    • Kesin olarak daha güncel olan version bulunup bazı eski değerler kaldırılabilir
    • Daha ayrıntılı kaynak olarak Dotted Version Vectors bağlantılıdır
    • Riak KV'de olduğu gibi çakışan değerlerin tamamını uygulamaya döndürüp, uygulamanın veri hakkındaki bilgisine dayanarak çözmesini sağlamak da mümkündür
    • Eventually consistent sistemlerde çakışmaları azaltmaya yönelik çeşitli teknikler genellikle Anti Entropy terimi altında toplanır

Anti Entropy Teknikleri

  • Read Repair

    • İstemci birden çok node'dan gelen read sonuçları arasından en güncel değeri seçtikten sonra, bu değeri henüz saklamayan node'lara tekrar gönderip repair eder

  • Hinted Handoff

    • Write isteği hedef node'a ulaşamazsa başka bir node'da hint olarak saklanır
    • Hedef node yeniden available olduğunda saklanan hint iletilir
    • Quorum write'ta bu yöntem Sloppy Quorum olarak da adlandırılır ve quorum isteklerinin availability'sini daha da artırır

  • Merkle Trees

    • Read repair yalnızca sorgulanan veriyi düzelttiği için çok sayıda veri uzun süre tutarsız durumda kalabilir
    • Node'ların birbirleriyle senkronize olup tüm farkı bulması, veri çok olduğunda O(n) maliyetlidir
    • Merkle tree, veri aralığı hash'ini leaf'lerde saklayan, parent'ın ise child hash'lerini birleştiren hash'i sakladığı hiyerarşik bir yapıdır
    • Root hash aynıysa iki node'un verisi aynıdır; farklıysa alt hash'ler özyinelemeli olarak karşılaştırılarak tutarsız veri bulunur ve senkronizasyon O(log n) hızına indirilebilir

  • Gossip Dissemination

    • Event'leri cluster geneline basit ve güvenilir biçimde yayma yöntemidir
    • Node, mesajı yapılandırılmış sayıdaki rastgele node'a, yani fanout'a gönderir; alan node da yeniden N rastgele node'a gönderir
    • Aynı gossip mesajı yapılandırılmış sayıda görüldüğünde artık broadcast edilmez
    • Veri yakınsamasını hissedebileceğiniz bir simulator bağlantılıdır
    • Gossip mesajları genellikle UDP ile iletilir

Daha Derinlemesine Ele Alınabilecek Alanlar

  • Veritabanlarında burada ele alınanların dışında da birçok konu vardır
    • Linux'ta O_DIRECT kullanımı ve kendi page cache'ini uygulama
    • Dağıtık sistemlerde failure detection
    • Raft gibi consensus algoritmaları
    • Distributed transaction
    • Leader election
  • Bir veritabanı seçerken veya uygularken storage engine, ACID, isolation level, distributed replication ve conflict resolution yöntemlerinin gerçek gereksinimlerle nasıl örtüştüğüne birlikte bakmak gerekir

İlgili okumalar

1 yorum

 
GN⁺ 2023-12-16
Hacker News görüşleri

  • compact metodunda bir hata var: tombstone kayıtları yalnızca son, yani en büyük seviye sıkıştırılırken atlanmalı; tüm seviyeler arasında kaldırılmamalı
    Aksi halde üst seviyedeki tombstone’lar sıkıştırma sırasında kaybolur ve alt seviyelerdeki girdiler yeniden görünür hale gelir
    LSM tabanlı veritabanlarında silme/tombstone kayıtlarının uzun süre kalması özelliklerden biridir; RocksDB gibi bazı veritabanları ise bundan kaçınmaya yönelik optimizasyonlar ekler

    • Doğru, yazıda kısalık için bilerek çıkardım; dbeel içinde ise ele alınıyor
    • RocksDB’nin nasıl bir optimizasyon yaptığını merak ediyorum
      Aralık silme tarafındaki özelliği biliyorum ama tekil anahtar silme için pek bir şey okuduğumu hatırlamıyorum

  • Birçok kişi SQL öğrenirken veritabanlarını da öğreniyor, ama böyle bir dersi alıp B-tree’yi anlayarak öğrenmeyi öneririm
    RDBMS’lerin artıları ve eksileri çoğunlukla B-tree’yi ve bunun anahtar ekleme, sorgulama ve sıralama üzerindeki etkisini bilince anlaşılır
    Birçok kişi indeks ekleyerek veritabanını hızlandırmaya çalışıyor; ama sonuçta bu, bir ağacın üstüne başka bir ağaç koymaktan ibaret ve temel sorunu gizlemiş oluyor
    Bazı problemler B-tree’ye iyi uyar, ama birçok problem uymaz
    SQL, uzaktaki bir B-tree sistemine yönelik bir sorgu arayüzünden ibarettir

    • Bu fazla indirgemeci
      B-tree tek indeksleme stratejisi olmadığı gibi, indekslerin okuma performansını artırmak karşılığında yazma performansından feragat etmeye yarayan bir araç olduğu da iyi bilinir
      Çünkü veritabanları genellikle yazmadan çok daha fazla okuma işler
      “Bir ağacın üstüne başka bir ağaç koymanın” tam olarak hangi sorunu gizlediğini ve indekse dokunmadan bunu nasıl çözeceğinizi merak ediyorum
      Makul büyüklükteki tablolar için indeksler fiilen zorunludur
    • Buna katılıyorum
      B-tree ve hash indeksleri, G/Ç katmanı, süreç modeli gibi şeyleri öğrenmek gerekir
      Günümüzde sütun yönelimli veritabanlarının genel stratejilerini öğrenmek de değerli: geç tuple materyalizasyonu, tembel yürütme, doğrusal tarama ve ikili arama, komut hattı işleme gibi şeyler
      Bunlara aşina olunca, sahada kimi zaman bir DBMS yerine basit düz dosyaların ya da RocksDB gibi gömülü bir veritabanının yeterli olduğunu da görürsünüz
    • B-tree de olabilir, LSM-tree, trie ya da duruma uygun başka bir indeks yapısı da olabilir
      Elbette covering index de olabilir
    • “Bir ağacın üstüne başka bir ağaç koyduğu için sorunu gizler” kısmını somut bir örnekle açıklarsanız iyi olur

  • “Dağıtık olmayan bir çözüm yeterliyse dağıtık sistemlerden kaçının” tavsiyesine tersinden yanıt vermek isterim
    Önemsiz olmayan her operasyonel sistem bir dağıtık sistemdir
    En azından veritabanınız bir replikasyon setiyse zaten dağıtık bir sistemdir; bu yüzden dağıtık sistemleri öğrenmemek risk almaktır
    https://jepsen.io/ ve https://raft.github.io/ bakmaya değer

    • Sistemin bazı parçaları ağ çağrılarından veya dağıtık yönlerden kaçınamayabilir
      Ama bu, bunları her yere sokmanın sorun olmayacağı anlamına gelmez; böyle yaparsanız karmaşıklık gereğinden çok artar
    • Önce “önemsiz olmayan operasyonel sistem”i tanımlamak gerekir
      Böyle söylemek, gereksiz karmaşıklıktan kaçınma tavsiyesini çürütmez. Asıl mesele teknik olarak dağıtık olup olmadığı değil, gerçekten gerekli olup olmadığıdır
      Dağıtık sistemleri öğrenmek ile kullanmak farklı şeylerdir
      Öğrendikten sonra da yalnızca uygun yerlerde uygulayacak ölçülülüğe sahip olup olmadığınız önemlidir
      Günümüzde basit ve iyi çalışan sistemleri daha güçlü bir dağıtık modele taşımak için çok emek harcandığı ve bunun neredeyse maliyetsizmiş gibi ele alındığı çok oluyor
      Oysa çözülmek istenen probleme ve ölçeğe bakınca tek bir Postgres örneği ve monolitin yeterli olacağı durumlar açıkça görülüyor
      Orijinal tavsiye bana bu anlamda görünüyor
    • HN balonu içinde doğru olabilir, ama ortalama bir iş dünyası bakış açısından hiç de öyle değil
      En azından mutlaka öyle olmak zorunda değil
    • Dağıtık/yedekli sistemler yedekleme değildir
      Ben yine de basit çözümü seçme tavsiyesini verirdim
      Sistemler “önemsiz ve basit depolarda” bile kalıcı durumu doğru şekilde saklama, yedekleme ve geri yükleme konusunda çoğu zaman başarısız oluyor
      Felaket kurtarma durumunda dağıtık bir deponun durumunu geri yüklemeye çalışmak daha da zordur
      Dağıtık çözüme geçmeden önce çalışan bir yedekleme çözümüne sahip olabilirsiniz
    • Replika failover’ını dağıtık sistem diye adlandırmak zor
      Salt okunur replikaları olan master yapılandırması da insanların genellikle “dağıtık” dediği şeyden farklıdır. Çünkü yazmalar dağıtık değildir
      Pratikte dağıtık çoğunlukla verinin shard edildiği anlamına gelir ve gerçekten gerekmiyorsa kesinlikle kaçınmak isteyeceğiniz kısım budur

  • Veritabanı oluştururken ilgili birçok kavramı güzelce taradığı için keyifle okudum
    Tek bir makineden performans çıkarmaya yönelik SIMD’den konsensüs algoritmalarına kadar uzanıyor
    Veritabanı, güvenilirlik ve dağıtık sistemler konuşuluyorken, bu durumlara ve veritabanı iç uygulamalarına uygulanabilecek formal yöntemler hakkında da okumaya değer
    S3 ekibinin TLA+ ile modellediği ilginç bir makale var
    [0] Use of Formal Methods at Amazon Web Services
    https://lamport.azurewebsites.net/tla/formal-methods-amazon....
    [1] How Amazon Web Services uses formal methods
    https://www.amazon.science/publications/how-amazon-web-servi...

  • Tutarlılığın veritabanı tutarlılığı ve uygulama tutarlılığı diye iki yönü vardır
    Örneğin tek bir tablo düzeyinde atomiklik, izolasyon ve kalıcılık sağlanabilir; ama birden çok tabloya yayılan yazmalarda başarısız olunabilir
    Birden çok tabloyu aynı anda güncelleyen işlemlerle uğraşmaya başladığınızda tutarlılık önemli hale gelir
    Tüm tablolar aynı anda güncellenmeli ya da hiçbiri güncellenmemelidir

    • Güzel bir örnek, yazıya ekleyeceğim

  • “MongoDB gibi bir belge API’si, Cassandra gibi lidersiz replikasyon, ScyllaDB gibi çekirdek başına iş parçacığı mimarisi var” şeklindeki tasarım çok hoş
    Üstelik tamamı Rust ile yazılmış

  • “Kitaplar merakımı uyandırdığı için küçük bir veritabanını kendim yaptım” aşaması, sanırım pek çok geliştiricinin bir kez olsun geçtiği bir aşama
    Bunu özellikle engellemeye çalışmam. Kendin yapınca nelerin çalışmadığını gerçekten çok öğreniyorsun
    Zaman ayırabiliyorsan son derece değerli bir ders
    Kendi veritabanımı yapmış olmam, mevcut çözümlere duyduğum saygıyı en çok artıran şey oldu
    Baytları diske hızlı yazıp okumak zor kısım değil
    Asıl zor olan, hayal bile etmediğin kullanım senaryolarını desteklerken yıllar boyunca kararlı biçimde çalışmasını sağlamak

    • Modern DBMS'lerin karmaşıklığının ne kadarı, belirli iş alanlarındaki kullanım senaryolarının getirdiği kısıtlardan kaynaklanıyor diye sık sık merak ediyorum
      Alan dışındaki kullanım senaryolarını yasaklayıp yok sayabileceğimiz varsayımıyla alana özgü DBMS tasarlasak nasıl bir verimlilik elde edebiliriz?
      Örneğin bugün doğası gereği yalnızca eklemeli olan veri kümelerinde bile genel amaçlı veritabanları kullanıyoruz
      Mevcut satırların güncellenmesi ya da silinmesi diye bir kavramın hiç olmadığı, yalnızca ekleme ve tablo/veri kümesinin tamamını silme gibi işlemlerin bulunduğu bir veritabanı nasıl olurdu?
      Böyle bir veritabanı MVCC transaction'larını uygulamak zorunda kalmaz mıydı? Her tablo zaten write-ahead log olduğu için ayrı bir write-ahead log'dan kaçınabilir miydi? Daha verimli depolayabilir miydi? İndekslemeyi tüm tablo düzeyinde atomiklik yerine chunk düzeyinde atomiklikle yapıp kilitlemeyi azaltabilir miydi?

  • Bash sürümünde atomiklik, dosyayı geçici bir dosyaya kopyalayıp düzenledikten sonra sync; mv; sync kullanarak “basitçe” sağlanamaz mı?

    • Kopyalama sırasında ters yönde bir grep filtresiyle yinelenenleri de önleyebilirsin
      Kopyalarken sıralamayı da garanti edebilirsin ama bunu sadece “bash” ve temel yardımcı araçlarla yapmak pek mantıklı görünmüyor
      Bu amaç için DJB'nin CDB'si, yani cdbget, cdbmake vb. var:
      https://cr.yp.to/cdb.html
    • Doğru, daha sonra ekleyeceğim

  • Harika bir yazı
    Database Internals kitabı iyi görünüyor; iç uygulamaya derinlemesine giren benzer başka kitaplar var mı?

    • Kitap değil ama CMU'daki @apavlo grubunun yüklediği veritabanı derslerini öneririm
      https://www.youtube.com/c/cmudatabasegroup
      Hem giriş hem ileri düzey dersler çevrimiçi; ayrıca sektördeki ürünler hakkında sunumlar ve dersler de var
      Çok faydalı
      Daha üst düzey, teorik bilgisayar bilimi açısından bakan ve fiziksel uygulamaya daha az odaklanan bir kaynak olarak “Alice” kitabı, yani “Foundations of Databases” mükemmel
      Çok yoğun ve matematiksel, ama ilişkisel cebiri ve Datalog'u, ayrıca Datalog'un ilişkisel cebire dönüştürülmesini ele alıyor
      Basılı kitabı artık bulmak zor; ikinci el aldığım nüshanın cildi dağılmış, sayfaları kopmuş halde gelmişti ama kitabın tamamı çevrimiçi: http://webdam.inria.fr/Alice/
    • Postgres'e odaklanan ünlü bir kaynak da var: https://www.interdb.jp/pg/
    • Benzer tarzda bir genel bakış için şu makale iyi:
      https://dsf.berkeley.edu/papers/fntdb07-architecture.pdf
    • Raghu Ramakrishnan'ın Database Management Systems kitabı da çok faydalıydı
      Ancak Database Internals daha modern

  • Yazının “veritabanı”nı gizemlileştirmeden, Bash'te tek satırlık önemsiz bir uygulama göstererek başlaması hoşuma gidiyor
    Harika bir giriş