Skip to main content
SpringerLink
Log in

A partition model and strategy based on the Stoer–Wagner algorithm for SaaS multi-tenant data

  • Methodologies and Application
  • Published:
Soft Computing Aims and scope Submit manuscript

Abstract

Partition technology is the key step to realize the extensional architecture in the cloud and support the data placement on multiple nodes. This paper proposes a multi-tenant data partition model and algorithm for SaaS (Software as a Service) application. It solves the problem that data partitions would produce lots of distributed transactions caused by the existing cloud data management. The management is unconscious of SaaS tenants during the transformation from a single node to multiple nodes in the cloud to obtain the dynamic extension of the system’s scale. With the increase of tenants and data, the single node becomes the bottleneck of the whole system. Fortunately, the scale of the whole system can be expanded by data partition. This paper puts forward a multi-tenant data partition model with three-layer structure: Tenant layer, Relevance, Group layer and Tenant Partition layer. Furthermore, we propose the concepts of Relevance, Relevance Value and Relevance Matrix. The customized tables for one tenant accessed by the same transactions can form a minimum high-relevance granularity based on the Relevance Group algorithm. Then we construct an abstracted graph, where group is the basic unit and transaction accessing is weight. Through the Stoer–Wagner algorithm, the multi-tenant partition with group as granularity is obtained. The partition algorithm proposed in this paper enables the greatest reduction of distributed transactions between partitions while realizing the dynamic extension on multiple nodes for multi-tenant data based on shared storage. Experiments show that the number of distributed transactions is reduced dramatically compared with other data partition techniques. We also prove that the SaaS applications run at high efficiency.

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

Access this article

Log in via an institution

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

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6
Fig. 7
Fig. 8
Fig. 9
Fig. 10

Similar content being viewed by others

