Cấu trúc dữ liệu và giải thuật - Chương 2: Truy nhập dữ liệu đa phương tiện

Nguyễn Thị Oanh Bộ môn HTTT – Viện CNTT & TT oanhnt@soict.hut.edu.vn Chương 2: Truy nhập dữ liệu đa phương tiện 1 Đặt vấn đề 2  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% YouTube_May_Lose_470_Million_In_2009_Analysts.php Đặt vấn đề 3  YouTube Video Server (2010): – May 2010, 2 Billion videos served per day – More than 24 hours of video uploaded every minute (and +) (2011: 48h /minute) – Videos usually less than 10 minutes long – Top videos ("Evolution of Dance", "Charlie Bit My Finger", and Lady Gaga's "Bad Romance“) are approaching 200 million views  billion-served-per-day/ Đặt vấn đề 4  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) Đặt vấn đề 5  Dành cho dữ liệu động, DL có thông số thời gian – Audio – Video  DL đòi hỏi tính liên tục (continuous) được đảm bảo  DL tĩnh: – Các phương pháp biểu diễn DL đa chiều: B-tree, R-tree, 1. Truy nhập dữ liệu đa phương tiện từ đĩa từ 6 Nhắc lại: cấu trúc đĩa từ 7  Nhiều đĩa phẳng (platters), xếp đồng trục trên 1 trục chính (spindle)  Các cần di chuyển đầu đọc/ghi được gắn chung trên 1 trục quay  Mỗi mặt đĩa có 1 đầu đọc/ghi Cấu trúc đĩa từ 8  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: – Tập các tracks có cùng bán kính trên tất cả các mặt đĩa Truy nhập đĩa từ 9  2 bước: – phép dịch (seek operations): tìm đến track có chứa địa chỉ cần tìm kiếm  seek time  tăng tốc (acceleration phase)  chạy ổn định (coast phase)  giảm tốc độ (deceleration phase)  ổn định vị trí (settle phase) – phép quay (rotational operations) rotational latency (spin time) Thời gian = tgian dịch + tgian quay + tgian đọc DL Truy nhập đĩa từ 10  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 Truy nhập đĩa từ 11 Ký hiệu Ý nghĩa tj , j Vị trí đầu đọc hiện tại: sector j, track tj ti, i Vị trí DL sẽ được đọc: sector i, track ti rd mật độ dữ liệu (MB/sector) dtr tốc độ đọc DL (MB/giây) rv vận tốc dịch trung bình của cần di chuyển đầu đọc/ghi rnum số vùng trên mỗi mặt đĩa ss tốc độ quay (độ / phút) Thời gian đọc DL 12 dtr rd jitimespinttSkjireadtime ji  ),(_),(),(   ssrnum rnumjiabsjitimespin 1360 mod)(),(_  rv ttabs ttSk ji ji )( ),(   Phương pháp lưu trữ phổ biến 13  RAID: Redundant Array of Inexpensive Disks – RAID-0 – RAID-1 – RAID-5 – RAID-2, RAID-3, RAID-4, RAID0+1, RAID1+0,  Nguyên tắc: ghép nhiều ổ đĩa cứng vật lý thành một hệ thống ổ đĩa cứng – gia tăng tốc độ đọc/ghi dữ liệu – hoặc/và nhằm tăng thêm sự an toàn của dữ liệu  Khái niệm: – block: khối DL nhỏ nhất được quan tâm khi đọc, ghi RAID-0 14 – 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 RAID-0 15 – Movie 1: blocks: b0, b1, b2, b3, b4 với k = 3 bắt đầu từ đĩa 0 – Movie 2: blocks: c0, c1, c2, c3, c4, c5 với k = 4 bắt đầu từ đĩa 1 – Tổng quát: các block liên tiếp b0, b1, b2, ..., br-1 lưu trữ trong RAID 0 với nhóm k đĩa bắt đầu ở đĩa j  block bi sẽ được lưu vào đĩa (i+j) mod k RAID-0 16  Ư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 RAID-1 17  Sử dụng khái niệm đối xứng (mirroring): – Mỗi đĩa có 1 đĩa đối xứng – Nếu có N đĩa có thể sử dụng  chỉ có n = N/2 đĩa được sử dụng đồng thời. – Striping có thể được sử dụng cho n đĩa này  Ghi: ghi đồng thời lên đĩa chính + đĩa đối xứng  Đọc: từ đĩa chính hoặc từ đĩa đối xứng nếu đĩa chính hỏng  Ưu: tăng độ an toàn, tin cậy về DL  Nhược: tốn không gian lưu trữ (hiệu suất sử dụng:50%) RAID-1 18 RAID-1 + striping RAID-5 19  RAID-5: striping + parity checking – Cân đối được không gian lưu trữ và sự an toàn của DL  Mỗi nhóm k đĩa (cluster) sẽ có 1 đĩa parity giúp kiểm tra và phục hồi DL nếu 1 đĩa trong nhóm bị hỏng Ví dụ n=k = 4 RAID-5 20  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)  jDjDjDjD nn ....... 2101   RAID-5 21 – Giả sử D2 hỏng, giá trị các bit j của D1, D3, Dp lần lượt là (1, 1, 0) bit j của D2 ? – Tổng quá hóa ? D1 D2 D3 Dp (parity disk) = D1  D2  D3 1 1 1 1 1 1 0 0 1 0 1 0 1 0 0 1 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 RAID-5 22  Lưu ý: – Phần DL parity có thể được để trên nhiều đĩa khác nhau RAID-5 23  Ưu điểm: chỉ sử dụng 1 đĩa cho 1 cluster để phục hồi dữ liệu khi có sự cố sảy ra – Có thể đọc/ghi đồng thời trên nhiều đĩa – Hiệu năng sử dụng cao – Tăng độ tin cậy, an toàn của DL  Nhược điểm: – mỗi khi ghi dữ liệu trên 1 đĩa thì cũng phải cập nhật lại đĩa parity – không hoạt động hiệu quả khi nhiều hơn 1 đĩa gặp sự cố đồng thời – Ghi chậm hơn so với RAID-0 và RAID-1 QA 24  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 Yêu cầu lấy dữ liệu từ đĩa của nhiều clients? 25 Giải thuật 26  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) FCFS 27  Mỗi y/cầu của client được gán nhãn thời gian  Các y/c được phục vụ theo nhãn tgian này  VD: – Thứ tự phục vụ: R2, R1, R4, R3 RequestID ReqTime Est. Seek Est.Rotational Delay R1 10 24 3 R2 8 12 5 R3 14 30 6 R4 11 18 4 SCAN 28  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: – Thứ tự phục vụ: R2, R4, R1, R3 RequestID ReqTime Est. Seek (Num of tracks) Est.Rotational Delay R1 10 24 (8) 3 R2 8 12 (4) 5 R3 14 30 (10) 6 R4 11 18 (6) 4 SCAN - EDF 29  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: – Thứ tự phục vụ: R4, R1, R2, R3 Req.ID Req.Time Est. Seek (Num of tracks) Est.Rotational Delay Deadline R1 10 24 (8) 3 100 R2 8 12 (4) 5 120 R3 14 30 (10) 6 120 R4 11 18 (6) 4 100 SCAN - EDF 30  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: – Thứ tự phục vụ: R4, R1, R2, R3 Req.ID Req.Time Est. Seek (Num of tracks) Est.Rotational Delay Deadline R1 10 24 (8) 3 100 R2 8 12 (4) 5 120 R3 14 30 (10) 6 120 R4 11 18 (6) 4 100 Others 31  Group Sweeping  Mixed scheduling  Building Disk-based Media Server 32 Yêu cầu 33  Phục vụ đồng thời cho nhiều client  Client có thể: – Playback (xem thường) – Rewind (tua lại) – Fast-forward (tua đi) – Pause (tạm dừng), .. Yêu cầu 34  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 Tham số 35  Giả thiết: – Số đĩa server: n (d1, d2, , dn) – Số movie: k (m1, m2, , mk) – 1 movie = chuỗi liên tiếp các block, block có kích thước cố định – Block = 1 tập các frames liên tục (30 frames (1 giây); 5400 frames (3 phút) ) – b: 1 block của movie m, – r : là số block client xem trên 1 đơn vị thời gian – data(i, t): yêu cầu của client Ci tại thời điểm t về các khối DL Yêu cầu từ phía client 36  Xem bình thường (play – normal view):  Tua đi (fast-forward):  Tua lại (rewind):  Tạm dừng (pause): ffs: fast forward step rws: rewind step  )1,(),...,1,(),,(),(  rbmbmbmtidata  )()(&),(),( mbnumffsibrjffsjbmtidata   1)(&),(),(  rwsjbrirwsjbmtidata  ),(),( bmtidata  Yêu cầu từ phía client 37  Tổng quát hóa: – Các block được yêu cầu là: b, (b+ step), (b + 2*step), , (b + (len-1)*step)  play-normal viewing: step = 1  fast-forward: step = ffs  rewind: step = -rws  pause: step = 0   0,,,,),(  lensteplenbmtidata Giải thuật hỗ trợ chức năng VCR 38  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 Scenario 1: 1 client y/c 39 Client Hành động Định dạng data(client,t) Block được y/c MOD server u1 ở thời điểm t đang xem block 140, tốc độ r = 2 blocks/đơn vị thời gian, đang được Disk 1 phục vụ u1 Play (m, 140, 2, 1) 140, 141 Gửi yêu cầu đến Disk 1 Pause (m, 140, 1, 0) Giữ nguyên block 140 trên màn hình Fast-forword, ffs = 6 blocks/s (m, 140, 2, 6) 146, 152 Gửi y/c đến Disk 1 và Disk 2 Rewind, rws = 6 blocks/s (m, 140, 2, -6) 134, 128 Gửi y/c đến Disk 1 Scenario 2: 40  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 Scenario 2: 41 Thời điể m Client Hành động Định dạng data(client,t) Block được y/c MOD server t u1 xem block 140, tốc độ r = 2 blocks/s, đang được Disk 1 phục vụ u2 đang xem block 199, tốc độ r = 2 blocks/s t u1 fast-forward, ffs = 5 blocks/s (m, 140, 2, 5) 140, 145 Gửi y/c đến Disk 1 u2 play (m, 199, 2, 1) 199, 200 Gửi y/c đến Disk 2 t+1 u1 fast-forward, ffs = 5 blocks/s (m, 150, 2, 5) 150 (Disk 1& 2) 155 (Disk 2) C1: splitting u1: (m, 150, 1, 5) => D1 (m, 155, 1, 5) => D2 u2: (m, 201, 1, 1) => D2 (m, 202, 1, 1) => D3 C2:splitting&switching u1: splitting => D1, D2 u2: switching Chuyển toàn bộ giao dịch của u2 sang D3 (m, 201, 2, 1) => D3 42  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 Giải thuật () 43  Khi có nhiều yêu cầu (transactions) xảy ra, mỗi transaction được gán 1 nhãn ưu tiên Giao dịch Độ ưu tiên ban đầu Độ ưu tiên được đánh giá lại Ngừng sử dụng - Existing client 5 5 Đang sử dụng: Xem thường – normal viewing, Tua đi – fast-forwarding, Tua lại – rewind, Tạm dừng – pause (không cần splitting hoặc switching) 4 4 Đang sử đụng: (Xem thường, tua, tạm dừng) (cần splitting hoặc switching) 4 3 Đang ký mới - new (entering) client (không cần splitting hoặc switching) 2 2 Đang ký mới - new (entering) client (cần splitting hoặc switching) 2 1 Giải thuật () 44  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 Tiêu chí 45  Khi gán 1 client Cj cho DS di thì MOD server phải đảm bảo DS có đủ tài nguyên cho yêu cầu hiện tại của client: – Dữ liệu: Đĩa phải có DL được yêu cầu – Bộ đệm: đủ lớn – Tốc độ đọc DL: đủ nhanh Tiêu chí () 46 – 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 )(),,( ),(_ ibuftijbufref tiactivedj         buf(i) kích thước bộ đệm cho mỗi DS i. bufreq(j, i , t) Kích thước bộ đệm cần thiết ở DS i cho client Ci sao cho 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 Tiêu chí () 47 – Tốc độ đọc DL: tốc độ đọc của đĩa phải đảm bảo đủ nhanh để phục vụ cho client mới mà tránh không làm client khác bị đẩy ra )( ),( )(*),( ),( ),(_ idtr ticyctime idtrtiswitchtime tjcons tiactivedj         dtr(i) Tốc độ đọc (disk transfert rate), MB/giây cons(j, t) Tốc độ sử dụng dữ liệu của client Ci tại thời điểm t (tốc độ đọc dữ liệu từ bộ điệm của clients Ci ) 48 cyctime(i,t) Thời gian cần thiết để DS i phục vụ được hết các yêu cầu của các client ở thời điểm t switchtime(i, t) Thời gian cần thiết cho DS i để dịch chuyển đầu đọc từ vị trí DL của client này đến vị trí DL của client khác timealloc(i, j, t) thời gian để đọc yêu cầu từ mỗi client Cj ở thời điểm t: 2. Truy nhập dữ liệu từ CD-ROM 49 Cấu trúc 50  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ừ) Đọc dữ liệu từ CD ROM 51  VD: – CD có 100 sectors, vị trí đầu đọc hiện tại là sector 58 – Client muốn đọc các sectors 10, 30, 50, 70 và 90, – Bộ đệm của client có thể chứa được 3 sectors Đọc dữ liệu từ CD ROM 52  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 Đọc dữ liệu từ CD ROM 53  Cách 2: đưa đầu đọc vào vị trí 0 – Đọc sector 10, 30, 50 vào buffer – Sector 10 được sử dụng đọc sector 70 vào buffer – Sector 30 được sử dụng đọc sector 90 vào buffer – Đọc dữ liệu từ CD ROM 54  Đọ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 Yêu cầu về bộ đệm 55  Đảm bảo: – DL hiển thị liên tục phía client (continuity) – DL trên bộ đệm không bị ghi đè (buffer utilisation) 56 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 Xác định kích thước bộ đệm 57 – Trong tfill (s), server có thể đọc (tfill x bwd )(bytes) DL nén – 1s, client sử dụng cons bytes DL không nén – 1 byte DL nén tương đương cr bytes DL không nén – Thời gian tối đa client phải sử dụng DL không nén trong tfill (s) là: : hệ số thời gian cần thiết để giải nén DL trong chu kỳ tfill (s) fill fill fill t cons crdcrt t      crdcrcons cons   Xác định kích thước bộ đệm () 58 – Như vậy, trong tfill (s), server có thể ghi vào bộ đệm (bytes): – Client có thể đọc (bytes): Để đảm bảo chất lượng: dfill bwskt  )( crdcrt fill  crdcrt crdcrcons cons crdcrtbwskt fill filldfill     )( Xác định kích thước bộ đệm () 59 Kích thước bộ đệm tối thiểu: )1()()( )()(    dd d fill bwcrdcrconsbw crdcrconsbwsk t d dd d dfill bw bwcrdcrconsbw crdcrconsbwsk bwt     )1()()( )()( Scheduling retrieval of Multisectors from CDROMs 60  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) Placement Methods 61  Real-Time File (RTF): bộ (lf, bf, pf) Placement Methods 62  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:  1)1()()1()()(  fffi bpifstjpifstjfocc )()( 1 foccfocc i l i f   Start Assignment Problem 63 Xác định vị trí đầu cho 1 tập các file: f1, f2, , fn ??  Start Assignment Problem : NP –hard – Tập các file cần lưu trữ: f1, f2, , fn – Xác định các điểm đầu của các file sao cho không có xung đột tài nguyên: không có sector nào chứa DL thuộc nhiều hơn 1 file ?  )()(:,, jiji foccfoccjiff Placement 2 file 64 Disk vs.CD ROM 65 – Giá thành: CD rẻ – Tốc độ: tốc độ truyền DL chậm – Kích thước vật lý – Dung lượng bộ nhớ Bài tập 66  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 Bài tập () 67  RAID-5: – Trong 1 cluster có 2 đĩa DL hỏng thì có khả năng phục hồi không ? Giải thích ? – Một cách tổng quát nếu sử dụng đĩa parity thì DL ở đĩa hỏng được xác định như thế nào ? (giả sử chỉ 1 đĩa bị hỏng) Bài tập () 68  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 Bài tập () 69  Đánh giá hiệu quả của các thuật toán FCFS, SCAN, SCAN-EDF (giả sử vị trí đầu đọc luôn ở vị trí 0) về: – Tổng khoảng cách đầu đọc phải di chuyển – Thời gian cần thiết để thực hiện thuật toán Bài tập () 70  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ả 71