Sehr große Tabelle, welches Backend, wie sortieren?

A

antimon

Mitglied
Hallo,

für einen CAN-Sniffer (wem das nichts sagt, ist sowas für CAN wie Ethereal für Ethernet) schreibe ich gerade eine Software, die alle Datenpakete in einer Tabelle auflistet... da die maximale Datenrate aber bis zu 1 MBit beträgt können sehr schnell sehr viele Daten zusammenkommen.

Jede Nachricht besteht aus einer ID und Nutzdaten, die ID könnte man im weitesten Sinne wie eine IP-Adresse sehen.

Die Daten sollen wenn möglich folgendermaßen dargestellt werden:
* Mehrere Pakete mit der gleichen ID werden gruppiert dargestellt, optimal wäre eine aufklappbare Ansicht wie bei einem JTree - in der Summenzeile stehen Informationen, wie viele Pakete empfangen wurden und der zeitliche Abstand zwischen dem aktuellen und dem davor, wenn man die Ansicht aufklappt sieht man alle dazugehörigen Pakete mit der Ankunftszeit und weiteren Informationen

* Alternativ dazu sollte man umgruppieren können, also statt der Gruppierung nach der ID beispielsweise nach der Anzahl der Nutzdaten-Bytes gruppieren

* Optimal wäre auch eine Sortierung nach verschiedenen Kriterien, beispielsweise Zeit, ID, Daten, wobei in diesem Fall die Gruppierung wohl abgeschaltet werden sollte


Nun ist das erste Problem: Wie werden die empfangenen Daten am besten gespeichert? Einerseits könnte ich alle Daten in einer LinkedList speichern, wie ist das dann allerdings mit der Performance beim Auslesen und Sortieren? Und wie ließe sich eine Gruppierung bewerkstelligen?
Andererseits habe ich darangedacht, eine Datenbank im RAM zu erstellen (z.B. HSQLDB) und die die Sortierung bzw. Gruppierung machen zu lassen, aber bringt das wirklich Vorteile in der Performance? Imho arbeitet die DB ja nicht mit Zeigern, deswegen würden wohl alle Datensätze zurückgegeben werden, dürfte dann wohl egal sein ob ich die Daten aus einer Datenbank oder LinkedList bekomme oder? Dann wäre wohl die Sortiermöglichkeiten der DB der einzige Vorteil, sehe ich das richtig?

Ich würde mich freuen, wenn ich ein paar Tips bekommen könnte, da ich in Sachen Performance nicht so wirklich viel Erfahrungen habe... und genau, da die Daten fortlaufend eintreffen, sollten die natürlich optimalerweise auch immer gleich eingefügt werden... ausser das geht gar nicht, also on-the-fly einsortieren, dann muss ich mir was anderes überlegen...
 
Hallo,

von der Idee so viele Daten anzuzeigen halte ich nichts. Damit kann kein Mensch mehr
etwas anfangen. DU solltest dir nochmal Gedanken darüber machen auf welcher Detailebene eine Anzeige Sinn macht.

Wenn Speicher kein Problem ist könntest du versuchen für jede Sortiermöglichkeit ein TreeSet / TreeMap zu verwenden. Das ist eine Struktur die intern einen Rot-Schwarz Baum verwendet und die Elemente schon beim einfügen richtig einsortiert.

Schau mal hier:
http://www.tutorials.de/forum/java/...ltern-einer-jtable-mit-sehr-vielen-daten.html

Mit ein wenig trickserei kann man damit auch ganz schnell Aggregationen berechnen lassen.

Ansonsten könntest du mal schauen ob du bei Javolution was passendes findest:
http://javolution.org/

Gruß Tom
 
Also alle Daten auf einmal anzeigen will ich auf keinen Fall! Sollte das so rübergekommen sein, sorry...

Eigentlich soll die Anzeige so funktionieren: Ich sehe in jeder Zeile eine Zusammenfassung für eine bestimmte ID. Wenn mehrere Nachrichten dieser Art eingetroffen sind, wird deren Anzahl angezeigt und das wars... allerdings kann es manchmal interessant sein zu wissen, wie denn genau die Pakete einer bestimmten ID aussehen - wenn ich weiss dass 5 angekommen sind, können die aber auch 5x unterschiedliche Nutzdaten haben.

