這個(gè)算是google云數(shù)據(jù)庫(kù)的介紹吧-資料下載頁(yè)
2025-09-25 20:27本頁(yè)面
【正文】 s – Keep blocks small for random access (~64KB pressed data) – Exploit fact that many values very similar – Needs to be low CPU cost for encoding/decoding ? Two building blocks: BMDiff, Zippy BMDiff ? Bentley, Mcllroy DCC’99: “Data Compression Using Long?Common?Strings” ? Input: dictionary * source ? Output: sequence of – COPY: x bytes from offset y – LITERAL: literal text ? Store hash at every 32byte aligned boundary in – Dictionary – Source processed so far ? For every new source byte – Compute incremental hash of last 32 bytes – Lookup in hash table – On hit, expand match forwards amp。 backwards and emit COPY ? Encode: ~100MB/s, Decode: ~1000MB/s Zippy ? LZWlike: Store hash of last four bytes in 16K entry table ? For every input byte: – Compute hash of last four bytes – Lookup in table – Emit COPY or LITERAL ? Differences from BMDiff: – Much smaller pression window (local repetitions) – Hash table is not associative – Careful encoding of COPY/LITERAL tags and lengths ? Sloppy but fast: Algorithm % remaining Encoding Decoding Gzip % 21MB/s 118MB/s LZO % 135MB/s 410MB/s Zippy % 172MB/s 409MB/s BigTable Compression ? Keys: – Sorted strings of (Row, Column, Timestamp): prefix pression ? Values: – Group together values by “type” (. column family name) – BMDiff across all values in one family ? BMDiff output for values 1..N is dictionary for value N+1 ? Zippy as final pass over whole block – Catches more localized repetitions – Also catches crosscolumnfamily repetition, presses keys Compression Effectiveness ? Experiment: store contents for page crawl in BigTable instance – Key: URL of pages, with hostname portion reversed ? : – Groups pages from same site together ? Good for pression (neighboring rows tend to have similar contents) ? Good for clients: efficient to scan over all pages on a web site ? One pression strategy: gzip each page: ~28% bytes remaining ? BigTable: BMDiff + Zippy Type Count(B) Space(TB) Compressed %remaining Web page contents Links Anchors In Development/Future Plans ? More expressive data manipulation/access – Allow sending small scripts to perform read/modify/write transactions so that they execute on server? ? Multirow (. distributed) transaction support ? General performance work for very large cells ? BigTable as a service ? – Interesting issues of resource fairness, performance isolation, prioritization, etc. across different clients Fin ^^ ?Thanks !
公司管理相關(guān)推薦
鄂ICP備17016276號(hào)-1