Dokumente auf mehrere Server aufteilen mit Consistent Hashing

Ich verwende sehr gerne die Suchmaschine Meilisearch. Sie ist sehr einfach einzurichten und zu bedienen, skaliert aber leider nur mit dem Server. Laut Roadmap arbeitet Meilisearch zwar an einer verteilten Lösung, aber bis dahin wollte ich ausprobieren, ob es per Proxy geht. Ich weiß noch nicht, ob ich den ganzen Prozess als Artikel hier festhalten werde.

Sharding link

Dieser Begriff wird oft in riesigen Artikeln erklärt. Eigentlich bedeutet Sharding nur das Aufteilen von Tabellen in mehrere Shards. Dies geschieht meistens nach eindeutigen Kriterien. Der einfachste Weg ist über die ID. Dann liegen 0-10k auf Server A, 10k-20k auf Server B usw. Aber auch komplexere Lösungen sind möglich. Z.B. Heavy User auf einem Server oder User aus einem bestimmten Land auf einem Server.

Consistent Hashing

Aufteilung mit einem eindeutigen Hash link

Um Server und Dokumente zuordnen zu können, benötige ich einen Hash. Damit beim Speichern und beim späteren Abrufen des Dokuments der gleiche Server ausgewählt wird, muss die Hashmethode immer das gleiche Ergebnis liefern.

In Go geht dies mit den FNV-1 und FNV-1a Hash Funktionen von Glenn Fowler, Landon Curt Noll und Phong Vo.

import "hash/fnv"

func hash(key string) uint32 {
    // hash string to int
	h := fnv.New32a()
	h.Write([]byte(key))
	return h.Sum32()
}

Der eindeutige Hash ist ein uint32. Die leichteste Methode ist, die Anzahl der Server zu nehmen und den Hash mit dem Modulo zu berechnen.

serverAddrs := []string{"http://127.0.0.1:7700", "http://127.0.0.1:7701", "http://127.0.0.1:7702"}

hashKey := hash(documentID)
serverIndex := hashKey % len(serverAddrs)
serverAddr := serverAddrs[serverIndex]

Wenn sich die Server Liste allerdings ändert, verschieben sich die Positionen und die Dokumente werden nicht mehr gefunden.

Consistent Hashing link

Die Idee des Consistent Hashing besteht darin, die Server mit ihrem Hash auf einem Ring (0 bis 2^32-1) anzuordnen. Alle Dokumente werden ebenfalls mit einem Hash auf dem Ring angeordnet. Der nächste Server im Uhrzeigersinn wird ausgewählt. Fällt ein Server aus, werden die Dokumente auf den nächsten Server im Uhrzeigersinn verschoben.

Consistent Hashing

Auf jedem Proxy kann die Reihenfolge der Server auf die gleiche Weise berechnet werden. Um den zuständigen Server zu ermitteln, muss der DokumentenHash nicht als State im Ring gespeichert werden. Es genügt, wenn der Proxy den Hash des Dokuments berechnet und den nächsten Server im Uhrzeigersinn auswählt.

var sortedServerHashes = []uint32{}
var serverRing = map[uint32]string{}

func addServer(serverName string) {
    serverHash := hash(serverName)
    sortedServerHashes = append(sortedServerHashes, serverHash)
    serverRing[serverHash] = append(serverRing, serverName)

    sort.Slice(sortedServerHashes, func(i, j int) bool {
        return sortedServerHashes[i] < sortedServerHashes[j]
    })
}

Wenn nun eine Anfrage für ein Dokument eintrifft, wird der Hash berechnet und der nächste Server im Uhrzeigersinn ausgewählt. Dazu kann die binäre Suche verwendet werden. Damit diese Suche effizient arbeiten kann, muss die Liste der Server-Hashes sortiert sein. Anschließend wird der Servername aus dem Ring ausgelesen.

func getServerByDocument(documentID string) string {
    hashKey := hash(documentID)

    // index of the first element that is greater than hashKey
    i := sort.Search(len(sortedServerHashes), func(i int) bool {
        return sortedServerHashes[i] > hashKey
    })

    // if i is greater than the length of the slice, use the first element
    if i >= len(c.sortedServerHashes) {
        i = 0
    }

    return serverRing[sortedServerHashes[i]]
}

Lastverteilung mit virtuellen Server link

Der Hash hat den Nachteil, dass er nicht gleichmäßig verteilt ist. Es kann passieren, dass alle Hashwerte für Dokumente auf Server 1 landen und die anderen Server leer ausgehen.

Um dieses Problem zu lösen werden gerne virtuelle Server verwendet. Die sortedServerHashes werden zu sortedVirtualHashes und jeder Server erzeugt eine bestimmte Anzahl von virtuellen Hashes. Um aufzuschlüsseln, welcher virtuelle Server zu welchem Server gehört, wird eine weitere Map verwendet. Die Idee dahinter ist, dass die virtuellen Server weiter verteilt sind und somit die Last besser verteilt wird.

var sortedVirtualHashes = []uint32{}
var virtualServerRing = map[uint32]uint32{}
var serverRing = map[uint32]string{}

func addServer(name string) {
    serverHash := hash(name)
    serverRing[serverHash] = name

    // add virtual servers
    for i := 0; i < 10; i++ {
        virtualServerHash := hash(fmt.Sprintf("%s-%d", name, i))
        sortedVirtualHashes = append(sortedVirtualHashes, virtualServerHash)
        // map virtual server hash to server hash
        virtualServerRing[virtualServerHash] = serverHash
    }

    sort.Slice(sortedVirtualHashes, func(i, j int) bool {
        return sortedVirtualHashes[i] < sortedVirtualHashes[j]
    })
}

func getServerByDocument(documentID string) string {
    hashKey := hash(documentID)

    // index of the first element that is greater than hashKey
    i := sort.Search(len(sortedVirtualHashes), func(i int) bool {
        return sortedVirtualHashes[i] > hashKey
    })

    // if i is greater than the length of the slice, use the first element
    if i >= len(sortedVirtualHashes) {
        i = 0
    }

    // get the physical server hash
    serverHash := virtualServerRing[sortedVirtualHashes[i]]

    return serverRing[serverHash]
}