Giới thiệu

Hầu hết các hệ thống SQL database hiện nay đều lưu trữ data ở disk. Như chúng ta đã biết thì truy suất từ disk sẽ chậm hơn khoảng 80 lần so với RAM. Nếu giàu hơn chúng ta có thể thay thế disk bằng ổ SSD những vẫn sẽ chậm hơn 4 lần so với RAM.

Latency every programmer should know

Các hệ cơ sở dữ liệu SQL xử lý việc này bằng kỹ thuật buffer. Buffer hoạt động trên nguyên tắc: đưa 1 phần thông tin thường dùng, chứa thẳng trên RAM để có tốc độ truy suất nhanh. Những lần sử dụng sau thì sẽ không phải cực nhọc xuống disk để lấy data nữa.

Trong PostgreSQL, hệ thống đảm nhân việc này có tên là Buffer Manager.

Có thể thấy nguyên tắc của buffer rất giống với cache. Tuy nhiên đây là 2 kỹ thuật khác nhau và hướng đến 2 mục tiêu khác nhau.

Phân biệt cache và buffer

Cache là kỹ thuật lưu lại những data đã được xử lý, vào 1 bộ nhớ tạm. Bộ nhớ tạm này sẽ có tốc độ truy suất nhanh (RAM, hoặc local storage trên device của client). Những lần sau cần dùng thông tin thì ta truy suất ngay từ bộ nhớ tạm mà không cần phải làm thêm gì.

Buffer giống cache ở điểm là nó cũng lưu data ở bộ nhớ tạm. Tuy nhiên buffer sẽ chỉ lưu data thô. Điều này nhằm mục đích tối đa hoá khả năng tái sử dụng lại được data vì từ data thô đó ta có thể tính toán cho nhiều nhu cầu cụ thể của từng lần sử dụng.

Tóm lại: Chiến thuật chính của cache là tiết kiệm thời gian tính toán, còn buffer là tiết kiệm thời gian truy suất dữ liệu thô.

Cấu trúc của buffer manager

Buffer manager gồm có 3 thành phần: buffer table, buffer descriptors và buffer pool. Để đơn giản vấn đề chúng ta sẽ chỉ nói về buffer pool.

Buffer pool chính là bộ nhớ tạm mà chúng ta đã nói qua ở kỹ thuật buffer. Buffer pool được implement dưới dạng 1 array, được lưu trữ ở RAM. Mỗi slot của array này sẽ chứa một lượng "data thô", và index của slot này được goi là buffer_id.

Buffer_tag

Ai đã từng làm việc với SQL đều biết là data của chúng ta được chứa trong những table. Tuy nhiên table là một khái niệm mang tính hình tượng để chúng ta dễ suy nghĩ. Data thật sự của mỗi table được chia nhỏ ra và chứa trong các page có kích thước bằng nhau. Các bạn có thể đọc thêm về cấu trúc của page tại đây

Mỗi page được đặt cho 1 mã định danh gọi là buffer_tag. Buffer_tag này bao gồm 3 con số, mà thông qua nó sẽ định danh page này thuộc về table nào, và là page thứ mấy trong số các page đang chứa data của table. Chi tiết hơn tại đây

Dữ liệu trong page chính là data thô sẽ được lưu trữ trong bộ nhớ tạm, cụ thể là buffer pool layer của buffer manager.

Quy trình buffer manager hoạt động

How backend process reads pages

  1. Khi 1 SQL request đến, backend process sẽ xử lý logic của query, và biết được data cần thiết hiện đang được lưu ở page nào. Backend process sẽ mang buffer_tag của page đó đến kiểm tra với Buffer manager xem page này hiện có được buffer chưa.
  2. Nếu page chưa được lưu trong buffer pool thì buffer manager sẽ yêu cầu persistent layer truy suất trục tiếp xuống disk để lấy, sau đó lưu nó vào 1 trong các slot của buffer pool. Vụ trí của slot đó (buffer_id) sẽ được trả về cho backend process
    Nếu page đang được lưu trong buffer pool thì quá tốt, buffer manager sẽ trả về buffer_id của slot hiện đang chứa page này.
  3. Backend process với buffer_id trong tay có thể truy suất trực tiếp data mà nó cần.

Khi buffer pool bị đầy.

Buffer pool được lưu trữ trên RAM, 1 lúc nào đó nó cũng sẽ phải đầy. Do đó chúng ta cần 1 thuật toán để xác định nên bỏ đi page nào để lấy chỗ cho page mới.

Có nhiều thuật toán khác nhau để làm việc này. PostgreSQL từ bản 8.1 trở đi sử dụng thuật toán Clock Sweep thay cho LRU ở các phiên bản trước.

Ý tưởng là Clock Sweep là: ưu tiên loại bỏ page nào ít được truy suất nhất (usage_count), và tại thời gian xem xét, page đó đang không bị process nào truy suất (unpinned).

peusudo code

demonstration

Thông tin về số lượng truy suất, số lượng process đang truy suất page đó gọi là metadata của buffer slot đó, và được quản lý bởi Buffer descriptor. Chi tiết hơn về thuật toán tại đây

Khi dữ liệu trong buffer pool bị thay đổi.

Khi 1 request thực hiện logic modify dữ liệu của table, sự thay đổi đó sẽ được
áp dụng trực tiếp lên page tương ứng trong buffer (chứ ko phải là version gốc ở storage). Buffered page đã modify sẽ được goi là dirty.

Những thông tin mới này 1 lúc nào đó sẽ phải được persist xuống storage. Hành động này gọi là Flush dirty page Đảm nhận nhiện vụ này sẽ là 2 background process là checkpointerbackground writer.

Có 1 điểm thú vị ở đây. Như các bạn đã biết buffer pool nằm trên RAM, dữ liệu của RAM sẽ mất hết nếu hệ thống xảy ra sự cố (mất điện chẳng hạn). Vậy nếu page trở nên dirty, chưa kịp flush xống storage mà sự cố xảy ra thì đồng nghĩa là chúng ta sẽ bị mất những dữ liệu mới này. => Cần phải có 1 thành phần khác đảm nhiệm viêc này: WAL - Write Ahead Log(ging)

Chi tiết của WAL sẽ nằm ngoài scope của bài viết này. Ý tưởng của WAL sẽ là: Nếu 1 hành động nào đó làm thay đổi trạng thái của dữ liệu, sự thay đổi đó sẽ được log lại trước cả khi buffered page được cập nhật. Nếu sự cố xảy ra thì hệ thống sẽ xem xét lại các log chưa được xử lý và đảm bảo là dữ liệu nguyên vẹn.

References:

http://r.grokking.org/blog-sql-server-memory-buffer-pools
http://r.grokking.org/blog-interdb-pgsql
http://r.grokking.org/blog-understanding-dirty-pages-and-buffer-cache