Dateigestützte Collection für große Datenmengen

[ralfz]

Hallo,

ich versuche gerade eine art Container für große Datenmengen zu erstellen und dabei auf relationale Datenbanken zu verzichten. Die Datenstruktur ist vereinfacht als List<List> bzw. List<DataRow> zu verstehen, wobei diese weder in der Anzahl der Spalten noch der Zeilen festgelegt, bzw. beschränkt ist. Da die Datenmenge sehr groß (größer als der RAM) werden kann, müssen die Daten gesplittet werden ( Pages=Chunks !?).

Jede DataRow hat einen key (externer identifier) und vermutlich am Besten auch eine ID, sowie die Daten (Spaltenwerte) in einer Liste.

Der Hauptfokus liegt hierbei auf dem Einfügen, dem Suchen und dem Durchlauf durch die Daten. Updates sind erst einmal unwichtig.

Überlegungen:
a) Implementierung des Collection-Interface
b) Iterationsmöglichkeit
c) Backend für die Chunks als Serialized-Files oder in Objekdatenbank db4o.
d) Gleichzeitig interessiert mich die Performance im Vergleich zwischen Serialisierung und der Objektdatenbank beim Speichern, Suchen, Durchlaufen; Ich möchte die Geschwindigkeit optimieren, daher würde ich auf das Trove-Paket zurückgreifen
e) Trennung von Daten und Index -> B+ Baum

Fragen:
1) Das Collection-Interface greift auf int als Indexwerte zurück. Wenn ich aber von "großen" Mengen spreche, wäre dann nicht long besser? long macht aber viele Probleme.
2) Der Index wird bei long-Werten irgendwann auch zu groß für den Speicher. Wie kann ich den aufteilen bzw. möglichst klein halten?
3) Bisher bin ich davon ausgegangen, dass ich die keys als Indexschlüssel in dem B-Baum verwalte, der dann auf den jeweiligen Chunk bzw. die DataRow in dem Chunk verweist.
3a) Wie gehe ich denn mit evtl. doppelten Einträgen vor? Im prinzip müsste der User die keys vergeben.
3b) Nehme ich aber key und id, dann ist die Frage wie ich die ID vergebe: ID=key? und was mache ich bei belegter ID?
3c) Sollte ich doppelte Schlüssel erlauben? Gäbe das nicht ziemliche Probleme beim suchen bzw. balancieren des Baums!?
4) Wenn der Benutzer für den key einer DataRow andere Werte als int oder long nutzen möchte, müsste ich vermutlich auf String als allgemeinen Typ zurückgreifen. Wie aber nutze ich den als Index? Bzw. wenn ich eine interne ID mit long oder int benutze, wie vergebe ich dann die id? (so eine Art Auto-Increment?). Wie finde ich dann Daten per key, ohne die ganze Datenbank zu durchlaufen? Brauche ich dann noch einen weiteren kompletten Index?
5) Macht es Sinn mehrere Chunks im Speicher zu halten? So eine Art Last-Used-Liste, um zu verhindern, dass immer wieder Chunks gespeichert/geladen werden müssen, die gerader erst gebraucht wurden.
6) Wie erstelle ich einen Iterator für die Collection? Wie verhindere ich, dass dabei zu inkonsistenzen bei Chunks kommt?

So, dass wären die Hauptfragen...
Ich habe schon erste Interfaces deklariert und einige Methoden, aber das wird recht groß, daher verzichte ich hier erst einmal auf das posten.

Hoffe Ihr könnt mir ein wenig helfen...

Gruß
Ralf

 

[XHelp]

Ich denke nicht, dass dein Vorhaben sinnvoll ist. Aus welchem Grund willst du auf Datenbanken verzichten? Ich denke nicht, dass du dir DBMS aus dem Ärmel schütteln kannst.

Bei großen Datenmengen wirst du dich extrem ausbremsen. Liste musst du ja durchlaufen um einen Eintrag zu finden. Und zwar auch die ausgelagerten Teile.
Und deine Fragen lassen sich nicht alle beantworten, z.B.:

Wie gehe ich denn mit evtl. doppelten Einträgen vor?

Das kommt doch drauf an was du machst.

Nehme ich aber key und id, dann ist die Frage wie ich die ID vergebe: ID=key? und was mache ich bei belegter ID?

