05.032014

Flexihash - Ein kleiner Helfer für konsistentes Hashing

Ich möchte heute die PHP Blibliothek "Flexihash" vorstellen. Aber zuerst einmal zur Problemstellung: Der ein oder andere Entwickler stand sicherlich auch schon einmal vor der Anforderung, dass seine Anwendung ein Caching benötigt. Bei kleineren Anwendungen kann man hier vielleicht mit einem einzigen Memcache-Server arbeiten, da es unter Umständen vielleicht auch nicht um bedingt auf die Ausfallsicherheit des Caches ankommt.Steigen jetzt aber die Anforderungen an die Anwendung und es wird gefordert, dass der Cache möglichst nicht leer sein darf, wenn mal ein Memcache-Server ausfällt, dann muss man sich eine Möglichkeit überlegen, wie dies realisiert werden kann.

Der ein oder andere wird vielleicht denken, "ich kann ja die Keys in Abhängigkeit der Server zuweisen, indem ich die Anzahl der verfügbaren Server modulo zu einem Hash des Cacheeintrags setze". Dies mag zwar im ersten Augenblick funktionieren, kommen jetzt aber weitere Memcache-Server hinzu, so wird für jeden Cacheeintrag ein neuer Hash berechnet und der Cache ist somit quasi leer.

Die Lösung für dieses Problem nennt sich "Consistent Hashing".

Um es etwas anschaulicher zu beschreiben, nehmen wir uns mal einen Kreis. Auf diesem platzieren wir in gleichmäßigen Abständen unsere Memcache-Server. Jeder der Memcache-Server bekommt dabei eine bestimmte Hash-Range zugewiesen. Nun haben wir einen Wert, der in den Cache eingetragen werden soll. Für diesen neuen Cacheeintrag wird zuerst ein Hash berechnet. Anschließend wird überprüft, welche Hash-Range, sprich welcher Memcache-Server, am Besten zu dem Cacheeintrag passt und dort wird er dann gespeichert.

Jetzt kommt vielleicht die Frage auf, "muss ich mir jetzt einen Hashing-Algorithmus überlegen?".

Nein, dies ist nicht der Fall, da bereits andere Entwickler vor der gleichen Problemstellung standen und hierfür unter anderem die PHP Blibliothek "Flexihash" bei GitHub veröffentlicht wurde. Sie ist zwar schon einige Jahre alt, erfüllt aber vollkommen ihren Zweck.

Mal ein Beispiel, wie ein simpler CacheClient in Verbindung mit Flexihash aussehen könnte. Ich habe für meine Zwecke die Einzeldatei aus den Sourcen gebaut:

require_once('flexihash.php');

class CacheClient {
	private $hasher = null;

	/**
	 *
	 * @param array $config
	 */
	public function __constructor($config) {
		// eine Instanze des Flexihash holen
		$this->hasher = new Flexihash();
		// Setzen der verfuegbaren Cacheserver als Ziele im Flexihash
		$this->hasher->addTargets($config['servers']);
	} 

	/**
	 *
	 * @param string $key
	 * @param string $value
	 */
	public function set($key, $value) {
		$host = $this->hasher->lookup($key);
		if ($host) {
			$socket = @fsockopen($host, '11211', $errno, $errstr);
			if (is_resource($socket)) {
				$length = strlen($value);
				$command = "set {$key} 0 0 {$length}\r\n{$value}\r\n";
				@fwrite($socket, $command);
			}
		}
	}

	/**
	 *
	 * @param string $key
	 * @return NULL
	 */
	public function get($key) {
		$host = $this->hasher->lookup($key);
		if ($host) {
			$socket = @fsockopen($host, '11211', $errno, $errstr);
			if (is_resource($socket)) {
				$command = "get {$key}\r\n";
				if (@fwrite($socket, $command, strlen($command))) {
					return @fgets($socket);
				}
			}
		}
		return null;
	}
}

Dies simple Beispiel fügt im Constructor die vorhandenen Memcache-Server als Targets zur Flexihash-Instanze hinzu. Kommt jetzt beim nächsten Holen einer Instanze des CacheClients ein weiterer Memcache-Server hinzu, so wird dieser nun im Kreis der verfügbaren Server eingereiht und nur die dazu passenden Cacheinträge werden dort gesucht und geschrieben. Alle sonstigen werden weiterhin von ihren bestimmten Servern gelesen und geschrieben.

Man kann nun auch noch weiteres Feintuning durchführen, indem man sich zum Beispiel die verfügbaren Server separat nochmal merkt und sobald es Probleme mit einem Memcache-Server gibt, diesen für einen gewissen Zeitraum als unerreichbar einstuft und in der Flexihash-Instanze als Ziel entfernt. Hierzu steht die Methode ->removeTarget() zur Verfügung. Ist der Timeout abgelaufen, so kann man den Server mit der Methode ->addTarget einfach wieder zu den zur Verfügung stehenden Zielen hinzufügen.