References

  • Agrawal D, El Abbadi A, Antony S, Das S (2010) Data management challenges in cloud computing infrastructures. In: Databases in networked information systems.Springer, pp 1–10

  • Agrawal S, Narasayya V, Yang B (2004) Integrating vertical and horizontal partitioning into automated physical database design. In: Proceedings of the 2004 ACM SIGMOD international conference on management of data. ACM, pp 359–370

  • Aulbach S, Jacobs D, Kemper A, Seibold M (2009) A comparison of flexible schemas for software as a service. In: Proceedings of the 2009 ACM SIGMOD international conference on management of data. ACM, pp 881–888

  • Baker J, Bond C, Corbett JC, Furman JJ, Khorlin A, Larson J, Leon J-M, Li Y, Lloyd A, Yushprakh V (2011) Megastore: providing scalable, highly available storage for interactive services. CIDR 11:223–234

    Google Scholar 

  • Campbell DG, Kakivaya G, Ellis N (2010) Extreme scale with full sql language support in microsoft sql azure. In: Proceedings of the 2010 ACM SIGMOD international conference on management of data. ACM, pp 1021–1024

  • Chang F, Dean J, Ghemawat S, Hsieh WC, Wallach DA, Burrows M, Chandra T, Fikes A, Gruber RE (2008) Bigtable: a distributed storage system for structured data. ACM Trans Comput Syst (TOCS) 26(2):4

    Article  Google Scholar 

  • Chen X, Li J, Susilo W (2012) Efficient fair conditional payments for outsourcing computations. Inf Forensics Secur IEEE Trans 7(6):1687–1694

    Article  Google Scholar 

  • Cooper BF, Ramakrishnan R, Srivastava U, Silberstein A, Bohannon P, Jacobsen H-A, Puz N, Weaver D, Yerneni R (2008) Pnuts: Yahoo!’s hosted data serving platform. Proc VLDB Endow 1(2):1277–1288

    Article  Google Scholar 

  • Curino C, Jones Zhang Y, Eugene W, Madden S (2010) The case for a database service. New England Database Summit, Relational cloud

    Google Scholar 

  • Das S, Agrawal D, El Abbadi A (2013) Elastras: an elastic, scalable, and self-managing transactional database for the cloud. ACM Trans Database Syst(TODS) 38(1):5

  • Hartung I, Goldschmidt B (2014) Performance analysis of windows azure data storage options. In: Large-scale scientific computing. Springer, pp 499–506

  • Li H (2013) Research on key technology in multi-tenant data architecture for saas application. Chongqing University (Doctoral Dissertation), Chongqing

  • Li H, Yanga D, Zhangb X (2013) A mixed partitioning approach for multi-tenant data schema. J Inf Comput Sci 10:4869–4878

    Article  Google Scholar 

  • Li J, Kim K (2010) Hidden attribute-based signatures without anonymity revocation. Inf Sci 180(9):1681–1689

    Article  MathSciNet  MATH  Google Scholar 

  • Li J, Wang Y (2006) Universal designated verifier ring signature (proof) without random oracles. In: Emerging directions in embedded and ubiquitous computing. Springer, pp 332–341

  • Li J, Zhang F, Wang Y (2006) A new hierarchical id-based cryptosystem and cca-secure pke. In: Emerging directions in embedded and ubiquitous computing. Springer, pp 362–371

  • Li J, Kim K, Zhang F, Chen X (2007) Aggregate proxy signature and verifiably encrypted proxy signature. In: Provable security. Springer, pp 208–217

  • Li J, Wang Q, Wang C, Cao N, Ren K, Lou W (2010) Fuzzy keyword search over encrypted data in cloud computing. In: INFOCOM, 2010 Proceedings IEEE. IEEE, pp 1–5

  • Li J, Li J, Chen X, Jia C, Lou W (2015a) Identity-based encryption with outsourced revocation in cloud computing. Comput IEEE Trans 64(2):425–437

    Article  MathSciNet  MATH  Google Scholar 

  • Li J, Li YK, Chen X, Lee PPC, Lou W (2015b) A hybrid cloud approach for secure authorized deduplication. Parallel Distrib Syst IEEE Trans 26(5):1206–1216

    Article  Google Scholar 

  • Li X (2015) Research on placement mechanism for saas multi-tenant data. Shandong University (Doctoral Dissertation), Jinan

  • Li X-N, Li Q-Z, Kong L-J, Pang C (2012) Research on multi-tenant data partition mechanism for saas application based on shared schema. J Commun 33(S1):110–120

  • Palmieri F, Fiore U, Ricciardi S (2008) A minimum cut interference-based integrated rwa algorithm for multi-constrained optical transport networks. J Netw Syst Manag 16(4):421–448

    Article  Google Scholar 

  • Rao J, Zhang C, Megiddo N, Lohman G (2002) Automating physical database design in a parallel database. In: Proceedings of the 2002 ACM SIGMOD international conference on management of data. ACM, pp 558–569

  • Schiller O, Cipriani N, Mitschang B (2013) Prorea: live database migration for multi-tenant rdbms with snapshot isolation. In: Proceedings of the 16th international conference on extending database technology. ACM, pp 53–64

  • Stoer M, Wagner F (1997) A simple min-cut algorithm. J Acm 44(4):585–591

  • Stonebraker M (2010) Sql databases v. nosql databases. Commun ACM 53(4):10–11

    Article  Google Scholar 

  • Taft R, Mansour E, Serafini M, Duggan J, Elmore AJ, Aboulnaga A, Pavlo A, Stonebraker M (2014) E-store: fine-grained elastic partitioning for distributed transaction processing systems. Proc VLDB Endow 8(3):245–256

    Article  Google Scholar 

  • Wang J, Ma H, Tang Q, Li J, Zhu H, Ma S, Chen X (2013) Efficient verifiable fuzzy keyword search over encrypted data in cloud computing. Comput Sci Inf Syst 10(2):667–684

    Article  Google Scholar 

  • Weissman CD, Bobrowski S (2009) The design of the force. com multitenant internet application development platform. In: SIGMOD Conference, pp 889–896

  • Zilio DC (1998) Physical database design decision algorithms and concurrent reorganization for parallel database systems. PhD thesis, Citeseer

Download references

Acknowledgments

This work was partially supported by the National Natural Science Foundation of China (No. 61501276; No. 61502218), Outstanding Young Scientists Foundation Grant of Shandong Province (No. BS2014DX016), Guangzhou Scholars Project (No. 1201561613). Professional Development Support Project for Application-oriented Talents Training in general undergraduate Universities funded by Shandong Provincial Education Department and Shandong Province Finance Bureau in 2015.

Author information

Authors and Affiliations

  1. School of Data Science and Software Engineering, Qingdao University, Qingdao, 266071, China

    Xiaona Li, Junli Zhao, Yumei Ma, Pingping Wang & Hongyi Sun

  2. Department of Mathematics, Guangzhou University, Guangzhou, 510006, China

    Yi Tang

Authors
  1. Xiaona Li
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Junli Zhao
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yumei Ma
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Pingping Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Hongyi Sun
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. Yi Tang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Xiaona Li.

Ethics declarations

Conflict of interest

Xiaona Li declares that she has no conflict of interest. Junli Zhao declares that she has no conflict of interest. Yumei Ma declares that she has no conflict of interest. Pingping Wang declares that she has no conflict of interest. Hongyi Sun declares that she has no conflict of interest. Yi Tang declares that he has no conflict of interest.

Ethical approval

This article does not contain any studies with human participants or animals performed by any of the authors.

Additional information

Communicated by V. Loia.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Li, X., Zhao, J., Ma, Y. et al. A partition model and strategy based on the Stoer–Wagner algorithm for SaaS multi-tenant data. Soft Comput 21, 6121–6132 (2017). https://doi.org/10.1007/s00500-016-2169-z

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00500-016-2169-z

Keywords

Search

Navigation