Skip to main content

2018 | OriginalPaper | Buchkapitel

Efficient Snapshot Isolation in Paxos-Replicated Database Systems

verfasst von : Jinwei Guo, Peng Cai, Bing Xiao, Weining Qian, Aoying Zhou

Erschienen in: Database Systems for Advanced Applications

Verlag: Springer International Publishing

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Modern database systems are increasingly deployed in a cluster of commodity machines with Paxos-based replication technique to offer better performance, higher availability and fault-tolerance. The widely adopted implementation is that one database replica is elected to be a leader and to be responsible for transaction requests. After the transaction execution is completed, the leader generates transaction log and commit this transaction until the log has been replicated to a majority of replicas. The state of the leader is always ahead of that of the follower replicas since the leader commits the transactions firstly and then notifies other replicas of the latest committed log entries in the later communication. As the follower replica can’t immediately provide the latest snapshot, both read-write and read-only transactions would be executed at the leader to guarantee the strong snapshot isolation semantic. In this work, we design and implement an efficient snapshot isolation scheme. This scheme uses adaptive timestamp allocation to avoid frequently requesting the leader to assign transaction timestamps. Furthermore, we design an early log replay mechanism for follower replicas. It allows the follower replica to execute a read operation without waiting to replay log to generate the required snapshot. Comparing with the conventional implementation, we experimentally show that the optimized snapshot isolation for Paxos-replicated database systems has better performance in terms of scalability and throughput.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literatur
2.
Zurück zum Zitat Bailis, P., Davidson, A., Fekete, A., et al.: Highly available transactions: virtues and limitations. PVLDB 7(3), 181–192 (2013) Bailis, P., Davidson, A., Fekete, A., et al.: Highly available transactions: virtues and limitations. PVLDB 7(3), 181–192 (2013)
3.
Zurück zum Zitat Baker, J., Bond, C., Corbett, J.C., et al.: Megastore: providing scalable, highly available storage for interactive services. In: CIDR, pp. 223–234 (2011) Baker, J., Bond, C., Corbett, J.C., et al.: Megastore: providing scalable, highly available storage for interactive services. In: CIDR, pp. 223–234 (2011)
4.
Zurück zum Zitat Berenson, H., Bernstein, P., Gray, J., et al.: A critique of ANSI SQL isolation levels. SIGMOD Rec. 24(2), 1–10 (1995)CrossRef Berenson, H., Bernstein, P., Gray, J., et al.: A critique of ANSI SQL isolation levels. SIGMOD Rec. 24(2), 1–10 (1995)CrossRef
5.
Zurück zum Zitat Binnig, C., Hildenbrand, S., et al.: Distributed snapshot isolation: global transactions pay globally, local transactions pay locally. VLDB J. 23(6), 987–1011 (2014)CrossRef Binnig, C., Hildenbrand, S., et al.: Distributed snapshot isolation: global transactions pay globally, local transactions pay locally. VLDB J. 23(6), 987–1011 (2014)CrossRef
6.
Zurück zum Zitat Bornea, M.A., Hodson, O., Elnikety, S., Fekete, A.: One-copy serializability with snapshot isolation under the hood. In: ICDE, pp. 625–636 (2011) Bornea, M.A., Hodson, O., Elnikety, S., Fekete, A.: One-copy serializability with snapshot isolation under the hood. In: ICDE, pp. 625–636 (2011)
7.
Zurück zum Zitat Chairunnanda, P., Daudjee, K., Özsu, T.M.: ConfluxDB: multi-master replication for partitioned snapshot isolation databases. In: VLDB, pp. 947–958 (2014) Chairunnanda, P., Daudjee, K., Özsu, T.M.: ConfluxDB: multi-master replication for partitioned snapshot isolation databases. In: VLDB, pp. 947–958 (2014)
8.
Zurück zum Zitat Cooper, B.F., Silberstein, A., Tam, E., Ramakrishnan, R., Sears, R.: Benchmarking cloud serving systems with YCSB. In: SoCC, pp. 143–154 (2010) Cooper, B.F., Silberstein, A., Tam, E., Ramakrishnan, R., Sears, R.: Benchmarking cloud serving systems with YCSB. In: SoCC, pp. 143–154 (2010)
9.
Zurück zum Zitat Corbett, J.C., Dean, J., Epstein, M., et al.: Spanner: Google’s globally distributed database. TOCS 31(3), 8 (2013)CrossRef Corbett, J.C., Dean, J., Epstein, M., et al.: Spanner: Google’s globally distributed database. TOCS 31(3), 8 (2013)CrossRef
10.
Zurück zum Zitat Daudjee, K., Salem, K.: Lazy database replication with snapshot isolation. In: VLDB, pp. 715–726 (2006) Daudjee, K., Salem, K.: Lazy database replication with snapshot isolation. In: VLDB, pp. 715–726 (2006)
11.
Zurück zum Zitat Elnikety, S., Zwaenepoel, W., Pedone, F.: Database replication using generalized snapshot isolation. In: SRDS, pp. 73–84. IEEE Computer Society (2005) Elnikety, S., Zwaenepoel, W., Pedone, F.: Database replication using generalized snapshot isolation. In: SRDS, pp. 73–84. IEEE Computer Society (2005)
12.
Zurück zum Zitat Gray, J., Helland, P., O’Neil, P., Shasha, D.: The dangers of replication and a solution. SIGMOD Rec. 25(2), 173–182 (1996)CrossRef Gray, J., Helland, P., O’Neil, P., Shasha, D.: The dangers of replication and a solution. SIGMOD Rec. 25(2), 173–182 (1996)CrossRef
13.
Zurück zum Zitat Jung, H., Han, H., Fekete, A., Röhm, U.: Serializable snapshot isolation for replicated databases in high-update scenarios. In: VLDB, pp. 783–794 (2011) Jung, H., Han, H., Fekete, A., Röhm, U.: Serializable snapshot isolation for replicated databases in high-update scenarios. In: VLDB, pp. 783–794 (2011)
14.
Zurück zum Zitat Kemme, B., Alonso, G.: A suite of database replication protocols based on group communication primitives. In: ICDCS, pp. 156–163 (1998) Kemme, B., Alonso, G.: A suite of database replication protocols based on group communication primitives. In: ICDCS, pp. 156–163 (1998)
15.
Zurück zum Zitat Kemme, B., Alonso, G.: Database replication: a tale of research across communities. PVLDB 3(1), 5–12 (2010) Kemme, B., Alonso, G.: Database replication: a tale of research across communities. PVLDB 3(1), 5–12 (2010)
16.
Zurück zum Zitat Kraska, T., Pang, G., Franklin, M.J., et al.: MDCC: multi-data center consistency. In: EuroSys, pp. 113–126 (2013) Kraska, T., Pang, G., Franklin, M.J., et al.: MDCC: multi-data center consistency. In: EuroSys, pp. 113–126 (2013)
17.
18.
Zurück zum Zitat Lamport, L.: Paxos made simple. ACM SIGACT News 32(4), 18–25 (2001) Lamport, L.: Paxos made simple. ACM SIGACT News 32(4), 18–25 (2001)
19.
Zurück zum Zitat Lin, Y., Kemme, B., Patiño Martínez, M., Jiménez-Peris, R.: Middleware based data replication providing snapshot isolation. In: SIGMOD, pp. 419–430 (2005) Lin, Y., Kemme, B., Patiño Martínez, M., Jiménez-Peris, R.: Middleware based data replication providing snapshot isolation. In: SIGMOD, pp. 419–430 (2005)
20.
Zurück zum Zitat Moraru, I., Andersen, D.G., Kaminsky, M.: Paxos quorum leases: fast reads without sacrificing writes. In: SOCC, pp. 22:1–22:13 (2014) Moraru, I., Andersen, D.G., Kaminsky, M.: Paxos quorum leases: fast reads without sacrificing writes. In: SOCC, pp. 22:1–22:13 (2014)
21.
Zurück zum Zitat Mu, S., Nelson, L., Lloyd, W., Li, J.: Consolidating concurrency control and consensus for commits under conflicts. In: OSDI, pp. 517–532 (2016) Mu, S., Nelson, L., Lloyd, W., Li, J.: Consolidating concurrency control and consensus for commits under conflicts. In: OSDI, pp. 517–532 (2016)
22.
Zurück zum Zitat Ongaro, D., Ousterhout, J.K.: In search of an understandable consensus algorithm. In: ATC (2014) Ongaro, D., Ousterhout, J.K.: In search of an understandable consensus algorithm. In: ATC (2014)
23.
Zurück zum Zitat Pedone, F., Wiesmann, M., Schiper, A., Kemme, B., Alonso, G.: Understanding replication in databases and distributed systems. In: ICDCS, pp. 464–474 (2000) Pedone, F., Wiesmann, M., Schiper, A., Kemme, B., Alonso, G.: Understanding replication in databases and distributed systems. In: ICDCS, pp. 464–474 (2000)
24.
Zurück zum Zitat Rao, J., Shekita, E.J., Tata, S.: Using Paxos to build a scalable, consistent, and highly available datastore. In: VLDB, pp. 243–254 (2011) Rao, J., Shekita, E.J., Tata, S.: Using Paxos to build a scalable, consistent, and highly available datastore. In: VLDB, pp. 243–254 (2011)
25.
Zurück zum Zitat Schneider, F.B.: Implementing fault-tolerant services using the state machine approach: a tutorial. CSUR 22(4), 299–319 (1990)CrossRef Schneider, F.B.: Implementing fault-tolerant services using the state machine approach: a tutorial. CSUR 22(4), 299–319 (1990)CrossRef
26.
Zurück zum Zitat Wiesmann, M., Schiper, A.: Comparison of database replication techniques based on total order broadcast. TKDE 17(4), 551–566 (2005) Wiesmann, M., Schiper, A.: Comparison of database replication techniques based on total order broadcast. TKDE 17(4), 551–566 (2005)
27.
Zurück zum Zitat Wu, Y., Arulraj, J., Lin, J., et al.: An empirical evaluation of in-memory multi-version concurrency control. Proc. VLDB Endow. 10(7), 781–792 (2017)CrossRef Wu, Y., Arulraj, J., Lin, J., et al.: An empirical evaluation of in-memory multi-version concurrency control. Proc. VLDB Endow. 10(7), 781–792 (2017)CrossRef
28.
Zurück zum Zitat Zhang, I., Sharma, N.K., Szekeres, A., et al.: Building consistent transactions with inconsistent replication. In: SOSP, pp. 263–278. ACM (2015) Zhang, I., Sharma, N.K., Szekeres, A., et al.: Building consistent transactions with inconsistent replication. In: SOSP, pp. 263–278. ACM (2015)
Metadaten
Titel
Efficient Snapshot Isolation in Paxos-Replicated Database Systems
verfasst von
Jinwei Guo
Peng Cai
Bing Xiao
Weining Qian
Aoying Zhou
Copyright-Jahr
2018
DOI
https://doi.org/10.1007/978-3-319-91458-9_40