Hành Trình Xây Dựng Hệ Thống Cache Siêu Tốc Bằng Go: Bí Kíp Từ A Đến Z!

Lê Lân

03/07/2025

Thiết Kế Hệ Thống Cache: Giải Pháp Lập Trình Cấp Thấp Hiệu Quả

Mở Đầu

Trong thế giới phát triển phần mềm hiện đại, hệ thống cache đóng vai trò quan trọng giúp tăng tốc độ truy xuất dữ liệu và giảm tải hệ thống backend. Việc thiết kế một cache hiệu quả vừa đảm bảo hiệu suất cao vừa phải có khả năng mở rộng và bảo trì là một thách thức không nhỏ.

Bài viết này chia sẻ cách tiếp cận của tôi trong việc thiết kế một hệ thống cache hỗ trợ các thao tác cơ bản như thêm, lấy, xóa dữ liệu với khả năng tự động loại bỏ các mục hết hạn (TTL) và áp dụng ba chính sách đuổi bộ nhớ phổ biến: LRU, LFU và FIFO. Cùng với đó, tôi cũng trình bày cấu trúc mã nguồn sử dụng ngôn ngữ Go (Golang) để xây dựng hệ thống, kèm theo những phân tích chi tiết về cách hoạt động của từng thành phần.

Bạn có thể tham khảo toàn bộ mã nguồn tại kho GitHub của tôi: https://github.com/the-arcade-01/golang-low-level-design/tree/main/cache-system

Yêu Cầu Hệ Thống Cache

Các chức năng cơ bản

Hệ thống cache cần hỗ trợ:

Put(key, value, ttl): Lưu trữ cặp khóa-giá trị với thời gian sống (TTL).

Get(key): Lấy giá trị tương ứng nếu không bị hết hạn.

Delete(key): Xóa khóa theo yêu cầu.

Các chính sách đuổi bộ nhớ (Eviction Policies)

LRU (Least Recently Used): Loại bỏ mục ít được truy cập gần đây nhất.

LFU (Least Frequently Used): Loại bỏ mục ít được truy cập nhất về số lần.

FIFO (First In First Out): Loại bỏ mục cũ nhất được thêm vào trước.

Hệ thống phải tự động đuổi các mục khi cache đạt đến giới hạn dung lượng.

Xử lý TTL (Thời gian sống)

Tự động loại bỏ các mục đã hết hạn khi TTL kết thúc.

Cấu Trúc Mã Nguồn

Dưới đây là cấu trúc thư mục của dự án:

├── cmd
│   └── main.go
├── go.mod
└── internal
    ├── cache
    │   └── cache.go
    ├── evictionpolicy
    │   ├── evictionpolicy.go
    │   ├── fifo.go
    │   ├── lfu.go
    │   └── lru.go
    └── models
        └── node.go

cmd chứa điểm vào main cho ứng dụng.

internal/cache định nghĩa struct cache và các thao tác cơ bản.

internal/evictionpolicy bao gồm interface và các cài đặt cho chính sách đuổi bộ nhớ.

internal/models chứa các mô hình dữ liệu dùng chung như Node.

Các thành phần chính

Cache struct

Là trung tâm điều khiển các hoạt động lưu trữ và truy xuất dữ liệu:

EvictionPolicy interface

Giao diện này cho phép định nghĩa nhiều thuật toán đuổi bộ nhớ khác nhau một cách dễ dàng:

Node struct

Đại diện cho từng mục (tức cặp khóa-giá trị) trong cache:

Giải Thích Chi Tiết Mã Nguồn

Cache struct và thành phần dữ liệu

type Cache[T comparable, U any] struct {
  mtx            sync.Mutex
  capacity       int
  expireInterval int
  storage        map[T]*list.Element
  evictionpolicy evictionpolicy.EvictionPolicy
}

capacity : giới hạn số mục tối đa.

expireInterval : khoảng thời gian kiểm tra TTL.

storage : bản đồ chứa khóa liên kết tới phần tử trong danh sách.

evictionpolicy : giao diện chọn thuật toán đuổi bộ nhớ.

mtx : khóa bảo vệ đồng bộ đa luồng.

Các phương thức chính

Phương thức Get(key)

Tìm phần tử trong storage theo khóa.

Gọi phương thức Get của chính sách đuổi để tái sắp xếp vị trí phần tử.

Kiểm tra TTL và trả về kết quả hợp lệ.

Trả về lỗi nếu khóa không tồn tại hoặc đã hết hạn.

func (c *Cache[T, U]) Get(key T) (U, error) {
  c.mtx.Lock()
  defer c.mtx.Unlock()
  if element, ok := c.storage[key]; ok {
    element = c.evictionpolicy.Get(element)
    c.storage[key] = element
    if node, ok := element.Value.(*models.Node[T, U]); ok {
      if !node.IsExpire() {
        return node.GetValue(), nil
      }
    }
  }
  var zeroValue U
  return zeroValue, fmt.Errorf("key not found")
}

Phương thức Put(key, value, ttl)

Nếu khóa đã tồn tại, cập nhật giá trị và TTL sau đó tái sắp xếp.

