Chemnitzer Linuxtage

Es gibt diese Veranstaltung nun schon seit 16 Jahren und ich war noch nie da…
Aber es muss gut sein:

Dieser Artikel basiert auf einem Vortrag, den ich bei der Ruby on Rails User Group Schweiz in Zürich gehalten habe.

Naiver Zugang zu Transaktionen

Alle reden von Transaktionen, aber wer kennt sich wirklich gut damit aus?
Ist es vielleicht wie beim Multithreading, wo man sehr viele Leute findet, die behaupten, sich gut auszukennen, aber sehr wenige Multithreading-Programme, die wirklich unter Last auch korrekt laufen?

Immerhin haben wir so eine ganz brauchbare Vorstellung:

Wir beginnen implizit oder explizit eine Transaktion
Wir führen eine oder mehrere Operationen durch (z.B. SQL-Befehle)
Wir beschließen am Ende entweder ein „roll-back“ oder „commit“
Roll-back stellt den Zustand von vor der Transaktion wieder her
Commit akzeptiert die Änderungen definitiv

Das ist doch überschaubar. Warum brauchen wir da noch komplizierten Kram?

Wenn wir uns in einer einfachen Welt bewegen, wo nur ein DB-User mit einer Session auf der Datenbank ist.

Die komplizierte Welt

In einer komplizierten Welt finden leider parallele Aktivitäten statt.
Mehrere Threads, Prozesse oder auch externe Datenbank-Clients greifen auf die Datenbank zu.

Was machst das so kompliziert?
Wenn Dinge parallel werden, dann ist jeder Entwickler gut darin, das im Griff zu haben, aber komischerweise funktioniert es dann meistens gar nicht oder zumindest nur auf dem Laptop des Entwicklers, nicht aber langfristig auf dem Server unter Last.
Aber die Leute, die Datenbankprodukte entwickeln, sind wirklich gut. Datenbanken laufen mit vielen parallelen Zugriffen unter Last auf Millionen von Rechner und funktionieren dabei noch recht zuverlässig.
Nun haben wir aber ein paar zusätzliche Fragen:

Was passiert mit unvollständigen Transaktionen vor dem Commit?
Was passiert mit erfolgreich abgeschlossenen Transaktionen während eines langen SELECTs oder einer langen lesenden Transaktion?
Dasselbe betrifft auch lange Transaktionen, die Daten verändern, aber dabei auch lesend zugreifen.

Eine Naive Anforderung wäre, dass andere Clients die Transaktion entweder ganz oder gar nicht sehen. Reicht das?
Man stelle sich ein Problem vor, das in einer langweiligen Informatik I-Vorlesung in meinem Studium real war:

Die Vorlesung geht 90 min ohne Pause.
Der „Hörsal“ ist eine Maschinenhalle, die man provisorisch mit Stühlen ausgestattet hat.
Etwa 600 Leute sind anwesend.
Es gehen dauernd Leute raus.
Am Schluss der Vorlesung ist der Hörsal immer noch ziemlich voll.
Wie viele Leute sind zu einer bestimmten Zeit in dem Hörsal?
Eine präzise und korrekte Zahl existiert immer, denn so brutale Sachen wie halbe Studenten waren damals nicht üblich.
Aber das Zählen ist schwierig, weil während dem Zählen dauernd Leute den Raum verlassen.
Merke: Das Verlassen des Hörsals ist eine Transaktion. Nach dem Commit ist die betreffende Person draußen, vorher drin.

Da kommt nun das berühmte Snapshot too old ins Spiel, das einige von uns, die noch mit Oracle arbeiten, recht gut kennen. Oracle hat das Problem, die Hörer im Hörsaal zu zählen, nämlich gelöst. Und ähnliche Probleme auch. Das SELECT bei Oracle bekommt für seine Verarbeitungszeit einen konsistenten Datenstand, der auf dem Zustand beim Start der Abfrage basiert.
Transaktionen, die währenddessen erfolgreich mit einem Commit abgeschlossen werden, werden nicht berücksichtigt. Das wird „Snapshot“ genannt. Sehr lange laufende SELECTs, die auf Daten zugreifen, die sich häufig ändern, scheitern manchmal mit „Snapshot too old“.

Präzisierung

Diese Konzepte werden jetzt etwas präzisiert, aber die Details nachzulesen sprengt sicher den Rahmen eines Blog-Artikels.
Es geht um:

Anomalien (Read phenomena)
Transaction-Isolation-Levels
ACID

Anomalien bezeichnen ein unerwartetes oder unwillkommenes Verhalten beim Lesen.

„Dirty Read“ bedeutet, dass auf Daten zugegriffen werden kann, die in einer anderen Transaktion geändert werden, bevor sie committed worden sind. Das widerspricht jeder intuitiven Vorstellung von Transaktionen. Eine interessante Frage ist aber, ob die Transaktion, die die Daten verändert, bei ihren Zugriffen jeweils den Stand nach den eigenen Veränderungen sehen kann oder ob dies erst nach dem eigenen Commit möglich ist. Bei Oracle galt immer der erste Fall, außer es hat sich kürzlich geändert, was ich aber stark bezweifle.

„Non-repeatable read“ steht für Leseoperationen auf denselben Daten während einer Transaktion, die aufgrund in anderen Transaktionen vorgenommener Änderungen verschiedene Ergebnisse liefern. Das ist genau das Problem mit dem großen Höraal. Oracle vermeidet das zum Beispiel standardmäßig.

„Phantom reads“ stehen für Leseoperationen, bei denen zwar Daten sich selbst nicht ändern können, aber durch DELETE und INSERT Datensätze wegfallen oder hinzukommen können.

Isolationslevel bezeichnen eine Einstellung einer Datenbank und die Anforderungen dazu.

„Read Uncommited“ erlaubt „dirty read“. Mir ist kein Fall bekannt, in dem das tatsächlich so praktiziert wird. Diese Einstellung ist für parallel mehrfach verwendete Datenbanken kaum brauchbar. Man kann das konfigurieren und der Standard erlaubt Datenbanken „besser“ als das zu sein.

„Read Committed“ steht dafür, dass man nur Daten von vollständig abgeschlossenen Transaktionen sehen kann. Das bedeutet also, das „dirty read“ ausgeschlossen ist, aber „non-repeatable read“ möglich ist. Das ist die Grundeinstellung für viele Datenbanken, z.B. für PostgresSQL.

„Repeatable Reads“ steht für eine Einstellung, die die Daten gegenüber UPDATEs scheinbar konstant hält. Das unterbindet „non-repeatable-read“, aber nicht „phantom-read“.

Bei der Einstellung „Serializable“ werden alle Transaktionen komplett entflochten. Man bekommt das Verhalten als wären alle Transaktionen in einer Warteschlange (Queue) und es würde immer nur jeweils eine nach der anderen abgearbeitet, womit wir wieder am Anfang wären, aber das stimmt nicht ganz. Zunächst mal werden sogar phantom-reads unterbunden.

Reale Datenbanken

Reale-Datenbanken haben eine Standardeinstellung („default“) für die Transaktionsisolation, aber sie dürfen immer besser als der eingestellte Wert sein, ohne den Standard zu verletzen. Das gibt also die Möglichkeit, Mischformen zu implementieren. Oracle hat mit „read-only“ sogar einen zusätzlichen Wert.

Nun gibt es verschiedene Wege, so etwas zu implementieren, grob gesagt sind es Locking oder Multiversion. Beim Locking werden Datensätze, Bereich, Spalten, Tabellen oder ganze Schemata gelockt, also exklusiv von einer Transaktion in Anspruch genommen. Bei Multiversion werden verschiedene Kopien der Daten erstellt und jeweils mit diesen gearbeitet. Es bleibt eine Herausforderung, die Daten am Schluss zusammenzufügen.

Verschiedene Datenbankprodukte nutzen den Interpretationsspielraum des Standards recht gut aus. Z.B. ist Oracle natürlich der Standard und man muss nur so tun, als halte man sich an den SQL-Standard.

Ich empfehle am Anfang eines Projekts eine weise Entscheidung über die Wahl der Datenbank zu treffen. Gerade hier bei den Transaktions-Isolations-Levels zeigt sich einmal mehr, dass die verschiedenen Datenbanken nicht so gleich sind und deshalb der Astausch gegen ein anderes Produkt problematisch und teuer sein kann.

ACID

ACID ist das englische Wort für Säure. In der Chemie nennt man Substanzen mit einen pH-Wert < 7 Säuren.
Hier ist aber „ACID“ ein Acronym:

Atomicity
Consistency
Isolation
Durability

Ein paar Links

Transaction Isolation Levels

