eo
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
HỆ CƠ SỞ DỮ LIỆU PHÂN TÁN
RIAK
BÀI TẬP LỚN MÔN CƠ SỞ DỮ LIỆU NÂNG CAO
Ngành: Công nghệ thông tin
Khóa: 18
Cán bộ hướng dẫn: PGS.TS Nguyễn Hà Nam
Nhóm 1:
Nguyễn Thanh Tịnh
Vương Đình Dũng
HÀ NỘI - 2012
Mục lục
1
MỞ ĐẦU 1
Chương 1: Tổng quan về Riak 2
Chương 2: Phân tích ưu nhược điểm của Riak 21
Chương 3: Một số ứng dụng có thể dùng Riak 26
Chương 4: Tổng kết 28
Tài liệu tham khảo 29
Danh sách các hình vẽ
Hình 1: Vòng tròn cụm 3
Hình 2: Tổ chức dữ liệu trong Bitcask 4
Hình 3: Cấu trúc 1 entry trong Bitcask 5
Hình 4: Cấu trúc file dữ liệu trong Bitcask 5
Hình 5: Cấu trúc keydir trong Bitcask 6
Hình 6: Tiến trình hợp nhất dữ liệu trong Bitcask 7
Hình 7: Cơ chế tạo bản sao dữ liệu 8
Hình 8: Vector Clock Pruning 17
Hệ cơ sở dữ liệu phân tán Riak

bằng millisecond cũng là đủ tốt cho rất nhiều ứng dụng.
Riak là hệ thống có tính sẵn sàng, tính scalability và khả năng chịu lỗi cao. Sau đây
chúng ta sẽ cùng tìm hiểu Riak được thiết kế như thế nào để đảm bảo được những mục
tiêu vừa được đề cập ở trên.
1.1. Cụm Riak
Mỗi cụm Riak là một không gian các số nguyên 160 bit, được mô hình hóa là một
vòng tròn được chia thành các partition bằng nhau. Mỗi máy chủ vật lý là một node, mỗi
node chứa 1 hoặc nhiều node ảo được gọi là vnode. Mỗi vnode sẽ phụ trách 1 partition
trên vòng tròn cụm.
Mỗi node trong hệ thống phụ trách 1/(tổng số node) vòng tròn. Số vnode tại mỗi
node sẽ được tính là (số partition / số node). Ví dụ, nếu vòng tròn cụm có 32 partition, có
4 node, thì số vnode trên mỗi node là 32/4 = 8. Cấu hình này được thể hiện thông qua
hình vẽ dưới đây:
Trang 2
Hệ cơ sở dữ liệu phân tán Riak
Hình 1: Vòng tròn cụm
Khi có node mới được thêm vào hoặc đưa 1 node ra khỏi vòng tròn cụm thì Riak sẽ
thực hiện phân bổ lại dữ liệu trên mỗi node một cách tự động.
Tất cả các node trong cụm là bình đẳng, không tồn tại khái niệm master node. Mỗi
node có đầy đủ khả năng để đáp ứng các request từ client.
1.2. Giao thức Gossip
Riak sử dụng giao thức gossip để chia sẻ và thông tin về trạng thái vòng tròn cụm,
và các thuộc tính của các bucket trong cụm. Bất cứ khi nào một node thay đổi vai trò của
nó trên vòng tròn cụm (như thêm/bớt partition), nó thông báo sự thay đổi này qua giao
thức gossip. Mỗi node sẽ định kỳ (mặc định là 60 giây) gửi thông tin trạng thái hiện tại
của vòng tròn cụm mà nó biết đến một số node được lựa chọn ngẫu nhiên.
Giao thức gossip nhằm phát hiện các node bị mất kết nối với vòng tròn cụm, và
tránh cho các request của client được chuyển hướng tới các node hỏng.
Giao thức gossip làm tăng tính nhất quán của dữ liệu. Nó phản ánh kịp thời node
nào sẽ phụ trách partition nào khi trên vòng tròn cụm có sự thay đổi số node.

