· 8 years ago · Mar 13, 2018, 12:06 AM
1package edu.berkeley.cs186.database.table;
2
3import java.util.*;
4import java.io.Closeable;
5import java.nio.ByteBuffer;
6import java.util.concurrent.DelayQueue;
7
8import edu.berkeley.cs186.database.DatabaseException;
9import edu.berkeley.cs186.database.common.ArrayBacktrackingIterator;
10import edu.berkeley.cs186.database.common.BacktrackingIterator;
11import edu.berkeley.cs186.database.common.Bits;
12import edu.berkeley.cs186.database.databox.DataBox;
13import edu.berkeley.cs186.database.io.Page;
14import edu.berkeley.cs186.database.io.PageAllocator;
15import edu.berkeley.cs186.database.io.PageAllocator.PageIterator;
16
17/**
18 * # Overview
19 * A Table represents a database table with which users can insert, get,
20 * update, and delete records:
21 *
22 * // Create a brand new table t(x: int, y: int) which is persisted in the
23 * // file "t.table".
24 * List<String> fieldNames = Arrays.asList("x", "y");
25 * List<String> fieldTypes = Arrays.asList(Type.intType(), Type.intType());
26 * Schema schema = new Schema(fieldNames, fieldTypes);
27 * Table t = new Table(schema, "t", "t.table");
28 *
29 * // Insert, get, update, and delete records.
30 * List<DataBox> a = Arrays.asList(new IntDataBox(1), new IntDataBox(2));
31 * List<DataBox> b = Arrays.asList(new IntDataBox(3), new IntDataBox(4));
32 * RecordId rid = t.addRecord(a);
33 * Record ra = t.getRecord(rid);
34 * t.updateRecord(b, rid);
35 * Record rb = t.getRecord(rid);
36 * t.deleteRecord(rid);
37 *
38 * // Close the table. All tables must be closed.
39 * t.close();
40 *
41 * # Persistence
42 * Every table constructs a new PageAllocator which it uses to persist its data
43 * into a file. For example, the table above persists itself into a file
44 * "t.table". We can later run the following code to reload the table:
45 *
46 * // Load the table t from the file "t.table". Unlike above, we do not have
47 * // to specify the schema of t because it will be parsed from "t.table".
48 * Table t = new Table("t", "t.table");
49 * // Don't forget to close the table.
50 * t.close();
51 *
52 * # Storage Format
53 * Now, we discuss how tables serialize their data into files.
54 *
55 * 1. Each file begins with a header page into which tables serialize their
56 * schema.
57 * 2. All remaining pages are data pages. Every data page begins with an
58 * n-byte bitmap followed by m records. The bitmap indicates which records
59 * in the page are valid. The values of n and m are set to maximize the
60 * number of records per page (see computeDataPageNumbers for details).
61 *
62 * For example, here is a cartoon of what a table's file would look like if we
63 * had 5-byte pages and 1-byte records:
64 *
65 * Serialized Schema___________________________________
66 * / \
67 * +----------+----------+----------+----------+----------+ \
68 * Page 0 | 00000001 | 00000001 | 01111111 | 00000001 | 00000100 | |- header
69 * +----------+----------+----------+----------+----------+ /
70 * +----------+----------+----------+----------+----------+ \
71 * Page 1 | 1001xxxx | 01111010 | xxxxxxxx | xxxxxxxx | 01100001 | |
72 * +----------+----------+----------+----------+----------+ |
73 * Page 2 | 1101xxxx | 01110010 | 01100100 | xxxxxxxx | 01101111 | |- data
74 * +----------+----------+----------+----------+----------+ |
75 * Page 3 | 0011xxxx | xxxxxxxx | xxxxxxxx | 01111010 | 00100001 | |
76 * +----------+----------+----------+----------+----------+ /
77 * \________/ \________/ \________/ \________/ \________/
78 * bitmap record 0 record 1 record 2 record 3
79 *
80 * - The first page (Page 0) is the header page and contains the serialized
81 * schema.
82 * - The second page (Page 1) is a data page. The first byte of this data page
83 * is a bitmap, and the next four bytes are each records. The first and
84 * fourth bit are set indicating that record 0 and record 3 are valid.
85 * Record 1 and record 2 are invalid, so we ignore their contents.
86 * Similarly, the last four bits of the bitmap are unused, so we ignore
87 * their contents.
88 * - The third and fourth page (Page 2 and 3) are also data pages and are
89 * formatted similar to Page 1.
90 *
91 * When we add a record to a table, we add it to the very first free slot in
92 * the table. See addRecord for more information.
93 */
94public class Table implements Iterable<Record>, Closeable {
95 public static final String FILENAME_PREFIX = "db";
96 public static final String FILENAME_EXTENSION = ".table";
97
98 // The name of the database.
99 private String name;
100
101 // The filename of the file in which this table is persisted.
102 private String filename;
103
104 // The schema of the database.
105 private Schema schema;
106
107 // The allocator used to persist the database.
108 private PageAllocator allocator;
109
110 // The size (in bytes) of the bitmap found at the beginning of each data page.
111 private int bitmapSizeInBytes;
112
113 // The number of records on each data page.
114 private int numRecordsPerPage;
115
116 // The page numbers of all allocated pages which have room for more records.
117 private TreeSet<Integer> freePageNums;
118
119 // The number of records in the table.
120 private long numRecords;
121
122 // Constructors //////////////////////////////////////////////////////////////
123 /**
124 * Construct a brand new table named `name` with schema `schema` persisted in
125 * file `filename`.
126 */
127 public Table(String name, Schema schema, String filename) {
128 this.name = name;
129 this.filename = filename;
130 this.schema = schema;
131 this.allocator = new PageAllocator(filename, true);
132 this.bitmapSizeInBytes = computeBitmapSizeInBytes(Page.pageSize, schema);
133 numRecordsPerPage = computeNumRecordsPerPage(Page.pageSize, schema);
134 this.freePageNums = new TreeSet<Integer>();
135 this.numRecords = 0;
136
137 writeSchemaToHeaderPage(allocator, schema);
138 }
139
140 /**
141 * Load a table named `name` from the file `filename`. The schema of the
142 * table will be read from the header page of the file.
143 */
144 public Table(String name, String filename) throws DatabaseException {
145 this.name = name;
146 this.filename = filename;
147 this.allocator = new PageAllocator(filename, false);
148 this.schema = readSchemaFromHeaderPage(this.allocator);
149 this.bitmapSizeInBytes = computeBitmapSizeInBytes(Page.pageSize, this.schema);
150 this.numRecordsPerPage = computeNumRecordsPerPage(Page.pageSize, this.schema);
151
152 this.freePageNums = new TreeSet<Integer>();
153 this.numRecords = 0;
154
155 Iterator<Page> iter = this.allocator.iterator();
156 iter.next(); // Skip the header page.
157 while(iter.hasNext()) {
158 Page page = iter.next();
159 byte[] bitmap = getBitMap(page);
160
161 for (short i = 0; i < numRecordsPerPage; ++i) {
162 if (Bits.getBit(bitmap, i) == Bits.Bit.ONE) {
163 Record r = getRecord(new RecordId(page.getPageNum(), i));
164 numRecords++;
165 }
166 }
167
168 if (numRecordsOnPage(page) != numRecordsPerPage) {
169 freePageNums.add(page.getPageNum());
170 }
171 }
172 }
173
174 // Accessors /////////////////////////////////////////////////////////////////
175 public String getName() {
176 return name;
177 }
178
179 public String getFilename() {
180 return filename;
181 }
182
183 public Schema getSchema() {
184 return schema;
185 }
186
187 public PageAllocator getAllocator() {
188 return allocator;
189 }
190
191 public int getBitmapSizeInBytes() {
192 return bitmapSizeInBytes;
193 }
194
195 public int getNumRecordsPerPage() {
196 return numRecordsPerPage;
197 }
198
199 public long getNumRecords() {
200 return numRecords;
201 }
202
203 public int getNumDataPages() {
204 // All pages but the first are data pages.
205 return allocator.getNumPages() - 1;
206 }
207
208 public byte[] getBitMap(Page page) {
209 byte[] bytes = new byte[bitmapSizeInBytes];
210 page.getByteBuffer().get(bytes);
211 return bytes;
212 }
213
214 public static int computeBitmapSizeInBytes(int pageSize, Schema schema) {
215 // Dividing by 8 simultaneously (a) rounds down the number of records to a
216 // multiple of 8 and (b) converts bits to bytes.
217 return computeUnroundedNumRecordsPerPage(pageSize, schema) / 8;
218 }
219
220 public static int computeNumRecordsPerPage(int pageSize, Schema schema) {
221 // Dividing by 8 and then multiplying by 8 rounds down to the nearest
222 // multiple of 8.
223 return computeUnroundedNumRecordsPerPage(pageSize, schema) / 8 * 8;
224 }
225
226 // Modifiers /////////////////////////////////////////////////////////////////
227 private synchronized void insertRecord(Page page, int entryNum, Record record) {
228 int offset = bitmapSizeInBytes + (entryNum * schema.getSizeInBytes());
229 byte[] bytes = record.toBytes(schema);
230 ByteBuffer buf = page.getByteBuffer();
231 buf.position(offset);
232 buf.put(bytes);
233 }
234
235 /**
236 * addRecord adds a record to this table and returns the record id of the
237 * newly added record. freePageNums, and numRecords are updated
238 * accordingly. The record is added to the first free slot of the first free
239 * page (if one exists, otherwise one is allocated). For example, if the
240 * first free page has bitmap 0b11101000, then the record is inserted into
241 * the page with index 3 and the bitmap is updated to 0b11111000.
242 */
243 public synchronized RecordId addRecord(List<DataBox> values) throws DatabaseException {
244 Record record = schema.verify(values);
245
246 // Get a free page, allocating a new one if necessary.
247 if (freePageNums.isEmpty()) {
248 freePageNums.add(allocator.allocPage());
249 }
250 Page page = allocator.fetchPage(freePageNums.first());
251
252 // Find the first empty slot in the bitmap.
253 // entry number of the first free slot and store it in entryNum; and (2) we
254 // count the total number of entries on this page.
255 byte[] bitmap = getBitMap(page);
256 int entryNum = 0;
257 for (; entryNum < numRecordsPerPage; ++entryNum) {
258 if (Bits.getBit(bitmap, entryNum) == Bits.Bit.ZERO) {
259 break;
260 }
261 }
262 assert(entryNum < numRecordsPerPage);
263
264 // Insert the record and update the bitmap.
265 insertRecord(page, entryNum, record);
266 Bits.setBit(page.getByteBuffer(), entryNum, Bits.Bit.ONE);
267
268 // Update the metadata.
269 if (numRecordsOnPage(page) == numRecordsPerPage) {
270 freePageNums.pollFirst();
271 }
272 numRecords++;
273
274 return new RecordId(page.getPageNum(), (short) entryNum);
275 }
276
277 /**
278 * Retrieves a record from the table, throwing an exception if no such record
279 * exists.
280 */
281 public synchronized Record getRecord(RecordId rid) throws DatabaseException {
282 validateRecordId(rid);
283 Page page = allocator.fetchPage(rid.getPageNum());
284 byte[] bitmap = getBitMap(page);
285 if (Bits.getBit(bitmap, rid.getEntryNum()) == Bits.Bit.ZERO) {
286 String msg = String.format("Record %s does not exist.", rid);
287 throw new DatabaseException(msg);
288 }
289
290 int offset = bitmapSizeInBytes + (rid.getEntryNum() * schema.getSizeInBytes());
291 ByteBuffer buf = page.getByteBuffer();
292 buf.position(offset);
293 return Record.fromBytes(buf, schema);
294 }
295
296 /**
297 * Overwrites an existing record with new values and returns the existing
298 * record. An exception is thrown if rid does
299 * not correspond to an existing record in the table.
300 */
301 public synchronized Record updateRecord(List<DataBox> values, RecordId rid) throws DatabaseException {
302 validateRecordId(rid);
303 Record newRecord = schema.verify(values);
304 Record oldRecord = getRecord(rid);
305
306 Page page = allocator.fetchPage(rid.getPageNum());
307 insertRecord(page, rid.getEntryNum(), newRecord);
308 return oldRecord;
309 }
310
311 /**
312 * Deletes and returns the record specified by rid from the table and updates
313 * freePageNums, and numRecords as necessary. An exception is thrown
314 * if rid does not correspond to an existing record in the table.
315 */
316 public synchronized Record deleteRecord(RecordId rid) throws DatabaseException {
317 validateRecordId(rid);
318 Page page = allocator.fetchPage(rid.getPageNum());
319 Record record = getRecord(rid);
320 Bits.setBit(page.getByteBuffer(), rid.getEntryNum(), Bits.Bit.ZERO);
321
322 if(numRecordsOnPage(page) == numRecordsPerPage - 1) {
323 freePageNums.add(page.getPageNum());
324 }
325 numRecords--;
326
327 return record;
328 }
329
330 public void close() {
331 allocator.close();
332 }
333
334 // Helpers ///////////////////////////////////////////////////////////////////
335 private static Schema readSchemaFromHeaderPage(PageAllocator allocator) {
336 Page headerPage = allocator.fetchPage(0);
337 ByteBuffer buf = headerPage.getByteBuffer();
338 return Schema.fromBytes(buf);
339 }
340
341 private static void writeSchemaToHeaderPage(PageAllocator allocator, Schema schema) {
342 Page headerPage = allocator.fetchPage(allocator.allocPage());
343 assert(0 == headerPage.getPageNum());
344 ByteBuffer buf = headerPage.getByteBuffer();
345 buf.put(schema.toBytes());
346 }
347
348 /**
349 * Recall that every data page contains an m-byte bitmap followed by n
350 * records. The following three functions computes m and n such that n is
351 * maximized. To simplify things, we round n down to the nearest multiple of
352 * 8 if necessary. m and n are stored in bitmapSizeInBytes and
353 * numRecordsPerPage respectively.
354 *
355 * Some examples:
356 *
357 * | Page Size | Record Size | bitmapSizeInBytes | numRecordsPerPage |
358 * | --------- | ----------- | ----------------- | ----------------- |
359 * | 9 bytes | 1 byte | 1 | 8 |
360 * | 10 bytes | 1 byte | 1 | 8 |
361 * ...
362 * | 17 bytes | 1 byte | 1 | 8 |
363 * | 18 bytes | 2 byte | 2 | 16 |
364 * | 19 bytes | 2 byte | 2 | 16 |
365 */
366 private static int computeUnroundedNumRecordsPerPage(int pageSize, Schema schema) {
367 // Storing each record requires 1 bit for the bitmap and 8 *
368 // schema.getSizeInBytes() bits for the record.
369 int recordOverheadInBits = 1 + 8 * schema.getSizeInBytes();
370 int pageSizeInBits = pageSize * 8;
371 return pageSizeInBits / recordOverheadInBits;
372 }
373
374 private int numRecordsOnPage(Page page) {
375 byte[] bitmap = getBitMap(page);
376 int numRecords = 0;
377 for (int i = 0; i < numRecordsPerPage; ++i) {
378 if (Bits.getBit(bitmap, i) == Bits.Bit.ONE) {
379 numRecords++;
380 }
381 }
382 return numRecords;
383 }
384
385 private void validateRecordId(RecordId rid) throws DatabaseException {
386 int p = rid.getPageNum();
387 int e = rid.getEntryNum();
388
389 if (p == 0) {
390 throw new DatabaseException("Page 0 is a header page, not a data page.");
391 }
392
393 if (e < 0) {
394 String msg = String.format("Invalid negative entry number %d.", e);
395 throw new DatabaseException(msg);
396 }
397
398 if (e >= numRecordsPerPage) {
399 String msg = String.format(
400 "There are only %d records per page, but record %d was requested.",
401 numRecordsPerPage, e);
402 throw new DatabaseException(msg);
403 }
404 }
405
406 // Iterators /////////////////////////////////////////////////////////////////
407 public TableIterator ridIterator() {
408 return new TableIterator();
409 }
410
411 public RecordIterator iterator() {
412 return new RecordIterator(this, ridIterator());
413 }
414
415 public BacktrackingIterator<Record> blockIterator(Page[] block) {
416 return new RecordIterator(this, new RIDBlockIterator(block));
417 }
418
419 public BacktrackingIterator<Record> blockIterator(BacktrackingIterator<Page> block) {
420 return new RecordIterator(this, new RIDBlockIterator(block));
421 }
422
423 public BacktrackingIterator<Record> blockIterator(Iterator<Page> block, int maxRecords) {
424 return new RecordIterator(this, new RIDBlockIterator(block, maxRecords));
425 }
426
427 /**
428 * RIDPageIterator is a BacktrackingIterator over the RecordIds of a single
429 * page of the table.
430 *
431 * See comments on the BacktrackingIterator interface for how mark and reset
432 * should function.
433 */
434 public class RIDPageIterator implements BacktrackingIterator<RecordId> {
435 private byte[] bitmap;
436 private int pageNum;
437 private short cur;
438 private short mark;
439
440 public RIDPageIterator(Page page) {
441 this.pageNum = page.getPageNum();
442 this.bitmap = getBitMap(page);
443 }
444
445 public boolean hasNext() {
446 for (int i = cur; i < 8 * bitmap.length; i++) {
447 if (Bits.getBit(bitmap, i) == Bits.Bit.ONE) {
448 return true;
449 }
450 }
451
452 return false;
453 }
454
455 public RecordId next() {
456 while (Bits.getBit(bitmap, cur) == Bits.Bit.ZERO) {
457 cur++;
458 }
459
460 return new RecordId(pageNum, cur++);
461 }
462
463 public void mark() {
464 mark = (short) Math.max(0, (cur - 1));
465 }
466
467 public void reset() {
468 cur = mark;
469 }
470 }
471
472 /**
473 * Helper function to create a BacktrackingIterator from an Iterator of
474 * Pages, and a maximum number of pages.
475 *
476 * At most maxPages pages will be loaded into the iterator; if there are
477 * not enough pages available, then fewer pages will be used.
478 */
479 private static BacktrackingIterator<Page> getBlockFromIterator(Iterator<Page> pageIter, int maxPages) {
480 Page[] block = new Page[maxPages];
481 int numPages;
482 for (numPages = 0; numPages < maxPages && pageIter.hasNext(); ++numPages) {
483 block[numPages] = pageIter.next();
484 }
485 if (numPages < maxPages) {
486 Page[] temp = new Page[numPages];
487 System.arraycopy(block, 0, temp, 0, numPages);
488 block = temp;
489 }
490 return new ArrayBacktrackingIterator(block);
491 }
492
493 /**
494 * RIDBlockIterator is a BacktrackingIterator yielding RecordIds of a block
495 * of pages.
496 *
497 * A "block" is specified by a BacktrackingIterator of Pages: every single
498 * Page returned by the iterator is part of the block. Your code should only
499 * utilize this iterator's functionality for fetching pages, i.e. you should
500 * *not* fetch every Page from the block iterator into an array or collection.
501 *
502 * The mark and reset methods have been provided for you already, and work by
503 * saving a BacktrackingIterator of RecordIds over the appropriate page.
504 *
505 * The iterator maintains a few pieces of state:
506 * - block is simply the BacktrackingIterator<Page> specifying the pages in
507 * the block.
508 * - blockIter is a BacktrackingIterator over RecordIds of the current page we
509 * are iterating over.
510 * - prevRecordId is the last RecordId that next() returned.
511 * - nextRecordId is the next RecordId that next() will return.
512 *
513 * In addition to these, we maintain some state to help with the
514 * implementation of mark() and reset(); you should not need to use these
515 * for implementing next() and hasNext().
516 */
517 public class RIDBlockIterator implements BacktrackingIterator<RecordId> {
518 private BacktrackingIterator<Page> block = null;
519 private BacktrackingIterator<RecordId> blockIter = null;
520 private BacktrackingIterator<RecordId> markedBlockIter = null;
521
522 public RIDBlockIterator(BacktrackingIterator<Page> block) {
523 this.block = block;
524 }
525
526 /**
527 * This is an extra constructor that allows one to create an
528 * RIDBlockIterator by taking the first maxPages of an iterator of Pages.
529 *
530 * If there are fewer than maxPages number of Pages available in pageIter,
531 * then all remaining pages shall be used in the "block"; otherwise,
532 * only the first maxPages number of pages shall be used.
533 *
534 * Note that this also advances pageIter by maxPages, so you can do the
535 * following:
536 *
537 * Iterator<Page> pageIter = // ...
538 * RIDBlockIterator firstBlock = new RIDBlockIterator(pageIter, 100);
539 * RIDBlockIterator secondBlock = new RIDBlockIterator(pageIter, 100);
540 * RIDBlockIterator thirdBlock = new RIDBlockIterator(pageIter, 100);
541 *
542 * to get iterators over the first 100 pages, second 100 pages, and third
543 * 100 pages.
544 */
545 public RIDBlockIterator(Iterator<Page> pageIter, int maxPages) {
546 this(Table.getBlockFromIterator(pageIter, maxPages));
547 }
548
549 /**
550 * This is an extra constructor that allows one to create an
551 * RIDBlockIterator over an array of Pages.
552 *
553 * Every page in the pages array will be used in the block of pages.
554 */
555 public RIDBlockIterator(Page[] pages) {
556 this(new ArrayBacktrackingIterator(pages));
557 }
558
559 public boolean hasNext() {
560 if (blockIter != null && blockIter.hasNext()) {
561 return true;
562 } else if(block.hasNext()) {
563 blockIter = new RIDPageIterator(block.next());
564 return hasNext();
565 } else {
566 return false;
567 }
568 }
569
570 public RecordId next() {
571 return blockIter.next();
572 }
573
574 /**
575 * Marks the last recordId returned by next().
576 *
577 * This implementation of mark simply marks and saves the current page's
578 * iterator of RecordIds.
579 */
580 public void mark() {
581 block.mark();
582 blockIter.mark();
583
584 // Save the current blockIter
585 markedBlockIter = blockIter;
586 }
587
588 /**
589 * Resets to the marked recordId.
590 *
591 * This implementation of reset restores the marked page's iterator,
592 * and calls reset() on it to move it to the correct record. Some extra
593 * care is taken to ensure that we properly reset the block page iterator.
594 */
595 public void reset() {
596 // Restore the saved blockIter
597 blockIter = markedBlockIter;
598
599 block.reset();
600
601 // Don't want to get the same block again so just advance by one.
602 block.next();
603
604 // Also need to reset the saved blockIter since it could have been
605 // advanced after the mark()
606 blockIter.reset();
607 }
608 }
609
610 /**
611 * A helper function that returns the same iterator passed in, but with
612 * a single page skipped.
613 */
614 private static Iterator<Page> iteratorSkipPage(Iterator<Page> iter) {
615 iter.next();
616 return iter;
617 }
618
619 /**
620 * TableIterator is an Iterator over the record IDs of a table.
621 *
622 * This is just a very thin wrapper around RIDBlockIterator, where the "block"
623 * is an iterator of all the pages of the table (minus the header page). Once
624 * RIDBlockIterator is filled in, all tests on TableIterator should
625 * automatically pass.
626 */
627 public class TableIterator extends RIDBlockIterator {
628 public TableIterator() {
629 super((BacktrackingIterator<Page>) Table.iteratorSkipPage(Table.this.allocator.iterator()));
630 }
631 }
632}