Es müssen übrigens nicht immer so viele Daten sein, ich gehe einfach vom worst case aus... und wenn ich das richtig interpretiere bringt mir dann eine Datenbank auch nicht mehr, richtig?

Habe ich das Beispiel aus dem Link von dir richtig verstanden? Ich habe im Prinzip alle Daten der Tabelle in einem Array unsortiert gespeichert und zusätzlich für jede Spalte, nach der ich sortieren können möchte, einen Index in Form einer TreeMap? Und sobald ich die Sortierung anschalte, wird die vorsortierte Map ausgelesen und für jeden Eintrag aus dem globalen Daten-Array die passende Zeile ausgegeben?

Und wie kann ich dann realisieren dass ich zusätzlich noch die Summen-Zeilen bekomme? Also angenommen ich habe folgende Daten:

ID 1, Daten abc
ID 1, Daten bcd
ID 1, Daten cde
ID 2, Daten xyz
ID 2, Daten wxy

Diese sollen so ausgegeben werden:
+ ID 1, 3 Pakete empfangen
|- ID 1, Daten abc
|- ID 1, Daten bcd
|- ID 1, Daten cde

+ ID 2, 2 Pakete empfangen

In diesem Beispiel wäre das "x Pakete empfangen" die Summenzeile und bei ID1 ist der Ast ausgeklappt und die einzelnen Pakete sind sichtbar, bei ID 2 ist nur die Summenzeile sichtbar (Ast eingeklappt)

Eine JTreeTable ist ja momentan nur in einer Swing-Betaversion vorhanden und bei der von swinglabs.org haut das mit dem Sortieren angeblich noch nicht hin, wobei ich das ja eh selbst machen müsste... aber wie kann ich überhaupt erst mal obige Struktur sinnvoll abbilden, wenn vielleicht sogar die Gruppierung, also Summenzeilen abgeschaltet werden können sollen und die Tabelle "flach" dargestellt werden soll?
 
Beim Anschauen deiner Beispiele ist mir noch eine Frage gekommen...

Nehmen wir an, die Datenmenge wäre statisch, also einmal gesammelt bleibt die Anzahl der Zeilen konstant... kein Problem.

Allerdings kommen in meinem Fall immer neue Datensätze, sprich Tabellenzeilen, hinzu. Gut, die kann ich schön per TreeSet einsortieren lassen, aber meine Tabelle bekommt davon ja nichts mit - es sei denn ich ließe sie neu aufbauen, mit den neu einsortierten Daten.

Aber das ist vermutlich nicht sehr praktikabel und schliesslich kann man ja der Tabelle auch mitteilen dass nur ein paar Zeilen neu hinzugekommen sind - vorausgesetzt ich kenne die Position. Aber da die Daten ja sortiert sind müsste ich wissen, wo die neuen Daten reingehören.

Theoretisch weiss ich ja nach welcher Spalte gerade sortiert werden soll - wenn ich jetzt noch wüsste an welcher Stelle im TreeSet der neue Eintrag hinverschwunden ist, könnte ich auch das Event feuern, dass die entsprechende Zeile eingefügt wird, wenn dann noch das Index-Array entsprechend angepasst ist, sollte alles stimmen - aber wie finde ich die neue Position heraus, bzw. kann ich das überhaupt?

Die add()-Methode des TreeSet gibt mir ja lediglich zurück, ob das einzufügende Objekt schon vorhanden ist...
 
Hi,

ich weis jetzt nicht ob ichs richtig verstanden habe aber die SetTrees sagen ja nichts über den internen Sorteirzustand aus. Und dann gibt es ja immer noch keine Möglichkeit für eine Änderung der Sortierkriterien.Oder seh ich das falsch?

Wenn also ein neues Element hinzukommt muss die Sortierung neu gemacht werden. Auser man hat eine Einfügemethode welche die entsprechenden Kriterien beachtet. Um eine Sortierung von allen Daten zu vermeiden würde ich sie auf mehrere Datenstrukturen verteilen.

1.) Eine Datenstruktur für alle Einträge. Da auf dieser wenn dann nur eine Suche über alle Elemente laufen muss, kann man etwas einfaches wie eine LinkedList nehmen.

2.) Eine Map für die Gruppierung der Daten. Der Key der Map Besteht aus dem Gruppierungskriterium. Die Daten werden wieder in einer Liste Gespeichert. (z.B. ArrayList). Um eine erneute Sortierung der Schlüssel zu vermeiden kann man diese noch in einer Sorted List speichern.

