Tagged Data SystemDesign Project One6.033 / Massachusetts Institute of TechnologySam Madden TR 10 / Hooria Komal F1March 22, 2007Alexander Valys1 OverviewThis document describ e s the impleme ntation of a database-like system for stor-ing ’triplets’, as required by the first 6.033 design project. These are short dataelements of the form subject,relationship,object.The system described is capable of storing approximately eight billion triplets(of approximately 100 bytes each) on a machine with 1 TB of available diskspace, and 1 GB of RAM. Insert, delete, and wildcard-based s earch are sup-ported. All operations in the example workloads run in constant time, withinsert and delete taking between 72 ms and 96 ms, and searching as little as 18ms (for a fixed numb er of results).This performance is achieved by maintaining two redundant but differently-organized copies of the data set on disk, each consisting of one-or-two-level hashtables, and compressing the raw triplet data b e fore storing it.2 Design Description2.1 Data Structure OverviewEach copy of the data set is referred to as a ’primary collection’. One is organizedby each triplet’s subjec t, and the other by each triplet’s object.Bucket0Bucket1Bucket2Bucket3...BucketBBucket0Bucket1Bucket2Bucket3...BucketBblock 88block 89block 90block 91...block 88+S'Subject' Primary Collection Header 'Object' Primary Collection HeaderPrimaryStorageGroup...;alex, is-a, student;alex, taking, 6.033;alex, took, 6.111;;block contentsSecondary CollectionHeaderBucket0Bucket1Bucket2Bucket3...BucketBblock 31...block 31+Sblock 234...SecondaryCollectionSecondaryStorageGroupFigure 1: Primary and secondary collection structure overview.Within each primary collection, location of specific triplets is accomplishedusing a hash-table-based lookup system. The collections are divided into somenumbe r B of buckets, with each bucket corresponding to a specific range of1values of the hash function. Either the subject or object triplet field value isused as a key, depending on the primary collection. Each bucket is associatedwith a storage group, which is a sequence of some number S of contiguous blockson disk in which triplets are actually stored.For extremely large buckets, the system uses another level of indirection.Rather than pointing directly to a storage group, the bucket points to a sec-ondary collection. This is another hash table, with a variable number of buckets,keyed on the value opposite that of the primary collection it is within (i.e. asecondary collection within the subject primary collection would be keyed onobject). Inside the secondary collection are a number of additional buckets, e achpointing to a storage group of length S.2.2 On-Disk LayoutSuperblockVolumeBitmapPrimary CollectionHeadersStorage GroupsandSecondary CollectionRegionS O100 blocks (used)100 blocks (free)Header RegionFigure 2: On-disk layout of headers and data structures.Figure 2 indicates the on-disk layout of the data structures described above.The first block on disk, the superblock, contains the location (starting blockand length) of the two primary collec tion headers. Each header is a large array,implementing a lookup table that associates each bucket in that primary collec-tion with the starting block and length of either a s torage group, or secondarycollection header. The target group type is indicated with a bit flag. Secondarycollection headers take the same form as primary collection headers, except theymay only p oint to storage groups.Between the superblock and the primary collection headers on disk is thevolume bitmap, indicating which blocks are in use.Triplets are stored within storage group blocks as compressed plaintext,delimited by semicolons and commas. For example:;subject,relationship,object;another,relationship,another-object;;Delimiters are permitted in field values, but they must be escap ed withforward slashes. The last triplet s tored within each block of a storage group isindicated by a double semicolon.2Each block within a storage group is compressed separately, using an algo-rithm such as BZ2.2.3 CachingThe primary collection headers and volume bitmap are stored and modified in-memory during normal execution of the system, and written to disk only duringshutdown.The remaining in-memory space is used to cache secondary collection head-ers, using a least-recently-used replacement strategy.3 API Implementations3.1 Search(Subject, Relationship, Object, Start, Count,SessionInfo)Because of the way the data is laid out on disk, different search behavior isrequired dep e nding on the pattern of wildcards used in the request.3.1.1 A: (*, reln, obj), (subj, reln, *), (*, *, obj), (subj, *, *)To perform a search of this type, we must first select a primary collection to use.We use the object collection if the subject search field is a wildcard - otherwise,we use subject.Having selected a collection, we then determine the bucket we will searchin by computing the hash of the appropriate field, and then find the structurecorresponding to that bucket from the corresponding primary collection header.If it is a storage group, we can read it directly - if it is a secondary collection, wemust read the secondary collection header from disk or cache, and start readingfrom the storage group associated with the first secondary bucket.We read the storage group with a single read blocks command, and returnthe triplets that match the search criteria.If we are reading a secondary collection and the first bucket does not containCount results, we procee d to read the se cond bucket.3.1.2 B: (subj, *, obj)This search typ e uses the subject primary collection.If the structure associated with the primary bucket is a storage group, weread that directly. If it is a secondary collection, we determine the secondarybucket to read using the hash of the object field, and then read the associatedstorage group, returning triplets that match the search criteria.33.1.3 C: (*, reln, *), (*, *, *)For this type of search, we have no choice but to read all storage groups linearly,looking for any triplets with the specified relation.3.1.4 SessionInfoI had to modify the API slightly to improve performance. The Search procedurenow returns a SessionInfo object along with the result set. This object must bepassed back to Search when the client wants to retrieve additional values fromthe same result set. It contains a pointer to the storage group that the lasttriplet in the set came
View Full Document
Unlocking...