Bài giảng Cơ sở dữ liệu đa phương tiện - Chương 2: Truy nhập dữ liệu đa phương tiện - Nguyễn Thị Oanh

Nội dung text: Bài giảng Cơ sở dữ liệu đa phương tiện - Chương 2: Truy nhập dữ liệu đa phương tiện - Nguyễn Thị Oanh

1. Đặt vấn đề  Youtube: – 2009: over 1 billion videos per day – Bandwidth accounts for about 51% of expenses with a run rate of $1 million per day with content licensing accounting for 36% 2 YouTube_May_Lose_470_Million_In_2009_Analysts.php
2. Đặt vấn đề  Dailymotion: – Dailymotion is the second largest video site in the world after YouTube – 29th most visited website in the world – 114 millions unique visitors and more than 1,2 billions video views every month (Comscore, 5/2011) 4
3. 1. Truy nhập dữ liệu đa phương tiện từ đĩa từ 6
4. Cấu trúc đĩa từ  Track (A): – Nơi chứa DL – Vòng tròn đồng tâm trên các mặt đĩa  Region (B): – Mỗi mặt đĩa được chia thành k vùng đều nhau  Sector (C): – Là phần giao của mỗi track và region  Cluster (D): tập các sector  Cylinder: 8 – Tập các tracks có cùng bán kính trên tất cả các mặt đĩa
5. Truy nhập đĩa từ  Transfer rate (bandwidth) (TR): – MB/s – Tốc độ ghi và đọc thường khác nhau – Thường TR được ngầm hiểu là tốc độ đọc, còn tốc độ ghi thì thường được chỉ rõ  Vận tốc góc: – hầu hết các đĩa có vận tốc góc quay không đổi (constant angular veolocity - CAV) – Thời gian chuyển từ sector x -> sector y là giống nhau trên tất cả các track 10
6. Thời gian đọc DL rd readtime(i, j) Sk(t ,t ) spin_time(i, j) i j dtr abs(t t ) Sk(t ,t ) i j i j rv 360 1 spin_time(i, j) abs (i j)mod rnum rnum ss 12
7. RAID-0 – 1 đĩa điều khiển + n đĩa dữ liệu (0, 1, , n-1), n >= 2 – Sử dụng kỹ thuật phân chia (striping): chia dữ liệu thành các phần bằng nhau đặt trên nhiều đĩa và không có sự lặp lại DL – k-stripe: (k<n)  mỗi DL được phân chia trên nhóm gồm k đĩa (1 cluster)  mỗi nhóm có thể được bắt đầu từ bất kỳ đĩa nào 14
8. RAID-0  Ưu điểm: – Tốc độ đọc dữ liệu ra tăng lên do có thể đọc đồng thời từ k đĩa, tuy nhiên có giới hạn, phụ thuộc vào:  Kích thước bộ đệm  Độ rộng băng thông của đường bus cho thiết bị ra  Nhược điểm – Không đảm bảo tính tin cậy: nếu 1 đĩa hỏng mất dữ liệu và ảnh hưởng toàn bộ hệ thống 16
9. RAID-1 RAID-1 + striping 18
10. RAID-5  Giả sử – k = n đĩa (1 cluster), các đĩa được gán nhãn: 0, 1, 2, , n-1 – khối DL được lưu trong (n-1) đĩa, đĩa parity sẽ được xác định từ DL trong (n-1) đĩa  giả sử đĩa parity là đĩa thứ n-1  Di.j: dữ liệu bít thứ j của đĩa i  : phép hoặc loại trừ (exclusive-or) Dn 1. j D0. j  D1. j   Dn 2. j 20
11. RAID-5  Lưu ý: – Phần DL parity có thể được để trên nhiều đĩa khác nhau 22
12. QA  Phân biệt các khái niệm sau và mục đích, tác dụng của nó: – Striping – Mirroring – Parity 24
13. Giải thuật  Mục đích: Sắp xếp để thực hiện các yêu cầu đọc dữ liệu trên đĩa từ các client khác nhau  Các giải thuật phải chạy rất nhanh, i.e không mất quá nhiều thời gian để xác định thứ tự đọc DL  Một số giải thuật: – First Come First Served (FCFS) – SCAN – SCAN Earliest Deadline First (SCAN-EDF) 26
14. SCAN  Dựa trên số tracks cần di chuyển từ vị trí hiện thời của đầu đọc, tính theo 1 chiều (hướng ra tâm hoặc hướng vào tâm)  VD: RequestID ReqTime Est. Seek Est.Rotational (Num of tracks) Delay R1 10 24 (8) 3 R2 8 12 (4) 5 R3 14 30 (10) 6 R4 11 18 (6) 4 – Thứ tự phục vụ: R2, R4, R1, R3 28
15. SCAN - EDF  Dựa trên EDF (Earliest Deadline First) + số track  Mỗi y/cầu có 1 nhãn deadline nhóm theo thứ tự tăng dần trong mỗi nhóm, thực hiện SCAN  VD: Req.ID Req.Time Est. Seek Est.Rotational Deadline (Num of tracks) Delay R1 10 24 (8) 3 100 R2 8 12 (4) 5 120 R3 14 30 (10) 6 120 R4 11 18 (6) 4 100 – Thứ tự phục vụ: R4, R1, R2, R3 30
16. Building Disk-based Media Server 32
17. Yêu cầu  Với mỗi client, phải đảm bảo: – Xem được liên tục – Tốc độ đẩy DL vào buffer phải hợp lý:  Quá nhanh: DL bị ghi đè  Quá chậm: dịch vụ có thể bị gián đoạn 34
18. Yêu cầu từ phía client  Xem bình thường (play – normal view): data(i,t) (m,b),(m,b 1), , (m,b r 1)  Tua đi (fast-forward): data(i,t) (m,b j ffs ) j r &(b i ffs ) bnum(m)  Tua lại (rewind): data(i,t) (m,b j rws)i r &(b j rws) 1  Tạm dừng (pause): data(i,t) (m,b) ffs: fast forward step rws: rewind step 36
19. Giải thuật hỗ trợ chức năng VCR  Chức năng VCR (Video-Cassette-Recording): play, fast- forward, rewind, pause  Ví dụ: 1 MOD server, có 3 đĩa, giả sử chỉ có 1 movie, gồm 300 blocks đặt trên 3 đĩa 38
20. Scenario 2:  2 clients cùng xem đồng thời vào 1 movie  Ở thời điểm nào đó sẽ có 2 y/cầu truy nhập đồng thời Giả sử ở 1 thời điểm 1 đĩa server chỉ phục vụ được 1 client 40
21.  Splitting: – Một giao dịch của user bị cắt thành 2 hay nhiều phần nhỏ  Switching: – Một giao dịch của user được chuyển hẳn sang được phục vụ bởi 1 đĩa server khác 42
22. Giải thuật ( )  Sắp xếp theo thứ tự ưu tiên giảm dần  Các yêu cầu có thể thực hiện được được thực hiện theo thứ tự giảm dần độ ưu tiên  Y/cầu thoát khỏi hệ thống có độ ưu tiên cao nhất  Nếu 1 y/cầu không thể thực hiện được, không thể chuyển hẳn sang server khác thì chia nhỏ y/cầu (splitting) và chèn lại vào d/sách y/cầu với độ ưu tiên nhỏ hơn (3)  Các yêu cầu từ client mới có độ ưu tiên thấp nhất 44
23. Tiêu chí ( ) – Bộ đệm: Kích thước bộ đệm của đĩa i có khả năng phục vụ thêm cho client mới Cj hay không bufref ( j,i,t) buf(i) j d _ active(i,t) buf(i) kích thước bộ đệm cho mỗi DS i. Kích thước bộ đệm cần thiết ở DS i cho client C sao cho bufreq(j, i , t) i DL của Ci không bị ghi đè d_active(i, t) Tập các client đang được phục vụ bởi DS i ở thời điểm t 46
24. Thời gian cần thiết để DS i phục vụ được hết các yêu cyctime(i,t) cầu của các client ở thời điểm t Thời gian cần thiết cho DS i để dịch chuyển đầu đọc từ switchtime(i, t) vị trí DL của client này đến vị trí DL của client khác 48 timealloc(i, j, t) thời gian để đọc yêu cầu từ mỗi client Cj ở thời điểm t:
25. Cấu trúc  Chỉ có 1 đĩa phẳng – 1 track dài hình xoáy ốc, được chia thành các sector có độ dài giống nhau – Đầu đọc đĩa di chuyển dọc theo track với vận tốc không đổi (vận tốc dài, không phải vận tốc góc như đĩa từ) 50
26. Đọc dữ liệu từ CD ROM  Cách 1: sử dụng bộ đệm – Đọc sector 70 => 90 => 10 lưu vào bộ đệm – Sector 10 được lấy ra sử dụng sector 30 được đọc vào bộ đệm – Sector 30 được sử dụng sector 50 được đọc vào bộ đệm Phần lớn các thiết bị đọc CD không sử dụng cách này 52
27. Đọc dữ liệu từ CD ROM  Đọc theo vòng  Mỗi vòng bắt đầu từ vị trí 1  Trong mỗi chu trình, DL được sắp xếp theo thứ tự tăng dần của số sector 54
28. Ký hiệu Diễn giải Đơn vị ss Sector size bytes bwd Bandwidth of disk to prefetch buffer bytes/second dcr Decompression rate bytes/second cr Compression ratio integer cons Consumption rate of client Bytes/second sk Average seek time seconds tfill Buffer filling time seconds 56
29. Xác định kích thước bộ đệm ( ) – Như vậy, trong tfill (s), server có thể ghi vào bộ đệm (bytes): (t fill sk) bwd – Client có thể đọc (bytes):  t fill dcr cr Để đảm bảo chất lượng: (t fill sk) bwd  t fill dcr cr cons t dcr cr cons dcr cr fill 58
30. Scheduling retrieval of Multisectors from CDROMs  Server nhận các y/cầu để đọc tập sector {s1, s2, , sk},  Tốc độ dịch chuyển của đầu đọc: lv (linear velocity) Trình tự đọc các sector này thế nào ? – FCFS – SCAN – SCAN-EDF – (VD và tính seek time cho mỗi phương pháp) 60
31. Placement Methods  Real-Time File: bộ (lf, bf, pf) – lf: độ dài của file = số block – bf: kích thước khối = số sector / 1 khối – pf: chu kỳ của file = khoảng cách giữa 2 sector đầu tiên của 2 block liên tiếp nhau  Dễ dàng xác định các sector chứa DL nếu biết vị trí bắt đầu của file: st(f) – Tập các sector chiếm bởi block thứ i của 1 RTF: occi ( f ) j st( f ) (i 1) p f j st( f ) (i 1) p f bf 1 l f 62 occ( f ) occi ( f ) i 1
32. Placement 2 file 64
33. Bài tập  Giả sử có – 1 hệ thống MOD có 4 đĩa, sử dụng kiến trúc RAID-0 – có 3 movies m1 (10 blocks), m2 (14 blocks), m3 (7 blocks)  Dùng hình vẽ để thể hiện cách lưu trữ các khối DL trên các đĩa nếu: – Với mỗi movie, kỹ thuật striping được thực hiện trên cả 4 đĩa – Movie m1, m2 được striping trên cả 4 đĩa, còn movie m3 được striping trên đĩa 2,3, 4 66
34. Bài tập ( )  Truy nhập DL đĩa: – 1 đĩa, tốc độ đọc DL: k MB/s, bộ đệm: b MB – 2 clients:  C1: cons(C1) = r1 MB/s  C2: cons(C2) = r2 MB/s – Xem cùng 1 movie (size MB), bắt đầu cùng thời gian – Giả sử thời gian cần client đọc từ bộ đệm là = 0 Điều kiện gì để đảm bảo thỏa mãn được yêu cầu của 2 clients và không bao giờ phải đọc 1 block 2 lần từ đĩa 68
35. Bài tập ( )  Cho 2 file RTF f1, f2, kiểm tra xem 2 file có đảm bảo không xung đột không nếu – st(f1) = s1, st(f2) = s2 – f1 : (l1, b1, p1) – f2: (l2, b2, p2) 1) Kiểm tra = giá trị cụ thể: f1: (2, 2, 5), st(f1) = 2 f2: (3, 1, 4), st(f2)= 1 2) Viết thuật toán kiểm tra = mã giả 70