Deutsch

This blog post is based on a talk that I have given in the Ruby on Rails User Group.

Who knows Transactions?

Who knows really well what transactions are?

What is a Transaction?

Just common sense what transactions mean:

We open an transaction (implicitely or explicitely)
We perform a certain number of operations (for example SQL-statements)
We decide in the end to either „roll-back“ or „commit“
Roll-back restores the state before the transaction
Commit accepts the changes for good

That’s it?

So, that’s it, we are done…
Just scrap these stupid confusing advanced stuff, do it simple…

Simple world

In the simple world, only one DB-user at a time exists
Then we are really almost done..

Complicated World

In a complicated world we have parallel activities taking place:
Multiple threads, processes or external database clients simultanously using the database

Complications of Complication

What happens now?
When things get parallel, everybody is good in doing that, but it usually does not work.
So DB-developers are really good, because databases do actually sometimes work quite well, even under load…
What happens with incomplete transactions?
What happens with complete transactions during one complicated read query?

Naïve Requirement

Other clients should see an transaction either completely or not at all.
Is that enough?
Think of an auditorium for a boring lecture: 90 min, people continuously leaving the room (so boring), but at the end it is still quite full.
How many people are in the room?
Counting is hard, because more people leave during the count.

Snapshot too old

Oracle has solved that problem of counting the students and similar ones…
The SELECT-statement gets for its duration a consistent data content, based on what was in the DB when the statement started.
Transactions that have been committed successfully after starting the SELECT are not taken into account
This is called snapshot. Long SELECTs that work on data that is actively changed sometimes fail with „Snapshot too old“

Now the hardcore stuff

Read phenomena
Transaction Isolation Levels
ACID

Read Phenomena: Dirty Read

„Dirty read“ refers to uncommitted data being available for reading by other transactions. Sounds cool, right? Intuitive?
Interesting question: can you read your own uncommitted data within the running transaction?

Read Phenomena: Non-repeatable Read

„Non-repeatable read“ refers to a reading operations on the same piece of data that happen during the same transaction (or SELECT statement in the Oracle world) and give different results.
With Oracle this should not happen, we get snapshot too old instead.

Read Phenomena: Phantom reads

Data records are the same
But the set of records may change

Isolation Level: Read Uncommited

Allows „dirty Read“
I do not know of any case where this is done
You can configure it and may get „better“ than that

Isolation Level: Read Committed

Read data only from completed transaction
Non-repeatable read is possible
Default for many databases, like PostgreSQL

Isolation Level: Repeatable Reads

During one transaction data does not change
Phantom reads are still possible
Default for many databases, for example Oracle

Isolation Level: Serializable

Pretend all transactions are queued and only one at a time is happening
No phantom reads possible

Real databases

They have some default
But may always be „better“ than that
So mixtures are possible
For example Oracle has „read-only“ as isolation level…

Locking vs. Multiversion

Two mechanisms:
Locking of parts of the data
Multiversion: multiple copies (maybe copy on write?) around, for each transaction… Have fun when merging. 😉

Different DB products

Different DB products use the freedom to interpret the standard quite liberally
Oracle is the standard, they only pretend to care about SQL-standard…
Make a wise decision which DB to support with your software in the beginning
Remember: some commercial DB vendors might not have any customers, they just have hostages

ACID

ACIDs in chemistry are substances with a pH-value < 7.
Here acronym for

Atomicity
Consistency
Isolation
Durability

Some Links

Früher ging alles schneller

Früher ging alles schneller, aber dann kamen die Computer und haben alles kompliziert gemacht.
Oder es wurden einfache Computer durch komplizierte ersetzt.

Nur zwei Beispiele:
Früher hatten die Leute beim Fahrkartenschalter der Bahn ein mechanisches Gerät, mit dem sie blitzschnell die gewünschte Fahrkarte generieren konnten. Die Fahrkarte war nur so groß wie zwei mittelgroße Münzen nebeneinander, passte also noch in das Gepäck. Und die Schlangen im Bahnhof waren noch kurz, weil alles blitzschnell ging.
Dann kamen Computer und die richtigen Schlangen. Die Computer hatten solche grünen Terminals und Masken, wo man mit ein paar Tasten die Fahrkarte bekam. Für den geübten Eisenbahner immer noch schnell. In der Bank hatten sie auch solche Terminals und man war auch dort schnell.
Dann kam aber Coolness ins Spiel. Die Arbeitsplätze bei Banken und Bahnschaltern bekamen grafische Oberflächen. Plötzlich waren die Schlangen lang und man brauchte viel Zeit.

