Memahami Consistent Hashing

Pendahuluan

Dalam dunia sistem terdistribusi, seperti penyimpanan data skala besar, load balancing, atau cache terdistribusi, salah satu tantangan utama adalah mendistribusikan data atau beban kerja secara efisien dan skalabel di antara banyak server. Salah satu pendekatan yang popoiler untuk mengatasi masalah ini adalah consistent hashing. Teknik ini memungkinkan sistem untuk mendistribusikan data dengan cara yang meminimalkan gangguan saat server ditambahkan atau dihapus, menjaga efisiensi dan keseimbangan beban. Artikel ini akan menjelaskan secara mendalam mengapa consistent hashing diperlukan dan bagaimana cara kerjanya, dengan bahasa yang mudah dipahami namun komprehensif.

Mengapa Consistent Hashing Diperlukan?

Untuk memahami pentingnya consistent hashing, mari kita lihat masalah yang dihadapi dalam sistem terdistribusi tanpa pendekatan ini.

  1. Masalah dengan Hashing Tradisional Dalam sistem terdistribusi, data biasanya didistribusikan ke server menggunakan fungsi hash sederhana, misalnya hash(key) % N, di mana N adalah jumlah server. Fungsi ini memetakan kunci (key) data ke salah satu server. Namun, pendekatan ini memiliki kelemahan besar:

    • Ketidakstabilan saat skala berubah: Jika jumlah server berubah (misalnya, server ditambahkan atau dihapus), nilai N berubah, sehingga hampir semua kunci harus dipetakan ulang ke server yang berbeda. Ini menyebabkan remapping massal, yang sangat mahal dalam hal waktu dan sumber daya karena data harus dipindahkan antar server.

    • Gangguan pada cache: Dalam sistem cache seperti Memcached, remapping massal menyebabkan banyak cache miss, yang mengurangi efisiensi sistem.

    • Skalabilitas terbatas: Proses remapping yang intensif membuat penambahan atau pengurangan server menjadi operasi yang mahal dan mengganggu.

  2. Kebutuhan akan Skalabilitas dan Stabilitas Dalam lingkungan seperti database terdistribusi (contoh: DynamoDB, Cassandra) atau sistem cache, server sering ditambahkan atau dihapus untuk menangani perubahan beban kerja. Consistent hashing diciptakan untuk meminimalkan jumlah data yang perlu dipindahkan saat terjadi perubahan seperti ini, sehingga:

    • Memastikan distribusi data tetap merata.

    • Mengurangi gangguan saat sistem menskalakan.

    • Menjaga performa sistem tetap tinggi.

  3. Tujuan Consistent Hashing

    • Minimalkan remapping: Hanya sebagian kecil data yang dipetakan ulang saat server ditambahkan atau dihapus.

    • Distribusi merata: Data tersebar secara merata di semua server.

    • Skalabilitas: Sistem dapat dengan mudah menangani penambahan atau pengurangan server tanpa gangguan besar.

Bagaimana Consistent Hashing Bekerja?

Consistent hashing menggunakan pendekatan yang berbeda dari hashing tradisional. Berikut adalah penjelasan langkah demi langkah tentang cara kerjanya:

  1. Konsep Dasar: Cincin Hash Consistent hashing memetakan baik kunci data maupun server ke dalam ruang hash yang sama, yang direpresentasikan sebagai cincin (hash ring). Bayangkan sebuah lingkaran (atau cincin) di mana:

    • Setiap titik pada cincin mewakili nilai hash tertentu.

    • Ruang hash biasanya besar (misalnya, 0 hingga 2³²-1 untuk hash 32-bit).

    • Kunci data dan server dipetakan ke titik-titik pada cincin ini menggunakan fungsi hash yang sama (misalnya, MD5 atau SHA-1).

  2. Memetakan Server ke Cincin

    • Setiap server diberi identifikasi unik (misalnya, alamat IP atau nama server).

    • Identifikasi ini di-hash menggunakan fungsi hash, dan hasilnya menentukan posisi server pada cincin.

    • Misalnya, jika ada tiga server (S1, S2, S3), masing-masing akan di-hash ke titik tertentu pada cincin, seperti pada posisi 100, 200, dan 300 (dalam ruang hash yang disederhanakan).

  3. Memetakan Kunci ke Cincin

    • Kunci data (misalnya, ID pengguna atau nama file) juga di-hash menggunakan fungsi hash yang sama.

    • Hasil hash menentukan posisi kunci pada cincin.

    • Untuk menentukan server mana yang menyimpan kunci tersebut, kita bergerak searah jarum jam (clockwise) dari posisi kunci hingga menemukan server pertama. Server ini bertanggung jawab atas kunci tersebut.

  4. Penanganan Penambahan atau Penghapusan Server

    • Penambahan server: Ketika server baru ditambahkan, server tersebut di-hash dan ditempatkan pada cincin. Hanya kunci yang berada di antara server baru dan server sebelumnya (searah jarum jam) yang perlu dipetakan ulang ke server baru. Kunci lainnya tidak terpengaruh.

    • Penghapusan server: Ketika server dihapus, kunci yang sebelumnya ditangani oleh server tersebut akan dipetakan ulang ke server berikutnya searah jarum jam. Sekali lagi, hanya sebagian kecil kunci yang terpengaruh.

  5. Virtual Nodes untuk Distribusi Merata Salah satu masalah dalam consistent hashing adalah distribusi data yang tidak merata, terutama jika jumlah server kecil atau fungsi hash tidak optimal. Untuk mengatasi ini, konsep virtual nodes digunakan:

    • Setiap server direpresentasikan oleh beberapa titik pada cincin (virtual nodes), bukan hanya satu titik.

    • Misalnya, server S1 dapat memiliki 10 virtual nodes (S1-1, S1-2, ..., S1-10), yang masing-masing di-hash ke posisi berbeda pada cincin.

    • Ini meningkatkan kemungkinan distribusi data yang lebih merata dan mengurangi kemungkinan satu server menjadi "hotspot" yang kelebihan beban.