Sau khi việc ghi dữ liệu vào file tích cực hoàn thành, một cấu trúc dữ liệu nằm trong
bộ nhớ trong có tên là “keydir” được cập nhật. keydir là một bảng băm thực hiện ánh xạ
mỗi khóa với một cấu trúc dữ liệu có kích thước cố định mô tả các thông tin về file, vị trí
của entry trong file, timestamp. Khi đã biết file id và vị trí của entry trong file, ta có thể
dễ dàng đọc được giá trị ứng với khóa.
Trang 5
Hệ cơ sở dữ liệu phân tán Riak
Hình 5: Cấu trúc keydir trong Bitcask
Khi thao tác ghi xảy ra, bảng keydir được cập nhật vị trí của dữ liệu mới nhất. Dữ
liệu cũ vẫn tồn tại trên đĩa, nhưng mọi hành động đọc dữ liệu về sau sẽ sử dụng phiên bản
mới nhất trong bảng keydir. Tiến trình hợp nhất dữ liệu sẽ xóa những dữ liệu cũ đi. Việc
đọc dữ liệu được thực hiện cực kỳ đơn giản, chỉ cần một thao tác nhảy vị trí trong file.
Khi đọc dữ liệu, đầu tiên ta tra cứu khóa trong bảng keydir, tìm được file id và vị trí entry
trong file, rồi tiến hành nhảy đến vị trí xác định trong file này và đọc dữ liệu ứng với
khóa.
Cơ chế lưu dữ liệu như trên khiến cho lượng dữ liệu được lưu tăng rất nhanh chóng,
do chúng ta chỉ ghi dữ liệu mới mà không động chạm đến dữ liệu cũ. Tiến trình hợp nhất
dữ liệu sẽ giải quyết vấn đề này. Tiến trình hợp nhất dữ liệu rà soát trên tất cả các file
đang ở trạng thái không tích cực (in-active) và tạo ra một tập các file dữ liệu mới chỉ chứa
các phiên bản “sống” hay các phiên bản mới nhất của dữ liệu ứng với các khóa hiện tại.
Tiến trình hợp nhất dữ liệu cũng tạo ra một file hint bên cạnh mỗi file dữ liệu mới. File
hint không chứa dữ liệu mà chỉ chứa các tham số định vị và đặc tả dữ liệu. File hint cho
phép việc tạo ra bảng keydir diễn ra nhanh chóng trong trường hợp ta cần tạo lại bảng này
từ 1 danh sách các file dữ liệu có sẵn, việc đọc file hint rõ ràng sẽ nhanh hơn nhiều so với
việc đọc file dữ liệu có kích thước lớn.
Trang 6
Hệ cơ sở dữ liệu phân tán Riak
Hình 6: Tiến trình hợp nhất dữ liệu trong Bitcask
Một số ưu điểm của việc sử dụng Bitcask
• Độ trễ khi đọc/ghi nhỏ.

