Bloom- und Counting-Filter – probabilistische Datenstrukturen

Eine nützliche Datenstruktur, wenn man schnell ein Ergebnis braucht, ob etwas definitiv nicht vorhanden ist, sind Bloom-Filter. Sie sind eine probabilistische Datenstruktur, die falsch Positive aufweisen kann. Das bedeutet, dass die Antwort “X befindet sich in der Datenstruktur” nicht unbedingt richtig sein muss. Falsch Negative treten hingegen nicht auf, d.h. die Antwort “X befindet sich nicht in der Datenstruktur” ist immer richtig.

Bloom-Filter funktionieren mit einem Bitarray der Länge . Alle Stellen des Bitarrays sind zu Beginn auf 0 initialisiert. Über verschiedene Hashfunktionen werden für einen Wert, der ins Bloom-Filter eingefügt werden soll, Hashwerte berechnet. Diese geben die Stellen im Bitarray an, welche auf 1 gesetzt werden sollen.

Wird nun eine Abfrage gestellt, ob X sich im Bloom-Filter befindet, werden wieder alle Hashfunktionen auf X angewendet. Befindet sich dann an jeder der Stellen, die diese Hashfunktionen angeben, eine 0, so wurde X sicher nicht eingefügt. Befindet sich an mindestens einer Stelle eine 1, so wurde entweder X eingefügt oder die Stelle wurde doch ein anderes Element und dessen Hashwert auf 1 gesetzt.

Es lässt sich auch nicht sagen, dass ein Element sicher eingefügt wurde, wenn alle Stellen 1 sind. Schließlich könnten alle Stellen durch verschiedene andere Elemente auf 1 gesetzt worden sein. Deshalb ist die Datenstruktur bei positiven Rückmeldungen immer unsicher.

Aus einem Bloom-Filter können keine Elemente gelöscht werden. Dies könnte dazu führen, dass versehentlich Stellen auf 0 gesetzt werden, die zuvor von mehreren eingefügten Elementen auf 1 gesetzt worden waren. Da keine Zählung der Stellen vorgenommen wird, ist dies nicht zu erkennen. Das Bloom-Filter lässt sich jedoch sehr einfach zu einem Counting-Filter erweitern. Bei diesem werden Stellen beim Einfügen nicht auf 1 gesetzt, sondern um 1 inkrementiert. Beim Löschen werden diese Stellen dann um 1 dekrementiert, sodass bei mehreren Einfügeoperationen und einer Löschoperation auf derselben Stelle, die Stelle immer noch als belegt gilt. Der Speicherverbrauch steigt dadurch natürlich. Die Situation zu falsch Positiven und falsch Negativen bleibt die gleiche wie beim Bloom-Filter.

Beispiel

In folgendem Beispiel werden zunächst die Werte x und y in ein Bloom-Filter eingefügt. Diese werden durch zwei Hashfunktionen und in Stellen im Bitarray umgerechnet. Diese Stellen werden beim Einfügen jeweils auf 1 gesetzt. Anschließend wird geprüft, ob y im Bloom-Filter vorhanden ist.

Ablauf eines Bloom-Filters beim Einfügen von x und y

Ablauf eines Bloom-Filters beim Einfügen von x und y

Raspberry Pi und Attiny 84V über I2C verbinden

Will man die Funktionalität seines Raspberry Pi um einen Atmel Mikrocontroller, z.B. Atmega oder Attiny erweitern, braucht man irgendeine Kommunikationsstrategie. Ich habe mich hierbei für eine I2C-Schnittstelle entschieden, da eine eigene Implementierung doch sehr umständlich ist (man muss immer auf einen Takt o.Ä. achten und somit doch ein komplettes Protokoll implementieren).

I2C

