OSS中嵌入式内存数据库研究
摘要
数据库作为一种高效的组织和管理数据的软件,过去一直是以磁盘作为存储介质,随着嵌入式软件技术的发展和内存容量的大幅度提高,嵌入式内存数据库应运而生。嵌入式内存数据库系统的数据永久驻留在内存中,而常规的磁盘数据库系统的数据主要驻留在磁盘等机械读取设备中,所以内存数据库访问数据比磁盘数据库有更高的效率。在通信领域,随着人们需求的发展,出现了很多业务数据短小但业务量急速增大同时又对交换速度要求很高的通信业务,如手机短信等。面对这些新设备和新业务,基于电信领域OSS(Operation Support System)的嵌入式内存数据库技术有了一个很好的展示自己的舞台。嵌入式内存数据库系统通过其快速的数据访问能力,比磁盘数据库更适合于需要快速响应和高事务吞吐量的电信领域,对于需要在严格要求的时间内完成数据访问的实时电信系统,嵌入式内存数据库系统是一个理想的选择。如今嵌入式内存数据库技术越来越受到人们的关注和研究。
近年来,随着计算机芯片技术的不断改进,中央处理器的速度和主存速度之间的差距逐渐扩大,系统对主存的存取访问成为新的瓶颈。Cache是一种容量非常小、但速度非常快的静态存储器,设置在CPU和主存之间。由于cache中保存着主存中最常使用的数据和指令,因此可以有效地减少CPU的等待时间。命中率越高,CPU的运算效率就越高。命中率对数据库系统索引结构的性能影响非常大,尤其是对嵌入式内存数据库索引结构的性能,更是至关重要。
本文在大量阅读内存数据库和磁盘数据库相关技术资料的基础上,首先研究了缓存的时间局部性和数据空间局部性结合的原理,采用局部冲突链的方法,提出了缓存敏感的散列结构,建立局部冲突链处理散列表,并研究分析了其性能;其次根据嵌入式系统事务特性,分析事务处理方法,设计了函数调用级事务处理方案,减少了事务处理中进程交互,加快了事务处理速度;接下来设计了自主调度锁系统,解决在OSS系统中信号量会阻塞一组进程的问题,实现了快速的锁系统,并兼顾了优先级和时间公平性;最后改进了优先级位图方法,增加了cache利用率,对于嵌入式系统有更优的效率。
As a kind of highly efficient organization and managerial data software, the database has been based on disk as the storage medium traditionally. With the development of the embedded software technology and the enhancement of the memory’s capacity, the embedded memory database arised at the historic moment. The data in embedded memory database system stays in memory permanently, but the data in conventional disk database system stays in the disk or other mechanical device mainly, therefore the efficiency for accessing data of memory database is higher than the disk database. In the correspondence domain, along with the people’s demands development, there were a lot of communications services which had short datas, large amount and high request of transfer speed appeared, such as short messages and so on. Facing these new devices and new services, the embedded memory database based on telecommunication domain OSS (Operation Support System) had a very good stage to display their own area. Because of the faster ability to access data, the embedded memory database system is more suitable in telecommunication domain which needs fast response and high-throughput than disk database system. Embedded memory database system is an good choice regards of the real-time telecommunications system which needs the strict data access time. Now the embedded memory database technology is receiving more attention and research.
In recent years, along with the improvement of computer chip technology and the disparity expanding gradually between CPU and memory, the access to memory becomes a new bottleneck. Cache is a kind of static memory which has very small capacity and fast speed and it is set in between the CPU and memory. As the cache keeps the most commonly used data and instruction in the memory, it can reduce the waiting time of the CPU effectively. The higher of the cache hits, the higher efficiency of the CPU is. Percentage of the cache hits has a large effect on the performance of the database system’s index structure, especially on the performance of the embedded memory database’s index structure.
Researching a large number of technology information about memory database and disk database, firstly I studied the principle based on the combination of the cache’s local time and the data’s local space, used local conflict chain, presented cache sensitive hash structure, bulit local conflict chain hash and analysed its performance. Secondly, based on the characteristics of embedded system's transaction, I analysed the method for processing transactions, designed the function call-level transaction processing programs which reduced the process interactions in transaction and speeded up the transaction's processing speed. Then I designed self-scheduling lock system which solved the problem blocking a set of processes in OSS system, achieved a fast lock system and taked into account the priorities and fairness of the time. Finally, I gived a optimized bitmap ways to increase the utilization rate of cache which has better efficiency in embedded systems.
近年来,随着计算机芯片技术的不断改进,中央处理器的速度和主存速度之间的差距逐渐扩大,系统对主存的存取访问成为新的瓶颈。Cache是一种容量非常小、但速度非常快的静态存储器,设置在CPU和主存之间。由于cache中保存着主存中最常使用的数据和指令,因此可以有效地减少CPU的等待时间。命中率越高,CPU的运算效率就越高。命中率对数据库系统索引结构的性能影响非常大,尤其是对嵌入式内存数据库索引结构的性能,更是至关重要。
本文在大量阅读内存数据库和磁盘数据库相关技术资料的基础上,首先研究了缓存的时间局部性和数据空间局部性结合的原理,采用局部冲突链的方法,提出了缓存敏感的散列结构,建立局部冲突链处理散列表,并研究分析了其性能;其次根据嵌入式系统事务特性,分析事务处理方法,设计了函数调用级事务处理方案,减少了事务处理中进程交互,加快了事务处理速度;接下来设计了自主调度锁系统,解决在OSS系统中信号量会阻塞一组进程的问题,实现了快速的锁系统,并兼顾了优先级和时间公平性;最后改进了优先级位图方法,增加了cache利用率,对于嵌入式系统有更优的效率。
As a kind of highly efficient organization and managerial data software, the database has been based on disk as the storage medium traditionally. With the development of the embedded software technology and the enhancement of the memory’s capacity, the embedded memory database arised at the historic moment. The data in embedded memory database system stays in memory permanently, but the data in conventional disk database system stays in the disk or other mechanical device mainly, therefore the efficiency for accessing data of memory database is higher than the disk database. In the correspondence domain, along with the people’s demands development, there were a lot of communications services which had short datas, large amount and high request of transfer speed appeared, such as short messages and so on. Facing these new devices and new services, the embedded memory database based on telecommunication domain OSS (Operation Support System) had a very good stage to display their own area. Because of the faster ability to access data, the embedded memory database system is more suitable in telecommunication domain which needs fast response and high-throughput than disk database system. Embedded memory database system is an good choice regards of the real-time telecommunications system which needs the strict data access time. Now the embedded memory database technology is receiving more attention and research.
In recent years, along with the improvement of computer chip technology and the disparity expanding gradually between CPU and memory, the access to memory becomes a new bottleneck. Cache is a kind of static memory which has very small capacity and fast speed and it is set in between the CPU and memory. As the cache keeps the most commonly used data and instruction in the memory, it can reduce the waiting time of the CPU effectively. The higher of the cache hits, the higher efficiency of the CPU is. Percentage of the cache hits has a large effect on the performance of the database system’s index structure, especially on the performance of the embedded memory database’s index structure.
Researching a large number of technology information about memory database and disk database, firstly I studied the principle based on the combination of the cache’s local time and the data’s local space, used local conflict chain, presented cache sensitive hash structure, bulit local conflict chain hash and analysed its performance. Secondly, based on the characteristics of embedded system's transaction, I analysed the method for processing transactions, designed the function call-level transaction processing programs which reduced the process interactions in transaction and speeded up the transaction's processing speed. Then I designed self-scheduling lock system which solved the problem blocking a set of processes in OSS system, achieved a fast lock system and taked into account the priorities and fairness of the time. Finally, I gived a optimized bitmap ways to increase the utilization rate of cache which has better efficiency in embedded systems.
引文
1 Stefan Manegold, Peter Boncz, Martin Kersten. Optimizing Main-Memory Join on Modern Hardware. IEEE Transactions on Knowledge and Data Engineering. 2002.06,14(6):709~730
2阳国贵,王升.主存数据库系统与技术.软件学报. 1994, 5(3):22~28
3 HweeHwa Pang, Bobby Jose, M. s. Krishnan. Resource Scheduling In A High-Performance Multimedia Server. IEEE Transactions on Knowledge and Data Engineering. 1999.05,11(2):303~320
4 SO Hvasshovd, ? Torbj?rnsen, SE Bratsberg. Proceedings of the 21th International Conference on Very Large Data Bases. 1995:469~477
5 E Rahm. Parallel query processing in shared disk database systems. ACM SIGMOD Record. 1993,(11):32~37
6 D Kroft. Lockup-free instruction fetch/prefetch cache organization. International Symposium on Computer Architecture. 1998:195~201
7 RH Thomas. A Majority consensus approach to concurrency control for multiple copy databases. ACM Transactions on Database Systems (TODS). 1979,(6):180~209
8 P Schwarz, W Chang, JC Freytag, G Lohman. Extensibility in the Starburst database system. Proceedings on the 1986 international workshop on Object-oriented database systems.1986:85~92
9 Jayant R. Haritsa, Miron Livny. Data access scheduling in firm real-time database systems. Springer. 1992,(9):203~241
10 Jun Rao, PKenneth A. Ross. Making B+- trees cache conscious in main memory. Proceedings of the 2000 ACM SIGMOD international conference on Management of data. 2000.05:475~486
11夏家莉.一种适用于嵌入式数据库系统的存取机制.计算机应用与软件. 2003,(6):61~63
12 P.A.Boncz, S.Manegold, M.L.Kersten. Database Architecture Optimized for the new bottleneck: Memory access. In Proceedings of the 25th VLDB Conference.1999,54~65
13 Chuanjun Zhang, Frank Vahid, Walid Najjar. A highly configurable cache for low energy embedded systems. ACM Transactions on Embedded Computing Systems (TECS). 2005.05,4(2):363~387
14 A.Ailamaki, et al. DBMSs on a modern processor. Where does time go?. In Proceedings of the 25th VLDB Conference. 1999:266~277
15 Yen L, Bastani F B. Parallel Hashing: Collision Resolution Strategies and Performance. Journal of Parallel and Distributed Computing. 1995,31(2):190~198
16 T.J.Lehman, M.J.Carey. A Study of Index Structures for Main Memory Database Management System. Proceedings 12th Int'l Conf. on Very Large Database. Kyoto, 1986:294~303
17林鹏,李航.关键业务中内存数据库的T树索引优化.计算机工程. 2004,30(17):75-76
18卢炎生,杨富民等.支持主存数据库的树研究.计算机工程与应用. 1993,(3):18~21
19 DJ DeWitt, RH Katz, F Olken, LD Shapiro. Implementation techniques for main memory database systems. ACM SIGMOD Record. 1984,(6):1~8
20 DW Clark, JS Emer. Performance of the VAX-11/780 translation buffer: simulation and measurement. ACM Transactions on Computer Systems. 1985,(2):31~62
21王洪海,潘朝华.内存数据库的数据结构分析.现代电子技术. 2004,(3):96-97
22 Michael Mitzenmacher, Salil Vadhan. Why Simple Hash Functions Work Exploiting The Entropy in a Data Stream. Society for Industrial and Applied Mathematics. 2008:746~755
23 Molina H G, Salem K. Main Memory Database Systems: An Overview. IEEE Transactions on Knowledge and Data Engineering. 1992, 4(6): 509~516
24 Lehman T J, Carey M J. A Study of Index Structures for Main Memory Database Management Systems[C]. Proceedings of the 12th International Conference on Very Large Databases, Kyoto. 1986-08:294~303
25 Owolabi O. Empirical Studies of Some Hashing Functions.Information and Software Technology. 2003, 45(2): 109~112
26 Sachedina, (Ajax, CA),Romanufa, Keriley K. (Scarborough, CA), Aamer(Newmarket, CA), Huras, Matthew A. Resizable Cache Sensitive Hash Table United States Patent. 2006
27 Jun Rao, PKenneth A. Ross. Cache Conscious Indexing for Decision-Support in Main Memory. Proceedings of the 25th International Conference on Very Large Data Bases. 1999.09:78~89
28 Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gabor Tardos. Linear Hash Functions. Journal of the ACM. 1999,46(5):667~683
29 Luo Wenbin. Hashing via Finite Field. Information Sciences. 2006,176(17): 2553~2566
30 Owolabi O. Empirical Studies of Some Hashing Functions[J].Information and Software Technology, 2003, 45(2): 109~112
31 Alex van Ballegooij, Roberto Cornacchia, Arjen P. de Vries and Martin Kersten. Distribution Rules for Array Database Queries. Springer. 2005:55~64
32 PM Lewis, A Bernstein, M Kifer. Databases and transaction processing: an application-oriented approach. ACM SIGMOD Record, 2002:74~75
33杨汉祥,陈江英.高性能嵌入式网络数据库管理系统的研究.计算机与现代化. 2004,(12):58
34 KP Eswaran, JN Gray, RA Lorie, IL Traiger. The notions of consistency and predicate locks in a database system. Communications of the ACM. 1976:624~633
35丁毓峰,蒋胜.支持协同测试的软件测试信息管理系统.计算机工程. 2005,(31):20~22
36居效密,张忠能.嵌入式数据库在数据密集型软件中的应用.计算机工程. 2003,29(11):186
37王京谦,万荏新.开源嵌入式数据库Berkeley和SQLite的比较.单片机与嵌入式系统应用. 2005,(2):5
38刘云生,迟岩.内存受限的实时内存数据库数据装入策略.计算机工程. 2004,30(20):50~51
39 CL Liu, JW Layland. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. ACM,1973(1):46~61
40 ? Ulusoy, GG Belford. Real-time transaction scheduling in database systems. Information Systems. 1993,Volume 18, Issue 9:559~580
41 VN Rao, V Kumar. Concurrent Access of Priority Queues. IEEE Transactions on Computers. 1998,(11):1657~1665
42 Sergio Sáez, Vicent Lorente, Silvia Terrasa, Alfons Crespo. Efficient Alternatives for Implementing Fixed-Priority Schedulers. 2005,(6):39~50
2阳国贵,王升.主存数据库系统与技术.软件学报. 1994, 5(3):22~28
3 HweeHwa Pang, Bobby Jose, M. s. Krishnan. Resource Scheduling In A High-Performance Multimedia Server. IEEE Transactions on Knowledge and Data Engineering. 1999.05,11(2):303~320
4 SO Hvasshovd, ? Torbj?rnsen, SE Bratsberg. Proceedings of the 21th International Conference on Very Large Data Bases. 1995:469~477
5 E Rahm. Parallel query processing in shared disk database systems. ACM SIGMOD Record. 1993,(11):32~37
6 D Kroft. Lockup-free instruction fetch/prefetch cache organization. International Symposium on Computer Architecture. 1998:195~201
7 RH Thomas. A Majority consensus approach to concurrency control for multiple copy databases. ACM Transactions on Database Systems (TODS). 1979,(6):180~209
8 P Schwarz, W Chang, JC Freytag, G Lohman. Extensibility in the Starburst database system. Proceedings on the 1986 international workshop on Object-oriented database systems.1986:85~92
9 Jayant R. Haritsa, Miron Livny. Data access scheduling in firm real-time database systems. Springer. 1992,(9):203~241
10 Jun Rao, PKenneth A. Ross. Making B+- trees cache conscious in main memory. Proceedings of the 2000 ACM SIGMOD international conference on Management of data. 2000.05:475~486
11夏家莉.一种适用于嵌入式数据库系统的存取机制.计算机应用与软件. 2003,(6):61~63
12 P.A.Boncz, S.Manegold, M.L.Kersten. Database Architecture Optimized for the new bottleneck: Memory access. In Proceedings of the 25th VLDB Conference.1999,54~65
13 Chuanjun Zhang, Frank Vahid, Walid Najjar. A highly configurable cache for low energy embedded systems. ACM Transactions on Embedded Computing Systems (TECS). 2005.05,4(2):363~387
14 A.Ailamaki, et al. DBMSs on a modern processor. Where does time go?. In Proceedings of the 25th VLDB Conference. 1999:266~277
15 Yen L, Bastani F B. Parallel Hashing: Collision Resolution Strategies and Performance. Journal of Parallel and Distributed Computing. 1995,31(2):190~198
16 T.J.Lehman, M.J.Carey. A Study of Index Structures for Main Memory Database Management System. Proceedings 12th Int'l Conf. on Very Large Database. Kyoto, 1986:294~303
17林鹏,李航.关键业务中内存数据库的T树索引优化.计算机工程. 2004,30(17):75-76
18卢炎生,杨富民等.支持主存数据库的树研究.计算机工程与应用. 1993,(3):18~21
19 DJ DeWitt, RH Katz, F Olken, LD Shapiro. Implementation techniques for main memory database systems. ACM SIGMOD Record. 1984,(6):1~8
20 DW Clark, JS Emer. Performance of the VAX-11/780 translation buffer: simulation and measurement. ACM Transactions on Computer Systems. 1985,(2):31~62
21王洪海,潘朝华.内存数据库的数据结构分析.现代电子技术. 2004,(3):96-97
22 Michael Mitzenmacher, Salil Vadhan. Why Simple Hash Functions Work Exploiting The Entropy in a Data Stream. Society for Industrial and Applied Mathematics. 2008:746~755
23 Molina H G, Salem K. Main Memory Database Systems: An Overview. IEEE Transactions on Knowledge and Data Engineering. 1992, 4(6): 509~516
24 Lehman T J, Carey M J. A Study of Index Structures for Main Memory Database Management Systems[C]. Proceedings of the 12th International Conference on Very Large Databases, Kyoto. 1986-08:294~303
25 Owolabi O. Empirical Studies of Some Hashing Functions.Information and Software Technology. 2003, 45(2): 109~112
26 Sachedina, (Ajax, CA),Romanufa, Keriley K. (Scarborough, CA), Aamer(Newmarket, CA), Huras, Matthew A. Resizable Cache Sensitive Hash Table United States Patent. 2006
27 Jun Rao, PKenneth A. Ross. Cache Conscious Indexing for Decision-Support in Main Memory. Proceedings of the 25th International Conference on Very Large Data Bases. 1999.09:78~89
28 Noga Alon, Martin Dietzfelbinger, Peter Bro Miltersen, Erez Petrank, Gabor Tardos. Linear Hash Functions. Journal of the ACM. 1999,46(5):667~683
29 Luo Wenbin. Hashing via Finite Field. Information Sciences. 2006,176(17): 2553~2566
30 Owolabi O. Empirical Studies of Some Hashing Functions[J].Information and Software Technology, 2003, 45(2): 109~112
31 Alex van Ballegooij, Roberto Cornacchia, Arjen P. de Vries and Martin Kersten. Distribution Rules for Array Database Queries. Springer. 2005:55~64
32 PM Lewis, A Bernstein, M Kifer. Databases and transaction processing: an application-oriented approach. ACM SIGMOD Record, 2002:74~75
33杨汉祥,陈江英.高性能嵌入式网络数据库管理系统的研究.计算机与现代化. 2004,(12):58
34 KP Eswaran, JN Gray, RA Lorie, IL Traiger. The notions of consistency and predicate locks in a database system. Communications of the ACM. 1976:624~633
35丁毓峰,蒋胜.支持协同测试的软件测试信息管理系统.计算机工程. 2005,(31):20~22
36居效密,张忠能.嵌入式数据库在数据密集型软件中的应用.计算机工程. 2003,29(11):186
37王京谦,万荏新.开源嵌入式数据库Berkeley和SQLite的比较.单片机与嵌入式系统应用. 2005,(2):5
38刘云生,迟岩.内存受限的实时内存数据库数据装入策略.计算机工程. 2004,30(20):50~51
39 CL Liu, JW Layland. Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. ACM,1973(1):46~61
40 ? Ulusoy, GG Belford. Real-time transaction scheduling in database systems. Information Systems. 1993,Volume 18, Issue 9:559~580
41 VN Rao, V Kumar. Concurrent Access of Priority Queues. IEEE Transactions on Computers. 1998,(11):1657~1665
42 Sergio Sáez, Vicent Lorente, Silvia Terrasa, Alfons Crespo. Efficient Alternatives for Implementing Fixed-Priority Schedulers. 2005,(6):39~50