Contoh Ilustrasi

Bayangkan sebuah cincin hash dengan rentang 0 hingga 999, dan tiga server (S1, S2, S3) dipetakan ke posisi 200, 400, dan 600. Misalkan ada kunci data K1 yang di-hash ke posisi 300.

  • Dari posisi 300, kita bergerak searah jarum jam hingga menemukan server berikutnya, yaitu S2 di posisi 400. Maka, K1 disimpan di S2.

  • Jika server baru (S4) ditambahkan pada posisi 350, maka K1 akan dipetakan ulang ke S4, karena S4 sekarang adalah server pertama searah jarum jam dari posisi 300. Namun, kunci lain yang tidak berada di antara 200 dan 350 tidak terpengaruh.

Sekarang, jika S2 dihapus, kunci seperti K1 (pada posisi 300) akan dipetakan ke server berikutnya, yaitu S3 di posisi 600. Hanya kunci yang sebelumnya ditangani oleh S2 yang perlu dipetakan ulang.

Keunggulan Consistent Hashing

  1. Minimalkan Remapping: Hanya sebagian kecil kunci yang terpengaruh saat server ditambahkan atau dihapus, yaitu sekitar 1/N dari total kunci untuk N server.

  2. Skalabilitas: Sistem dapat dengan mudah menskalakan tanpa gangguan besar.

  3. Fleksibilitas: Dapat digunakan dalam berbagai aplikasi, seperti database terdistribusi (Cassandra, DynamoDB), cache (Memcached), atau load balancer.

  4. Distribusi Merata dengan Virtual Nodes: Mengurangi kemungkinan ketidakseimbangan beban.

Kelemahan Consistent Hashing

  1. Kompleksitas Implementasi: Lebih rumit dibandingkan hashing tradisional, terutama dengan penambahan virtual nodes.

  2. Ketergantungan pada Fungsi Hash: Kualitas distribusi data bergantung pada seberapa baik fungsi hash mendistribusikan kunci dan server.

  3. Overhead Virtual Nodes: Menambahkan banyak virtual nodes meningkatkan overhead komputasi untuk menghitung posisi hash.

Aplikasi Nyata Consistent Hashing

Consistent hashing digunakan secara luas dalam sistem berikut:

  • Database Terdistribusi: Apache Cassandra dan Amazon DynamoDB menggunakan consistent hashing untuk mendistribusikan data di antara node.

  • Sistem Cache: Memcached menggunakan consistent hashing untuk mengelola cache terdistribusi.

  • Load Balancer: Consistent hashing membantu mendistribusikan permintaan ke server dengan cara yang konsisten, bahkan saat server ditambahkan atau dihapus.

  • Content Delivery Networks (CDN): CDN seperti Akamai menggunakan consistent hashing untuk memetakan konten ke server cache terdekat.

Consistent hashing adalah teknik yang sangat penting dalam sistem terdistribusi karena kemampuannya untuk mendistribusikan data secara efisien sambil meminimalkan gangguan saat sistem menskalakan. Dengan memetakan kunci dan server ke dalam cincin hash dan menggunakan konsep seperti virtual nodes, consistent hashing memastikan distribusi data yang merata dan skalabilitas yang baik. Meskipun lebih kompleks daripada hashing tradisional, manfaatnya dalam hal stabilitas dan efisiensi menjadikannya pilihan utama untuk sistem seperti database terdistribusi, cache, dan load balancer. Dengan memahami mengapa dan bagaimana consistent hashing bekerja, pengembang dapat merancang sistem yang lebih skalabel dan tangguh.

Berikut daftar teknologi dan database yang menggunakan consistent hashing sebagai bagian dari arsitektur mereka, beserta penjelasan singkat tentang bagaimana mereka mengimplementasikannya:

1. Database Terdistribusi

  • Apache Cassandra

    • Penggunaan: Cassandra menggunakan consistent hashing untuk mendistribusikan data di antara node dalam klaster. Setiap node bertanggung jawab atas rentang kunci tertentu pada cincin hash.

    • Detail: Cassandra menggunakan konsep virtual nodes (vnodes) untuk meningkatkan distribusi data yang merata dan memudahkan penanganan kegagalan node. Setiap node dapat memiliki banyak vnodes, yang memungkinkan distribusi beban yang lebih baik dan pemulihan yang lebih cepat saat node ditambahkan atau dihapus.

  • Amazon DynamoDB

    • Penggunaan: DynamoDB, database NoSQL milik AWS, menggunakan consistent hashing untuk mempartisi data di antara node.

    • Detail: DynamoDB mengimplementasikan consistent hashing dengan replikasi data untuk memastikan ketersediaan tinggi. Setiap kunci dipetakan ke node tertentu di cincin hash, dan data direplikasi ke beberapa node untuk toleransi kesalahan.

  • Riak

    • Penggunaan: Riak, database NoSQL berbasis key-value, menggunakan consistent hashing untuk mendistribusikan data di seluruh klaster.

    • Detail: Riak membagi ruang hash menjadi partisi tetap (disebut "partitions") dan menetapkan partisi ini ke node menggunakan consistent hashing. Riak juga mendukung vnodes untuk distribusi yang lebih merata.

  • ScyllaDB

    • Penggunaan: ScyllaDB, yang kompatibel dengan Cassandra, juga menggunakan consistent hashing untuk distribusi data.

    • Detail: Mirip dengan Cassandra, ScyllaDB menggunakan vnodes untuk memastikan distribusi data yang seimbang dan skalabilitas yang baik, dengan fokus pada performa tinggi.

2. Sistem Cache Terdistribusi

  • Memcached

    • Penggunaan: Memcached, sistem cache terdistribusi, menggunakan consistent hashing dalam kliennya untuk memetakan kunci ke server cache.

    • Detail: Banyak klien Memcached (misalnya, dalam pustaka seperti libmemcached atau klien dalam bahasa seperti Python dan Java) mendukung consistent hashing untuk memastikan bahwa kunci tetap dipetakan ke server yang sama meskipun ada perubahan jumlah server, sehingga mengurangi cache miss.

  • Redis Cluster

    • Penggunaan: Redis, dalam mode klaster, menggunakan consistent hashing untuk mendistribusikan data di antara node.

    • Detail: Redis Cluster membagi ruang hash menjadi 16.384 slot hash, yang didistribusikan ke node-node dalam klaster. Ketika node ditambahkan atau dihapus, slot hash dipetakan ulang dengan cara yang mirip dengan consistent hashing untuk meminimalkan perpindahan data.

3. Content Delivery Networks (CDN)

  • Akamai

    • Penggunaan: Akamai, salah satu penyedia CDN terbesar, menggunakan consistent hashing untuk memetakan permintaan konten ke server cache terdekat.

    • Detail: Consistent hashing membantu Akamai menentukan server mana yang menyimpan konten tertentu, memastikan distribusi beban yang efisien dan pengurangan latensi saat server ditambahkan atau dihapus.

  • Cloudflare

    • Penggunaan: Cloudflare menggunakan teknik berbasis consistent hashing untuk mengelola distribusi konten di server edge mereka.

    • Detail: Consistent hashing memungkinkan Cloudflare untuk menjaga konsistensi dalam memetakan permintaan ke server tertentu, bahkan saat infrastruktur mereka menskalakan.

4. Load Balancer

  • NGINX

    • Penggunaan: NGINX, ketika digunakan sebagai load balancer, dapat dikonfigurasi untuk menggunakan consistent hashing untuk mendistribusikan permintaan ke server backend.

    • Detail: Modul seperti ngx_http_upstream_hash_module mendukung consistent hashing, memastikan bahwa permintaan dari klien tertentu selalu diarahkan ke server yang sama, kecuali server tersebut dihapus.

  • HAProxy

    • Penggunaan: HAProxy, load balancer open-source, mendukung consistent hashing untuk distribusi beban.

    • Detail: HAProxy menggunakan consistent hashing untuk memastikan bahwa permintaan dengan kunci tertentu (misalnya, ID sesi) selalu diarahkan ke server yang sama, meningkatkan efisiensi cache dan konsistensi sesi.

5. Sistem Penyimpanan Objek

  • Swift (OpenStack)

    • Penggunaan: Swift, sistem penyimpanan objek dalam OpenStack, menggunakan consistent hashing untuk mendistribusikan objek di antara node penyimpanan.

    • Detail: Swift menggunakan cincin hash untuk memetakan objek ke node, dengan replikasi untuk memastikan ketersediaan dan toleransi kesalahan.

6. Sistem File Terdistribusi

  • Ceph

    • Penggunaan: Ceph, sistem penyimpanan terdistribusi, menggunakan algoritma CRUSH (Controlled Replication Under Scalable Hashing), yang merupakan variasi dari consistent hashing.

    • Detail: CRUSH memetakan data ke node penyimpanan dengan cara yang meminimalkan perpindahan data saat klaster menskalakan, serupa dengan prinsip consistent hashing.

7. Sistem Messaging dan Streaming

  • Apache Kafka

    • Penggunaan: Kafka menggunakan consistent hashing untuk mendistribusikan partisi topik di antara broker.

    • Detail: Kafka menggunakan consistent hashing untuk menentukan broker mana yang bertanggung jawab atas partisi tertentu, memungkinkan skalabilitas dan redistribusi partisi yang efisien saat broker ditambahkan atau dihapus.

