ZStandard - Nén và giải nén dữ liệu nhanh hơn, hiệu quả hơn

Việc lưu trữ dữ liệu ngày nay đã trở nên phổ biến và đơn giản hơn rất nhiều. Những thiết bị lưu trữ ngày càng nhỏ nhưng có thể chứa được lượng dữ liệu lớn. Vì thế, nhiều người ít quan tâm tới vấn đề nén dữ liệu để giảm dung lượng lưu trữ.

Tuy nhiên, cùng với sự phát triển của điện toán đám mây, nhiều ứng dụng đã sử dụng dịch vụ đám mây để lưu trữ và xử lý dữ liệu. Vấn đề lưu trữ trên đám mây luôn được quan tâm bởi vì dung lượng lưu trữ trên mây khá hạn chế và chi phí cũng khá cao, do đó người ta luôn tìm cách giảm kích thước các file một cách tối đa để tối ưu hóa không gian lưu trữ.

Tại hội nghị Scale 2016 vừa qua, Facebook đã giới thiệu Zstandard 1.0 – thuật toán mã nguồn mở dùng để nén và giải nén theo thời gian thực. Nó được giới thiệu là nhanh hơn trong việc nén và giải nén, cũng như có tỉ lệ nén cao hơn so với thuật toán nén hiện tại.

So sánh với các thuật toán hiện nay

Để đánh giá chất lượng của một thuật toán nén, ta đánh giá dựa trên 3 thông số sau:

• Tỉ lệ nén (Compression ratio): tỉ lệ giữa file gốc và file sau khi đã được nén. Giá trị này thường lớn hơn 1.0 (Tỉ lệ càng lớn tức hiệu quả nén càng tốt).
• Tốc độ nén: Tốc độ thuật toán để nén file, tính bằng MB/s
• Tốc độ giải nén: Tốc độ khôi phục lại file gốc từ file đã nén, tính bằng MB/s.

Trong 3 thông số này, thông thường các thuật toán nén sẽ ưu tiên một thông số và chấp nhận hy sinh những thông số còn lại (Ví dụ tỉ lệ nén cao thì tốc độ nén và giải nén sẽ chậm; Tốc độ nén và giải nén cao thì tỉ lệ nén thấp). Do đó tùy vào nhu cầu và mục đích sử dụng mà người dùng có thể lựa chọn thuật toán phù hợp với nhu cầu.

Các thuật toán nén thông dụng hiện nay đang được sử dụng là zlib, lz4, xz. Mỗi thuật toán phục vụ một nhu cầu riêng:

• Ø Lz4: Tập trung vào tốc độ nén và giải nén.
• Ø Xz: tập trung vào tỉ lệ nén.
• Ø Zlib: Cân bằng giữa tốc độ và tỉ lệ nén.

Hình ảnh so sánh tốc độ nén, giải nén cũng như tỉ lệ nén của các thuật toán hiện nay.

Cơ chế

ZStandard được phát triển dựa trên việc kế thừa zlib cũng như ứng dụng những thành tựu về mặt vật lý của phần cứng.

1. Bộ nhớ

Theo thiết kế thông thường vào những năm 90, zlib bị giới hạn trong 32KB bộ nhớ. Tuy nhiên, với sự phát triển của phần cứng hiện tại, các ứng dụng có thể truy cập và sử dung nhiều bộ nhớ hơn.

ZStandard không bị giới hạn và có thể truy cập và sử dụng tới 1 Terabytes bộ nhớ (tuy nhiên điều này hiếm khi xảy ra). Thông thường thì nên giới hạn bộ nhớ sử dụng ở 8MB.

2. Thiết kế để thực hiện tiến trình song song

CPUs ngày nay rất mạnh mẽ và có thể giải quyết nhiều lệnh trong một chu kỳ nhờ vào phát triển của công nghệ ALUs (arithmetic logic units). Chúng ta cùng coi ví dụ sau:

a = b1 + b2;
c = d1 + d2;

Trong trường hợp này, giữa biến “a” và “c” không có môi liên kết nào, nên nó sẽ có thể thực hiện tính toán song song. Điều đó có nghĩa là để tận dụng được sức mạnh của các CPU hiện đại, thuật toán phải thiết kế sao cho dữ liệu không bị phụ thuộc lẫn nhau.

ZStandard đã thực hiện việc này bằng cách chia nhỏ dữ liệu ra thành nhiều dòng dữ liệu có thể xử lý song song (Sử dụng Huffman decoder – Huff0).

Sử dụng thực tế

1. Đối với dữ liệu bình thường

ZStandard có cả ở 2 phiên bản : command line và library (thư viện). Được viết bằng ngôn ngữ C nên nó có thể phù hợp với tất cả các platform thường dùng hiện nay – server, laptop, kể cả điện thoại. Chỉ cần get repository từ github và compile với câu lệnh make install và sử dụng như sử dụng gzip.

$ zstd access.log
access.log  :  8.07%   (6695078 => 540336 bytes, access.log.zst)

Ngoài ra có thể sử dụng trong command pipeline.

$ mysqldump --single-transaction --opt pokemon | zstd -q -o /srv/backups/mysqldump.sql.zst

Đối với câu lệnh tar hỗ trợ các thuật toán nén khác nhau, ta có thể sử dụng.

$ time tar -I zstd -cf linux-4.6.4.tar.zst linux-4.6.4
tar -I zstd -cf linux-4.6.4.tar.zst linux-4.6.4  
3.15s user 0.50s system 107% cpu 3.396 total

$ time tar -zcf linux-4.6.4.tar.gz linux-4.6.4
tar -zcf linux-4.6.4.tar.gz linux-4.6.4  
13.74s user 0.43s system 102% cpu 13.784 total

2. Đối với dữ liệu nhỏ

Đối với dữ liệu nhỏ, thông thường các thuật toán nén đều gặp khó khăn trong việc nâng cao tỉ lệ nén. Nguyên nhân là do các thuật toán nén đều học cách nén những dữ liệu từ các dữ liệu trong quá khứ, thế nhưng đối với các dữ liệu nhỏ, mọi thứ đều bắt đầu từ zero nên thuật toán không có dữ liệu quá khứ để dựa vào.

Để giải quyết vấn đề này, Zstd đã đưa ra phương án “training mode“, bằng cách sử dụng một vài mẫu thử cho thuật toán. Kết quả của việc training sẽ được lưu trong file gọi là “dictionary” – có thể load lên lúc nén và giải nén. Khi sử dụng “dictionary” cho việc nén, tỉ lệ nén sẽ tăng lên đáng kể!

Cách sử dụng

• Tạo file “dictionary”

<span class="pln">zstd </span><span class="pun">--</span><span class="pln">train </span><span class="typ">FullPathToTrainingSet</span><span class="com">/* -o dictionaryName</span>

• Nén dữ liệu với “dictionary”

zstd FILE -D dictionaryName

• Giải nén với “dictionary”

zstd --decompress FILE.zst -D dictionaryName

Ứng dụng

Hiện tại, thuật toán này đã được implement trên các ngôn ngữ lập trình sau:

Ngoài ra, chúng ta còn có phiên bản window với ứng dụng 7-zip sử dụng ZStandard: https://mcmilk.de/projects/7-Zip-zstd/

Tham khảo

• https://code.facebook.com/posts/1658392934479273/smaller-and-faster-data-compression-with-zstandard/
• http://facebook.github.io/zstd/