Was sollte der Quatsch? Es ist wie mit Malerei und Fotografie. Der Maler, der heute fotografisch perfekt malen kann, ist nicht mehr so gefragt, das kann man mit digitalen oder analogen Kameras auch als Laie schaffen. Aber der Maler, der irgendwas Schönes malt, was man nicht so leicht fotografieren kann, ist noch interessant.
Fahrkarten und Geldabhebungen und Überweisungen und Überprüfung des Kontostands kann man heute an Automaten oder im Internet erledigen. Oder mit dem Mobiltelefon.
Der Schalter bekommt eine andere Funktion, denn dort kann man die Spezialitäten bekommen, die weder die grün-schwarze Terminal-Maske noch die coolste Mobile-App bieten können. Auslandsfahrkarten waren noch in den 80er-Jahren sehr schwierig zu kriegen. Man musste zum Sonderschalter, das Geld vorauszahlen und dann wurde die Reservierung per Telex oder Fax an die Partnerbahn geschickt und wenn man Pech hatte, klappte es dann doch nicht. Heute kauft man die einfach.

Login Mechanisms

By Karl Brodowsky IT Sky Consulting GmbH…

Deutsch

E-Banking examples

„Calculator“
RSA-Number-Generator
SMS
Sheet with 100 Codes
Android-App
USB-Device
SmartCard
Not so common for banks: plain old username+password
Login with google, twitter, facebook

Calculator

Enter PIN Code
Enter Code from login page
Read Result from calculator
Enter Result in Login Page

Security Questions:

Depends on how the calculator works
Due to calculator PIN/Password some security agains theft/loss of device

Practical Questions:

Always forgotten calculator
Expensive hardware required

Summary:

This method is potentially quite good, if it is done well with good algorithms and good data.

Number Generator

On login page enter 6-digit code from RSA device in addition to username+password

Security issues

Looks good because it comes from RSA
Does the timing always work well enough in sync (apparently yes)?
Device can be stolen, no additional protection
No Challenge-Response, not as good as the calculator

Practical issues:

Device is small enough to be in the pocket all the time
Device is quite expensive

SMS

Enter username and password
Receive code by SMS
Enter Code

Security issues

How secure is the mobile network?
How secure is the phone? Not-so-smart phones are better. Ideally use the old Nokia phone for this with a prepaid SIM-card
For m-banking two phones are needed or the security is much lower

Practical issues

Phone is in the pocket
But if an additional phone is needed just for this not very practical any more
Sometimes SMS get lost
some people play with many SIM cards (not a common problem)
Battery of phone can be empty (only a problem for older generation)

Summary

This seems to be a solid mechanism, but is slightly inferior to the calculator.

Sheet with 100 codes

Login with username and password
Page requests code with a given number from a given sheet.
Each number is used only once
New sheet supplied when 80% used up

Security issues

Depends on quality of numbers
Paper can be lost or stolen
Printing and handling of numbers leaves a lot of vulnerability which is hard to control.

Practical issues

Paper needs to be managed by bank and customer
Needs to be in the luggage or as image on the phone
Needs to be stored carefully

Summary

Mechanism seems to be in the middle field. Apart from being uncool the mechanism is not so bad, but it is inferior to the calculator.

Android App

Can off course technically work for your favorite smart phone, even if it is not Android… 😉

Login with username and password
A colored code is displayed:

Run Android App which takes a photo of the code and provides a 6 digit code plus some information.
Enter that for login
Remark: the App needs to be personalized, so it is only working for the own e-banking, not for someone elses.

Security issues

No password within App
Depends on keeping phone safe
Positive is that it is so easy that it can be used a lot, even for verifiying single bookings to an unknown receipient
The code can transport information that can be displayed in the

Practical issues

Requires Smart phone that supports the App
Phone is always in the pocket

USB-Device

An USB-device is plugged into the PC. It can be „smart“ and communicate directly with the server. Can also provide secure browser or even boot PC into a specially safety-hardened Linux distribution.

I have only theoretical knowledge about this, not used it.

Security issues

Has a lot of potential
A „bad PC“ can be a problem, but there are ways to implement this that are quite secure, as long as encrypted data traffic is considered secure at all. If not, we should forget the internet for anything that requires any non-trivial level of security.

