C# Stream.Read en performantie

[SideShow]

Hallo

Ik heb een implementatie gemaakt van een binary search tree, dit persistent (op schijf dus).
Wikipedia: Binary search tree

Kort gezegd is elke node een aantal bytes, waarbij er sommigen bytes verwijzen naar een andere locatie binnenin het bestand (parent, left child, right child).

Nu, geen echte verrassing, bij het wegschrijven van veel nodes (met unieke key dan), begint dit lang te duren. (1 miljoen nodes wegschrijven duurde 3 minuten).
Misschien tegenstrijdig voor mensen die deze datastructuur niet kennen: bij profilen in Visual Studio is het de native Stream.Read methode die ongeveer 75% van de totale tijd in beslag neemt. Dit omdat de tree constant gelezen moet worden om af te dalen en te bepalen waar een volgende node moet komen.

Ik heb geprobeerd om het bestand (enkele tientallen megabytes, zeer variabel natuurlijk) gewoon in een MemoryStream te steken, daar alle bewerkingen te doen, en dan weg te schrijven, maar een MemoryStream is jammergenoeg niet uitbreidbaar, dus m.a.w. ik kan geen nieuwe data toevoegen.

Zijn er nog zaken die ik (relatief makkelijk) kan proberen vooraleer ik kijk naar MemoryMapped files of iets dergelijks? Ook deze laatste lijkt me niet direct een oplossing lijkt me, omdat dit op het eerste zicht enkel in memory views maakt van een file (?)

Enige tips over "random read/ocassional write" gekoppeld aan performantie zijn welkom.

[EddoH]

Ik vind je post een beetje warrig opgezet, maar begrijp ik het goed dat je tijdens het schrijven ook de file continue leest om te bepalen waar er geschreven moet worden? Dit is natuurlijk niet erg efficient...

Het lijkt me dat je de tree in memory beschikbaar hebt, en op het moment dat je deze wilt opslaan je de tree naar een file serialiseert.

[Woy]

Ik begrijp ook niet helemaal waarom je je file telkens zou moeten lezen tijdens het wegschrijven. Op het moment van opslaan kun je toch prima bepalen waar welke node in het bestand moet komen te staan?

[Paul]

Je hebt een datastructuur (in jouw geval een binary search tree) en die heb je de functions WriteToDisk en ReadFromDisk (of vergelijkbaar) gemaakt?

Waarom zou je tijdens het schrijven je eigen bestand weer inlezen? Die informatie heb je toch allemaal al?

[beany]

Probeer nodes te cachen en als het mogelijk is rekening te houden met de blocksize van je filesystem. Iedere lees (en schrijf) actie leest standaard van schijf 4kb of 8kb(afhankelijk van welk filesystem je gebruikt en wat de instellingen zijn).

[SideShow]

Weten waar een node moet komen = de tree afdalen = vertrekken van de root node en vervolgens afdalen in child nodes = continue stukjes van de file uitlezen om uiteindelijk de referentie van de laatste node aan te passen naar de locatie van de nieuwe node. Ook de nieuwe node moet een referentie bevatten naar de locatie van de laatste node.

@beany: dat lijkt me inderdaad een idee !

[Hydra]

Dan nog ga je bij dit soort operaties enorm last hebben van de latency van je disk. Je zit iedere keer te wachten tot de leeskop op de juiste plek staat, en op het moment dat die data ook onder die kop doordraait. Ik zou toch echt proberen een in-memory index aan te leggen van waar welke node naartoe wijst zodat alleen het lezen en schrijven van data zelf op disk zit te wachten/

[SideShow]

Ok, dit zijn zaken waarmee ik inderdaad verder kan. Bedankt iedereen.

[HMS]

Een B-Tree is veel beter geschikt voor 'on disk' gebruik dan een standaard BST.

Daarnaast lijkt mij dit het makkelijkste:

EddoH schreef op maandag 31 maart 2014 @ 16:53:
Het lijkt me dat je de tree in memory beschikbaar hebt, en op het moment dat je deze wilt opslaan je de tree naar een file serialiseert.

[ Voor 68% gewijzigd door HMS op 31-03-2014 17:47 ]

[SideShow]

Het cachen van de nodes (left en right) per node, bleek uiteindelijk zeer eenvoudig.

Resultaat van 200.000 unieke nodes wegschrijven: 16 seconden zonder cache en 4.5 seconden met cache. Lijkt me fantastisch om deze kant verder uit te spitten.

@HMS: inderdaad, maar ik wou beginnen met het implementeren van de eenvoudigste tree structuur, gewoon om van te leren. Toch bedankt!

[Sjaaky]

SideShow schreef op maandag 31 maart 2014 @ 16:41:
Enige tips over "random read/ocassional write" gekoppeld aan performantie zijn welkom.

Ik heb niet geen concrete tips voor je. Alleen een url naar de blog Ayende @ Rahien waar het afgelopen jaar veel geschreven is over onderzoek naar en de bouw van een storage engine.

Wat je vantevoren moet weten is dat RavenDB hun nosql database is, die de Esent storage engine van Microsoft gebruikt. En Voron hun daarna ontwikkelde storage engine, die ook als basis kan dienen voor RavenDB.

Vanaf maart 2013 start de auteur met onderzoek naar bestaande c(++) storage engines zoals leveldb en lmdb. In augustus worden b+ trees besproken. In de maanden daarna verschillende manieren om datastructuren naar disk te schrijven. Hoe zaken efficient en ook consistent gehouden kunnen worden.

Imho een zeer interessante blog.

Wellicht toch nog een tip. Kijk of je een goede bestaande storage engine kunt vinden .

[SideShow]

Hola, dat is inderdaad een machtig interessante blog! Echter, je laatste tip vind ik minder... net door zelf een simpele implementatie te maken, krijg je voeling met zaken.

Een quote uit de blog:
"I don’t learn by just reading code, I really need to do some writing to actually understand the concepts."
Dit is 1 van de vele quotes die ik uit die blog kan halen in dit verband. :-)

En inderdaad, voor mijn werk gebruiken we inderdaad gewoon SQL en Lucene hoor, geen nood