Ethereum çekirdek geliştiricileri: MPT hex ağacı değiştirilecek
5.000 sayfalık bir kitabı çevirdiğinizi hayal edin.Yazar sizi arayıp hikayede ayarlamalar yaptığını söylemeye devam ediyor. Bu zaten çevirmiş olduğunuz sayfaları etkileyecek ... ve bu sonsuza kadar devam edebilir. Bu Ethereum Halen kullanılan MPT onaltılık ağaçtan ikili ağaç yapısına dönüşümde de benzer bir ikilemle karşılaşıldı. Bu bağlamda, Ethereum çekirdek geliştiricisi Guillaume Ballet, dönüşüm işlemini üç adımda yaklaşık birkaç günde tamamlayabilecek bir çözüm önerdi.
(Resim: tuchong.com)
Teklifle ilgili olarak, Ethereum kurucu ortağı vitalik şunları söyledi:
"Ballet'in önemli araştırma temeli, Ethereum'u devletsiz ve dost canlısı hale getirecek ve aynı zamanda protokolü büyük ölçüde basitleştirmek için bir fırsat yaratacak. Önümüzdeki birkaç ay için Ethereum 1.x geliştiricileri daha olağanüstü olacak Çalışma ve sonuçlar. "
Aşağıdaki çeviridir:
Ethereum'u etkileyen birçok sorundan biri, hesap ve sözleşme verilerinin saklanma yöntemidir.Ethereum tarafından şu anda seçilen yapıya Merkle Patricia Ağacı (Merkle Patricia Ağacı veya MPT) denir. Teoride anlamlı olsa da pratikte çözdüğünden daha fazla sorun getiriyor. Uzun yıllardır çekirdek geliştiriciler ikili ağaçlara dönüşüm konusunu tartışıyorlar.Bu yazıda, bu soruna ilişkin görüşlerimi netleştirip sonra ona bir çözüm sunacağım.
Önerilen süreç, her iki ağaç yapısının da var olacağı bir geçiş dönemini ortaya koymaktadır. Bunun avantajı, ağaç yapısı dönüştürüldüğünde ana zincirin çalışmaya devam edebilmesi ve ayrıca tüm hesapların ikili ağaç formatına dönüştürülmesini sağlayabilmesidir.
arka fon
Şu anda Ethereum hesapları onaltılık bir ağaçta saklanmaktadır. Sözde on altı çatal, bir düğümün 16 çocuk düğüme sahip olduğu anlamına gelir Teorik olarak, bu iyidir, çünkü tüm verilerinizi depolamak için daha az "aşamaya" ihtiyacınız olduğu anlamına gelir.
Örneğin bu, anahtar ve değer çiftini (170, v) onaltılık ağaç biçiminde temsil etme işlemidir. Onaltılık olarak 170, 0xaa olarak temsil edilir, bu nedenle yalnızca iki katmana ihtiyacınız vardır: biri ilk a için, diğeri ikinci a için.
Şekil 1: Bu, "v" değerinin 0xaa anahtarında nasıl saklandığını gösteren onaltılık bir üçlü ağaç örneğidir. Bu ağacın yalnızca 2 baytlık anahtarları vardır ve yalnızca 0xaa anahtarının alt ağacı boyunca genişletilir. Kısaca, ilgisiz alt ağaçlar "..." ile değiştirilir.
Bu ağacın çok sığ ve çok geniş olduğuna dikkat edin. Ardından, aynı anahtar ve değer çiftinin aşağıdaki ikili ağaç gösterimi ile karşılaştırın. İkili olarak 170, 10101010 olarak temsil edilir.
Şekil 2: Şekil 1'dekiyle aynı anahtar / değer çiftleri, ikili ağaç biçiminde saklanır. Kısalık olması açısından, ilgisiz alt ağaçlar "..." olarak belirtilir.
Gördüğünüz gibi ağaç çok daha derin ve daha dardır.
Ethereum'da her blok, MPT kökünün hash değeri olan bir stateRoot alanı içerir. Sonuç olarak, bu hash, kökün 16 çocuğunun hash listesinin hash edilmesi ile elde edilir. Bu alt karma sütunların her biri, sırayla alt karma listesinin karmasıdır ve bu böyle devam eder.
Her yeni blok oluşturulduğunda, madenci hesap ağacını günceller ve kök hash değerini yeniden hesaplar. Karma, yeni bloğun stateRoot alanında saklanır ve ardından yeni blok mühürlenir.
Şekil 3 Blok başlığının durum kök alanı, onaltılık ağacın köküne işaret eder. Sorun burada ortaya çıkıyor: tüm düğümleri karma hale getirerek karma kökü yeniden hesaplamak çok uzun sürüyor Bu nedenle, kök düğümü hesaplamak için, madenci kardeş karmasını veritabanından alacaktır. Veritabanından tüm kotiledonları almak ve tüm ağaca hash işlemi uygulamak çok zaman almasa da, bu işlem yine de çok zaman alıyor. Bunun nedeni, her hash'in veritabanından alınması gerektiğidir.
Onaltılık bir ağaçta, genellikle her aşamada 15 kardeş karması elde edilir. Yukarıdaki örnekte, bu 30 Bir esrar.
Daha derine inse bile, ikili ağacın her aşaması yalnızca bir kardeş karmasına ihtiyaç duyar. Yukarıdaki örnekte, yalnızca 8 Bir esrar! Pratikte ikili ağaçların aslında daha iyi olmasının nedeni budur.
Kaplama Dönüşümü
Ne yazık ki, Ethereum'u onaltılık bir ağaçtan ikili ağaca geçirmek kolay bir iş değil. Dönüştürülecek çok fazla veri var ve değişikliği gerçekleştirmek 15 saniyeden fazla blok süresi alıyor .
Ek olarak, 5.000 sayfalık bir kitabı çevirdiğinizi ve yazarın sizi arayıp hikayeyi düzelttiğini söyleyin. Bu, zaten çevirmiş olduğunuz sayfaları etkileyecektir ... ve bu sonsuza kadar sürebilir. .
Bu, Ethereum tarafından şu anda karşılaşılan sorundur, çünkü kullanıcı dönüştürülen adresi güncelleyebilir, bu da dönüştürme sürecini yeniden başlatmanız gerektiği anlamına gelir.
Bu problemi çözme önerisi, onaltılık ağacın tepesine bir örtücü ikili ağacın yerleştirildiği bir geçiş periyodu belirlemektir.Fonksiyonu, temel ağaç bir ikili ağaca dönüştürülene kadar durumdaki tüm değişiklikleri kaydetmektir.
Bu geçiş üç adıma bölünecektir:
Adım 1-Dönüştürme
Bu yöntemde, blok yüksekliğinde H1, bloğun iki stateRoots'a sahip olduğu belirlenir: biri "taban" onaltılık ağaç için ve diğeri "örten" ikili ağaç için.
Şekil 4: Dönüştürme işlemi sırasında, bloğun 2 durum kökü vardır: biri geleneksel onaltılık ağacın salt okunur kökü, ikincisi ise "örtücü" ikili ağacın köküdür.
Onaltılık ağaç salt okunur olarak kabul edilir, bu nedenle durumdaki herhangi bir güncelleme, kaplama ağacında bir güncelleme olacaktır.
Bir işlem bir hesabı okuduğunda veya güncellediğinde, sistem ilk olarak kaplama ağacını arar. Hesap orada bulunamazsa, sistem eski onaltılık ağaçtaki değeri arayacaktır.
Aynı zamanda, onaltılık ağaç arka planda dönüştürülüyor. Artık ekleme konusunda endişelenmenize gerek yok, çünkü tüm değişiklikler üst ağaçta saklanıyor.
Adım 2 tabanlı dönüştürme
Arka plan dönüştürme işlemi tamamlandıktan sonra, madenciler, geçiş yapmaya hazır olduklarını duyurmak için salt okunur onaltılık ağaç kökünü dönüştürme sonucuyla değiştirecekler. Durumun okuma ve yazma işlemleri 1. adımdaki ile aynıdır.
Şekil 5: Dönüşümün ikinci aşamasında, blok başlığı, ağa hazır olduklarının sinyalini vermek için onaltılık ağacın temel kökünü ikili ağaç dönüşümünün temel köküyle değiştirir.
Yeterince büyük bir dizi bloğu, dönüştürülen temel kök için aynı değere sahipse, bu, çoğu madencinin dönüşümü tamamladığı ve dönüştürülen ağacın görünümü üzerinde bir fikir birliğine ulaştığı anlamına gelir. Açtıktan sonra birleşme sürecine girin.
3. Adım - iki ağacı birleştirin
Birleştirme işlemi kademeli olarak ilerler: her yeni blok oluşturulduğunda, n anahtar kaplamadan kaldırılır ve ardından temel ağaca yeniden yerleştirilir. Bu işlem, tüm anahtarlar kaplamadan kaldırılıncaya kadar devam edecektir. Bu aşamada, kapsam durumu kökü blok başlığından silinecektir.Ek olarak, işlemin yürütülmesi kaplama ağacında bulunan bir anahtarı yazarsa, anahtar kaplama ağacından silinecek ve doğrudan temel ağaca yazılacaktır.
Sonraki adım
Dönüşümü tamamlamak için gereken süreyi tahmin etmek için bir ön prototip oluşturduk. Tüm sürecin makul bir sürede (yaklaşık birkaç gün) tamamlanabileceğine inanıyoruz. Algoritma geliştikçe daha fazla ayrıntı yayınlayacağım.
Teşekkürler
Bu öneride Alexey Akhunov, Vitalik Buterin, Anna George, Sina Mahmoodi, Tomasz Stanczak ve Martin H. Swende tarafından sağlanan değerli yorumlardan yararlanıldı.
İlgili tartışma: https://ethresear.ch/t/overlay-method-for-hex-bin-tree-conversion/7104