Für I2C hingegen existieren schon diverse Implementierungen sowohl für Master- als auch für Slave-Systeme. I2C ist ein Protokoll, welches zwei Busleitungen benötigt: Adress- und Datenleitung. Über diese kommunizieren Master und Slaves miteinander. Die Slaves reagieren jedoch nur auf Befehle des Masters und agieren nicht von sich aus. Der Vorteil von I2C ist jedoch, dass man viele Slaves an dieselbe Leitung hängen kann. Man benötigt am Master trotzdem nur zwei Pins.

Manche Mikrocontroller von Atmel unterstützen bereits selbst I2C. Die Attiny-Reihe hat häufig eine sogenannte USI-Schnittstelle (Universal Serial Interface). Über diese können mit Software relativ gut verschiedene serielle Protokolle implementiert werden.

Ich habe mich bei meinem Projekt entschieden, den Raspberry Pi als Master zu betreiben und den Attiny als Slave. Hierbei soll der Attiny Benutzereingaben einlesen und später gesammelt an den Pi zurückgeben. Später sollen noch weitere Mikrocontroller für Ausgabeanzeigen hinzukommen (z.B. Display oder LEDs). Deshalb wird der Raspberry Pi als Master betrieben.

Raspberry Pi vorbereiten

Der Raspberry Pi lädt in seiner Standardeinstellung das Modul für I2C noch nicht. Unter ArchlinuxARM kann man dies laden, indem man i2c-tools installiert und die Kernelmodule i2c-dev und i2c-bcm2708 lädt. Wichtig ist außerdem (und das stand in keinem Tutorial, das ich gelesen habe), dass man die Baudrate korrekt einstellt. Bei mir war diese für den Attiny viel zu hoch, sodass dieser mit der Kommunikation nicht hinerher kam.

  • i2c-tools installieren
  • in /etc/modules-load.d/raspberrypi.conf die beiden Module i2c-bcm2708 und i2c-dev eintragen
  • Datei /etc/modprobe.d/i2c-bcm2708.conf anlegen und dort options i2c-bcm2708 baudrate=4000 eintragen (4000 ist so ziemlich der geringste mögliche Wert, den kann man sicherlich noch höher stellen)
  • Raspberry neustarten oder die Module per modprobe alle noch laden

I2C auf dem Attiny

Für den Attiny existieren auch verschiedene Implementierungen von I2C-Slave. Ich habe mich mit i2cslave für eine entschieden, bei der man mit Speicherbereichen/Registern arbeitet, die sowohl geschrieben als auch gelesen werden. Dies scheint mir eher dem Prinzip von I2C zu entsprechen, wie ich es in den i2c-tools kennengelernt habe.

Jedoch gibt es auch Implementierungen, die mit zwei getrennten In- und Out-Buffern arbeiten. Nicht alle Implementierungen sind jedoch für jeden Attiny-Typ geeignet. In der obigen sieht man z.B. in i2cslave.h Regeln für verschiedene Attiny. Hierbei wird für jeden Attiny angegeben, welcher PIN welche Funktion übernimmt. Solche Regeln muss man in anderen Implementierungen evtl. für den eigenen Attiny-Typ ergänzen.

Um die gewählte Implementierung zu verwenden, muss man dann die Header-Datei im eigenen Programm inkludieren und die c-Datei zusammen mit dem eigenen Quelltext kompilieren.

Attiny und Raspberry Pi verkabeln

Verbindung von Pi und Attiny. Die Pin-Nummern im Bild stimmen nicht mit den eigentlichen Pin-Nummern überein.

Verbindung von Pi und Attiny. Die Pin-Nummern im Bild stimmen nicht mit den eigentlichen Pin-Nummern überein.


Die Verkabelung beider Bausteine ist dann grundsätzlich einfach. Man muss die beiden SLC- und SDA-Pins verbinden und den Attiny korrekt an die Stromquelle anschließen. Hierbei empfiehlt es sich, den Attiny mit nur 3,3V Versorgungsspannung zu verbinden (sofern er es unterstützt). Somit benötigt man keine Spannungswandler, weil der Attiny dann auch 3,3V als HIGH-Pegel verwendet.