Nếu khóa mới và cache đã đầy, gọi Evict để xóa phần tử theo chính sách đuổi.

Thêm phần tử mới vào storage và danh sách quản lý.

func (c *Cache[T, U]) Put(key T, value U, ttl int) {
  c.mtx.Lock()
  defer c.mtx.Unlock()
  if c.capacity == 0 {
    return
  }
  if element, ok := c.storage[key]; ok {
    element.Value.(*models.Node[T, U]).UpdateValue(value).UpdateTTL(ttl)
    element = c.evictionpolicy.Get(element)
    c.storage[key] = element
  } else {
    if c.capacity <= len(c.storage) {
      del := c.evictionpolicy.Evict()
      if del != nil {
        delete(c.storage, del.Value.(*models.Node[T, U]).GetKey())
      }
    }
    c.storage[key] = c.evictionpolicy.Put(models.NewNode(key, value, ttl))
  }
}

Phương thức Delete(key)

Xóa phần tử khỏi cả storage và danh sách đuổi bộ nhớ.

func (c *Cache[T, U]) Delete(key T) {
  c.mtx.Lock()
  defer c.mtx.Unlock()
  c.delete(key)
}

func (c *Cache[T, U]) delete(key T) {
  if element, ok := c.storage[key]; ok {
    c.evictionpolicy.Delete(element)
    delete(c.storage, key)
  }
}

Giao diện và cài đặt EvictionPolicy

type EvictionPolicy interface {
  Get(element *list.Element) *list.Element
  Evict() *list.Element
  Put(node any) *list.Element
  Delete(element *list.Element)
}

Get : tái sắp xếp khi có truy cập.

Evict : xóa phần tử theo thuật toán.

Put : thêm phần tử mới.

Delete : xóa phần tử theo yêu cầu.

Ví dụ cài đặt LRUCache

type LRUCache struct {
  list *list.List
}

func (c *LRUCache) Get(element *list.Element) *list.Element {
  c.list.MoveToFront(element)
  return element
}

func (c *LRUCache) Evict() *list.Element {
  last := c.list.Back()
  if last != nil {
    c.list.Remove(last)
  }
  return last
}

func (c *LRUCache) Put(node any) *list.Element {
  return c.list.PushFront(node)
}

func (c *LRUCache) Delete(element *list.Element) {
  if element != nil {
    c.list.Remove(element)
  }
}

Cách thiết kế hướng tới sự mở rộng linh hoạt với Factory Pattern, cho phép tạo ra các cache với chính sách đuổi bộ nhớ đa dạng chỉ bằng cách gọi hàm khởi tạo tương ứng.

Những Cải Tiến Tiềm Năng

Tối ưu việc xử lý TTL

Hiện tại, cache kiểm tra TTL của mỗi phần tử theo chu kỳ bằng cách duyệt toàn bộ storage với độ phức tạp O(n):

func (c *Cache[T, U]) expire() {
  ticker := time.NewTicker(time.Duration(c.expireInterval) * time.Second)
  fmt.Printf("Cache expire interval started, interval: %v\n", c.expireInterval)
  for range ticker.C {
    c.mtx.Lock()
    for key, value := range c.storage {
      if value.Value.(*models.Node[T, U]).IsExpire() {
        c.delete(key)
      }
    }
    c.mtx.Unlock()
  }
}

Một số giải pháp tối ưu:

Duy trì một heap theo thời gian TTL, chỉ kiểm tra phần tử có TTL nhỏ nhất.

Giảm thiểu tài nguyên hệ thống khi cache có số lượng lớn mục.

Tách rời Storage Map

Hiện tại, storage được khởi tạo bên trong struct Cache . Có thể nâng cấp thành interface riêng biệt để dễ hỗ trợ các loại lưu trữ khác (cơ sở dữ liệu, cache phân tán...).

Kết Luận

Việc thiết kế một hệ thống cache không chỉ đơn thuần là lưu trữ và truy xuất dữ liệu mà còn bao gồm nhiều vấn đề phức tạp như chính sách đuổi bộ nhớ, xử lý TTL, và khả năng mở rộng linh hoạt. Với cách tiếp cận dựa trên giao diện EvictionPolicy cùng mô hình sử dụng list.Element , tôi đã xây dựng một cache có thể dễ dàng thay đổi thuật toán đuổi bộ nhớ và đảm bảo hiệu suất tốt.

Nếu bạn quan tâm đến chi tiết code hoặc muốn đóng góp ý kiến, hãy truy cập repository GitHub của tôi và mở Issue hoặc pull request: https://github.com/the-arcade-01/golang-low-level-design

Cảm ơn bạn đã theo dõi bài viết!

Tham Khảo

Factory Method Design Pattern - Refactoring Guru

Golang official package - container/list: https://pkg.go.dev/container/list

GitHub Cache System Repository

Tài liệu về thuật toán LRU, LFU, FIFO trên Wikipedia

T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein - Introduction to Algorithms, 3rd Edition

Go by Example: Generics - https://gobyexample.com/generics