falcon storage engine 调研

6月 27th, 2012

falcon storage engine 调研

杭研后台——何登成

1. 事务    1

2. 索引    1

3. 索引(续)    1

4. 多版本    2

5. 内存堆    2

6. Insert    2

7. Multi-Range-Read(MRR)    3

8. Gopher Thread    5

9. Scavenge Thread    5

10. Full Table Scan    6

11. 外存数据组织    7

参考资料    7

调研Falcon引擎处理事务/多版本/内存堆(索引)/外存堆(索引)/后台线程/索引扫描/表扫描/Insert等操作的逻辑

1. 事务

Falcon的事务,含有两个id:transactionId与commitId,二者同用一个自增序列。transactionId代表事务开始逻辑号,commitId代表事务提交逻辑号。与InnoDB的处理完全一致。

2. 索引

事务的I/U/D操作,记录首先保存在内存中——内存多版本。同时,对应于表的每一个索引,Falcon在事务级别维护相同的索引结构——DeferredIndex,事务索引记录就是事务I/U/D操作产生的数据。一个索引扫描,会遍历外存索引以及内存事务索引,合并所有索引的查询结果并返回。

3. 索引(续)

事务提交时,属于事务的DeferredIndex中的索引项,被写入Redo Log。同时,Falcon有一个后台线程,定期扫描所有的提交事务,将当前活跃事务均可见的提交事务所做的修改,合并到外存。功能类似于InnoDB的Purge操作。

4. 多版本

Falcon引擎的多版本可见性判断逻辑如下:1. RC隔离级别下,提交事务生成的记录均可见;2. RR隔离级别下,记录对应的事务必须已提交,同时当前事务的transactionId < 提交事务的commitId;3. 与InnoDB相比,无ReadView的概念。

函数调用流程(全表扫描):

    StorageInterface::rnd_next();

        StorageTable::next();

            StorageDatabase::nextRow();

                RecordVersion::fetchVersion();

                    Transaction::visible();

5. 内存堆

Falcon引擎的多版本记录,首先存储与内存之中,一个外存表对应于一个内存堆。内存堆被组织为树形结构,树的叶子节点固定存储100条记录(RecordLeaf),树的非叶子节点,固定存储100个指向下一层节点的指针(RecordGroup)。因此,1层 = 100条记录;2层=100*100。内存堆中的记录,由后台线程逐步Merge到外存堆之中。

函数调用流程:

    Table::insert();

        Table::insertIntoTree();

            RecordLeaf::store();

            // 内存堆,对应有一个RecordBitmap,内存堆中插入一条记录,记录的

            // RecordNumber对应的Bitmap位就设置为1,标识当前RecordNumber记录在

            // 内存堆中存在,可以读取内存堆获取记录的全项

            Bitmap::setSafe(recordNumber);

6. Insert

Falcon的Insert记录,首先同样插入内存中,由于内存中并没有物理的RowId,因此需要为插入记录分配一个唯一标识——RecordNumber(递增分配)。RecordNumber功能:1. 决定记录在内存堆(TREE)中的位置;2. 决定索引项在DeferredIndex中的位置(非唯一索引);3. 通过此值进行回表查询(类似于RowId)。

函数调用流程:

    StorageInterface::write_row();

        StorageTable::insert();

            StorageDatabase::insert();

                Table::insert();

                    // 为Insert记录,分配一个RecordNumber,此RecordNumber,

// 也标识了记录在内存堆中的位置

                    Dbb::insertStub();

                        Section::insertStub();

// 将Insert记录插入到事务的DeferredIndex中,DeferredIndex中的索引项,

// 是[recordNumber, keyLength, key]的组织形式。同时,索引键值的比较函数,

// 有DeferredIndex::compare实现,先对比索引键值,最后对比索引记录的

// RecordNumber值

                    Index::insert();

                        Index::insert();

                            DeferredIndex::addNode();

                                DeferredIndex::compare();

  • 注意:究竟RecordNumber是什么?

    RecordNumber是一个逻辑RowId,有着RowId的所有功能。优势:有RecordNumber的支持,Falcon引擎的Insert操作,才能够插入内存中。劣势:由于RecordNumber是逻辑RowId,指向物理RowId,因此查询操作,多了一次I/O:索引叶页面 -> Record Locator Page -> 数据页面

7. Multi-Range-Read(MRR)

MRR流程:1. 构建Bitmap,读取索引范围,对于满足查询条件的索引项对应的RecordNumber,设置其在Bitmap中的bit;2. 从最低位(0位)开始遍历Bitmap,对于bit为1的位置,取出对应的RecordNumber,回表进行查询,此时,完整的可以在内存/日志/外存中。

