KAL
Menu

Cache Terdistribusi

Cluster Redis, consistent hashing, eviction, dan pilihan konsistensi cache.

Daftar isi

Cache terdistribusi menyatukan memori beberapa server menjadi satu cluster yang dipakai bersama oleh seluruh instance aplikasi, sehingga data yang sering dibaca dapat dilayani dari memori alih-alih dari basis data. Topik ini membahas cara cluster membagi kunci, kebijakan eviction ketika memori penuh, dan pilihan konsistensi cache setelah data ditulis. Semua contohnya berupa simulasi Python yang dapat dijalankan ulang tanpa layanan eksternal.

Cluster cache dan consistent hashing#

Satu instance cache memiliki dua batasan, yaitu kapasitas memori satu mesin dan risiko mati tunggal yang membuat seluruh trafik tiba-tiba jatuh ke basis data. Cluster mengatasi keduanya dengan membagi ruang kunci ke beberapa node. Klien atau proxy menghitung node tujuan dari nama kuncinya, sehingga setiap kunci berada di tepat satu node dan total kapasitasnya adalah jumlah memori seluruh node.

Pembagian kunci ke node dilakukan dengan consistent hashing, yaitu skema hashing yang memindahkan hanya sebagian kecil kunci ketika node bergabung atau keluar, alih-alih memindahkan hampir semuanya. Redis Cluster mengimplementasikan gagasan ini dengan membagi ruang kunci menjadi 16384 hash slot yang dipetakan ke node, dan pemetaan itulah yang dipindahkan saat topologi cluster berubah. Untuk cache, replika node tetap berguna menambah ketersediaan baca, meskipun cache pada dasarnya dapat diisi ulang dari basis data bila node hilang.

Eviction: LRU dan LFU#

Eviction adalah pengusiran entri cache ketika memori yang dialokasikan sudah penuh, dan kebijakan eviction menentukan entri mana yang dikorbankan. Redis menyediakan beberapa kebijakan melalui maxmemory-policy, antara lain noeviction, allkeys-lru, dan allkeys-lfu. Kebijakan LRU (Least Recently Used) mengusir kunci yang paling lama tidak diakses, sedangkan LFU (Least Frequently Used) mengusir kunci dengan frekuensi akses terendah. Perbedaannya terasa pada pola akses tertentu, dan hal itu dapat disimulasikan.

Program berikut menguji LRU dan LFU naif pada tiga pola akses deterministik dengan kapasitas 50 entri, tanpa bilangan acak sehingga keluarannya dapat dihitung ulang.

python simulasi-eviction.py 
"""Simulasi eviction LRU dan LFU pada tiga pola akses.

Kapasitas cache 50 entri. Semua pola akses dibangkitkan secara
deterministik tanpa bilangan acak, sehingga keluarannya dapat
dihitung ulang.
"""
from collections import Counter, OrderedDict

KAPASITAS = 50


class CacheLRU:
    def __init__(self):
        self.entri = OrderedDict()

    def akses(self, kunci):
        if kunci in self.entri:
            self.entri.move_to_end(kunci)
            return 1  # cache hit
        if len(self.entri) >= KAPASITAS:
            self.entri.popitem(last=False)  # buang yang paling lama tidak diakses
        self.entri[kunci] = True
        return 0  # cache miss


class CacheLFU:
    def __init__(self):
        self.frekuensi = Counter()
        self.masuk = {}

    def akses(self, kunci, t):
        if kunci in self.frekuensi:
            self.frekuensi[kunci] += 1
            return 1  # cache hit
        if len(self.frekuensi) >= KAPASITAS:
            # buang frekuensi terendah, seri dipecah oleh urutan masuk terlama
            kunci_buangan = min(
                self.frekuensi, key=lambda k: (self.frekuensi[k], self.masuk[k]))
            del self.frekuensi[kunci_buangan]
            del self.masuk[kunci_buangan]
        self.frekuensi[kunci] = 1
        self.masuk[kunci] = t
        return 0  # cache miss