Practical issues

requires special USB-stick
USB is disabled or „castrated“ on many PCs, so it might be hard to let the PC accept the device
Are there „device driver issues“?

Smart Card

This is just like the USB device, but with a chip card instead of an USB device.

Username + Password

For ebanking not enough (some banks don’t care)
For „simple“ apps it is a pain to keep usernames and passwords safe on server
Still „easy default“
How about user management?

Security issues

This has the lowest security of all mechanisms presented here.
user and password database is always a risk

Login with Google

Use google+, facebook, twitter etc. for login
Assume Google here…
Login into google (you normally are anyway…)
Click login with google
First time google asks if it is ok to provide the identity information to web page xyz
In Google settings this can be removed…

Security issues:

Do we want to have NSA-connected companies involved in our login process?
User management is something that the big guys claim to do well
OAuth2 is our friend for this, it is not so hard to do

Just remember this

Always use https when serious about security
http means transmitting password unencrypted and making some of our „friends“ who could intercept traffic very happy
Especially if it deals with money.
Serious https helps at least a little bit
Maybe, who knows what the NSA knows. 🙁

As a task for me I have to get this page on https…

Login-Verfahren

Karl Brodowsky IT Sky Consulting GmbH…

English

Für die Authentisierung in Webapplikationen gibt es verschieden Ansätze.
Ich beschreibe einmal einige, die mir tatsächlich begegnet sind, und mache mir ein paar Gedanken, was man davon erwarten kann.

Nun ist die Frage, ob so etwas nicht sehr einfach ist, man muss nur irgendwo Namen und Passwörter speichern und dann beim login einen Abgleich machen. Das können die ganzen coolen Frameworks heute gut, egal ob Java, Ruby, Perl, PHP, Scala, F# oder Python.

Aber es kommen einige Fragen auf:
– Sicherheit
– Vergessene Passwörter
– Benutzerfreundlichkeit

Beispiele für E-Banking und anderes

„Taschenrechner“
RSA-Zahlen-Generator
SMS
Zettel mit 100 Codes
Android-App
USB-Device
SmartCard
Einfach Username + Password
Login mit Google, Twitter oder Facebook

Taschenrechner

Auf Login-Seite Username + Password eingeben
PIN Code in TR eingeben
Code von Login-Seite in TR eingeben
Ergebnis von Taschenrechner ablesen
In Login-Seite eingeben

Security.Fragen:

Abhängig davon, wie der Taschenrechner funktioniert
Weil der Taschenrechner einen PIN-Code braucht gewisse Sicherheit gegen Verlust + Diebstahl

Praktische Fragen:

Taschenrechner nie dabei
Wer bezahlt die teure Hardware
Distribution der Hardware muss organisiert werden

Zusammenfassung:

Diese Methode is potentiell recht gut, wenn sie sauber und mit guten Algorithmen und guten Daten implementiert ist.

RSA-Zahlen-Generator

Auf der Login-Seite wird zusätzlich ein vom Gerät abgelesener 6-stelliger Code eingegeben.
Alle paar Sekunden/Minuten ändert sich der angezeigte Code

Security-Fragen

Sieht gut aus weil es von RSA kommt
Sind die Uhren immer gut genug synchron? Es scheint so.
Kein zusätzlicher Schutz, wenn das Gerät gestohlen wird
Kein Challenge-Response, nicht so gut wie der Taschenrechner

Praktische Fragen:

Gerät ist klein genug um es immer dabei zu haben
Gerät ist sehr teuer

SMS

username und password eingeben
code kommt als SMS
Code eingeben

Security-Fragen

Wie sicher ist das Mobilnetz?
Wie sicher ist das Telefon? Altes Nokia mit Prepaid-SIM ist sicher, aber modernes Smartphone riskanter
Für m-banking problematisch, wenn beides auf demselben Telefon läuft

Praktische Fragen

Telefon ist immer dabei
Aber nicht, wenn man dem Smartphone nicht traut und ein zweites braucht
SMS gehen verloren
Manche Leute haben viele SIM-Karten. Ist aber nicht so verbreitete Gewohnheit, man zahlt sehr gerne große Roaming-Rechnungen
Batterie kann leer sein. (Nur ein Problem der älteren Generation)
SMS-Roaming-Gebühren spielen für diesen Anwendungsfall keine große Rolle