函数调用流程:

    // 1. 将Index Range Scan中的记录,首先读取到一个Bitmap中,

// Bitmap中的1 bit对应于一个RecordNumber

    StorageInterface::multi_range_read_init();

        StorageInterface::fillMrrBitmap();

            StorageInterface::scanRange();

                // 标识当前索引扫描是否为limit查询,需要保证索引返回记录的有序性

                StorageTable::indexScan(int indexOrder);

                    StorageDatabase::indexScan();

                        // 进行索引扫描

                        Index::scanIndex();

                            // 首先扫描内存提交事务的DeferredIndex索引

                            DeferredIndex::scanIndex();

                            // 然后扫描外存索引

                            IndexRootPage::scanIndex();

                                IndexRootPage::findLeaf();

                                IndexPage::findNodeInLeaf();

                                IndexNode::getNext();

                                // 对于扫描到的记录,取出其RecordNumber,然后根据

// 此RecordNumber,设置对应的Bitmap位

                                node.getNumber();

                                bitmap->set(number);

    // 2. 逐个读取Bitmap中的记录,返回MySQL Server,此时的记录是按照RecordNumber排序,

// 而非索引键值顺序

    StorageInterface::multi_range_read_next();

        StorageInterface::index_next();

            StorageTable::nextIndexed();

                StorageDatabase::nextIndexed();

                    Bitmap::nextSet();

                    Table::fetch();

                        // 1. RecordNumber对应的记录在内存中

                        RecordSection::fetch();

                        // 2. RecordNumber对应的记录在日志中

                        backloggedRecords->get();

                        // 3. RecordNumber对应的记录在外存中

                        Table::databaseFetch();

                            Dbb::fetchRecord();

                                Section::fetchRecord();

                                    // 4.1 读取RecordNumber对应的外存Page,每条记录,

                                    // 在RecordNumber Page中维护一个RecordIndex结构,

                                    // RecordIndex结构中包含[page,line,spaceAvailable]信息,

                                    // 是一个记录索引,记录的实际数据存储于[page,line]对应

                                    // 的page中的line指定位置

                                    Section::fetchLocatorPage();

                                        Dbb::fetchPage();

                                            Cache::fetchPage();

                                                IO::readPage();

                                                    IO::pread();

                                                    IO::validateChecksum();

                                                        IO::computeChecksum();

                                    // 4.2 RecordIndex中[page]指定的位置,读取记录数据页

                                    // RecordIndex中[line]指定的位置,读取真正的记录数据

                                    Dbb::handoffPage();

                                        Dbb::fetchPage();

                                    DataPage::fetchRecord();

                        // 3.1 每个Record中,存储有一个generation,标识当前记录属于第几代

                        // 在Database结构中,有currentGeneration,标识当前系统进行了多少次

                        // scavenge(purge),每进行一次scavenge,currentGeneration++。记录

                        // 读进内存时,需将记录的generation设置为Database->currentGeneration

                        //

                        // 猜测 1:generation目的是处理RecordNumber的重用问题,系统每次

                        // scavenge,清除过期的RecordNumer,就可能被重用,generation

                        // 可以用来标识当前记录的RecordNumber,是可能重用的RecordNumber

                        //

                        // 猜测 2:generation目的是标识记录进入内存的时间,scavenge时,可

                        // 根据generation判断出哪些记录可以被回收

                        //

                        // 猜测 3:根据RecordScavenge::inventoryRecord函数,generation也可能

                        // 用于计算统计信息。每次scavenge,统计可以从哪些generation中retire

                        // 多少空间?在真正retire时,可以首先retire old generation记录,然后

                        // young generation记录,变相的实现LRU的功能

                        // 总结:猜测 3应该是正确的。

                        Record::poke();

                        // 3.2 若记录在外存中,则读取时加载到内存堆

                        insertIntoTree();

8. Gopher Thread

囊地鼠(后台)线程,事务提交后唤醒,负责将提交事务所做的更新操作(I/U/D),合并到外存堆/索引中。此时,内外存均有提交事务的最新数据,外存记录无版本信息,内存记录上存在版本信息。记录的可见性通过内存记录上的版本信息来判断。在记录最新版本可被所有活跃事务看见之前,内存记录不可删除。

函数调用流程:

    Gopher::gopherThread();

        SerialLogTransaction::doAction();

            SerialLogTransaction::commit();

                SRLUpdateRecords::commit();

                    Dbb::updateRecord();

                        Section::updateRecord();

                            Section::storeRecord();

                                // 将记录的更新,最终写到外存Datapage中

                                Datapage::storeRecord();