Wird also nun ein neuer Eintrag hinzugefügt muss geschaut werden ob er in eine bereits existierende Gruppe gehört. Wenn ja in die entsprechende Liste in der Map ablegen.
Ist dieser Teilbaum zur Ansicht geöffnet muss eine sortierung dieser Liste nach den gegebenen Kriterien vorgenommen werden udn die entsprechende Tabelle aktualisiert werden.
Existiert die Gruppe noch nicht muss ein neuer Eintrag in der Map hinterlegt werden.
Führt man nebenbei noch die SortedList mit den Schlüsseln der Map kann die Position der Gruppe in der Tabbelle einfahc bestimmt werden.
Die Anzahl der in einer Gruppe Hinterlegten Einträge kann über mit der Map und Der ArrayList dann sehr schnell bestimmt werden. Auch das aktualisieren dieses Wertes ist sehr einfach machbar da die entsrechende Tabellenzeile über die SortedList sehr einfach gefunden werden kann.

Für eine Sortierung der Gruppen würde ich dann die Array Repräsentation der entsprechenden Liste nehmen und diese z.B. mit einem Heapsort nach den verschiedenen Kriterien sortiern.

Bei einer neuGruppierung muss leider die map für jeden Eintrag neu berechnet werden, außer man erstellt für alle Gruppierungsmöglichkeiten die entsprechenden Maps beim Einfügen eines neuen Datums. Wenne snur zwei oder drei sind ist das vieleicht sogar sinnvoll.

So Ich hoffe ich konnte mich einigermasen verständlich ausdrücken.

Gruß,
Benny

ps.: Ich bin jederzeit für Kritik bereit. Danke.
 
Hallo,

wenn man die packet geschickt logisch / natürlich verkettet kann man sie den Umweg über entsprechende Listen / Arrays etc.komplett sparen und spart damit Speicher, was bei den vermeintlich großen Datenmengen sehr sinnvoll ist. Leider wird dadruch das Handling mit dem Collections API ein wenig unhandlich...

Wenn man das Packet Capture über einen anderen Thread laufen lassen will sollte man die Datenstrukturen aus java.util.concurrent verwenden - wie etwa die ConcurrentSkipListMap

Btw.
kann sein, dass in der Netzwerkterminologie Packete die im Fluss (Flow) und in Sequenz (Sequence) kommen eine andere Semantik haben. Bei mir sind Pakete die über Flow verkettet sind in der Reihenfolge wie sie am Netzwerk Interface angekommen sind.
In Sequence heißt in meinem Beispiel, dass die Pakete irgendwie zusammen gehören- in meinem Fall stammen sie von der selben Quelle (Source).

schau mal hier: (nur mal so als Spielerei...)
Java: 
/**
 * 
 */
package de.tutorials;

import java.util.AbstractCollection;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Random;
import java.util.Set;
import java.util.TreeMap;
import java.util.TreeSet;

/**
 * @author Thomas.Darimont
 * 
 */
public class AggregationExample {

