[C#] Pet project: document database

[SideShow]

Hallo

Omdat het mij interesseert, maak ik een eigen document database. In feite een veredelde serializer van (voorlopig nog) simpele POCO's, niettegenstaande ik toch wat extra's implementeer zoals indexen (in de vorm van binary search tree's - b-tree's zijn net nog iets te complex).

Ik heb in feite enkele basic vragen, maar weet niet direct welke oplossing nu de beste zou zijn voor dit speeltuin projectje :-)

=> Als een reeds persisted object wordt gewijzigd met als resultaat een kleinere byte size, dan kan je het gewoon wel laten staan op de zelfde positie in de file veronderstel ik? Stel dat het object eerst 10 bytes lang is en na de wijziging nog 8, dan zullen er 2 bytes ongebruikt zijn. Dit valt waarschijnlijk op te lossen door 1 of andere vacuum of reformat functie te implementeren, die al dan niet op afroep zijn werk kan doen voor de gehele file?

=> Als de wijziging resulteert in een grotere byte size, dan kan je het object op een andere plaats zetten. (In mijn simpele zandbak is dat gewoon achteraan de file). Maar om te voorkomen dat dit telkenmale moet gebeuren, neem ik dan best een soort grow factor? Bvb byte size laten groeien met factor 2? Je kan natuurlijk ook al meteen meer bytes dan nodig reserveren voor elk nieuw geserialiseerd/persisted object neem ik aan?

Misschien kan iemand zijn licht hierop laten schijnen.

[RobIII]

SideShow schreef op woensdag 11 september 2013 @ 11:06:
=> Als een reeds persisted object wordt gewijzigd met als resultaat een kleinere byte size, dan kan je het gewoon wel laten staan op de zelfde positie in de file veronderstel ik? Stel dat het object eerst 10 bytes lang is en na de wijziging nog 8, dan zullen er 2 bytes ongebruikt zijn. Dit valt waarschijnlijk op te lossen door 1 of andere vacuum of reformat functie te implementeren, die al dan niet op afroep zijn werk kan doen voor de gehele file?

Dat kan en is een optie ja.

SideShow schreef op woensdag 11 september 2013 @ 11:06:
=> Als de wijziging resulteert in een grotere byte size, dan kan je het object op een andere plaats zetten. (In mijn simpele zandbak is dat gewoon achteraan de file). Maar om te voorkomen dat dit telkenmale moet gebeuren, neem ik dan best een soort grow factor? Bvb byte size laten groeien met factor 2? Je kan natuurlijk ook al meteen meer bytes dan nodig reserveren voor elk nieuw geserialiseerd/persisted object neem ik aan?

Dat kan en is een optie ja. Hoewel ik een growfactor van 1.1 ofzo zou hanteren (10%) dus daar zou ik sowieso een double of andere float van maken.

[H!GHGuY]

Je wil misschien ook rekening houden met snapshots en versionering.
Dan heeft het zin om elk object (+versienummer?) in de eerstvolgende blok free space in te voegen en dan later nieuwe free space bij te maken door garbage collection of iets dergelijks.
Snapshots zijn dan gratis en versionering ook.

[djc]

SideShow schreef op woensdag 11 september 2013 @ 11:06:
Misschien kan iemand zijn licht hierop laten schijnen.

Ik zou zelf inzetten op een append-only datastructuur. Dit wordt bijvoorbeeld gebruikt in CouchDB, maar ook in systemen als Mercurial en git. Reden hiervoor is volgens mij vooral dat het een stuk moeilijker is data in je database te corrumperen door per ongeluk iets te overschrijven. Dus ik zou alles aan het einde schrijven en dan inderdaad een compaction-routine schrijven die de database helemaal herschrijft in een apart bestand en aan het eind het oude met het nieuwe overschrijft.

[Hydra]

Hoeft nieteens in een apart bestand. Je kunt vrij simpel in 'vrije tijd' blokken data naar 'voren' halen. In het databasesysteem waar ik in m'n vorige baan mee werkte gebeurde het met on-disk pages van X kB waarvan bijgehouden werd of ze vrij waren (simpele bitmap). Een object nam altijd n pages in beslag waarbij je dus gewoon stukjes lege data had. Als er dan een object verwijderd werd, werden die pages weer aangemerkt als vrij. Als er een nieuw object toegevoegd werd, werd gewoon de eerste de beste plek met genoeg vrije pages gepakt.

Een achtergrondproces deed ook aan compacting, dus pages werden naar voren gehaald op momenten dat er verder niks te doen was voor het system.

[HMS]

Ik zou inderdaad ook naar iets als MVCC kijken voor je concurrency: Wikipedia: Multiversion concurrency control

Dan kan je simpel garbage collection doen door een threshold op het aantal versies te zetten, en zo blokken vrij te maken.

Trouwens, Ayende is ook bezig met een nieuwe storage engine voor RavenDB, dus misschien kan je op zijn blog nog wat interessante info vinden met betrekking tot design decisions: http://ayende.com/blog

[SideShow]

Hiermee kan ik deze zaak alweer wat meer laten rijpen in mijn hersenpan. :-) Alvast bedankt