lưu ở trên một số node nhất định trong cụm, tùy thuộc vào giá trị n_val được thiết lập cho
bucket.
Chọn giá trị n_val như thế nào phụ thuộc vào ứng dụng và hình thái dữ liệu. Nếu dữ
liệu có tính tạm thời và có thể được tạo lại một cách dễ dàng bởi ứng dụng thì việc chọn
giá trị n_val nhỏ giúp tăng hiệu suất đáng kể. Nếu bạn cần đảm bảo dữ liệu luôn sẵn sàng
kể cả khi có node bị mất kết nối thì việc chọn giá trị n_val cao sẽ giúp ngăn ngừa mất dữ
liệu. Bạn hy vọng tại một thời điểm chỉ có bao nhiêu node bị mất kết nối? Hãy chọn giá
trị n_val lớn hơn số node này và dữ liệu của bạn vẫn có thể truy cập được nếu số node này
thực sự bị mất kết nối. Giá trị n_val cũng tác động đến cách cư xử của các request đọc
Trang 8
Hệ cơ sở dữ liệu phân tán Riak
(GET) và ghi (PUT). Các tham số có thể tùy chỉnh thông qua các request này bị giới hạn
bởi giá trị n_val. Chằng hạn, nếu n_val = 3, giá trị R (Read Quorum) sẽ có giá trị lớn nhất
là 3. R là giá trị do client thiết lập nhằm đảm bảo tính nhất quán của dữ liệu. Một request
đọc dữ liệu với R = 2 sẽ yêu cầu 2 node phải trả về kết quả để thao tác đọc dữ liệu được
xem là thành công. Nếu giá trị R lớn hơn số node hiện tại có thể trả về dữ liệu thì thao tác
đọc dữ liệu sẽ bị lỗi.
Tiến trình Read Repair
Riak không khuyến khích việc thay đổi giá trị n_val sau khi bucket đã chứa dữ liệu.
Nếu n_val thay đổi, đặc biệt là khi ta tăng giá trị của nó, ta cần phải thực hiện tiến trình
Read Repair.
Read Repair xảy ra khi một thao tác đọc thành công, nhưng không phải tất cả các
bản sao của đối tượng cần đọc đều khớp với nhau. Tình huống này có thể xảy ra trong 2
trường hợp sau:
1) Có một node trả về thông điệp “not found”, nghĩa là nó không chứa bản sao của
dữ liệu.
2) Một node trả về bản sao với vector clock bị cũ so với vector clock của một thao
tác đọc đúng. Khái niệm vector clock sẽ được bàn chi tiết ở mục 1.7.
Khi 1 trong 2 trường hợp này xảy ra, Riak sẽ bắt những node trả về dữ liệu không
đúng phải cập nhật lại dữ liệu của mình dựa trên dữ liệu của thao tác đọc đúng.

{1096126227998177188652763624537212264741949407232, '[email protected]'},
{1278813932664540053428224228626747642198940975104, '[email protected]'}]
Khi 1 node A nhận được request này, nó sẽ băm khóa bucket-key và thu được 1 số
nguyên 160 bit, giả sử tên là DocIdx:
DocIdx = riak_core_util:chash_key({<<"my_bucket">>, <<"my_key">>})
1045375627425331784151332358177649483819648417632
Node A tìm kiếm các partition dựa trên giá trị DocIdx này trên vòng tròn cụm và thu
được 1 danh sách các partition phù hợp, gọi là danh sách preflist. Node A chỉ chọn
n_val=3 partition đầu tiên từ danh sách này, các partition còn lại được đưa vào danh sách
dự trữ, phòng khi có một số partition được chọn không sẵn sàng. Node A gửi 1 message
đến mỗi node cha của các partition được chọn, message này chứa Object và định danh
partition:
'[email protected]' ! {put, Object, 1096126227998177188652763624537212264741949407232}
Trang 10
Hệ cơ sở dữ liệu phân tán Riak
'[email protected]' ! {put, Object, 1278813932664540053428224228626747642198940975104}
'[email protected]' ! {put, Object, 0}
Nếu một trong số các partition được chọn không sẵn sàng, node A sẽ gửi object đến
một partition dự phòng. Khi message được gửi đến node dự phòng, message tham chiếu
object và định danh partition ban đầu. Chẳng hạn, nếu node ‘[email protected]’ không sẵn
sàng, node A sẽ cố gắng thử từng node dự phòng.
Giả sử node dự phòng sẵn sàng là ‘[email protected]’. Node A sẽ gửi một message
tới node dự phòng này với object và định danh partition ban đầu:
'[email protected]' ! {put, Object, 1278813932664540053428224228626747642198940975104}
Lưu ý rằng giá trị định danh partition trong message này giống với giá trị định danh
trong message đã được gửi cho node ‘[email protected]’ trước đó. Mặc dù
‘[email protected]’ không phải là node cha của partition đó nhưng nó hiểu rằng nó đang
giữ hộ object cho đến khi node ‘[email protected]’ hoạt động bình thường trở lại.
1.6. Xử lý các request
Việc xử lý các request tại mỗi partition là khá đơn giản. Mỗi node chạy một tiến