Ähnliche Geschichte... und was ist bei die "key" und "id"?

Sollte ich doppelte Schlüssel erlauben?

Auch hier musst du es wissen was du damit anstellen willst.

 

[Landei]

Eine eigene Implementierung halte ich für vergeudete Arbeit. Warum das Rad nochmal neu erfinden?

Wenn dir die relationalen Datenbanken nicht gefallen, solltest du mal einen Blick auf NoSQL-Datenbanken werfen: NOSQL DATABASES

 

[ralfz]

Hallo xhelp,

also wenn ich eine DB wie MySQL nehme, dann hätte ich das Problem, dass ich zu Anfang die Columns festlegen muss.
Bei meinen Daten kann es aber sein, dass eine Zeile nur wenige Daten enthält, die nächste aber sehr viele und dabei auch noch die bestehende Breite erweitert. Desweiteren ist es die Vorgabe des Projektes auf eine relationale DB zu verzichten.

Es sollen große Datenmengen gespeichert werden, daher brauche ich Files. Gewünscht wird eine Realisierung mittels Serialisierung. Ich habe das Problem mit dem Aufwand und der Performance beim Schreiben/Lesen ganzer Chunks auch angesprochen und dabei auf die Möglichkeit einer OODB (hier db4o) hingewiesen. Jetzt soll ich quasi beides implementieren und vergleichen, z.B. mit verschiedenen Chunk-Größen.

class Container<DataRow> implements Collection{
//... einige essentielle Methoden

  Chunk curChunk;
}

class Chunk{
String id;
List<DataRow> rows;

}

class DataRow{
int id; // oder long ; interne ID = sowas wie ZeilenNr
String key; // vom Benutzer vergebene Kennung

List data;
}

So in etwa

Gruß
Ralf

 

[ralfz]

@Landei:

Ja, dass es auch anders geht habe ich auch gesehen und bin ebenfalls auf einige NOSQL DBs gestossen und habe mir dabei u.A. db40, versant, couch usw. mal kurz angeschaut. Gerade db4o hat mir sehr gut gefallen.

Beim reinen Schreiben von 10000 Datensätzen (Rows) kommt aber an einfache Serialisierung in ein File nichts von der Geschwindigkeit her heran. Daher die Idee File-Chunks zu nutzen. Natürlich ist klar, dass das Suchen nach einzelnen nicht zusammenhängenden Daten dagegen eine Sau-Performance hat. Das Iterieren wiederum dürfte recht fix sein...

Daher jetzt die Idee einen Index per B+ Baum zu haben und dann entweder auf einen Chunk zu verweisen, der in der db4o liegt oder als File vorliegt.

Gruß
Ralf

 

[SlaterB]

also wenn ich eine DB wie MySQL nehme, dann hätte ich das Problem, dass ich zu Anfang die Columns festlegen muss.
Bei meinen Daten kann es aber sein, dass eine Zeile nur wenige Daten enthält, die nächste aber sehr viele und dabei auch noch die bestehende Breite erweitert. Desweiteren ist es die Vorgabe des Projektes auf eine relationale DB zu verzichten.

ich weiß nicht ob es anderen Vorgaben widerspricht, aber du könntest eine Tabelle mit nur eine Volltext-Spalte anlegen,
das entspricht dann einer Zeile deiner alternativen Text-Datei,

ab Zeilenebene kannst du wieder selber basteln, nur gesamt hättest du dann weniger Probleme,
um die riesige Menge an Zeilen hin zu GBs würde sich die DB kümmern, Indexzugriff auf eine Zeile oder noch besser Laden eines Invervalls von 1000 Zeilen ginge perfekt,

Volltextsuche wird auch einigermaßen unterstützt, jedenfalls schneller als was man selber mit sequentiellen Durchlauf einer Datei hinbekommen könnte,
Map/ Tree ist was anderes, dagegen müssten dann bei DB-Speicherung wohl höhere Tools wie Lucene-Framework arbeiten,
wobei deine internen Maps/ Trees auch praktisch genauso gut mit DB wie mit Datei zusammenarbeiten

edit:
Speichern von neuen Zeilen ist durchaus ein Punkt eher für Datei, richtig