Nachdem ich die Baudrate heruntergesetzt hatte (siehe oben), habe ich gute Erfahrungen sowohl mit eigenen Pullup-Widerständen (1,5kOhm) als auch mit den internen Pullup-Widerständen des Raspberry Pi alleine gemacht. Hier kann ich also im Moment keine klare Empfehlung geben. Da an die Widerstände jedoch nach der Länge der Leitung und der Anzahl an Slaves berechnen soll, muss man hier eventuell externe Widerstände einplanen, wenn man mehrere Slaves anschließen will.

Ein-Aus-Schalter für den Raspberry Pi

Im Internet gibt es bereits einige Tutorials, wie man den Raspberry Pi sauber herunterfahren und danach auch wieder hochfahren kann. Diese verwenden jedoch alle zwei getrennte Knöpfe zum Herunterfahren und zum Hochfahren.

Dies ist grundsätzlich einfacher, da beide Vorgänge komplett unterschiedlich funktionieren, jedoch nicht sehr intuitiv. Will man das Board nur zum Entwickeln nutzen, ist diese Variante möglicherweise sinnvoll, bei einem Endprodukt jedoch nicht (z.B. mein Internetradio).

Hoch- und Runterfahren

Das Herunterfahren des Raspberry Pi muss aus dem Betriebssystem heraus durch das shutdown-Kommando erfolgen. D.h. man muss mit einem GPIO-Pin auf eingehende Signale lauschen und prüfen, ob ein Taster gedrückt wurde oder nicht. Sobald der Taster gedrückt wurde, kann man shutdown -h now aufrufen.

Um den Pi anschließend wieder hochzufahren, muss man die RESET-Pins des Raspberry Pi verwenden. Verbindet man diese, führt der Raspberry Pi ein Reset durch. Da er bereits heruntergefahren ist, entspricht dies einem Hochfahren.

Anstatt die beiden Pins zu verbinden, kann man jedoch auch nur den weiter am Rand des Boards liegenden Pin (ich vermute Pin 1) auf 0V ziehen.

Vorbereitung

Standardmäßig existieren für diese beiden Pins jedoch noch keine Steckstifte. Man muss sich selbst eine 2-Pin-Stiftleiste auf die entsprechenden Anschlüsse des P6 löten.

IMG_6080

Hierzu führt man die Stiftleiste erst durch die Löcher hindurch und lötet sie dann von unten her fest.

Schaltung

Wie oben geschrieben, sollen beide Kommandos durch nur einen Knopf möglich sein.

  • Ist der Pi hochgefahren: Herunterfahren
  • Ist der Pi heruntergefahren: Hochfahren

Hierzu wird von irgendwoher ein Signal benötigt, in welchem Zustand sich der Raspberry Pi im Moment befindet. Da ich nicht herausfinden konnte, ob der Pi von sich aus so ein Signal anbietet, habe ich einen GPIO-Ausgang eingeplant. Dieser steht auf HIGH, wenn der Raspberry Pi läuft. Beim Herunterfahren schaltet er dann auf LOW um.

Wie in den Beschreibungen zum Hoch- und Runterfahren erläutert, erfolgt das Herunterfahren durch Signal an einem GPIO-Pin. Das Hochfahren durch Signal am P6-Anschluss. Zusammengefasst gibt es also zwei Pins, die Signale empfangen sollen – einer bei laufendem Pi, einer bei ruhendem Pi.

IMG_6083

Für die Eingabe des Shutdown-Signals habe ich GPIO-Pin 9 gewählt. Die Ausgabe, ob der Pi hoch- oder runtergefahren ist, wird auf GPIO-Pin 10 gesendet.

Der Shutdown-Pin kann jedoch auch im heruntergefahrenen Zustand Signale erhalten – er kann sowieso noch nicht reagieren. Insofern ist nur wichtig, dass RESET nicht ausgeführt wird, wenn der Pi läuft.

