[CONF] Apache Labs > Physical pages

[Confluence]

Physical pages Page edited by Emmanuel Lécharny Changes (16) ... h1. Logical structure mapping on disk We will now describe how each logical structure is serialized on disk. h2. RecordManager header We keep a few bytes at the beginning of the file to store some critical information about the *RecordManager*. Here is the list of stored informations : * The *PageIO* size (in bytes) ... !RMHeader.png! We keep a track of the free pages (a free page is a *PageIO* that is not anymore used, for instance because the data have been deleted.) This is done by keeping a link between each *PageIO* and by pointing to the first feee *PageIO* and to the last free *PageIO* of this list. At startup, of course, we have no free pages, and those pointers contain the *-1* offset. h2. The internal RecordManager structure The *RecordManager* manages *BTrees*, and we have to store them into *PageIOs*. How do we do that ? ... Each *BTree* has to keep many informations so that it can be used. Those informations are : * revision (8 bytes) : the current revision for this *BTree*. This value is updated after each modification in the *BTree*. * nbElems (8 bytes) : the total number of elements we have in the *BTree*. This is updated after each modification either. * rootPage offset (8 bytes) : the position in the file where the *rootPage* is stored * nextBtree offset (8 bytes) : the position of the next *BTree* header in the file (or -1 if we don't have any other *BTree*) * pageSize (4 bytes) : the number of elements we cans store in a *Node* or a *Leaf*. It's not related in any possible way with the *PageIO* size. * name : The *BTree* name * nameSize (4 bytes) : The *BTree* name size * name (nameSize bytes) : the *BTree* name * keySerializerSize (4 bytes) : The size of the java FQCN for the key serializer * keySerializer (keySerializerSize bytes) : The java FQCN for the key serializer * valueSerializerSize (4 bytes) : The size of the java FQCN for the value serializer * valueSerializer : (valueSerializerSize bytes): The java FQCN for the value serializer * dupsAllowed : (1 byte): tells if the *BTree* can have duplicated values. As we can see, thi sheader can have various length, and if one one the names is long, we may need more than one *PageIOs* to store it. Here is a diagram which present this data structure on disk : ... Full Content The RecordManager stores all the Btrees in one single file, which is split in many physical pages, all having the same size. The page size Currently, the choice was to use one single size for all the pages, regardless the data we store into them. The rationnal is to get close to the OS page size (frequently 512 bytes or 4096 bytes). This is not necessarily the best choice though, let's say it's something we might want to change later. If we except a small header at the beginning of the file, everything is stored in PageIOs in the file. General file structure The file we use to store the data is a plain binary file, used to store all the BTrees. We can store many btrees in one single file. This file is considered as a fileSystem, with fixed size 'pages' (a page is an array of bytes). The page size is arbitrary fixed when teh RecordManager is created, and we will store every logical data n those physical pages, which will require to spread the logical data in many pages in most of the cases. PageIO Let's first introduce the PageIO, which is used to store the data on disk. a PageIO contains some raw data. As we have to map some logical data that may be wider than a physical fixed size PageIO, we use potentially more than one PageIO to store the data, and we link the PageIOs alltogether. Each PageIO has a height bytes pointer at the beginning, pointing to the next PageIO (or to nothing, if there is no more PageIO in the chain), plus an extra 4 bytes on the first PageIO to define the number of bytes stored in the chain of PageIO. Here is the mapping between a logical page and some PageIOs : Every PageIOs are contiguous on disk, but the PageIOs used to stor a logical page may be located anywhere on the disk, they don't have to be continuous. Here is the structure of a PageIO on disk : next page offset (8 bytes) : the offset of the next PageIO, or -1L if no more PageIO is needed data size (4 bytes) : for the first PageIO, the size of the stored data across all the PageIOs used to store a page. data (N bytes) : a block of data, which size will be min( PageSize - offset - data size, data size) for the first PageIO or min( PageSize - offset, data size) for any other PageIOs Logical structure mapping on disk We will now describe how each logical structure is serialized on disk. RecordManager header We keep a few bytes at the beginning of the file to store some critical information about the RecordManager. Here is the list of stored informations : The PageIO size (in bytes) The number of managed BTrees The offset of the first free page The offset of the last free page Here is a picture that shows the header content : We keep a track of the free pages (a free page is a PageIO that is not anymore used, for instance because the data have been deleted.) This is done by keeping a link between each PageIO and by pointing to the first feee PageIO and to the last free PageIO of this list. At startup, of course, we have no free pages, and those pointers contain the -1 offset. The RecordManager structure The RecordManager manages BTrees, and we have to store them into PageIOs. How do we do that ? All the BTrees have a header that contains many informations about them, and point to a rootPage which is the current root (so the root for the latest revision). As a RecordManager can manage more than one BTree, we have to find a way to retreive all the BTrees at startup : we use an internal link, so that a btree points to the next btree. At startup, we read the first BTree which is stored in the first PageIO in the file (so just after the RecordManager header), then we read the next btree pointed by the first btree, and so on. The BTree header Each BTree has to keep many informations so that it can be used. Those informations are : revision (8 bytes) : the current revision for this BTree. This value is updated after each modification in the BTree. nbElems (8 bytes) : the total number of elements we have in the BTree. This is updated after each modification either. rootPage offset (8 bytes) : the position in the file where the rootPage is stored nextBtree offset (8 bytes) : the position of the next BTree header in the file (or -1 if we don't have any other BTree) pageSize (4 bytes) : the number of elements we cans store in a Node or a Leaf. It's not related in any possible way with the PageIO size. nameSize (4 bytes) : The BTree name size name (nameSize bytes) : the BTree name keySerializerSize (4 bytes) : The size of the java FQCN for the key serializer keySerializer (keySerializerSize bytes) : The java FQCN for the key serializer valueSerializerSize (4 bytes) : The size of the java FQCN for the value serializer valueSerializer (valueSerializerSize bytes): The java FQCN for the value serializer dupsAllowed (1 byte): tells if the BTree can have duplicated values. As we can see, thi sheader can have various length, and if one one the names is long, we may need more than one PageIOs to store it. Here is a diagram which present this data structure on disk : Note that a BTree header can be stored on one or many IOPages, depending on its size. The Nodes and Leaves Nodes and Leaves are logical BTree pages which are serialized on disk into one to many PageIOs. They have slightly different data structures, as Nodes contains pointers to leaves, and no data, while Leaves contains data. On disk, each Node and Leaf are stored in PageIOs, as we said. A Node will have pointers to some other logical pages, and on disk, those pointers will be offset of the first PageIO used to store the logical page it points to. Here is the Node and Leaf data structures once serialized : Note that we store the size of the serialized data : this is necessary as we have to know how much PageIOs will be needed to store the logical page. The rootPage is just a Node or a Leaf. Special BTrees We have two special BTrees we use to manage the revisions and the copied pages. We will explain what they are good for Revision tree We need to keep a track of each active revision, so that a search can work with a specific revision. The idea is that when a search starts, it uses the latest revision, but as some modification can occur while teh search is beng processed, some new revisions will be added. In some case, we may want to keep a revision active for quite a long time. So we store the active revisions in a dedicated BTree. As we may have many BTrees, we have to use a key which is a combinaison of the BTree name and its revision. So the revision BTree manage the revisions of all the managed BTrees. When a revision is not anymore used, we can remove it from the revision BTree. This BTree is not a MVCC BTree, like the other ones. In other words, we only keep the latest revision of this BTree (ie, all the modified pages are immediately freed) Copied pages BTree Once we create a new revision, the pages we copied are not anymore in use except if the revisions they are associated with are still in use. The problem is that we can't discard those pages and move them to the free list until the associated revision is free. We use a dedicated BTree to keep a track of the copied pages, which will be reclaimed and moved to the free pages list once the associated revision will be released. Managing the free pages We have a mechanism to manage the PageIO that are not anymore in use. This is a linked list in which the free pages are added. If we need some page, we first look into this list, and get back as many PageIOs as we need - until we reach the end of this list. If we free some page, we add them at the end of the free list. We always free a logical page, which may be stored into many PageIOs. The good thing is that those pageIOs are already linked, so we just need to make the last free PageIO to point on the first freed PageIO, and to move the pointer to the last free page to the last PageIO used to store the logical page. Stop watching space | Change email notification preferences View Online | View Changes | Add Comment --------------------------------------------------------------------- To unsubscribe, e-mail: commits-unsubscr...@labs.apache.org For additional commands, e-mail: commits-h...@labs.apache.org