9. Scavenge Thread

后台清理线程,定期启动,扫描内存中的所有表的记录:1. 回收(prune)记录的过期历史版本(类似于InnoDB中的Purge线程);2. 收回(retire)记录当前版本(当记录当前版本所有活跃事务均可见时)(类似于InnoDB中的Buffer Pool Pages的LRU替换)

函数调用流程 1:

    Database::scavengerThreadMain();

        Database::scavenge();

            Database::scavengeCompiledStatements();

            TransactionManager::purgeTransactions();

                TransactionManager::purgeTransactionsWithLocks();

                    // 获取活跃事务链表中的最小活跃事务ID

                    TransactionManager:;findOldestInActiveList();

            Database::scavengeRecords();

                // 遍历Database的tablelist链表,prune所有的table

                Database::pruneRecords();

                    Table::pruneRecords();

                        RecordLeaf::pruneRecords();

                            // 从记录的最新版本出发,反向遍历记录的所有历史版本

                            // 1. 判断记录的所有历史版本中,哪些可以被prune,哪些不能?

                            //     所有活跃事务均不可见的历史版本,可以被prune,直接删除

                            // 2. 判断记录的当前版本,是否可以被retire?

                            //     若记录的所有历史版本均可被prune,仅当前记录可见,那么

                            //     当前记录可以被retire(retire指的是可见记录被替换出内存)

                            //     按照记录的generation与Scavenge的generation,确定记录

                            //     所属的ageGroup,在后续的retire过程中,会优先选择大的

                            //     ageGroup进行回收 —— Record的LRU策略

                            RecordScavenge::inventoryRecord(Record* record);

                            Record(RecordVersion)::clearPriorVersion();

                            // 回收旧版本所占用的空间,包括:索引/Field/Blob

                            Table::garbageCollect();

                                Index::garbageCollect();

                                Table::garbageCollectInversion();

                            Record::queueForDelete();

                // 遍历database的tablelist链表,尝试retire tables,释放足够的内存空间

                Database::retireRecords();

                    // 根据传入的spaceToRetire参数,计算回收到哪一级的generation,即可

                    // 达到目标。最老的generation,可以优先被回收 —— LRU策略

                    RecordScavenge::computeThreshold(spaceToRetire);

                    Table::retireRecords();

                        RecordLeaf::retireRecords();

10. Full Table Scan

全表扫描,从RecordNumber=0出发,读取Page_Record_Locator页面,取出RecordNumber对应的[page, slot]组合,然后根据此信息,读取对应的Data_Page页面,获取记录,并回溯记录的可见版本。读取完一条记录之后,RecordNumber++,然后开始新一轮的读取。

函数调用流程:

    StorageInterface::rnd_next();

        StorageTable::next();

            StorageDatabase::nextRow();

                Table::fetchNext();

                    // 判断当前RecordNumber在内存对的RecordBitmap中是否设置

                    // 若设置,说明记录可能在内存堆之中

                    Bitmap::nextSet();

                    RecordLeaf(RecordGroup)::fetch();

                    Table::backlogFetch();

                    // 内存/日志中不存在,从外存读取记录

                    Table::databaseFetch();

                Record(RecordVersion)::fetchVersion();

11. 外存数据组织

Falcon Engine 外存数据组织结构图

 

参考资料

http://forge.mysql.com/wiki/Falcon

http://en.wikipedia.org/wiki/InterBase

http://forge.mysql.com/wiki/Falcon_Feature_Preview

http://ftp.nchu.edu.tw/MySQL/tech-resources/articles/falcon-in-depth.html    — Falcon storage engine in depth

http://downloads.mysql.com/archives.php?p=mysql-6.0&o=other            — MySQL 6.0 Source Code

http://en.wikipedia.org/wiki/Falcon_(storage_engine)

http://ftp.nchu.edu.tw/MySQL/tech-resources/articles/falcon-transactional-engine-part1.html

http://ftp.nchu.edu.tw/MySQL/tech-resources/articles/falcon-transactional-engine-part2.html

http://ftp.nchu.edu.tw/MySQL/tech-resources/articles/falcon-transactional-engine-part3.html

http://www.mysqlperformanceblog.com/2007/01/12/falcon-storage-engine-design-review/

http://www.mysqlperformanceblog.com/2007/01/08/innodb-vs-myisam-vs-falcon-benchmarks-part-1/

http://blogs.teamb.com/craigstuntz/2005/02/18/2699/                — Multiversion Concurrency Control Before InterBase

http://www.firebirdnews.org/?p=1742                            — Jim Starkey: “Well,here we go again”


目前还没有任何评论.