Echte databases gelegen aan de wereldwijde knopen zijn al lang bekend, maar tot nu toe weten nog maar weinigen hoe ze deze superwapens effectief kunnen gebruiken.
Als je de wereldwijde knopen gebruikt om de taken op te lossen waarin ze echt goed zijn, kun je opmerkelijke resultaten behalen. Ofwel in prestaties, ofwel in het vereenvoudigen van de oplossing van de taak (, ).
Wereldwijde knopen zijn een speciale manier van gegevensopslag en -verwerking, heel anders dan tabellen in SQL. Ze verschenen in 1966 in de taal (evolutionaire ontwikkeling — , verder COS) in medische databases en worden daar nog steeds , en zijn ook door gedrongen in enkele andere gebieden waar betrouwbaarheid en hoge prestaties vereist zijn: financiën, handel, enzovoorts.
Wereldwijde knopen in moderne databasesystemen ondersteunen transacties, logging, replicatie en partitionering. Dat wil zeggen, je kunt moderne, betrouwbare, gedistribueerde en snelle systemen op hen bouwen.
Wereldwijde knopen beperken je niet tot de grenzen van het relationele model. Ze geven vrijheid voor de ontwikkeling van datastructuren die geoptimaliseerd zijn voor specifieke taken. Voor veel applicaties kan het verstandige gebruik van wereldwijde knopen daadwerkelijk een geheim wapen zijn, dat zorgt voor prestaties waar ontwikkelaars van relationele applicaties alleen maar van kunnen dromen.
Wereldwijde knopen als gegevensopslag kunnen in veel moderne programmeertalen worden gebruikt, zowel hoog- als laag-niveau. Daarom zal ik in dit artikel specifiek op wereldwijde knopen focussen en niet op de taal waarvan ze ooit zijn voortgekomen.
2. Hoe werken wereldwijde knopen
Laten we eerst begrijpen hoe wereldwijde knopen werken, en wat hun sterke punten zijn. Wereldwijde knopen kunnen vanuit verschillende perspectieven worden bekeken. In dit deel van het artikel zullen we ze als bomen bekijken. Of als hiërarchische datastores.
In vereenvoudigde termen is een globale een persistente array. Een array die automatisch op schrijfbare schijf wordt opgeslagen.
Het is moeilijk om iets eenvoudiger voor gegevensopslag voor te stellen. In de code (in de talen COS/M) verschilt het alleen van een gewone associatieve array door het teken ^ voor de naam.
Om gegevens in een globale op te slaan, hoef je de SQL-querytaal niet te leren; de opdrachten voor het werken ermee zijn heel eenvoudig. Je kunt ze in een uur leren.
Laten we beginnen met het eenvoudigste voorbeeld. Een eendimensionale boom met 2 takken. Voorbeelden zijn geschreven in COS.
Set ^a("+7926X") = "John Sidorov"
Set ^a("+7916Y") = "Sergey Smith"
Bij het invoegen van informatie in de global (commando Set) gebeuren er automatisch 3 dingen:
- Opslaan van gegevens op schijf.
- Indexeren. Wat tussen haakjes staat, fungeert als de sleutel (in Engelse literatuur - "subscript"), en rechts van het gelijkteken als waarde ("node value").
- Sorteren. Gegevens worden gesorteerd op sleutel. Bij het traverseren van de array zal het eerste element "Sergey Smith" zijn en het tweede "John Sidorov". Bij het opvragen van de gebruikerslijst uit de global besteedt de database geen tijd aan sorteren. Bovendien kan een gesorteerde lijst vanaf elke sleutel, zelfs een niet-bestaande, worden opgevraagd (de output begint met de eerste echte sleutel die volgt op de niet-bestaande).
Al deze bewerkingen gebeuren ongelooflijk snel. Op mijn thuiscomputer behaalde ik waarden tot 750.000 invoegen/sec in één proces. Op multicore-processors kunnen de waarden oplopen tot invoegen/sec.
Natuurlijk zegt de snelheid van invoegen op zichzelf weinig. Bijvoorbeeld, je kunt informatie heel snel in tekstbestanden schrijven - zo werkt de verwerking van Visa. Maar in het geval van globals krijgen we een gestructureerde, geïndexeerde opslag waar we later eenvoudig en snel mee kunnen werken.
- De sterkste kant van globals is de snelheid van het invoegen van nieuwe knooppunten.
- Gegevens in de global zijn altijd geïndexeerd. Hun traverseren is snel, zowel op één niveau als diep in de boom.
Laten we nog een paar takken van de tweede en derde niveau aan de global toevoegen.
Set ^a("+7926X", "city") = "Moskou"
Set ^a("+7926X", "city", "street") = "Req Square"
Set ^a("+7926X", "age") = 25
Set ^a("+7916Y", "city") = "Londen"
Set ^a("+7916Y", "city", "street") = "Baker Street"
Set ^a("+7916Y", "age") = 36 
Het is duidelijk dat je op basis van globals veelniveau bomen kunt bouwen. Toegang tot elk knooppunt is vrijwel onmiddellijk dankzij de auto-indexering bij invoegen. En op elk niveau van de boom zijn alle takken gesorteerd op sleutel.
Zoals je kunt zien, kan informatie zowel in de sleutel als in de waarde worden opgeslagen. De totale lengte van de sleutel (de som van de lengtes van alle indexen) kan oplopen tot , en de waarden voor Caché. Het aantal niveaus in de boom (aantal dimensies) is 31.
Een ander interessant punt. Je kunt een boom bouwen zonder waarden voor de knooppunten op hogere niveaus op te geven.
Set ^b("a", "b", "c", "d") = 1
Set ^b("a", "b", "c", "e") = 2
Set ^b("a", "b", "f", "g") = 3 Lege cirkels zijn knooppunten waaraan geen waarde is toegewezen.
Om globalen beter te begrijpen, vergelijken we ze met andere bomen: met tuinbomen en met de bomen van bestandssystemen.
Laten we de bomen in globalen vergelijken met de meest vertrouwde hiërarchische structuren: met gewone bomen die groeien in tuinen en velden, evenals met bestandssystemen.
Zoals we zien, bevinden bladeren en vruchten van tuinbomen zich alleen aan de uiteinden van takken.
In bestandssystemen wordt informatie alleen opgeslagen aan de uiteinden van takken, die de volledige namen van bestanden zijn.
Hier is de datastructuur van de global.
Verschillen:
- Interne knooppunten: informatie in een global kan worden opgeslagen in elk knooppunt, en niet alleen aan de uiteinden van takken.
- Externe knooppunten: in een global moeten waarden worden gedefinieerd aan de uiteinden van takken, terwijl dat bij bomen van bestandssystemen en tuinbomen niet het geval is.
In sommige interne knooppunten kan men zeggen dat de structuur van de global een superset is van de structuur van naamstructuren in bestandssystemen en tuinbomen. Dat wil zeggen, flexibeler.
In het algemeen geval stelt een global een geordende boom voor met de mogelijkheid om gegevens in elk knooppunt op te slaan.
Om beter te begrijpen hoe globalen werken, stel je voor hoe het zou zijn als de makers van bestandssystemen een benadering zoals globalen gebruikten voor het opslaan van informatie?
- Bij het verwijderen van een enkel bestand in een map zou de map automatisch worden verwijderd, evenals alle bovenliggende mappen die alleen de net verwijderde map bevatten.
- De noodzaak voor mappen zou verdwijnen. Er zouden gewoon bestanden zijn met subbestanden en bestanden zonder subbestanden. Als je het vergelijkt met een gewone boom, zou elke tak een vrucht worden.
- Dingen zoals README.txt-bestanden zouden misschien verdwijnen. Alles wat gezegd moest worden over de inhoud van de map kon in het zelfde bestand van de map worden geschreven. In het padensysteem is de naam van het bestand niet te onderscheiden van de naam van de map, dus zou men met alleen bestanden kunnen werken.
- De snelheid van het verwijderen van mappen met geneste submappen en bestanden zou drastisch toenemen. Vaak verschijnen er op Habr artikelen over hoe lang en moeilijk het is om miljoenen kleine bestanden te verwijderen (, ). Echter, als je een pseudo-bestandssysteem op globalen maakt, dan neemt het seconden of delen daarvan in beslag. Toen ik de verwijdering van subbomen op mijn thuiscomputer testte, verwijderde ik in 1 seconde 96-341 miljoen knooppunten uit een twee-laags boom op een HDD (geen SSD). Het gaat hier om het verwijderen van een deel van de boom, niet gewoon het hele bestand met globalen.
Het verwijderen van subbomen is nog een sterke kant van globalen. Hiervoor is geen recursie nodig. Dit gebeurt ongelooflijk snel.
In onze boom zou dit kunnen worden gedaan met het commando Kill.
Kill ^a("+7926X") 
Voor een beter begrip van welke acties we met de globalen kunnen uitvoeren, geef ik een korte tabel.
Belangrijkste commando's en functies voor het werken met globalen in COS
Instellen van takken tot knooppunt (als deze nog niet zijn gedefinieerd) en waarde van knooppunt
Kopiëren van subboom
Verwijderen van subboom
Verwijderen van de waarde van een specifiek knooppunt. De subboom die vanuit het knooppunt komt, wordt niet aangeraakt.
Volledige doorlooptijd door de boom met diepte-ingang
Doorloop van takken van een specifiek knooppunt
Controle op of het knooppunt gedefinieerd is
Atomaire incrementeerwaarde van het knooppunt. Om geen uitlezingen en schrijvingen te doen, voor ACID. De laatste tijd wordt aangeraden om over te schakelen naar
Dank voor uw aandacht, we staan klaar om uw vragen te beantwoorden.
Disclaimer: Dit artikel en mijn opmerkingen hierover zijn mijn mening en hebben geen relatie met de officiële positie van de onderneming InterSystems.
Vervolg . U leert welke datatypen op globalen kunnen worden weergegeven en bij welke taken ze de grootste winst opleveren.
Bron: habr.com
