Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

The log-structured merge-tree (LSM-tree)

  • Published:
Acta Informatica Aims and scope Submit manuscript

Abstract

High-performance transaction system applications typically insert rows in a History table to provide an activity trace; at the same time the transaction system generates log records for purposes of system recovery. Both types of generated information can benefit from efficient indexing. An example in a well-known setting is the TPC-A benchmark application, modified to support efficient queries on the history for account activity for specific accounts. This requires an index by account-id on the fast-growing History table. Unfortunately, standard disk-based index structures such as the B-tree will effectively double the I/O cost of the transaction to maintain an index such as this in real time, increasing the total system cost up to fifty percent. Clearly a method for maintaining a real-time index at low cost is desirable. The log-structured mergetree (LSM-tree) is a disk-based data structure designed to provide low-cost indexing for a file experiencing a high rate of record inserts (and deletes) over an extended period. The LSM-tree uses an algorithm that defers and batches index changes, cascading the changes from a memory-based component through one or more disk components in an efficient manner reminiscent of merge sort. During this process all index values are continuously accessible to retrievals (aside from very short locking periods), either through the memory component or one of the disk components. The algorithm has greatly reduced disk arm movements compared to a traditional access methods such as B-trees, and will improve cost-performance in domains where disk arm costs for inserts with traditional access methods overwhelm storage media costs. The LSM-tree approach also generalizes to operations other than insert and delete. However, indexed finds requiring immediate response will lose I/O efficiency in some cases, so the LSM-tree is most useful in applications where index inserts are more common than finds that retrieve the entries. This seems to be a common property for history tables and log files, for example. The conclusions of Sect. 6 compare the hybrid use of memory and disk components in the LSM-tree access method with the commonly understood advantage of the hybrid method to buffer disk pages in memory.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Aho, A. V., Hopcroft, J. E., Ullman, J. D.: The design and analysis of computer algorithms. Reading, MA, Addison-Wesley

  2. Anon et al.: A measure of transaction processing power. In: Stonebraker, M. (ed.) Readings in database systems, 2nd. edn., pp. 442–454. San Mateo, CA, Morgan Kaufmann, 1988

    Google Scholar 

  3. Bayer, R., Schkolnick, M.: Concurrency of operations on B-trees. In: Stonebraker, M. (ed.) Readings in database systems, pp. 129–139, San Mateo, CA, Morgan Kaufmann, 1988

    Google Scholar 

  4. Bernstein, P. A., Hadzilacos, V., Goodman, N.: Concurrency control and recovery in database systems. Reading, MA, Addison-Wesley 1987

    Google Scholar 

  5. Corner, D.: The ubiquitous B-tree. Comput. Surv. 11, 121–137 (1979)

    Article  Google Scholar 

  6. Copeland, G., Keller, T., Smith, M.: Database buffer and disk configuring and the battle of the bottlenecks. Proc. 4th International Workshop High Performance Transaction Systems, September 1991

  7. Dadam, P., Lum, V., Praedel, U., Shlageter, G.: Selective deferred index maintenance & concurrency control in integrated information systems. Proc. 11th International VLDB Conference, pp. 142–150, August 1985

  8. Daniels, D. S., Spector, A. Z., Thompson, D. S.: Distributed logging for transaction processing. ACM SIGMOD Transactions pp. 82–96, (1987)

  9. Fagin, R., Nievergelt, J., Pippenger, N., Strong, H. R.: Extendible hashing — a fast access method for dynamic files. ACM Trans. Database Systems, 4 (N3) 315–344 (1979)

    Article  Google Scholar 

  10. Garcia-Molina, H., Salem, K.: Sagas. ACM SIGMOD Transactions, pp. 249–259 (1987)

  11. Garcia-Molina, H., Gawlick, D., Klein, J., Kleissner, K., Salem, K.: Coordinating multitransactional activities. Princeton University Report, CS-TR-247-90, February 1990.

  12. Garcia-Molina, H.: Modelling long-running activities as nested sagas. IEEE Data Engineering 14 (No 1) 14–18 (1991)

    Google Scholar 

  13. Gray, J., Putzolu, F.: The five minute rule for trading memory for disk accessess and the 10 Byte rule for trading memory for CPU time. Proc. 1987 ACM SIGMOD Conference, pp. 395–398

  14. Gray, J., Reuter, A.: transaction processing, concepts and techniques. San Mateo, CA, Morgan Kaufmann 1992

    Google Scholar 

  15. Kolovson, C. P., Stonebraker, M.: Indexing techniques for historical databases. Proc. 1989 IEEE Data Engineering Conference, pp. 138–147

  16. Lomet, D., Salzberg, B.: Access methods for multiversion data. Proc. 1989 ACM SIGMOD Conference, pp. 315–323

  17. Lomet, D., Salzberg, B.: The performance of a multiversion access method. Proc. 1990 ACM SIGMOD Conference, pp. 353–363.

  18. Lomet, D. B.: A simple bounded disorder file organization with good performance. ACM Trans. on Database Systems 13 (4) 525–551 (1988)

    Article  MATH  Google Scholar 

  19. O’Neil, P. E.: The escrow transactional method. TODS, 11 (No. 4) 405–430 (1986)

    Article  Google Scholar 

  20. O’Neil, P., Cheng, E., Gawlick, D., O’Neil, E.: The log-structured merge-tree (LSM-tree). UMass/Boston Math & CS Dept Technical Report, 91–6, November, 1991

  21. O’Neil, P. E.: The SB-tree: An index-sequential structure for high-performance sequential acess. Acta Inf. 29, 241–265 (1992)

    Article  MATH  MathSciNet  Google Scholar 

  22. O’Neil, P., Weikum, G.: A log-structured history data access method (LHAM). Presented at the Fifth International Workshop on High-Performance Transaction Systems, September 1993

  23. Rosemblum, M., Ousterhout, J. K.: The design and implementation of a log structured file system. ACM Trans. Comp. Sys. 10 (No. 1) 26–52 (1992)

    Article  Google Scholar 

  24. Reuter, A.: Contracts: A means for controlling system activities beyond transactional boundaries. Proc. 3rd International Workshop on High Performance Transaction Systems, September 1989

  25. Severance, D. G., Lohman, G. M.: Differential files: their application to the maintenance of large databases. ACM Trans. Database Systems 1 (No 3) 256–267 (1976)

    Article  Google Scholar 

  26. Transaction Processing Performance Council (TPC): TPC BENCHMARK A standard specification. The performance handbook: for database and transaction processing systems, 2nd edn. San Mateo, CA, Morgan Kauffman, 1993

    Google Scholar 

  27. Wächter, H.: Contracts: A means for improving reliability in distributed computing. IEEE Spring CompCon 91

  28. Weikum, G.: Principles and realization strategies for multilevel transaction management. ACM Trans. Database Systems. 16 (No 1) 132–180 (1991)

    Article  Google Scholar 

  29. Wodnicki, J. M., Kurtz, S. C.: GPD performance evaluation lab database 2 Version 2 Utility analysis, IBM Document Number GG09-1031-0, September 28, 1989

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Computer Science, University of Massachusetts/Boston, 02125-3393, Boston, MA, USA

    Patrick O’Neil & Elizabeth O’Neil

  2. Digital Equipment Corporation, 94301, Palo Alto, CA, USA

    Edward Cheng

  3. Oracle Corporation, Redwood Shores, CA, USA

    Dieter Gawlick

Authors
  1. Patrick O’Neil
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Edward Cheng
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Dieter Gawlick
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Elizabeth O’Neil
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Patrick O’Neil.

Rights and permissions

Reprints and permissions

About this article

Cite this article

O’Neil, P., Cheng, E., Gawlick, D. et al. The log-structured merge-tree (LSM-tree). Acta Informatica 33, 351–385 (1996). https://doi.org/10.1007/s002360050048

Download citation

  • Received:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s002360050048

Keywords

Search

Navigation