Globala variabler — svärd som kan lagra data. Träd. Del 1

Verkliga databaser med globala kluster har varit kända länge, men fortfarande är det få som vet hur de effektivt använder dessa supervapen.

Om man använder globala kluster för de uppgifter där de verkligen är bra kan man uppnå utmärkta resultat. Antingen i prestanda eller genom att förenkla lösningen av uppgiften (1, 2).

Globala kluster är ett speciellt sätt att lagra och bearbeta data, helt annorlunda än tabeller i SQL. De introducerades 1966 i språket M(UMPS) (evolutionär utveckling — Caché ObjectScript, senare COS) inom medicinska databaser och används fortfarande där aktivt, samt har även trängt in i andra områden där hög tillförlitlighet och prestanda krävs: finans, handel etc.

Globala kluster i moderna databasystem stöder transaktioner, loggning, replikering och partitionering. Det vill säga, de kan användas för att bygga moderna, pålitliga, distribuerade och snabba system.

Globala kluster begränsar dig inte till gränserna för den relationella modellen. De ger frihet att utveckla datastrukturer som är optimerade för specifika uppgifter. För många applikationer kan rimlig användning av globala kluster vara ett verkligt hemligt vapen, som ger prestanda som utvecklare av relationella applikationer bara kan drömma om.

Globala kluster som ett sätt att lagra data kan användas i många moderna programmeringsspråk, både hög- och lågnivåspråk. Därför kommer jag i denna artikel att fokusera specifikt på globala kluster, snarare än på språket de en gång härrörde från.

2. Hur globala kluster fungerar

Låt oss först förstå hur globala kluster fungerar och vad deras styrkor är. Globala kluster kan ses från olika perspektiv. I denna del av artikeln kommer vi att betrakta dem som träd. Eller som hierarkiska datalagringar.

Ett förenklat sätt att se på globala kluster är att de är ett persistent array. Ett array som automatiskt sparas på disken.
Det är svårt att föreställa sig något enklare för datalagring. I kod (i språken COS/M) skiljer det sig från en vanlig associativ array endast genom tecknet ^ före namnet.

För att spara data i ett globalt kluster behöver du inte lära dig SQL-frågespråket, kommandona för att arbeta med dem är mycket enkla. Du kan lära dig dem på en timme.

Låt oss börja med det mest grundläggande exemplet. Ett enskiktsträd med 2 grenar. Exemplet är skrivet i COS.

Set ^a("+7926X") = "John Sidorov"
Set ^a("+7916Y") = "Sergey Smith"

Vid inmatning av information i globalen (kommandot Set) sker automatiskt 3 saker:

1. Sparar data på disk.
2. Indeksering. Det som står inom parentes fungerar som en nyckel (i den engelskspråkiga litteraturen — "subscript"), medan värdet till höger om likhetstecknet är "node value".
3. Sortering. Data sorteras efter nyckeln. Vid traversal av arrayen blir den första elementen "Sergey Smith" och den andra "John Sidorov". Vid hämtning av användarlistan från globalen ägnar databasen ingen tid åt sortering. Dessutom kan en sorterad lista begäras att visas, med start från vilken nyckel som helst, även en icke-existerande (utskriften börjar med den första verkliga nyckeln efter den icke-existerande).

Alla dessa operationer sker otroligt snabbt. På min hemmadator fick jag värden upp till 750 000 insättningar/s i en process. På flerkärniga processorer kan värdena nå tiotals miljoner insättningar/s.

Självklart säger hastigheten på insättningar i sig inte mycket. Man kan till exempel väldigt snabbt skriva information till textfiler - så säger ryktena att Visa-processering fungerar. Men i fallet med globaler får vi en strukturerad indexerad lagring som kan hanteras enkelt och snabbt i framtiden.

• Den starkaste sidan av globaler är hastigheten på insättning av nya noder.
• Data i globalen är alltid indexerade. Traversalen, både på en nivå och djupt ner i trädet, är alltid snabb.

Låt oss lägga till några fler grenar av andra och tredje nivån i globalen.

Set ^a("+7926X", "city") = "Moskva"
Set ^a("+7926X", "city", "street") = "Req Square"
Set ^a("+7926X", "age") = 25
Set ^a("+7916Y", "city") = "London"
Set ^a("+7916Y", "city", "street") = "Baker Street"
Set ^a("+7916Y", "age") = 36

Det är tydligt att flerdimensionella träd kan byggas på grundval av globaler. Dessutom är tillgången till vilken nod som helst praktiskt taget omedelbar tack vare autoindexeringen vid insättning. Och på vilken nivå i trädet som helst är alla grenar sorterade efter nyckel.