Ob RESET ein Signal erhalten soll, kann dann durch einen Transistor gesteuert werden.

Raspberry-Pi-Ein-Aus-Schalter

Grundsätzlich liegt bei dieser Schaltung am GPIO-9 über einen Pulldown-Widerstand Ground an. Wird der Taster betätigt, liegt am GPIO-9 HIGH an.

Die beiden Transistoren kümmern sich um die korrekte Beschaltung von RESET. Solange GPIO-9 auf HIGH steht, schaltet der linke Transistor durch. Dadurch liegen im gesamten Bereich unten rechts 0V an. Das Gate des rechten Transistors steht also auch auf 0V und schaltet nicht durch.

Interessant wird es, wenn GPIO-9 auf LOW steht – d.h. der Pi heruntergefahren ist. Dann sperrt der linke Transistor. Solange der Taster nicht gedrückt ist, gelangt über zwei 10kOhm-Widerstände jedoch immer noch GND an das Gate des rechten Transistors. Erst wenn der Taster betätigt wird, überwiegt die Spannung von 3,3V und der rechte Transistor schaltet durch. RESET wird auf GND gezogen und der Pi fährt hoch.

Software

Die Ein- und Ausgaben müssen natürlich auch noch in Software gesteuert werden. Dazu habe ich ein kleines Script erstellt, welches beim Booten als Daemon gestartet wird.

Als Programmiersprache verwende ich Python. Im Grunde setze ich beim Starten des Skripts nur GPIO-10 auf HIGH, um anzuzeigen, dass der Pi nun läuft.

Dann warte ich auf Signale am GPIO-9. Wichtig ist hierbei auf die fallende Flanke zu achten, also wenn der Knopf losgelassen wird. Ansonsten fährt der Raspberry Pi beim Herunterdrücken schon runter und setzt GPIO-10 auf LOW. Der Benutzer hält den Knopf noch gedrückt, der RESET-Transistor schaltet durch (da GPIO-10 ja auf LOW steht) und der Pi führt einen Reset durch statt eines sauberen Shutdowns.

Um zusätzlich noch Reset-Fehler durch Bouncing (also mehrmaliges Springen des Signals, wenn man einen Knopf drückt oder loslässt) zu verhindern, warte ich beim Herunterfahren noch eine Sekunde ab, bevor GPIO-10 auf LOW gesetzt wird.

#!/usr/bin/python2
 
import RPIO
import subprocess
import time
 
RPIO.setup(9, RPIO.IN)
RPIO.setup(10, RPIO.OUT, initial=RPIO.HIGH)
 
def shutdown(gpio_id, val):
        time.sleep(1) # wait a while to avoid resetting due to signal bouncing
        RPIO.output(10, False)
        subprocess.call(['shutdown', '-h', 'now'])
 
RPIO.add_interrupt_callback(9, shutdown, edge='falling')
 
RPIO.wait_for_interrupts()

Dieses Skript kann man unter ArchlinuxARM mittels systemd automatisch starten. Hierzu muss man sich eine Datei unter /etc/systemd/system erstellen, z.B. /etc/systemd/system/piboot.service.

[Unit]
Description=Control and listen to boot and shutdown

[Service]
ExecStart=/path/to/python/script.py

[Install]
WantedBy=multi-user.target

Unter ExecStart muss man als absoluten Pfad eintragen, wo die obige Python-Datei liegt. Diese Datei muss ausführbar sein (also muss man ggfs. chmod +x ausführen).

Dann kann man den Dienst mittels systemctl start piboot starten und mittels systemctl enable piboot für jeden Start aktivieren.

Anmerkung

Gestern traten bei mir selten Signalsprünge auf, die zum Herunterfahren führten, obwohl ich den Knopf nicht betätigt hatten. Diese lassen sich vermutlich durch einene Kondensator im Schaltkreis oder aber durch eine Zeitprüfung in der Software verhindern.