    /**
     * @param args
     */
    public static void main(String[] args) {

        //Packet next in flow means the actual (natural) order
        //Packets next in sequence means correlated packets e.g. with the same source header
        
        Map<String, Packet> sourceToFirstPacketInSequenceMap = new TreeMap<String, Packet>();
        Map<String, Packet> sourceToLastPacketInSequenceMap = new HashMap<String, Packet>();

        Packet firstPacketInFlow = null;
        Packet lastPacketInFlow = null;
        
        for (Packet currentPacketInFLow : generatePackets(100000)) {

            if (firstPacketInFlow == null) {
                firstPacketInFlow = currentPacketInFLow;
            }

            if (lastPacketInFlow != null) {
                lastPacketInFlow.setNextInFlow(currentPacketInFLow);
            }

            Packet previousLastPacketInSequence = sourceToLastPacketInSequenceMap
                    .put(currentPacketInFLow.getSource(), currentPacketInFLow);

            if (previousLastPacketInSequence != null) {
                previousLastPacketInSequence
                        .setNextInSequence(currentPacketInFLow);
            } else {
                sourceToFirstPacketInSequenceMap.put(currentPacketInFLow
                        .getSource(), currentPacketInFLow);
            }

            lastPacketInFlow = currentPacketInFLow;

        }

        // Aggregate: could be sourced out to an Aggregator Strategy

        for (String source : sourceToFirstPacketInSequenceMap.keySet()) {
            Packet firstPacketPacketInSequence = sourceToFirstPacketInSequenceMap
                    .get(source);

            long packetCount = 0L;
            long dataLengthInBytes = 0L;
            Packet currentPacketInSequence = firstPacketPacketInSequence;

            boolean drillDown = false;

            if (source.equals("100")) { // simulates a drill down
                drillDown = true;
            }

            do {
                packetCount++;
                dataLengthInBytes += currentPacketInSequence.getData().length; // should
                // be
                // equal
                // to
                // packetCount

                if (drillDown) {
                    System.out.println(currentPacketInSequence);
                }

                currentPacketInSequence = currentPacketInSequence
                        .getNextInSequence();

            } while (currentPacketInSequence != null);

            String message = String.format(
                    "Packets from source: %s count: %s size in bytes: %s",
                    source, packetCount, dataLengthInBytes);

            System.out.println(message);

        }

        System.out.println("#### Sort by ArrivalTime");

        final int size = lastPacketInFlow.getFlowNumber();
        final Packet firstPacket = firstPacketInFlow;

        Set<Packet> packetsSortedByArrivalTime = new TreeSet<Packet>(
                new ArrivalTimeComparator());
        packetsSortedByArrivalTime.addAll(new AbstractCollection<Packet>() {
            @Override
            public Iterator<Packet> iterator() {
                return new Iterator<Packet>() {

                    Packet currentPacket = firstPacket;

                    public boolean hasNext() {
                        return currentPacket.nextInFlow != null;
                    }

                    public Packet next() {
                        currentPacket = currentPacket.nextInFlow;
                        return currentPacket;
                    }

                    public void remove() {
                        throw new UnsupportedOperationException();
                    }
                };
            }

            @Override
            public int size() {
                return size;
            }
        });

        for (Packet packet : packetsSortedByArrivalTime) {
            System.out.println(packet);
        }

    }

    static class ArrivalTimeComparator implements Comparator<Packet> {
        public int compare(Packet first, Packet second) {
            long result = first.getArrivalTimeStamp()
                    - second.getArrivalTimeStamp();
            if (result == 0) {
                return 0;
            }

            if (result > 0) {
                return 1;
            }

            return -1;
        }
    }

    static class Packet {
        int flowNumber;
        String source;
        long arrivalTimeStamp;
        static final byte[] dummyData = new byte[1]; // just for
        // demonstration
        // purposes
        byte[] data;
        Packet nextInFlow;
        Packet nextInSequence;

        public Packet(int flowNumber, String source, long arrivalTimeStamp) {
            this.flowNumber = flowNumber;
            this.source = source;
            this.arrivalTimeStamp = arrivalTimeStamp;
            this.data = dummyData;
        }

        public long getArrivalTimeStamp() {
            return arrivalTimeStamp;
        }

        public void setArrivalTimeStamp(long arrivalTimeStamp) {
            this.arrivalTimeStamp = arrivalTimeStamp;
        }

        public byte[] getData() {
            return data;
        }

        public void setData(byte[] data) {
            this.data = data;
        }

        public String getSource() {
            return source;
        }

        public void setSource(String source) {
            this.source = source;
        }

        public Packet getNextInFlow() {
            return nextInFlow;
        }

        public void setNextInFlow(Packet next) {
            this.nextInFlow = next;
        }

        public Packet getNextInSequence() {
            return nextInSequence;
        }

        public void setNextInSequence(Packet nextInSequence) {
            this.nextInSequence = nextInSequence;
        }

        public int getFlowNumber() {
            return flowNumber;
        }

        @Override
        public String toString() {
            StringBuilder stringBuilder = new StringBuilder();
            stringBuilder.append("Flownumber:").append(flowNumber).append(" ");
            stringBuilder.append("Source:").append(source).append(" ");
            stringBuilder.append("ArrivalTimeStamp:").append(arrivalTimeStamp)
                    .append(" ");
            stringBuilder.append("Data size in bytes:").append(data.length)
                    .append(" ");
            stringBuilder.append("Next in flow packet flowNumber:");
            if (nextInFlow != null) {
                stringBuilder.append(nextInFlow.getFlowNumber()).append(" ");
            } else {
                stringBuilder.append("NONE").append(" ");
            }

            stringBuilder.append("Next in sequence packet flowNumber:");
            if (nextInSequence != null) {
                stringBuilder.append(nextInSequence.getFlowNumber());
            } else {
                stringBuilder.append("NONE");
            }

            return stringBuilder.toString();
        }

    }