Som man kan se kan information lagras både i nyckeln och värdet. Den totala längden på nyckeln (summan av längderna på alla index) kan nå 511 byte, och värdena 3.6 MB för Caché. Antalet nivåer i trädet (antal dimensioner) är 31.

Ytterligare en intressant punkt. Ett träd kan byggas utan att ange värden för noderna på de övre nivåerna.

Set ^b("a", "b", "c", "d") = 1
Set ^b("a", "b", "c", "e") = 2
Set ^b("a", "b", "f", "g") = 3

Tomma noder är de som inte har tilldelats något värde.

För att bättre förstå globala variabler kan vi jämföra dem med andra träd: med trädgårdsträd och med filsystemets träd.

Vi jämför de globala variablernas träd med de mest bekanta hierarkiska strukturerna: med vanliga träd som växer i trädgårdar och fält, samt med filsystem.

Som vi ser har trädgårdsträd blad och frukter bara på ändarna av grenarna.
I filsystem lagras informationen endast i ändarna av grenarna, som är de fullständiga filnamnen.

Och här är strukturen för en global variabel.

Skillnader:

1. Internt noder: Information i den globala variabeln kan lagras i varje nod, inte bara på ändarna av grenarna.
2. Externa noder: Den globala variabeln måste ha definierade värden på ändarna av grenarna, medan träd i filsystem och trädgårdar inte behöver det.

När det gäller interna noder kan man säga att den globala variabelns struktur är en superset av strukturen hos filsystemets namnträd och trädgårdsträd. Dvs. mer flexibel.

I allmänhet representerar en global variabel ett ordnat träd med möjlighet att lagra data i varje nod..

För att bättre förstå hur globala variabler fungerar, föreställ dig vad som skulle hända om skaparna av filsystem använde en metod för att lagra information som liknar den för globala variabler?

1. Vid radering av en enda fil i en katalog skulle katalogen samt alla överordnade kataloger som endast innehåller just den nyligen raderade katalogen automatiskt raderas.
2. Behovet av kataloger skulle försvinna. Det skulle bara finnas filer med underfiler och filer utan underfiler. Om man jämför med ett vanligt träd, skulle varje gren bli en frukt.

   
   

3. Saker som filer som README.txt skulle kanske försvinna. Allt som behövde sägas om innehållet i katalogen skulle kunna skrivas direkt i filen för katalogen. I sökvägsrummet är filnamnet inte åtskiljbart från katalognamnet, så man skulle kunna klara sig med enbart filer.
4. Hastigheten för att radera kataloger med inbäddade underkataloger och filer skulle öka kraftigt. Många gånger har det cirkulerat artiklar på Habrahabr om hur lång tid och hur svårt det är att radera miljoner små filer.1, 2). Men om man gör ett pseudofilsystem på globalt plan, kommer det att ta sekunder eller delar av sekunder. När jag testade att ta bort underträd på min hemcomputer, raderades 96-341 miljoner noder från ett tvånivåträd på HDD (inte SSD) på 1 sekund. Det handlar alltså om att ta bort delar av trädet, inte bara hela filen med globala variabler.

Att ta bort underträd är ytterligare en styrka hos globala variabler. För detta behövs ingen rekursion. Det går otroligt snabbt.

I vårt träd kan detta göras med kommandot Kill.

Kill ^a("+7926X")

För att bättre förstå vilka åtgärder som är tillgängliga för oss över globala variabler, presenterar jag en kort tabell.

Huvudkommandon och funktioner för att arbeta med globala variabler i COS

Ställ in
Ställa in grenar fram till noden (om de fortfarande är obestämda) och nodens värde

Merge
Kopiera underträd

Kill
Ta bort underträd

ZKill
Ta bort värdet av en specifik nod. Underträdet som går ut från noden berörs inte.

$Query
Fullständig genomgång av trädet med djupdykning

$Order
Gå igenom grenar av en specifik nod

$Data
Kontrollera om noden är definierad

$Increment
Atomär inkrementering av nodens värde. För att undvika läsningar och skrivningar, för ACID. Nuförtiden rekommenderas det att byta till $Sequence

Tack för er uppmärksamhet, vi är redo att svara på era frågor.

Ansvarsfriskrivning: Denna artikel och mina kommentarer till den är min åsikt och har ingen koppling till företagets officiella ställning, InterSystems.

Fortsättning Globala system – skattkistor för lagring av data. Träd. Del 2. Du kommer att lära dig vilka datatyper som kan visas på globala och på vilka uppgifter de ger maximal vinning.

Källa: habr.com