def pola_lokal_panas(jumlah=5000):
    for t in range(jumlah):
        if t % 5 < 4:
            yield t % 20                # 80 persen akses ke 20 kunci panas
        else:
            yield 20 + (t // 5) % 80    # 20 persen akses ke 80 kunci dingin


def pola_pindai_siklik(jumlah=5000):
    for t in range(jumlah):
        yield t % 100                   # memindai 100 kunci berulang kali


def pola_campur(jumlah=6000):
    for t in range(jumlah):
        if t % 60 == 0:
            yield 0                     # satu kunci sangat panas, tiap 60 akses
        else:
            yield 1 + t % 200           # pindaian 200 kunci


def jalankan(nama_pola, aliran):
    lru, lfu = CacheLRU(), CacheLFU()
    total = hit_lru = hit_lfu = 0
    for t, kunci in enumerate(aliran):
        hit_lru += lru.akses(kunci)
        hit_lfu += lfu.akses(kunci, t)
        total += 1
    print(f"{nama_pola:<16}: LRU {hit_lru / total * 100:5.1f}%  "
          f"LFU {hit_lfu / total * 100:5.1f}%")


print(f"{'pola akses':<16}: hit rate (kapasitas {KAPASITAS})")
jalankan("lokal panas", pola_lokal_panas())
jalankan("pindai siklik", pola_pindai_siklik())
jalankan("campur", pola_campur())
text Keluaran 
pola akses      : hit rate (kapasitas 50)
lokal panas     : LRU  79.7%  LFU  79.7%
pindai siklik   : LRU   0.0%  LFU   0.0%
campur          : LRU   0.0%  LFU   0.0%

Pada pola lokal panas, kedua kebijakan sama baiknya, sekitar 79,7 persen, karena 20 kunci panas selalu muat di dalam cache 50 entri dan hanya kunci dingin yang saling mengusir. Pada pindai siklik, keduanya gagal total karena setiap kunci diakses lagi justru setelah diusir. Pola campur menunjukkan temuan yang paling menarik, yaitu LRU kehilangan kunci panas karena 59 kunci lain lewat di antara dua aksesnya, sedangkan LFU naif juga kehilangan kunci panas itu karena setiap kali masuk kembali, frekuensinya kembali ke 1 sementara kunci pindaian sudah menumpuk hitungan. Implementasi nyata seperti LFU Redis mengatasi kelemahan ini dengan penghitung yang menua, sehingga frekuensi lama meluruh perlahan alih-alih hilang dalam sekali usir.

Konsistensi cache setelah tulis#

Pola yang paling lazim adalah cache-aside. Saat membaca, aplikasi memeriksa cache terlebih dahulu, dan bila terjadi cache miss, aplikasi mengambil data dari basis data lalu mengisinya ke cache. Saat menulis, aplikasi memperbarui basis data, kemudian meng-invalidasi kunci cache yang bersangkutan, bukan memperbaruinya dengan nilai baru.

Invalidasi dipilih karena lebih aman daripada pembaruan. Dua penulis serentak dapat membuat cache berisi nilai yang lebih tua daripada basis data apabila keduanya menulis ke cache, sedangkan invalidasi memaksa pembaca berikutnya memuat ulang nilai yang paling baru. Meskipun begitu, celah kecil tetap ada, misalnya pembaca yang mengalami cache miss memuat nilai lama tepat sebelum penulis selesai, lalu mengisinya ke cache setelah invalidasi terjadi.

Alternatifnya adalah write-through, yaitu menulis ke cache dan basis data dalam satu alur. Skema ini menjaga cache selalu terisi, tetapi menaikkan biaya setiap penulisan dan tetap menulis kunci yang mungkin tidak pernah dibaca.

Arah konfigurasi Redis#

Konfigurasi cache Redis berpusat pada tiga keputusan, yaitu batas memori, kebijakan eviction, dan pengaturan cluster. maxmemory dipasang di bawah memori fisik agar tersisa ruang untuk fragmentasi dan buffer replikasi. Kebijakan allkeys-lfu umum dipilih untuk beban kerja cache yang memiliki beberapa kunci jauh lebih panas daripada yang lain, sedangkan noeviction sebaiknya dihindari pada cache murni karena penulisan kunci baru akan gagal ketika memori penuh. Pada mode cluster, Redis memerlukan cluster-enabled yes, berkas konfigurasi node, dan waktu tunggu antarnode yang wajar. Contoh berikut hanyalah arah konfigurasinya, bukan berkas lengkap yang siap dijalankan, karena setiap nilai sesungguhnya bergantung pada ukuran memori dan pola akses layanan yang bersangkutan.

text 
# tidak-dijalankan
# Arah konfigurasi Redis untuk cache (potongan, bukan berkas lengkap)
maxmemory 2gb
maxmemory-policy allkeys-lfu
cluster-enabled yes
cluster-node-timeout 15000

Kesalahan umum#

  • Memakai noeviction pada cache murni. Ketika memori penuh, operasi penulisan mengembalikan error dan aplikasi tampak gagal tanpa sebab yang jelas. Perbaikannya adalah memilih kebijakan eviction yang sesuai pola akses dan memantau rasio hit.
  • Meng-cache nilai yang jarang dibaca ulang. Rasio hit yang rendah berarti biaya kompleksitas tanpa imbalan, sehingga hanya kunci dengan rasio baca tinggi yang layak masuk cache.
  • Memperbarui nilai cache saat menulis alih-alih meng-invalidasi kuncinya. Urutan dua penulis serentak tidak bisa dijamin, dan cache dapat menyimpan nilai yang lebih tua daripada basis data.

Ringkasan#

  • Cluster cache membagi kunci antarnode dengan consistent hashing, dan Redis Cluster mewujudkannya melalui 16384 hash slot yang dipetakan ke node.
  • Kebijakan eviction menentukan hit rate ketika memori penuh, dan simulasi menunjukkan LRU sebaik LFU pada lokalitas panas, tetapi keduanya gagal pada pindai siklik dan pada kunci panas yang baru muncul bila LFU-nya naif.
  • Setelah penulisan, kunci cache di-invalidasi dan diberi TTL, sehingga nilai lama tidak menetap dan pembaca berikutnya memuat ulang data terbaru.

Referensi#