DOC PREVIEW
Berkeley COMPSCI 186 - Storing Data - Disks and Files

This preview shows page 1-2-3-18-19-37-38-39 out of 39 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 39 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Storing Data: Disks and FilesReviewDisks, Memory, and FilesDisks and FilesWhy Not Store Everything in Main Memory?The Storage HierarchyThought Experiment: How Much RAM?Quick ReviewJim Gray’s Storage Latency Analogy: How Far Away is the Data?DisksComponents of a DiskAccessing a Disk PageArranging Pages on DiskThought experimentDisk Space ManagementContextBuffer Management in a DBMSWhen a Page is Requested ...More on Buffer ManagementBuffer Replacement PolicyLRU Replacement Policy“Clock” Replacement PolicyDBMS vs. OS File SystemSlide 24Files of RecordsUnordered (Heap) FilesHeap File Implemented as a ListHeap File Using a Page DirectoryIndexes (a sneak preview)Record Formats: Fixed LengthRecord Formats: Variable LengthPage Formats: Fixed Length RecordsPage Formats: Variable Length RecordsSystem CatalogsAttr_Cat(attr_name, rel_name, type, position)pg_attributeSummarySummary (Contd.)Slide 39Storing Data: Disks and FilesLecture 5(R&G Chapter 9)“Yea, from the table of my memoryI’ll wipe away all trivial fond records.”-- Shakespeare, HamletReview•Aren’t Databases Great?•Relational model•SQLDisks, Memory, and FilesQuery Optimizationand ExecutionRelational OperatorsFiles and Access MethodsBuffer ManagementDisk Space ManagementDBThe BIG picture…Disks and Files •DBMS stores information on disks.–In an electronic world, disks are a mechanical anachronism!•This has major implications for DBMS design!–READ: transfer data from disk to main memory (RAM).–WRITE: transfer data from RAM to disk.–Both are high-cost operations, relative to in-memory operations, so must be planned carefully!Why Not Store Everything in Main Memory?•Costs too much. For ~$1000, PCConnection will sell you either –~20GB of RAM –~40GB of flash–~5 TB of disk•Main memory is volatile. We want data to be saved between runs. (Obviously!)The Storage HierarchySource: Operating Systems Concepts 5th Edition –Main memory (RAM) for currently used data.–Disk for the main database (secondary storage).–Tapes for archiving older versions of the data (tertiary storage).Smaller, FasterBigger, SlowerThought Experiment: How Much RAM?•Say your biz has –100,000 customers–10,000 products•Say space you need is–10K/customer–50K/product•How much space do you need?–1G cust + .5G product = 1.5G–Double it for space utilization = 3G–Times 10 for growth = 30G–at, say, $100/G =–… nothing! (to a company with 100,000 customers)Quick Review•1 millisecond = 1ms = 1/1000 second•1 microsecond = 1us = 1/1000 ms•1 nanosecond = 1ns = 1/1000 us•Clock rate 3Ghz, how long is a cycle?Jim Gray’s Storage Latency Analogy: How Far Away is the Data?RegistersOn Chip CacheOn Board CacheMemory Disk1ns210100Tape /Optical Robot109106SacramentoThis Lecture HallThis RoomMy Head10 min1.5 hr2 Years1 minPluto2,000 YearsAndromedaDisks•Secondary storage device of choice for ~40 years. •Main advantage over –tapes: random access vs. sequential–RAM: persistence, easy growth•Data is stored and retrieved in units called disk blocks or pages.•Unlike RAM, time to retrieve a disk block varies depending upon location on disk. –Therefore, relative placement of blocks on disk has major impact on DBMS performance!Components of a Disk Platters The platters spin (say, 120 rps).Spindle The arm assembly is moved in or out to position a head on a desired track. Tracks under heads make a cylinder (imaginary!).Disk headArm movementArm assemblyOnly one head reads/writes at any one time.TracksSector Block size is a multiple of sector size (which is fixed).Accessing a Disk Page•Time to access (read/write) a disk block:–seek time (moving arms to position disk head on track)–rotational delay (waiting for block to rotate under head)–transfer time (actually moving data to/from disk surface)•Seek time and rotational delay dominate.–Seek time varies between about 0.3 and 10msec–Rotational delay varies from 0 to 4msec–Transfer rate .01 - .05msec per 8K block•Key to lower I/O cost: reduce seek/rotation delays! Hardware vs. software solutions?Arranging Pages on Disk•`Next’ block concept: –blocks on same track, followed by–blocks on same cylinder, followed by–blocks on adjacent cylinder•Blocks in a file should be arranged sequentially on disk (by `next’), to minimize seek and rotational delay.•For a sequential scan, pre-fetching several pages at a time is a big win!Thought experiment•What is a good disk page size?–8K?–32K?–1Meg?•Why?Disk Space Management•Lowest layer of DBMS software manages space on disk (using OS file system or not?).•Higher levels call upon this layer to:–allocate/de-allocate a page–read/write a page•Best if a request for a sequence of pages is satisfied by pages stored sequentially on disk!–Responsibility of disk space manager.–Higher levels don’t know how this is done, or how free space is managed.–Though they may make performance assumptions!•Hence disk space manager should do a decent job.ContextQuery Optimizationand ExecutionRelational OperatorsFiles and Access MethodsBuffer ManagementDisk Space ManagementDBBuffer Management in a DBMS•Data must be in RAM for DBMS to operate on it!•Buffer Mgr hides the fact that not all data is in RAMDBMAIN MEMORYDISKdisk pagefree framePage Requests from Higher LevelsBUFFER POOLchoice of frame dictatedby replacement policyWhen a Page is Requested ...•Buffer pool information table contains: <frame#, pageid, pin_count, dirty> •If requested page is not in pool:–Choose a frame for replacement.Only “un-pinned” pages are candidates!–If frame is “dirty”, write it to disk–Read requested page into chosen frame•Pin the page and return its address.  If requests can be predicted (e.g., sequential scans) pages can be pre-fetched several pages at a time!More on Buffer Management•Requestor of page must eventually unpin it, and indicate whether page has been modified: –dirty bit is used for this.•Page in pool may be requested many times, –a pin count is used. –To pin a page, pin_count++– A page is a candidate for replacement iff pin count == 0 (“unpinned”)•CC & recovery may entail additional I/O when a frame is chosen for replacement. –Write-Ahead Log protocol; more later!Buffer Replacement Policy•Frame is chosen for replacement by a replacement policy:–Least-recently-used (LRU), MRU, Clock, etc.•Policy can have big impact on # of I/O’s;


View Full Document

Berkeley COMPSCI 186 - Storing Data - Disks and Files

Documents in this Course
Load more
Download Storing Data - Disks and Files
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Storing Data - Disks and Files and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Storing Data - Disks and Files 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?