Virtual nodes (atau vnodes) adalah konsep dalam consistent hashing yang digunakan untuk meningkatkan distribusi data yang lebih merata di antara server fisik dalam sistem terdistribusi. Alih-alih hanya memetakan satu server fisik ke satu titik pada cincin hash, setiap server direpresentasikan oleh beberapa titik (virtual nodes) pada cincin tersebut. Berikut adalah penjelasan singkat tentang virtual nodes:

  • Definisi: Virtual nodes adalah representasi logis dari server fisik dalam cincin hash. Setiap server memiliki beberapa virtual nodes, yang masing-masing di-hash ke posisi berbeda pada cincin.

  • Tujuan:

    • Distribusi Merata: Dengan memiliki banyak titik pada cincin, data lebih merata di antara server, mengurangi risiko satu server menjadi "hotspot" (kelebihan beban).

    • Skalabilitas: Memudahkan penanganan penambahan atau penghapusan server dengan meminimalkan jumlah data yang perlu dipetakan ulang.

    • Fleksibilitas: Server dengan kapasitas lebih besar dapat diberi lebih banyak virtual nodes (melalui bobot/weight) untuk menangani lebih banyak data.

  • Contoh: Jika server S1 memiliki 10 virtual nodes, masing-masing akan di-hash ke posisi berbeda (misalnya, S1-0, S1-1, ..., S1-9), sehingga server tersebut memiliki lebih banyak "slot" untuk menangani kunci data.

Cara Kerja Consistent Hashing (Recap dalam Poin-Poin)

Berikut adalah langkah-langkah cara kerja consistent hashing, termasuk peran virtual nodes, dalam bentuk poin-poin yang ringkas dan komprehensif:

  1. Pembuatan Cincin Hash:

    • Ruang hash (hash space) direpresentasikan sebagai cincin melingkar dengan rentang nilai (misalnya, 0 hingga 2³²-1 untuk hash 32-bit).

    • Cincin ini digunakan untuk memetakan baik kunci data maupun server ke titik-titik tertentu.

  2. Penempatan Server (Nodes):

    • Setiap server di-hash menggunakan fungsi hash (contoh: MD5, SHA-1) berdasarkan identifikasi uniknya (misalnya, alamat IP atau nama server).

    • Server ditempatkan pada posisi yang sesuai di cincin hash berdasarkan nilai hash-nya.

  3. Penambahan Virtual Nodes:

    • Setiap server fisik direpresentasikan oleh beberapa virtual nodes untuk meningkatkan distribusi data.

    • Jumlah virtual nodes biasanya ditentukan oleh bobot server (weight) atau konfigurasi tertentu (misalnya, 100 virtual nodes per server).

    • Setiap virtual node di-hash ke posisi unik pada cincin, biasanya dengan menambahkan indeks (misalnya, "server1-0", "server1-1", dst.).

  4. Pemetaan Kunci Data:

    • Kunci data (misalnya, ID pengguna, nama file) di-hash menggunakan fungsi hash yang sama untuk menentukan posisinya pada cincin.

    • Kunci dipetakan ke server dengan mencari server (atau virtual node) pertama yang ditemukan searah jarum jam (clockwise) dari posisi hash kunci tersebut.

  5. Penanganan Penambahan Server:

    • Ketika server baru ditambahkan, server tersebut (dan virtual nodes-nya) di-hash dan ditempatkan pada cincin.

    • Hanya kunci yang berada di antara server baru dan server sebelumnya (searah jarum jam) yang perlu dipetakan ulang ke server baru.

    • Virtual nodes memastikan bahwa hanya sebagian kecil data yang terpengaruh, meningkatkan efisiensi.

  6. Penanganan Penghapusan Server:

    • Ketika server dihapus, virtual nodes milik server tersebut dihapus dari cincin.

    • Kunci yang sebelumnya ditangani oleh server tersebut dipetakan ulang ke server berikutnya searah jarum jam.

    • Virtual nodes membantu meminimalkan jumlah kunci yang perlu dipetakan ulang.

  7. Distribusi Merata dengan Virtual Nodes:

    • Virtual nodes memastikan bahwa data terdistribusi lebih merata di antara server fisik, terutama jika server memiliki kapasitas berbeda.

    • Server dengan bobot lebih tinggi (misalnya, server yang lebih kuat) dapat memiliki lebih banyak virtual nodes untuk menangani lebih banyak kunci.

  8. Keunggulan:

    • Minimalkan Remapping: Hanya sebagian kecil kunci (sekitar 1/N untuk N server) yang perlu dipetakan ulang saat server ditambahkan/dihapus.

    • Skalabilitas: Sistem dapat menskalakan dengan mudah tanpa gangguan besar.

    • Efisiensi Cache: Dalam sistem seperti cache, consistent hashing mengurangi cache miss dengan menjaga kunci tetap pada server yang sama sebisa mungkin.

  9. Implementasi Praktis:

    • Fungsi hash yang baik (contoh: MD5, FNV-1a) diperlukan untuk memastikan distribusi yang merata.

    • Struktur data seperti array terurut atau pohon biner sering digunakan untuk mencari virtual node terdekat (lookup) dengan efisien, biasanya dengan kompleksitas O(log N).

