Veri Yoğun Uygulamalar İçin Veri Yapıları [PDF]
(cs-people.bu.edu)- Anahtar-değer veri yapıları, veri odaklı sistemlerin temel bileşenleridir ve iş yükü ile donanım koşullarına bağlı olarak performans farkları büyük ölçüde açılabilir
- Fiziksel yapı; veri yerleşimi, arama için kullanılan meta veriler ve depolama/arama algoritmaları olarak ayrılır; erişim yöntemleri (access methods), veri kapsayıcıları ve arama yapıları olarak da adlandırılır
- İş yükü; nokta sorguları, aralık sorguları, ekleme, silme ve güncelleme birleşimleriyle ifade edilir; bellek ve kalıcı depolamanın kapasitesi ve maliyeti de tasarım gereksinimleri arasındadır
- B+-tree okuma ve aralık sorgularında güçlüdür, ancak ekleme ve güncellemeler arttıkça yaprak düğümlerin yeniden düzenlenmesi yük oluşturur; LSM-tree ise tamponlama ve birleştirme ile çok sayıda eklemeyi işler
- Veri hareketinin darboğaz olduğu ortamlarda, yeni uygulamalara, donanım değişimlerine ve veri artışına uygun olarak mevcut yapıları seçmek ya da yeni yapılar tasarlamak gerekir
Anahtar-değer veri yapılarının çözdüğü problem
- Anahtar-değer veri yapıları, veri yoğun uygulamalarda yaygın olarak kullanılır ve anahtar-değer modelinin genel amaçlılığı sayesinde birçok sistemin temelini oluşturur
- Tek bir anahtar tek bir değere eşlenir, ancak aynı değer birden fazla anahtarla ilişkilendirilebilir
- Değerin anlamı uygulamaya göre değişir
- İlişkisel veritabanındaki bir kayıt olabilir
- Bir Pandas DataFrame olabilir
- NoSQL sisteminde uygulamanın ayrıştırıp kullandığı bir alan kümesi olabilir
- Sosyal ağ verileriyle çalışan bir sistemde, görüntü veya video gibi büyük nesnelere yönelik referanslar içerebilir
Fiziksel bileşenler ve uygulama kapsamı
- Fiziksel olarak anahtar-değer veri yapısı üç öğeden oluşur
- Belirli bir yerleşimde saklanan veri
- Veride gezinmeye yardımcı olan isteğe bağlı meta veri
- Depolama ve arama işlemlerini destekleyen algoritmalar
- Veri yapıları; veri sistemlerinde, işletim sistemlerinde, dosya sistemlerinde, derleyicilerde ve ağ sistemlerinde çeşitli biçimlerde kullanılır
- Kitaptaki örnekler ağırlıklı olarak büyük ölçekli veri sistemleri ve ikincil depolama aygıtları etrafında şekillense de, analiz ve tasarım yöntemi bellek içi sistemlere de uygulanır
- Bu analiz, iki veya daha fazla aşamalı bellek/depolama hiyerarşisine sahip ortamlara yöneliktir
İş yükü ve maliyet tasarımı belirler
- Bir uygulama ya da iş yükü, anahtar-değer işlemlerinin birleşimi olarak gösterilebilir
-
Nokta sorgusu
-
Aralık sorgusu
- Ekleme
- Silme
- Güncelleme
- Bellek ve kalıcı depolama için gereken kapasite ve maliyet de uygulama gereksinimlerini oluşturur
- Sistem türüne göre optimize edilmesi gereken veri yapısı değişir
- Dosya sistemleri, dosya meta verilerini ve içeriğini sık güncellemelere göre optimize edilmiş veri yapılarıyla yönetir
- Derleyiciler, değişkenleri yaşam döngüleri boyunca hash map ile yönetir ve programın genel biçimini abstract syntax tree olarak ifade eder
- Ağ cihazları, yönlendirme tablolarını verimli biçimde saklamak ve erişmek için özelleştirilmiş veri yapılarına ihtiyaç duyar
-
B+-tree ve LSM-tree arasında karşıt seçimler
- B+-tree, ekleme ve güncellemenin az, nokta ve aralık sorgularının çok olduğu iş yüklerinde okuma ve yazma maliyetini dengelemek için yaygın olarak kullanılır
- Yüksek düğüm fan-out’u, kökten yaprağa giderken gereken ikincil bellek erişimlerini azaltır; üst seviyeler daha hızlı bellek katmanlarında önbelleğe alınır
- Tüm anahtarları yaprak düğümlerde sıralı tutar ve yaprak düğümleri bağlı listeyle birbirine bağlayarak aralık sorgularını destekler
- Ekleme ve güncellemeler arttığında yaprak düğümlerin yeniden düzenlenmesi veya bölünmesi gerekir; bu da performans darboğazına dönüşebilir
- LSM-tree, çok sayıda ekleme içeren iş yükleri için farklı bir yaklaşım kullanır
- Tüm güncellemeleri ortak bir bellek tamponuna koyar
- Tampon dolduğunda diske flush eder
- Tamponlar biriktikçe daha büyük sıralı veri koleksiyonları hâlinde birleştirir
- Güncellemeler out-of-place ilkesiyle işlenir; aynı anahtara sahip anahtar-değer çiftleri yapı içinde birden fazla kez bulunabilir
- Belirli bir anahtarın güncel değeri, en son eklenen anahtar-değer çiftindedir
Uyarlanabilir veri yapıları
- İş yükünü önceden tahmin ederek veri yapısı tasarlamanın yanı sıra, çalışma sırasında kademeli olarak ideal biçime yaklaşan veri yapılarını da ele alır
- Özgün tasarımlarındaki B+-tree ve LSM-tree, tüm nokta veya aralık sorgularını yanıtlamak için diskte bulunan düğümler içinde sıralama düzenini zorunlu kılar
- Uyarlanabilir veri yapıları, bir veya daha fazla sıralanmamış düğümden başlayıp fırsat çıktıkça kademeli olarak sıralanabilir
- database cracking, gelen sorguların erişim örüntülerini kullanarak alttaki veriyi sürekli ve artımlı biçimde fiziksel olarak yeniden düzenler
- Amaç, gelecekteki sorgu performansını iyileştirmektir
Donanım katmanları ve bellek duvarı
- Donanım gelişimi, veri yapısı tasarımında yeni zorluklar ve fırsatlar yaratır
- Depolama hiyerarşisinde alt katmanlar daha düşük fiyata daha fazla depolama alanı sunar, ancak erişim gecikmeleri daha yüksektir; işlemciye yakın üst katmanlar daha hızlıdır, fakat daha küçüktür ve bayt başına maliyetleri daha yüksektir
- Belirli bir uygulamanın darboğaz katmanı, uygulama verisinin boyutuna ve her katmanın depolama kapasitesine göre değişir
- B+-tree başlangıçta fan-out’u en üst düzeye çıkararak disk erişimini azaltmayı hedefliyordu; ancak bellek boyutları büyüyüp veriler RAM’e veya kalıcı ikincil belleğe sığmaya başladıkça ödünleşimler büyük ölçüde değişti
- Bellek içi B+-tree, küçük fan-out değerlerinde en iyi performansı gösterir
- Bellek duvarı (memory wall), işlemci hızı ile off-chip bellek hızı arasındaki farkın büyüme eğilimini ifade eder
- 2000’lerin başından bu yana işletim sistemleri ve veri yönetim sistemleri, önbellek kullanımını optimize edecek şekilde yeniden tasarlanıyor
Tasarım alanı ve yönergeler
- Veri yapısı tasarım seçenekleri alanını düzenler ve uygulama hedefleriyle iş yüküne uygun yapıyı seçme yöntemini ele alır
- Donanım ve veri özellikleri sürekli değiştiği için veri yapısı tasarımında da sürekli yenilik gerekir
- Düzenlenmiş tasarım alanı ve yönergeler, mevcut veri yapıları arasından en uygun olanı seçmek ya da belirli bir iş yüküne uygun yeni bir veri yapısı tasarlamak için kullanılır
1 yorum
Hacker News yorumları
Henüz sadece göz gezdirdim ama bu yazı, devasa bir alanı kapsayan çok etkileyici bir araştırma çalışması
Sadece veri yapılarını sıralamakla kalmıyor; uygulamalarda veri yapıları oluştururken veya kullanırken dikkate alınması gereken unsurları zihinde sistematik hâle getirmeye yardımcı oluyor
Bu kitabın yazarlarından biri bu alanda bir araştırma laboratuvarı yönetiyor
En uygun veri yapısı tasarımına yardımcı olan harika bir araç da var: http://daslab.seas.harvard.edu/datacalculator/
Bu konu hakkında başka önerilen kaynakları merak ediyorum
Makale harika ve Martin Kleppmann’ın Designing Data-Intensive Applications kitabını da biliyorum; ama o kitap veri yapılarından çok veritabanlarına daha yakın
Analitik türde verileri tutacak bir yapı tasarlıyorsanız çok önemli olan yapı dizileri ile dizi yapıları karşılaştırması eksik
Yani konu tartışılıyor; sadece yapı dizileri/dizi yapıları terimleriyle açıklanmıyor
Bir tane almak isterdim ama Amazon’da 100 dolar
Hem yazarın hem okurun kaybettiği bozuk bir düzen
İçindekiler gerekli
Sayfa üstbilgilerini ve altbilgilerini yok saymasını söylediğimde de aynıydı; son durumunun çok daha iyi olduğunu sanıyordum