Zusammenfassung

Solider Mechanismus, aber etwas schlechter als Taschenrechner.

Zettel mit 100 Codes

Login mit Username und Password
Die Seite verlangt Code von einer bestimmten Seite und einer bestimmten Nummer
Jede Nummer wird nur einmal verwendet
Neuer Zettel, wenn alter ca. 80% aufgebraucht

Security-Fragen

Hängt von der Qualität der Zahlen ab
Papier kann verloren gehen oder gestohlen werden
Drucken und Handhaben der Zahlen bietet viele Schwachstellen im ganzen Prozess

Praktische Fragen

Papier muss von Kunde und Bank verwaltet und aufbewahrt werden
Muss immer dabei sein, eventuell als Foto auf dem Telefon
Muss sorgfältig aufbewahrt werden

Zusammenfassung

Mechanismus rangiert irgendwo im Mittelfeld. Abgesehen davon, dass es nicht so cool ist, ist es nicht wirklich schlecht, aber schlechter als der Taschenrechner.

Android App

Oder mit anderen Smartphones auch machbar…

Login mit Username und Password
Ein farbiger Code wird angezeigt:

Starte Android-App die den Code fotografiert und auswertet.
Eine 6-stellige Zahl und eventuell mehr Information wird angezeigt.
6-stelligen Code auf Login-Seite eingeben
Bemerkung: Die App muss personalisiert werden und funktioniert nur für das eigene e-Banking

Security-Fragen

Kein Password innerhalb der App
Telefon muss sicher aufbewahrt werden und Password- oder PIN-Schutz haben
Positiv ist, dass es so einfach geht, dass man das Verfahren auch zur Verifizierung einzelner Buchungen mit neuem Empfänger verwenden kann.
Der Code kann Information transportieren, die man in der App anzeigen kann

Praktische Fragen

Braucht passendes Smartphone
Smartphone ist immer dabei

USB-Device

Ein USB-Gerät wird in den Rechner gesteckt. Dieses kann „smart“ sein und direkt mit dem Server kommunizieren. Man kann sogar ein speziell sicheres Linux vom USB-Stick booten für das E-Banking.

Ich habe nur theoretisches Wissen dazu, keine Erfahrungen.

Security-Fragen

Hat sehr viel Potential
Ein manipulierter PC kann viel schaden, idealerweise aber den Traffic zwischen Device und Server nicht manipulieren.

Praktische Fragen

braucht speziellen USB-stick
USB ist in manchen Großbetrieben abgeschaltet, speziell das Booten von USB
Gerätetreiber sind immer ein Problem, wenn man sie braucht

Smart Card

Wie USB-Gerät, nur mit SmartCard statt USB-Stick.

Username + Password

Für E-Banking nicht genug, aber es soll Banken geben, denen das egal ist
Für einfache Applikationen ist es heikel, Username und Passörter auf dem eigenen Server zu haben
Immer noch der Default-Ansatz, einfach
Wie geht die User-Verwaltung??

Security-Fragen

Niedrigste Security
Benutzer- und Password-Datenbank ist immer ein Risiko, siehe iCloud

Login mit Google

Benutze google+, facebook, twitter etc. für login
Hier nehmen wir Google an um weniger schreiben und lesen zu müssen…
Bei Google einloggen. Sind wir sowieso normalerweise schon
Klick auf „Login mit Google“
Beim ersten Mal fragt Google, ob sie der Applikation die Identität geben dürfen.
In den Google-Settings kann das entfernt werden.

Security-Fragen:

Wie sehr lieben wir die NSA
User management kann Google besser als wir
OAuth2 ist unser Freund, nicht so schwierig zu verwenden

Immer dran denken

Wir sollten immer https verwenden
http bedeutet, dass Passwörter im Klartext übertragen werden, „Freunde“ im Netz können sie mitlesen.
Wenn es um Geld geht, geht http gar nicht, nur https
Das hilft jedenfalls etwas.
Wer weiß, was die NSA über https weiß, was nicht veröffentlicht worden ist?

Ich möchte diese Seite bald auf https umstellen… 😉

Auf GPU rechnen

Heutige Rechner haben bekanntlich sehr leistungsfähige CPUs mit „Quadcore“ und mehr.
Aber auch die Grafikkarten sind ziemlich toll geworden und haben zum Teil auch so große eigene Lüfter wie die CPU.
Sie haben eine Menge eigenes Memory und sie können recht komplizierte Operationen selbsttätig rechnen, natürlich nur für die grafische Darstellung.