Contoh Sederhana

  • Bayangkan cincin hash dari 0 hingga 999.

  • Server S1 (posisi 200), S2 (posisi 400), dan S3 (posisi 600), masing-masing dengan 2 virtual nodes (misalnya, S1-0 di 180, S1-1 di 220, dst.).

  • Kunci "user:123" di-hash ke posisi 300. Bergerak searah jarum jam, kunci ini akan dipetakan ke virtual node terdekat (misalnya, S2-0 di posisi 380).

  • Jika S2 dihapus, kunci dipetakan ulang ke S3 (posisi 600). Jika S4 ditambahkan di posisi 350, hanya kunci antara 200 dan 350 yang terpengaruh.

Catatan

  • Virtual nodes adalah kunci untuk mengatasi masalah distribusi tidak merata, terutama dalam sistem dengan jumlah server kecil.

  • Implementasi seperti yang diberikan sebelumnya (dalam Go) menunjukkan bagaimana virtual nodes diintegrasikan ke dalam cincin hash untuk mendukung skalabilitas dan distribusi yang efisien.

Berikut adalah implementasi lengkap Consistent Hashing Ring dari scratch menggunakan Go. Program ini mencakup semua konsep utama seperti virtual nodes, penambahan/penghapusan server, dan lookup kunci.

Consistent Hashing Ring Implementation in Go

1. Struktur Utama dan Interface

package main

import (
    "fmt"
    "sort"
    "strconv"
    "strings"
)

// HashFunc adalah interface untuk fungsi hash yang dapat diganti
type HashFunc func(key string) uint32

// Node mewakili server/node dalam sistem
type Node struct {
    ID       string  // Identifikasi unik server
    Address  string  // Alamat server (misal: IP:port)
    Weight   int     // Bobot server untuk distribusi virtual nodes
    VNodes   []uint32 // Virtual nodes yang dimiliki node ini
}

// ConsistentHashRing adalah struktur utama untuk consistent hashing
type ConsistentHashRing struct {
    nodes      map[string]*Node        // Map node ID ke Node
    vnodes     []uint32                // Sorted list of all virtual nodes
    vnodeToNode map[uint32]string      // Mapping virtual node ke node ID
    hashFunc   HashFunc                // Fungsi hash yang digunakan
    numReplicas int                    // Jumlah virtual nodes per node
}

// NewConsistentHashRing membuat ring baru dengan fungsi hash default
func NewConsistentHashRing(numReplicas int) *ConsistentHashRing {
    return &ConsistentHashRing{
        nodes:      make(map[string]*Node),
        vnodes:     make([]uint32, 0),
        vnodeToNode: make(map[uint32]string),
        hashFunc:   defaultHashFunc, // Gunakan MD5 hash sederhana
        numReplicas: numReplicas,
    }
}

2. Fungsi Hash

import (
    "crypto/md5"
    "encoding/binary"
    "hash"
)

// defaultHashFunc menggunakan MD5 untuk menghasilkan hash 32-bit
func defaultHashFunc(key string) uint32 {
    hasher := md5.New()
    hasher.Write([]byte(key))
    return binary.BigEndian.Uint32(hasher.Sum(nil)[:4])
}

// Custom hash function yang bisa digunakan (contoh: FNV-1a)
func fnv1aHash(key string) uint32 {
    hash := uint32(2166136261)
    for _, c := range key {
        hash ^= uint32(c)
        hash *= 16777619
    }
    return hash
}

// SetHashFunc mengganti fungsi hash yang digunakan
func (chr *ConsistentHashRing) SetHashFunc(hf HashFunc) {
    chr.hashFunc = hf
}

3. Metode untuk Mengelola Nodes

// AddNode menambahkan node baru ke ring
func (chr *ConsistentHashRing) AddNode(id, address string, weight int) error {
    if _, exists := chr.nodes[id]; exists {
        return fmt.Errorf("node %s already exists", id)
    }

    node := &Node{
        ID:      id,
        Address: address,
        Weight:  weight,
        VNodes:  make([]uint32, 0),
    }

    // Generate virtual nodes berdasarkan weight dan numReplicas
    totalReplicas := chr.numReplicas * weight
    for i := 0; i < totalReplicas; i++ {
        // Buat identifier unik untuk virtual node
        vNodeKey := fmt.Sprintf("%s-%d", id, i)
        vNodeHash := chr.hashFunc(vNodeKey)
        
        // Pastikan tidak ada duplikat
        if _, exists := chr.vnodeToNode[vNodeHash]; !exists {
            node.VNodes = append(node.VNodes, vNodeHash)
            chr.vnodes = append(chr.vnodes, vNodeHash)
            chr.vnodeToNode[vNodeHash] = id
        }
    }

    // Sort virtual nodes
    sort.Slice(chr.vnodes, func(i, j int) bool {
        return chr.vnodes[i] < chr.vnodes[j]
    })

    chr.nodes[id] = node
    fmt.Printf("Added node %s (%s) with %d virtual nodes\n", id, address, len(node.VNodes))
    return nil
}