tượng. Kỹ thuật này được gọi là Link-walking. Link-walking có thể được dùng để trả về
một tập các đối tượng có liên quan với đối tượng gốc bằng chỉ một request. Chi tiết về
Link-walking được trình bày ở mục 1.9.
Ghi dữ liệu
Mỗi cập nhật cho một đối tượng dữ liệu được đánh dấu bằng 1 vector clock. Các
vector clock cho phép Riak xác định thứ tự thao tác và phát hiện các xung đột trong 1 hệ
thống phân tán.
Riak sử dụng 2 cách để giải quyết các xung đột trong việc cập nhật các đối tượng dữ
liệu: cho phép lần cập nhật gần nhất giành chiến thắng hoặc trả về cho client tất cả các
phiên bản của đối tượng dữ liệu. Điều này tạo cho client cơ hội tự nó giải quyết xung đột.
Riak cho phép client thiết lập 1 giá trị W cho mỗi cập nhật. Giá trị W xác định số
node phải báo cáo cập nhật thành công để 1 thao tác cập nhật được xem là hoàn thành.
(N-W) là số node có thể bị mất kết nối mà cụm Riak vẫn có thể cho phép thao tác ghi
được đáp ứng.
Trang 12
Hệ cơ sở dữ liệu phân tán Riak
1.7. Giải quyết xung đột
Với việc mọi node đều có thể nhận và xử lý các request, cần có một phương pháp để
kiểm tra phiên bản nào của dữ liệu là mới nhất. Khái niệm vector clock được sử dụng để
giải quyết vấn đề này. Khi một đối tượng dữ liệu được lưu trong Riak, nó được đánh dấu
bằng 1 vector clock. Sau mỗi lần cập nhật dữ liệu, vector clock này cũng được cập nhật
sao cho Riak có thể so sánh được 2 phiên bản khác nhau của đối tượng dữ liệu và có khả
năng xác định những điều sau:
• Một đối tượng dữ liệu có phải là con cháu trực tiếp của 1 đối tượng dữ liệu
khác hay không.
• Các đối tượng dữ liệu có chung 1 đối tượng dữ liệu cha hay không.
• Các đối tượng dữ liệu không nằm trên cùng 1 cây phả hệ.
Sử dụng kiến thức trên, Riak có khả năng tự động sửa chữa những dữ liệu không
được đồng bộ, hoặc ít nhất là nó có thể cung cấp cho client cơ hội để tự lựa chọn phiên
bản dữ liệu phù hợp.

$ curl -v -X PUT -H "Content-Type: application/json" -d '{"props":{"allow_mult":true}}'
\
http://127.0.0.1:8098/riak/kitchen
# create an object we will create a sibling of
$ curl -v -X POST -H "Content-Type: application/json" -d '{"dishes":11}' \
http://127.0.0.1:8098/riak/kitchen/sink?returnbody=true
# the easiest way to create a sibling is update the object without
# providing a vector clock in the headers
$ curl -v -X PUT -H "Content-Type: application/json" -d '{"dishes":9}' \
http://127.0.0.1:8098/riak/kitchen/sink?returnbody=true
Có thể lấy danh sách các sibling của đối tượng dữ liệu trong ví dụ này về thông qua
lệnh:
$ curl http://127.0.0.1:8098/riak/kitchen/sink
Khi đó Riak sẽ trả về 1 danh sách các vtag, mỗi vtag là 1 khóa duy nhất, giúp phân
biệt các sibling. Client sẽ dùng vtag để lấy sibling tương ứng về. Trong ví dụ này,
message mà client nhận được sẽ có định dạng như sau:
Trang 14
Hệ cơ sở dữ liệu phân tán Riak
Siblings:
175xDv0I3UFCfGRC7K7U9z
6zY2mUCFPEoL834vYCDmPe
Có thể lấy sibling tương ứng với vtag đầu tiên thông qua lệnh:
$ curl http://127.0.0.1:8098/riak/kitchen/sink?vtag=175xDv0I3UFCfGRC7K7U9z
Khi đó Riak sẽ trả về sibling sau: {"dishes":9}
Client cũng có thể lấy về tất cả các sibling chỉ với 1 request nếu header của request
là "Accept: multipart/mixed".
Giải quyết xung đột
Khi có nhiều giá trị để lựa chọn cho một đối tượng dữ liệu, bạn cần xác định giá trị
nào là đúng. Điều này có thể được thực hiện tự động bởi ứng dụng hoặc do người dùng
quyết định. Để cập nhật giá trị đúng cho đối tượng, bạn cần sử dụng giá trị vector clock