    final static Random random = new Random();

    static Iterable<Packet> generatePackets(final int numberOfPackets) {
        return new Iterable<Packet>() {
            public Iterator<Packet> iterator() {
                return new Iterator<Packet>() {

                    int currentPacketCount;

                    public boolean hasNext() {
                        return currentPacketCount < numberOfPackets;
                    }

                    public Packet next() {
                        currentPacketCount++;
                        String source = String.valueOf(random.nextInt(1000));
                        return new Packet(currentPacketCount, source, System
                                .nanoTime());
                    }

                    public void remove() {
                        throw new UnsupportedOperationException();
                    }
                };
            }
        };

    }
}

Gruß Tom
 
Also erst mal ganz großen Dank an die hilfreichen Tips, besonders an Thomas für die Mühe mit dem Beispielcode - find ich sehr klasse.

Ich habe mir auch wieder viele Gedanken zu dem Thema gemacht und bin über ein paar Dinge gestolpert:
Erstens habe ich gar nicht dran gedacht, die Pakete miteinander direkt zu verketten, die Idee ist spitze. Allerdings würde ich dann am liebsten das normale Packet-Objekt in ein LinkedPacket-Objekt erweitern, damit die Klasse übersichtlich bleibt - und beispielsweise bei zu versendenden Paketen brauche ich keine Verkettung. Aber das sollte ja kein Problem sein, bezüglich Speicherbedarf und Overhead oder?

Allerdings: Was passiert bei der Methode mit der Verkettung wenn ich die Gruppierung einschalte und bestimmte Gruppen ausblenden möchte (also nur die Summenzeile für die Gruppe anzeigen will, nicht die einzelnen Pakete?). Müsste ich da die komplette Verkettung durchlaufen und überprüfen wann die nächste Gruppe beginnt? Oder eine zusätzliche Verkettung der Gruppen einführen?

Und wenn die Daten in einer Tabelle dargestellt werden - dort wird ja nicht die Verkettung durchlaufen, sondern über Zeilen- und Spaltenindex auf die Daten zugegriffen - da müsste ich dann im Prinzip einen eigenen Index für jede Spalte erstellen oder? Oder hab ich irgendwo was übersehen/missverstanden?

@kle-ben: Wenn ich das richtig verstanden habe, schlägst du vor, die Daten unsortiert abzuspeichern und dann die eigentliche Sortierung über ein Mapping durchzuführen, das eine Tabellenzeile einem der unsortierten Datensätze zuweist? Und die Mappings werden für alle möglichen Anzeigemöglichkeiten vorbereitet und dann nur bei Bedarf abgerufen?
Wenn ich das aber richtig verstanden habe, muss bei jedem Einfügen von Daten dieses Mapping neu aufgebaut werden... zumindest halt für die jeweilige Gruppe - habe ich das richtig verstanden?

Was halt dumm ist, ich kann nicht sagen wie die Verteilung der Daten aussieht, es könnte im dümmsten Fall vorkommen dass es nur eine Gruppe gibt, oder bei einer Gruppe besonders viele Daten anfallen - die Verteilung ist leider nicht unbedingt gleichmäßig, so wie in einem Ethernet auch bestimmte Stationen den Haupt-Traffic verursachen...

Ich denke, es gibt in diesem Fall wohl nicht die optimale Lösung, aber ihr habt mir auf jeden Fall schon sehr weitergeholfen, weil viele gute Möglichkeiten dabei waren, die mir nicht eingefallen sind. Aber für alle weiteren Tips und Hinweise bin ich natürlich weiterhin dankbar!
 
Das Mapping soll nicht für die Sortierung sondern für die Gruppierung der Daten verwendet werden. Eine Sortierung ist denke ich nach jedem Einfügen erneut nötig da die Positionierung abhängig von den Sortierkriterien ist. Um die Sortierung nicht immer zu erneuern müsste man Datenstruktur haben die beim Einfügen diese Kriterien beachtet. Alerdings ist mein Ansatz bei wenigen großen Gruppen in geöffneter Darstellung wahrscheinlich nicht wirklich sehr performant.

Benny
 
Um antworten zu können musst du eingeloggt sein.

Neue Beiträge

Zurück