// RemoveNode menghapus node dari ring
func (chr *ConsistentHashRing) RemoveNode(id string) error {
    node, exists := chr.nodes[id]
    if !exists {
        return fmt.Errorf("node %s not found", id)
    }

    // Hapus virtual nodes dari node ini
    for _, vNode := range node.VNodes {
        delete(chr.vnodeToNode, vNode)
        // Hapus dari sorted list
        for i, hv := range chr.vnodes {
            if hv == vNode {
                chr.vnodes = append(chr.vnodes[:i], chr.vnodes[i+1:]...)
                break
            }
        }
    }

    delete(chr.nodes, id)
    fmt.Printf("Removed node %s\n", id)
    return nil
}

// GetNode mengembalikan node yang bertanggung jawab untuk key tertentu
func (chr *ConsistentHashRing) GetNode(key string) (*Node, error) {
    if len(chr.vnodes) == 0 {
        return nil, fmt.Errorf("no nodes available")
    }

    // Hash key
    hashVal := chr.hashFunc(key)
    
    // Cari posisi hashVal dalam sorted vnodes menggunakan binary search
    idx := sort.Search(len(chr.vnodes), func(i int) bool {
        return chr.vnodes[i] >= hashVal
    })

    // Jika idx sama dengan length, wrap around ke index 0 (circular)
    if idx == len(chr.vnodes) {
        idx = 0
    }

    vNodeHash := chr.vnodes[idx]
    nodeID := chr.vnodeToNode[vNodeHash]
    node := chr.nodes[nodeID]
    
    return node, nil
}

// GetAllNodes mengembalikan semua nodes dalam ring
func (chr *ConsistentHashRing) GetAllNodes() []*Node {
    nodes := make([]*Node, 0, len(chr.nodes))
    for _, node := range chr.nodes {
        nodes = append(nodes, node)
    }
    return nodes
}

// GetNodeStats mengembalikan statistik distribusi virtual nodes
func (chr *ConsistentHashRing) GetNodeStats() map[string]int {
    stats := make(map[string]int)
    for _, vNode := range chr.vnodes {
        nodeID := chr.vnodeToNode[vNode]
        stats[nodeID]++
    }
    return stats
}

4. Fungsi Utilitas dan Testing

// SimulateKeys mensimulasikan distribusi keys ke nodes
func (chr *ConsistentHashRing) SimulateKeys(keys []string) map[string][]string {
    distribution := make(map[string][]string)
    
    for _, key := range keys {
        node, err := chr.GetNode(key)
        if err != nil {
            continue
        }
        distribution[node.ID] = append(distribution[node.ID], key)
    }
    
    return distribution
}

// PrintRingInfo mencetak informasi ring
func (chr *ConsistentHashRing) PrintRingInfo() {
    fmt.Println("\n=== Consistent Hash Ring Info ===")
    fmt.Printf("Total nodes: %d\n", len(chr.nodes))
    fmt.Printf("Total virtual nodes: %d\n", len(chr.vnodes))
    fmt.Printf("Replicas per node: %d\n", chr.numReplicas)
    
    fmt.Println("\nNode Statistics:")
    stats := chr.GetNodeStats()
    for nodeID, count := range stats {
        node := chr.nodes[nodeID]
        fmt.Printf("  %s (%s): %d virtual nodes (weight: %d)\n", 
            nodeID, node.Address, count, node.Weight)
    }
    
    fmt.Println("\nVirtual Nodes Distribution (first 20):")
    for i, vNode := range chr.vnodes[:20] {
        nodeID := chr.vnodeToNode[vNode]
        fmt.Printf("  %d: %d -> %s\n", i, vNode, nodeID)
    }
    if len(chr.vnodes) > 20 {
        fmt.Printf("  ... and %d more\n", len(chr.vnodes)-20)
    }
}

5. Program Utama dengan Contoh Penggunaan

func main() {
    // Buat consistent hash ring dengan 100 replicas per node
    ring := NewConsistentHashRing(100)
    
    // Tambahkan beberapa nodes dengan weight berbeda
    ring.AddNode("server1", "192.168.1.1:8080", 1)
    ring.AddNode("server2", "192.168.1.2:8080", 1)
    ring.AddNode("server3", "192.168.1.3:8080", 2) // Weight lebih tinggi
    ring.AddNode("server4", "192.168.1.4:8080", 1)
    
    // Tampilkan info ring awal
    ring.PrintRingInfo()
    
    // Test dengan beberapa keys
    testKeys := []string{
        "user:123", "user:456", "user:789", "user:101",
        "session:abc", "session:def", "cache:key1", "cache:key2",
        "data:obj1", "data:obj2", "data:obj3", "data:obj4",
    }
    
    fmt.Println("\n=== Key Distribution Test ===")
    distribution := ring.SimulateKeys(testKeys)
    for nodeID, keys := range distribution {
        fmt.Printf("Node %s: %d keys - %v\n", 
            nodeID, len(keys), keys[:min(3, len(keys))])
        if len(keys) > 3 {
            fmt.Printf("  ... and %d more\n", len(keys)-3)
        }
    }
    
    // Test lookup individual key
    testKey := "user:999"
    node, err := ring.GetNode(testKey)
    if err != nil {
        fmt.Printf("Error finding node for %s: %v\n", testKey, err)
    } else {
        fmt.Printf("\nKey '%s' mapped to node %s (%s)\n", 
            testKey, node.ID, node.Address)
    }
    
    // Simulasi penambahan node baru
    fmt.Println("\n=== Adding new node ===")
    ring.AddNode("server5", "192.168.1.5:8080", 1)
    ring.PrintRingInfo()
    
    // Simulasi penghapusan node
    fmt.Println("\n=== Removing node server2 ===")
    err = ring.RemoveNode("server2")
    if err != nil {
        fmt.Printf("Error removing node: %v\n", err)
    }
    ring.PrintRingInfo()
    
    // Test distribusi setelah perubahan
    fmt.Println("\n=== Distribution after changes ===")
    newDistribution := ring.SimulateKeys(testKeys)
    for nodeID, keys := range newDistribution {
        fmt.Printf("Node %s: %d keys\n", nodeID, len(keys))
    }
    
    // Test dengan custom hash function
    fmt.Println("\n=== Testing with FNV-1a hash ===")
    ring.SetHashFunc(fnv1aHash)
    ring.AddNode("server6", "192.168.1.6:8080", 1)
    ring.PrintRingInfo()
}