Nun stellt sich die Frage, ob man das auch sonst zum Rechnen benutzen kann. Man hört Geschichten, dass die Grafikkarte um Größenordnungen leistungsfähiger als die CPU sei. Warum schaffen das die Grafikkartenhersteller so leicht nebenbei, besser als die CPU in deren Kernaufgabe zu sein und außerdem noch Grafik darzustellen?

Grafikkarten bieten die Möglichkeit, massiv parallel zu rechnen, aber nach dem Prinzip SIMD. Das heißt, dass ein oder sehr wenige Befehlsströme verarbeitet werden und eine große Zahl von Recheneinheiten jeweils den identischen Code mit verschiedenen Daten ausführt. Für Vektoroperationen ist das optimal. Und es erklärt auch die brachiale Leistung der Grafikchips, weil man den aufwändigen Teil, Maschinencode zu interpretieren, nur einmal (oder wenige Male) baut und nur die eigentliche Recheneinheit mehrfach. Man bekommt so mit derselben Siliziummenge mehr Rechenleistung, aber mit der Einschränkung, SIMD (oder fast SIMD) zu sein. Aber man hat diese Geräte in den Rechnern drin. Es gibt sogar „Grafikkarten“, die nur rechnen können, aber bei denen man die eigentlichen Grafikchips weggelassen hat. Und viele Rechner haben den Grafikkern mit auf dem selben Chip wie die CPU-Kerne, so dass man eine einfache Grafik zur Verfügung hat, aber man baut dann doch zusätzlich noch eine externe Grafikkarte ein, die noch besser ist. Selbst ohne die Grafikfähigkeit zu gefährden hat man also eine GPU zum Rechnen übrig.

Nun ist das Programmieren dieser Geräte nicht so einfach. Grundsätzlich muss man sich mit einem völlig neuen Programmiermodell herumschlagen. Viele Algorithmen lassen sich speziell für SIMD entwickeln, aber sie sind anders als was wir gewohnt sind und automatisch lässt sich da nur beschränkt etwas optimieren. In der Regel muss man also mit C das Programm schreiben und kann dabei auf OpenCL bauen. Das ist ein nützlicher Standard, der einiges erleichtert, aber es bleibt schwierig. Für manche Zwecke lohnt es sich aber, den Entwicklungsaufwand zu treiben.

Vor ein paar Tagen habe ich drei Vorträge über Ansätze gehört, F# zu verwenden, um die GPU zu programmieren. Man kann also unter Einhaltung gewisser Regeln F#-Programme schreiben, die sich etwa in OpenCL übersetzen lassen und dann compiliert die GPU nutzen:

FSCL: Homogeneous Programming and Execution on Heterogeneous Platforms (by Gabriele Cocco, Pisa University)
Professional GPU Development with F# and the Alea Compiler Suite (by Daniel Egloff, QuantAlea)
New Abstractions for Radically Simplified GPU Programming in F# and .NET (by Luc Bläser, HSR, based on joint work with QuantAlea)

All diese Ansätze sollten schon heute oder zumindest in zukünftigen Implementierungen auch für Mono laufen und damit für Linux zur Verfügung stehen.

Es würde wohl den Rahmen dieses Artikels sprengen, im Einzelnen darauf einzugehen, aber vielleicht kann ich noch Links bekommen, die auf weiterführendes Material zu den einzelnen Lösungsansätzen führen.

Alle zwei Wochen

Ich werde den Rhythmus dieses Blog auf alle 14 Tage umstellen.

Einheiten mitführen

Typische Programme rechnen mit Größen, also mit Zahlwerten, die mit irgendeiner Einheit kombiniert sind. Das können Temperaturen, Längen, Zeitdauern, Geldbeträge und vieles mehr sein. Weil früher jedes Byte teuer war, hat sich etabliert, dass man nur mit den Zahlwerten arbeitet und die Einheiten implizit durch die Programmlogik ins Spiel kommen. Das funktioniert in einfache Fällen, wo die Einheit wirklich klar ist. Wenn aber mehrere Einheiten im Spiel sind, ist es besser, diese auch mitzuführe, außer bei dieser massiv strapazierten inneren Schleife, die man in Wirklichkeit im ganzen Programm doch nicht findet.