tượng mà không có cơ chế hòa giải xung đột. Điều này có thể dẫn đến vô số vấn đề tồi tệ
trên hệ thống. Việc có một đối tượng khổng lồ trên 1 node có thể khiến cho những thao
tác đọc đối tượng này làm cho node xảy ra sự cố. Các vấn đề khác có thể tính đến như
làm tăng độ trễ khi truy cập dữ liệu hay các lỗi tràn bộ nhớ.
Vấn đề bùng nổ dung lượng vector clock
Bên cạnh vấn đề bùng nổ số lượng sibling, độ lớn vector clock cũng có thể tăng lên
rất lớn khi có một lượng lớn các thao tác cập nhật xảy ra trên 1 đối tượng dữ liệu trong 1
khoảng thời gian ngắn. Riak sử dụng kỹ thuật Vector clock pruning để ngăn ngừa dung
lượng vector clock tăng lên quá nhanh. Ta sẽ nói thêm về kỹ thuật này bên dưới.
Vector Clock Pruning
Riak dùng kỹ thuật Vector Clock Pruning để ngăn ngừa sự gia tăng đột biến của
dung lượng các vector clock. Kỹ thuật này sử dụng 4 tham số sau:
• small_vclock
• big_vclock
• young_vclock
• old_vclock
Trang 16
Hệ cơ sở dữ liệu phân tán Riak
Hai tham số small_vclock và big_vclock liên quan đến độ dài của danh sách các
entry trong vector clock. Nếu độ dài của danh sách nhỏ hơn giá trị small_vclock, vector
clock sẽ không bị tỉa bớt. Nếu độ dài lớn hơn giá trị big_vclock nó sẽ bị tỉa bớt.
Các tham số young_vclock và old_vclock liên quan đến timestamp của mỗi entry.
Nếu độ dài danh sách nằm giữa 2 giá trị small_vclock và big_vclock, tuổi của từng entry
sẽ được kiểm tra. Nếu entry trẻ hơn giá trị young_vclock, vector clock sẽ không bị tỉa bớt.
Nếu entry già hơn giá trị old_vclock, vector clock sẽ bị tỉa bớt.
Hình 8: Vector Clock Pruning
1.8. Map-Reduce
Map-Reduce trong Riak cho phép xử lý dữ liệu theo thời gian thực và xử lý song
song. Các job của Map-Reduce được chứa trong định dạng JSON mô tả các input, các
phase, và thời gian timeout của 1 job. Một job có thể bao gồm một số tùy ý các Map