// Helper function untuk min
func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}

6. Contoh Output dan Testing Lanjutan

// Fungsi tambahan untuk testing load balancing
func testLoadBalancing() {
    fmt.Println("\n=== Load Balancing Test ===")
    ring := NewConsistentHashRing(50)
    
    // Tambahkan 5 nodes dengan weight berbeda
    nodes := []struct {
        id     string
        addr   string
        weight int
    }{
        {"n1", "10.0.0.1:8080", 1},
        {"n2", "10.0.0.2:8080", 2},
        {"n3", "10.0.0.3:8080", 1},
        {"n4", "10.0.0.4:8080", 3},
        {"n5", "10.0.0.5:8080", 1},
    }
    
    for _, node := range nodes {
        ring.AddNode(node.id, node.addr, node.weight)
    }
    
    // Generate 1000 random keys
    keys := make([]string, 1000)
    for i := range keys {
        keys[i] = fmt.Sprintf("key_%d_%d", i, rand.Intn(10000))
    }
    
    distribution := ring.SimulateKeys(keys)
    totalKeys := 0
    for nodeID, nodeKeys := range distribution {
        count := len(nodeKeys)
        totalKeys += count
        node := ring.nodes[nodeID]
        expected := (node.Weight * ring.numReplicas * 1000) / (sumWeights(nodes) * ring.numReplicas)
        fmt.Printf("Node %s (weight %d): %d keys (expected ~%d)\n", 
            nodeID, node.Weight, count, expected)
    }
    fmt.Printf("Total keys distributed: %d\n", totalKeys)
}

func sumWeights(nodes []struct{ id, addr string; weight int }) int {
    sum := 0
    for _, n := range nodes {
        sum += n.weight
    }
    return sum
}

Fitur Utama Implementasi Ini:

  1. Virtual Nodes: Setiap node memiliki multiple virtual nodes berdasarkan weight

  2. Sorted Ring: Virtual nodes diurutkan untuk binary search yang efisien

  3. Customizable Hash: Dapat menggunakan fungsi hash berbeda (MD5, FNV-1a, dll)

  4. Dynamic Scaling: Mudah menambah/menghapus nodes

  5. Load Balancing: Weight-based distribution untuk fairness

  6. Efficient Lookup: O(log N) lookup menggunakan binary search

  7. Statistics: Monitoring distribusi virtual nodes dan keys

Cara Menjalankan:

  1. Simpan kode dalam file consistent_hash.go

  2. Compile dan jalankan: go run consistent_hash.go

  3. Program akan menampilkan:

    • Inisialisasi ring dengan nodes

    • Distribusi test keys

    • Simulasi scaling (add/remove nodes)

    • Statistik distribusi

Untuk membuat visualisasi cincin hash dengan virtual nodes, saya akan menghasilkan diagram menggunakan Chart.js dalam bentuk kode yang merepresentasikan cincin hash sebagai grafik polarArea. Diagram ini akan menunjukkan posisi server dan virtual nodes pada cincin, serta beberapa kunci data untuk mengilustrasikan bagaimana mereka dipetakan. Karena Anda meminta diagram, saya akan membuatnya sebagai representasi visual dengan penjelasan untuk membantu memahami.

Penjelasan Diagram

  • Cincin Hash: Direpresentasikan sebagai lingkaran (polar area chart) dengan rentang hash dari 0 hingga 360 derajat untuk kesederhanaan visual.

  • Server: Setiap server (misalnya, S1, S2, S3) ditandai pada cincin berdasarkan nilai hash-nya.

  • Virtual Nodes: Setiap server memiliki beberapa virtual nodes, yang juga ditempatkan pada cincin di posisi hash yang berbeda.

  • Kunci Data: Kunci data (misalnya, "user:123") di-hash dan ditempatkan pada cincin, lalu dipetakan ke virtual node terdekat searah jarum jam.

  • Warna: Server dan virtual nodes-nya memiliki warna berbeda untuk membedakan. Kunci data ditampilkan dengan warna netral (abu-abu).

Kode Diagram (Chart.js)

Berikut adalah kode untuk menghasilkan diagram cincin hash dengan virtual nodes menggunakan Chart.js dalam format polarArea:

{
  "type": "polarArea",
  "data": {
    "labels": [
      "S1 (200)", "S1-v1 (180)", "S1-v2 (220)",
      "S2 (400)", "S2-v1 (380)", "S2-v2 (420)",
      "S3 (600)", "S3-v1 (580)", "S3-v2 (620)",
      "Key: user:123 (300)", "Key: user:456 (450)", "Key: user:789 (150)"
    ],
    "datasets": [
      {
        "label": "Hash Ring",
        "data": [
          10, 8, 8, // S1 dan virtual nodes-nya
          10, 8, 8, // S2 dan virtual nodes-nya
          10, 8, 8, // S3 dan virtual nodes-nya
          5, 5, 5    // Kunci data
        ],
        "backgroundColor": [
          "rgba(75, 192, 192, 0.8)", "rgba(75, 192, 192, 0.4)", "rgba(75, 192, 192, 0.4)", // S1
          "rgba(255, 99, 132, 0.8)", "rgba(255, 99, 132, 0.4)", "rgba(255, 99, 132, 0.4)",   // S2
          "rgba(54, 162, 235, 0.8)", "rgba(54, 162, 235, 0.4)", "rgba(54, 162, 235, 0.4)",  // S3
          "rgba(150, 150, 150, 0.6)", "rgba(150, 150, 150, 0.6)", "rgba(150, 150, 150, 0.6)" // Keys
        ],
        "borderColor": [
          "#4BC0C0", "#4BC0C0", "#4BC0C0",
          "#FF6384", "#FF6384", "#FF6384",
          "#36A2EB", "#36A2EB", "#36A2EB",
          "#999999", "#999999", "#999999"
        ],
        "borderWidth": 1
      }
    ]
  },
  "options": {
    "scales": {
      "r": {
        "angleLines": {
          "display": true,
          "color": "#ccc"
        },
        "grid": {
          "circular": true,
          "color": "#ccc"
        },
        "ticks": {
          "display": false
        },
        "pointLabels": {
          "display": true,
          "font": {
            "size": 12
          }
        }
      }
    },
    "plugins": {
      "legend": {
        "display": false
      },
      "tooltip": {
        "enabled": true
      },
      "title": {
        "display": true,
        "text": "Consistent Hash Ring with Virtual Nodes",
        "font": {
          "size": 16
        }
      }
    },
    "animation": false
  }
}

Penjelasan Elemen Diagram

  • Labels: Menunjukkan server (S1, S2, S3), virtual nodes (S1-v1, S1-v2, dll.), dan kunci data (user:123, dll.) dengan posisi hash dalam derajat (disimulasikan dari rentang 0-360 untuk visualisasi).

  • Data: Nilai data (10 untuk server, 8 untuk virtual nodes, 5 untuk kunci) menentukan panjang "segmen" di cincin, hanya untuk visualisasi. Nilai ini tidak mencerminkan hash sebenarnya, tetapi menunjukkan posisi relatif.

  • Warna:

    • Server: Warna lebih pekat (misalnya, S1: cyan, S2: pink, S3: biru).

    • Virtual Nodes: Warna lebih transparan dari server terkait.

    • Kunci Data: Abu-abu untuk membedakan dari server/nodes.

  • Posisi:

    • S1 di 200°, dengan virtual nodes di 180° dan 220°.

    • S2 di 400° (40° setelah wrap-around), dengan virtual nodes di 380° dan 420°.

    • S3 di 600° (240° setelah wrap-around), dengan virtual nodes di 580° dan 620°.

    • Kunci data: user:123 di 300°, user:456 di 450°, user:789 di 150°.

  • Pemetaan:

    • user:123 (300°) dipetakan ke S2-v1 (380°), server terdekat searah jarum jam.

    • user:456 (450°) dipetakan ke S3-v1 (580°).

    • user:789 (150°) dipetakan ke S1-v1 (180°).

Cara Kerja dalam Diagram

  1. Cincin Hash: Lingkaran polar mewakili ruang hash (0-360° untuk visualisasi sederhana).

  2. Server dan Virtual Nodes: Setiap server memiliki dua virtual nodes, ditempatkan di posisi hash yang berbeda untuk distribusi merata.

  3. Kunci Data: Kunci di-hash ke posisi tertentu, lalu dipetakan ke virtual node/server terdekat searah jarum jam.

  4. Efek Penambahan/Penghapusan: Jika server baru ditambahkan (misalnya, S4 di 350°), hanya kunci di antara server sebelumnya dan S4 yang dipetakan ulang. Virtual nodes memastikan distribusi tetap merata.

Catatan

  • Diagram ini menggunakan skala 0-360° untuk mempermudah visualisasi, tetapi dalam implementasi nyata, ruang hash biasanya jauh lebih besar (misalnya, 0 hingga 2³²-1).

  • Warna dan ukuran segmen hanya untuk tujuan visual; dalam consistent hashing sebenarnya, hanya posisi hash yang relevan.

  • Jika Anda ingin menyesuaikan diagram (misalnya, tambah server, kunci, atau ubah skala), beri tahu saya, dan saya bisa memperbarui kode chart-nya!

PreviousUkuran Letak DataNextDear CTO, Bicarakan Bisnis, Bukan Teknologi

Last updated