Man kann das durch Typisierung erreichen, also etwa Typen wie „KelvinTemperatur“ definieren oder man kann einen Typ „Temperatur“ definieren, der den Betrag und die Einheit enthält. So können bestimmte Fehler zur Laufzeit oder sogar zur Compilezeit entdeckt werden oder sogar passende Umrechnungen verwendet werden, wenn man eine Fahrenheit und eine Kelvintemperatur addiert.

Java bekommt hier einen Minuspunkt, weil man dort nicht vernünftig die elementaren Operationen für solche Typen definieren kann.

Die meisten anderen modernen Programmiersprachen können das natürlich.

Verbindung verschiedener Verabeitungsschritte

Häufig beinhaltet eine Software verschiedene Verarbeitungsschritte, die von den Daten nacheinander durchlaufen werden.

Im einfachsten Fall kann man mit Verabeitungsschritten f, g und h man so etwas machen wie (Pseudocode):

for x in input_data { y = h(g(f(x)); store_partial_result(y); }

Das stimmt, wenn die Datenmengen jeweils übereinstimmen. Häufig ist aber in der Praxis der Fall, dass die Datengrößen nicht so übereinstimmen. Man muss also Daten zwischenspeichern, bis für den jeweiligen Verarbeitungsschritt genug Eingaben da sind. Im Grunde genommen ist ein sehr einfacher und robuster Mechanismuns seit Jahrhunderten bewährt, zumindest wenn man in Jahrhunderten von zehn Jahren Dauer rechnet.. 😉

cat input_data_file| process_f | process_g | process_h > output_data_file

Der Ansatz lässt sich in einem Programm direkt nachbauen. Man muss named oder anonymous Pipes, TCP/IP, Message-Queues oder Messaging (wie JMS, RabbitMQ, MQ-Series,…) verwenden, um die Programmteile miteinander zu verbinden. Wenn man mit Akka arbeitet, kann man für jeden Verarbeitungsschritt einen (oder mehrere parallele) Aktor verwenden und diese mit Messages verknüpfen. Die Aktoren müssen und Daten sammeln, bis sie genug haben, um sie sinnvoll zu verarbeiten. Etwas unschön ist, dass man hier plötzlich „state“ im Aktor braucht.

Mehrere Threads sind auch möglich, wenn man für die Daten jeweils den augenblicklichen „Owner“ kennt und nur diesem Zugriff darauf erlaubt. Die zu implementierende Logik passt eigentlich sehr gut dazu, da definiert sein sollte, welchem Verarbeitungsschritt die Daten gerade unterzogen werden.

Es lässt sich aber auch mit einem Thread etwas machen, etwa entlang dieser Linie:
while (true) { if (enough_for_h(g_out)) { h_in = get_block(g_out, required_size_for_h) h_out = h(h_in) store_result(h_out) } else if (enough_for_g(f_out)) { g_in = get_block(f_out, required_size_for_g) append(g_out, g(g_in)); } else if (enough_for_f(new_data)) { f_in = get_block(new_data, required_size_for_f) append(f_out, f(f_in)); } else { append(new_data, read_block(input_data)); } }

Man muss immer aufpassen, dass sich das System nicht totläuft, was bei schlechten Implementierungen leicht passieren kann, weil entweder die Eingabedaten ausgehen oder die Buffer überlaufen. Die obige Implementierung strebt an, die Buffer immer auf der minimalen Füllung zu belassen.

Oft hat man natürlich die Möglichkeit und auch die Notwendigkeit, alle Daten auf einmal ins Memory zu laden. Dann gehen viele Dinge einfacher, man denke nur an Sortierfunktionen, die ja alle Daten sehen müssen.

Für große Datenmengen ist das aber nicht möglich und da sind die richtigen Ansätze nützlich, um nur eine verträgliche Datenmenge im Speicher zu halten.

Ein recht radikaler Ansatz ist es, alle Zwischenergebnisse in Dateien oder Datenbanken zu speichern. Dann kann man die Schritte sogar nacheinander ausführen.

In jedem Fall sollte man sich über die richtige Architektur Gedanken machen, bevor man munter drauf los programmiert.

In der Regel fährt man am besten, wenn die Quelldaten den Prozess treiben, also wenn diese sequentiell gelesen werden und zwar jeweils in den Mengen, die auch verabeitet werden. Das ist das Prinzip des „Backpressure“.