distributed coordination across
multiple servers that necessarily increases latency of all transactions fed
through this layer. Thus deterministic database systems may experience
higher latency than nondeterministic systems. However, recall that
deterministic systems shorten the
commit protocol, and that they can
commit trans actions after only partial execution. Thus, the latency disadvantage of preprocessing is often
counterbalanced (and more) by these
Information versus performance
trade-off. The easiest way to avoid
non-determinism arising from OS
thread scheduling to is to disallow
concurrency. This obviously would
result in poor performance. Each of
the deterministic database implementation techniques we described
earlier in this article (for example,
partitioning, ordered locking, and
dependency graphs) improves performance by enabling concurrency
at the cost of requiring information
about transactions before they begin
executing: either the partitions that
they will access, or the actual records
they will access. Although the OLLP
technique can be used to eliminate
the burden on the user to either provide this information directly or to
submit transactions where it can
be derived from inspection of the
transaction, OLLP adds latency and
increases the cost of processing the
transaction.d Furthermore, the OLLP
technique can only be used if the entire transaction is submitted to the
system at once, so the “trial run” can
complete. Therefore, OLLP cannot
be used in conjunction with “
interactive transactions,” in which a client communicates with the system
over multiple round-trips. Thus, for
interactive transactions, there is an
information vs. performance trade-off: either the client must declare the
access set of transactions (either in
terms of partitions or records) when
they are submitted to the system, or
otherwise the system will default to
(slow) serial execution.
d This cost increase is usually much less than
doubling the cost of the transaction, since the
trial mode can take several short-cuts not possible during runtime processing. 26
Deterministic database systems have
shown to be a promising direction
to improving transactional database system scalability, modularity,
throughput, and replication. However, all recent implementations have
limited or no support for interactive
transactions, thereby preventing
their use in many existing deployments. If the advantages of deterministic database systems will be realized in the coming years, one of two
things must occur: either database
users must accept a stored procedure
interface to the system, or additional
research must be performed in order
to enable improved support for interactive transactions.
Acknowledgments. This work was
sponsored by the NSF under grants
IIS-1763797 and IIS-1718581. We
thank Alexander Thomson and Kun
Ren for their contributions to the research described in this article.
1. Batoory, D., Barnett, J., Garza, J., Smith, K., Tsukuda,
K., Twichell, B. and Wise, T. Genesis: An extensible
database management system. IEEE Trans. Software
2. Berenson, H., Bernstein, P., Gray, J., Melton, J., O’Neil,
E. and O’Neil, P. A critique of ANSI SQL isolation
levels. In Proc. of SIGMOD, 1995, 1–10.
3. Bernstein, P.A. and Goodman, N. Concurrency control
in distributed database systems. ACM Comput. Surv.
13, 3 (1981), 185–221.
4. Bernstein, P.A., Hadzilacos, V. and Goodman, N.
Concurrency Control and Recovery in Database
Systems. Addison-Wesley, 1987.
5. Breitbart, Y., Komondoor, R., Rastogi, R., Seshadri, S.
and Silberschatz, A. Update propagation protocols for
replicated databates. In Proc. of SIGMOD, 1999.
6. Carey, M. J., Dewitt, D.J., Graefe, G., Haight, D. M.,
Richardson, J. E., Schuh, D. T., Shekita, E. J. and
Vandenberg, S. L. The EXODUS extensible DBMS
project: An overview. In Readings in Object-Oriented
Database Systems, 1990.
7. Chaudhuri, S. and Weikum, G. Rethinking database
system architecture: Towards a self-tuning risc-style
database system. In Proc. of VLDB, 2000.
8. Faleiro, J. M. and Abadi, D. J. Rethinking serializable
multiversion concurrency control. PVLDB 8, 11 (2015).
9. Faleiro, J. M., Abadi, D. J., and Hellerstein, J.M. High
performance transactions via early write visiblity.
PVLDB 10, 5 (2017).
10. Faleiro, J. M., Thomson, A. and Abadi, D.J. Lazy
evaluation of transactions in database systems. In
Proc. of SIGMOD, 2014, 15–26.
11. Gray, J., Helland, P., O’Neil, P. and Shasha, D. The
dangers of replication and a solution. In Proc. of
12. Harizopoulos, S., Abadi, D.J., Madden, S. R. and
Stonebraker, M. OLTP through the looking glass, and
what we found there. In Proc. of SIGMOD, 2008.
13. Hellerstein, J.M., Stonebraker, M. and Hamilton, J.
Architecture of a Database System, 2007.
14. Jimenez-Peris, R., Patino-Martinez, M. and Arevalo,
S. Deterministic scheduling for transactional
multithreaded replicas. In Proc. of SRDS, 2000.
15. Kemme, B. and Alonso, G. Don’t be lazy, be consistent:
Postgres-R, a new way to implement database
replication. In Proc. of VLDB, 2000, 134–143.
16. King, R. P., Halim, N., Garcia-Molina, H. and Polyzois,
C. A. Management of a remote backup copy for disaster
recovery. ACM Trans. Database Syst. 16, 2 (1991),
17. Larson, P.-A., Blanas, S., Diaconu, C., Freedman,
C., Patel, J.M., and Zwilling, M. High-performance
concurrency control mechanisms for main-memory
databases. PVLDB 5, 4 (Dec. 2011), 298–309.
18. Lomet, D., Fekete, A., Weikum, G. and Zwilling, M.
Unbundling transaction services in the cloud.
In CIDR, 2009.
19. Malviya, N., Weisberg, A., Madden, S., and Stonebraker,
M. Rethinking main memory OLTP recovery. In Proc. of
ICDE, 2014, 604–615.
20. Mohan, C., Haderle, D., Lindsay, B., Pirahesh, H., and
Schwarz, P. Aries: A transaction recovery method
supporting fine-granularity locking and partial
rollbacks using write-ahead logging. ACM Trans.
Database Syst. 17, 1 (1992), 94–162.
21. Pacitti, E., Minet, P., and Simon, E. Fast algorithms
for maintaining replica consistency in lazy master
replicated databases. In Proc. of VLDB, 1999, 126–137.
22. Polyzois, C.A. and Garcia-Molina, H. Evaluation of
remote backup algorithms for transaction-processing
systems. ACM Trans. Database Syst. 19, 3 (1994),
23. Ren, K., Diamond, T., Abadi, D.J. and Thomson,
A. Low-overhead asynchronous checkpointing in
main-memory database systems. In SIGMOD, 2016,
24. Ren, K., Faleiro, J. and Abadi, D.J. Design principles
for scaling multi-core OLTP under high contention. In
Proc. of SIGMOD, 2016.
25. Ren, K., Thomson, A. and Abadi, D.J. Lightweight
locking for main memory database systems. PVLDB 6,
2 (2012), 145–156.
26. Ren, K., Thomson, A. and Abadi, D.J. An evaluation of
the advantages and disadvantages of deterministic
database systems. PVLDB 7, 10 (2014), 821–832.
27. Ren, K., Thomson, A. and Abadi, D.J. Vll: A lock
manager redesign for main memory database
systems. VLDB J. 24, 5 (Oct. 2015), 681–705.
28. Schneider, F. Implementing fault-tolerant services
using the state machine approach: A tutorial. ACM
Comput. Surv. 22, 4 (1990).
29. Sears, R. C. Stasis: Flexible Transactional Storage. Ph. D.
thesis, EECS Department, UC Berkeley, 2010.
30. Stonebraker, M., Madden, S., Abadi, D., Harizopoulos, S.,
Hachem, N. and Helland, P. The end of an architectural
era (it’s time for a complete rewrite). In Proc. of VLDB,
31. Thomson, A. and Abadi, D. J. The case for determinism
in database systems. In Proc. of VLDB, 2010.
32. Thomson, A. and Abadi, D.J. Modularity and scalability
in Calvin. IEEE Data Engineering Bulletin 36, 2 (2013),
33. Thomson, A., Diamond, T., Weng, S.-C., Ren, K., Shao, P.
and Abadi, D. J. Calvin: Fast distributed transactions for
partitioned database systems. In SIGMOD, 2012.
34. Thomson, A., Diamond, T., Weng, S.-C., Ren, K., Shao,
P. and Abadi, D. J. Fast distributed transactions and
strongly consistent replication for OLTP database
systems. ACM Trans. Database Syst. 39, 2 (May 2014),
35. Tu, S., Zheng, W., Kohler, E., Liskov, B. and Madden,
S. Speedy transactions in multicore in-memory
databases. In Proc. of SOSP, 2013.
36. Wu, S.-H., Feng, T.-Y., Liao, M.-K., Pi, S.-K. and Lin,
Y.-S. T-part: Partitioning of transactions for for ward-pushing in deterministic database systems. In Proc. of
Daniel J. Abadi ( firstname.lastname@example.org) is the Darnell-Kanal
Professor of Computer Science at the University of
Maryland, College Park, MD, USA.
Jose M. Faleiro ( email@example.com) is a Ph. D. student
at Yale University, New Haven, CT, USA.
Copyright held by owners/authors.
Publication rights licensed to ACM. $15.00.