Danh sách input của một map phase phải là một danh sách các cặp khóa dữ liệu
bucket-key. Với mỗi khóa, Riak sẽ gửi request ước lượng hàm map đến partition A chứa
đối tượng dữ liệu có khóa là khóa này. Vnode đảm nhận partition A sẽ tìm đối tượng dựa
theo khóa, và ước lượng hàm map với đối tượng tìm được là tham số. Các tham số khác
của hàm map có thể là dữ liệu static của phase được xác định trong truy vấn.
Việc tìm dữ liệu được xử lý song song và tỉ lệ với số node trong vòng tròn cụm.
Riak ghi nhớ kết quả của việc tìm dữ liệu nhằm giảm tải cho storage backend.
Link phase
Trang 18
Hệ cơ sở dữ liệu phân tán Riak
Link phase là phiên bản đặc biệt của map phase. Một link phase tìm các đối tượng
dựa vào link-walking. Các link phase có thể được dùng để thực hiện xử lý map/reduce
trên tập các đối tượng liên quan nhau.
Reduce phase
Reduce phase có thể thực hiện xử lý tùy ý trên dữ liệu nhận được từ map phase hoặc
link phase. Không giống CouchDB, Reduce phase của Riak không được yêu cầu chỉ trả
về một câu trả lời duy nhất.
1.9. Link-walking
Link-walking là một trong những kỹ thuật nổi bật nhất của Riak.
Các link là metadata thiết lập các mối quan hệ một chiều giữa các đối tượng dữ liệu
trong Riak. Link cho phép bạn thực hiện những truy vấn lần theo (walk) các mối quan hệ
từ một đối tượng đến một đối tượng khác. Với link, bạn có thể tạo ra các con trỏ (pointer)
giữa các dữ liệu của bạn, chẳng hạn, con trỏ trỏ từ ‘projects’ đến ‘milestones’, rồi từ
‘milestones’ đến ‘tasks’, sau đó lấy dữ liệu dọc theo cây sử dụng các lệnh từ client API.
Link là một đặc trưng rất mạnh của Riak.
Các thao tác đọc và cập nhật link được thực hiện thông qua sử dụng HTTP Link
header. Header này mô phỏng ý nghĩa của các thẻ <link> trong HTML, đó là tạo ra mối
quan hệ đến các tài nguyên HTTP khác. Riak sử dụng định dạng khai báo link như sau:
Link: </riak/bucket/key>; riaktag= "tag"
Bên trong cặp dấu (<,>) là đường dẫn URL tương đối đến đối tượng dữ liệu khác

của node này cho đến khi nó được kết nối trở lại hệ thống, đây là kỹ thuật Hinted handoff.
Nếu node đó không kết nối lại được, người dùng có thể bổ sung 1 node mới và vòng tròn
cụm sẽ tự động thực hiện cân bằng tải.
Riak được phát triển dựa trên một nền tảng tốt. Riak được viết dựa trên Erlang - với
nguyên lý thiết kế OTP (Open Telecommunications Platform). Một khía cạnh của OTP là
các tiến trình trong hệ thống được tổ chức trên 1 cây giám sát. Khi 1 tiến trình bị chết, nó
sẽ được khởi động lại từ tiến trình giám sát của nó.
Tính sẵn sàng và tính Scalability cao
Điều này có được là do Riak là một phiên bản cài đặt của Amazon Dynamo.
Nếu cần nhiều dung lượng lưu trữ hơn, thông lượng lớn hơn hay có tính sẵn sàng
hơn, chỉ cần thêm node vào vòng tròn cụm Riak.
Điều gì khiến cho Riak có khả năng mở rộng xử lý hơn MongoDB, CouchDB hay
MySQL? Đó là nó được xây dựng ngay từ đầu với khái niệm không có bản sao chính.
Mọi node có vai trò bình đẳng trong cụm.
Hoàn toàn địa phương hóa dữ liệu
Không có master node. Mỗi node đều có khả năng nhận và xử lý mọi request từ
client.
Độ trễ thấp và thông lượng lớn
Trang 21
Hệ cơ sở dữ liệu phân tán Riak
- Sử dụng hàm băm khóa để cân bằng tải tốt.
- Xử lý truy vấn song song với Map-Reduce.
- Ưu điểm của storage backend mặc định - Bitcask.
HTTP + JSON
Riak sử đụng Erlang để viết bộ công cụ xây dựng các tài nguyên HTTP (HTTP
resource) tuân theo RFC. Điều này có nghĩa là, khi tương tác với 1 hệ thống Riak, bạn có
thể dùng các HTTP request theo cách tự nhiên và lấy về các kết quả ở dạng JSON. Tác
dụng chủ yếu của việc kết hợp Riak với các tài nguyên HTTP là hệ thống vận hành trơn
tru với những hạ tầng liên quan đến HTTP, bao gồm proxy, cache, và các loại client khác
nhau.