8 ms·

A history of the distributed transactional database

105 points by evanweaver 8y ago

deleted 8y ago
[deleted]
evanweaver 8y ago
For further reading, Dan Abadi's post at http://dbmsmusings.blogspot.com/2018/09/newsql-database-systems-are-failing-to.html http://dbmsmusings.blogspot.com/2018/09/newsql-database-syst... addresses the Spanner issues more directly. I don't think there's a great reference for the Percolator transaction architecture specifically, but there is a brief description here: https://blog.octo.com/en/my-reading-of-percolator-architecture-a-google-search-engine-component/ https://blog.octo.com/en/my-reading-of-percolator-architectu... One thing I learned recently is that FoundationDB is essentially the Percolator model (timestamp oracle), even though FoundationDB predated the Percolator paper.
- williamallthing 8y ago
  What consistency model does FDB provide?
  - evanweaver 8y ago
    In my understanding, it can provide strict serializability. The main difference from actual Percolator is that FoundationDB manages range locks through a logically separate pool of in-memory lock caches, instead of writing durable locks to the replicas, but the end result is the same. External consistency for read/write transactions within a single datacenter at a time.
    - wwilson 8y ago
      There is no correctness limitation on using FoundationDB in multiple datacenters, and if you do most of your writes in a single datacenter while using the others for disaster recovery, the latency is honestly pretty good too (especially with some of the new 6.0 features). EDIT: I was wondering why this conversation was giving me deja vu, and then I remembered that you and Dave discussed this in detail last month: https://news.ycombinator.com/item?id=18258805 https://news.ycombinator.com/item?id=18258805
      - evanweaver 8y ago
        I forgot about that; thanks for the link. I didn't intend to imply a correctness limitation.
wmf 8y ago
It's kinda sad that Tandem and similar work has been forgotten. I've wondered what we could learn from such history and never gotten a clear answer.
- zzzcpan 8y ago
  What didn't we learn about Tandem and NonStop? Pretty much anything there is to learn we did learn.
- yourapostasy 8y ago
  HP still manufactures and maintains Tandem systems, under the HPE Integrity Nonstop brand [1]. Just like IBM Systems Magazine [2], there is a lot of proprietary tech described that takes awhile to seep into Linux and the open source world. You can still read the Tandem documentation, so the ideas are still there to be picked up by anyone interested in re-implementing them on Linux. [1] https://www.hpe.com/us/en/servers/nonstop.html https://www.hpe.com/us/en/servers/nonstop.html [2] http://ibmsystemsmag.com/ http://ibmsystemsmag.com/
  - atombender 8y ago
    Is there a technical writeup anywhere about the design and architecture of Tandem? One that has enough detail that a skilled database designer could understand it well enough to reimplement it?
    - yourapostasy 8y ago
      Not in one place, and not sufficient to give anyone an implementation roadmap, but that is to be expected, as this is still a commercially-active architecture. They're not about to give away their architectural advantages that easily. But if you read between the lines, and are savvy enough to look up the background research papers, you'll pick up most of the technology. The devil as they say however, is in the engineering details, and that's where you'll run into a lot of special sauce. You'll want to look at their Transaction Monitoring Facility (TMF) in detail. They baked fault tolerance right into the bones of the architectural design, and TMF is an identifiable chunk of how that was done. You aren't going to be able to pull off the same kind of fault tolerance they're delivering at just the database level, too. Their thinking about fault tolerance goes way beyond, down into the hardware level though it stops short of the silicon.
zzzcpan 8y ago
> This is not at all a theoretical problem. Deliberately inducing withdrawal races at ATMs is a widely reported type of fraud. Thus, databases need “external consistency”, colloquially known as ACID. In all those fraud cases banks were actually running ACID databases as they always do. Because ACID has nothing to do with "external consistency", unless you can run it in a human brain, which you can't. Interactions with humans can only be eventually consistent. But nobody even bothers to have ACID all the way to the web browser or APIs, so it's only limited to the application, but not beyond that. With all the frauds and double spending problems remaining unsolved. Overall the usual FaunaDB attacks on other systems, especially AP. Strong eventual consistency of AP systems is actually much stronger, than ACID and is much much easier to verify and AP is where the cutting edge of distributed systems research happens. But more importantly, SEC can offer the best theoretically possible performance and latency for multi datancenter deployments. While distributed ACID transactions don't even show viability in multi datacenter deployments at the moment, forcing vendors to degrade into weak consistency models in such setups.
- freels 8y ago
  I don't think it's correct to pit ACID against AP systems this way. Consistency is orthogonal. ACID is model for reasoning about transaction guarantees in terms of allowed anomalies at each isolation level. Serializability in ACID implies CP over AP, but weaker levels don't have the same requirement. It still comes down to tradeoffs for a specific use-case of a database system. Not sure what you're getting at when you say ACID transactions don't work in a multi-DC context. FaunaDB aside, there are many production systems (commercial or internal) that provide them that I am aware of.
  - espadrine 8y ago
    > Not sure what you're getting at when you say ACID transactions don't work in a multi-DC context. I expect they are talking about DC as _regions_, not DC as _availability zones_ (in the AWS parlance). Planetary databases hit latency issues on cross-region ACID transactions. Whatever the sharding, a transaction modifying one piece whose leader is in Paris and another in Beijing will have at least the round-trip time between the two. It is already unforgiving at that scale, and will become inadmissible at interplanetary scale, requiring some form of eventual consistency. However, I still expect that we will retain ACID operations for local changes. Humans tolerate latencies that are necessary for planetary ACID transactions. The combination of the size of the Earth and the speed of light is a lucky draw.
iblaine 8y ago
TiDB should be in here but trying to keep up with the latest trends is overwhelming.
- freels 8y ago
  TiDB uses the Percolator protocol
spullara 8y ago
I was using IBM DB/2 Parallel Edition in 1995 at Trans Union for a year 2000 project to move off the mainframe. It was running on 60 RS/6000 SP2s. I was hoping the blog post would go further back in time. https://pdfs.semanticscholar.org/9c08/4a56c1c625da116eca474208d9780539ceff.pdf https://pdfs.semanticscholar.org/9c08/4a56c1c625da116eca4742...
doombolt 8y ago
Apache Ignite is an ACID key-value CP database that does not depend on clock.
known 8y ago
Cap theorem states that it is impossible for a distributed data store to simultaneously provide more than two out off Consistency, Availability and Partition tolerance https://en.wikipedia.org/wiki/CAP_theorem https://en.wikipedia.org/wiki/CAP_theorem
likeabbas 8y ago
Where does FoundationDB fit with this?
majidazimi 8y ago
Why the hell does everyone make a banking example when they want to talk about transactions? BANKS RUN ON EVENTUAL CONSISTENCY, PERIOD. Another point worth mentioning is that, single transaction coordinator model is undervalued in community. Majority of systems have the following query pattern (sorted descending): 1. Single key read --> you don't need to contact coordinator 2. Single key write --> you don't need to contact coordinator. OCC with simple version number works here. 3. Multi-key asynchronous write (updating second, third keys using a pub/sub infrastructure) --> you don't need to contact coordinator in this case. 4. True multi-key transactions that should happen atomically --> need to contact coordinator If a single coordinator can process 20-30K/s transactions of category 4, then total throughput of the system would be around 300K queries per second which is sufficient for many workloads.
- pritambaral 8y ago
  > BANKS RUN ON EVENTUAL CONSISTENCY, PERIOD. Especially American banks. I can't think of any other retail banking market where banks abuse eventual consistency so bad that transfers take days to clear.
deleted 8y ago
[deleted]
dongxu 8y ago
TiDB developer here, 'This model is equivalent to the multiprocessor RDBMS—which also uses a single physical clock, because it’s a single machine—but the system bus is replaced by the network. In practice, these systems give up multi-region scale out and are confined to a single datacenter.' I don't think so, although Percolaotor has a single point of physical clock, but it is easy to eliminate the SPOF problem by using high-availability algorithms such as Raft or Paxos (Just like the design in TiDB). On the other hand, the strong consistency across multiple data centers, I think, without hardware devices such as TrueTime, it is difficult to have low latency and strong consistency while allowing writes happen in multiple data centers at the same time. The more realistic situation is that there is a primary data center (where both read and write occur), and multiple data centers guarantee high availability with strong consistency, we can achieve this goal by scheduling Paxos or Raft leader to the primary data center.

105 points by evanweaver 8y ago

deleted 8y ago

[deleted]

For further reading, Dan Abadi's post at http://dbmsmusings.blogspot.com/2018/09/newsql-database-systems-are-failing-to.html http://dbmsmusings.blogspot.com/2018/09/newsql-database-syst... addresses the Spanner issues more directly. I don't think there's a great reference for the Percolator transaction architecture specifically, but there is a brief description here: https://blog.octo.com/en/my-reading-of-percolator-architecture-a-google-search-engine-component/ https://blog.octo.com/en/my-reading-of-percolator-architectu... One thing I learned recently is that FoundationDB is essentially the Percolator model (timestamp oracle), even though FoundationDB predated the Percolator paper.

williamallthing 8y ago
What consistency model does FDB provide?
- evanweaver 8y ago
  In my understanding, it can provide strict serializability. The main difference from actual Percolator is that FoundationDB manages range locks through a logically separate pool of in-memory lock caches, instead of writing durable locks to the replicas, but the end result is the same. External consistency for read/write transactions within a single datacenter at a time.
  - wwilson 8y ago
    There is no correctness limitation on using FoundationDB in multiple datacenters, and if you do most of your writes in a single datacenter while using the others for disaster recovery, the latency is honestly pretty good too (especially with some of the new 6.0 features). EDIT: I was wondering why this conversation was giving me deja vu, and then I remembered that you and Dave discussed this in detail last month: https://news.ycombinator.com/item?id=18258805 https://news.ycombinator.com/item?id=18258805
    - evanweaver 8y ago
      I forgot about that; thanks for the link. I didn't intend to imply a correctness limitation.

wmf 8y ago

It's kinda sad that Tandem and similar work has been forgotten. I've wondered what we could learn from such history and never gotten a clear answer.

zzzcpan 8y ago
What didn't we learn about Tandem and NonStop? Pretty much anything there is to learn we did learn.
yourapostasy 8y ago
HP still manufactures and maintains Tandem systems, under the HPE Integrity Nonstop brand [1]. Just like IBM Systems Magazine [2], there is a lot of proprietary tech described that takes awhile to seep into Linux and the open source world. You can still read the Tandem documentation, so the ideas are still there to be picked up by anyone interested in re-implementing them on Linux. [1] https://www.hpe.com/us/en/servers/nonstop.html https://www.hpe.com/us/en/servers/nonstop.html [2] http://ibmsystemsmag.com/ http://ibmsystemsmag.com/
- atombender 8y ago
  Is there a technical writeup anywhere about the design and architecture of Tandem? One that has enough detail that a skilled database designer could understand it well enough to reimplement it?
  - yourapostasy 8y ago
    Not in one place, and not sufficient to give anyone an implementation roadmap, but that is to be expected, as this is still a commercially-active architecture. They're not about to give away their architectural advantages that easily. But if you read between the lines, and are savvy enough to look up the background research papers, you'll pick up most of the technology. The devil as they say however, is in the engineering details, and that's where you'll run into a lot of special sauce. You'll want to look at their Transaction Monitoring Facility (TMF) in detail. They baked fault tolerance right into the bones of the architectural design, and TMF is an identifiable chunk of how that was done. You aren't going to be able to pull off the same kind of fault tolerance they're delivering at just the database level, too. Their thinking about fault tolerance goes way beyond, down into the hardware level though it stops short of the silicon.

zzzcpan 8y ago

> This is not at all a theoretical problem. Deliberately inducing withdrawal races at ATMs is a widely reported type of fraud. Thus, databases need “external consistency”, colloquially known as ACID. In all those fraud cases banks were actually running ACID databases as they always do. Because ACID has nothing to do with "external consistency", unless you can run it in a human brain, which you can't. Interactions with humans can only be eventually consistent. But nobody even bothers to have ACID all the way to the web browser or APIs, so it's only limited to the application, but not beyond that. With all the frauds and double spending problems remaining unsolved. Overall the usual FaunaDB attacks on other systems, especially AP. Strong eventual consistency of AP systems is actually much stronger, than ACID and is much much easier to verify and AP is where the cutting edge of distributed systems research happens. But more importantly, SEC can offer the best theoretically possible performance and latency for multi datancenter deployments. While distributed ACID transactions don't even show viability in multi datacenter deployments at the moment, forcing vendors to degrade into weak consistency models in such setups.

freels 8y ago
I don't think it's correct to pit ACID against AP systems this way. Consistency is orthogonal. ACID is model for reasoning about transaction guarantees in terms of allowed anomalies at each isolation level. Serializability in ACID implies CP over AP, but weaker levels don't have the same requirement. It still comes down to tradeoffs for a specific use-case of a database system. Not sure what you're getting at when you say ACID transactions don't work in a multi-DC context. FaunaDB aside, there are many production systems (commercial or internal) that provide them that I am aware of.
- espadrine 8y ago
  > Not sure what you're getting at when you say ACID transactions don't work in a multi-DC context. I expect they are talking about DC as _regions_, not DC as _availability zones_ (in the AWS parlance). Planetary databases hit latency issues on cross-region ACID transactions. Whatever the sharding, a transaction modifying one piece whose leader is in Paris and another in Beijing will have at least the round-trip time between the two. It is already unforgiving at that scale, and will become inadmissible at interplanetary scale, requiring some form of eventual consistency. However, I still expect that we will retain ACID operations for local changes. Humans tolerate latencies that are necessary for planetary ACID transactions. The combination of the size of the Earth and the speed of light is a lucky draw.

iblaine 8y ago

TiDB should be in here but trying to keep up with the latest trends is overwhelming.

freels 8y ago
TiDB uses the Percolator protocol

spullara 8y ago

I was using IBM DB/2 Parallel Edition in 1995 at Trans Union for a year 2000 project to move off the mainframe. It was running on 60 RS/6000 SP2s. I was hoping the blog post would go further back in time. https://pdfs.semanticscholar.org/9c08/4a56c1c625da116eca474208d9780539ceff.pdf https://pdfs.semanticscholar.org/9c08/4a56c1c625da116eca4742...

doombolt 8y ago

Apache Ignite is an ACID key-value CP database that does not depend on clock.

known 8y ago

Cap theorem states that it is impossible for a distributed data store to simultaneously provide more than two out off Consistency, Availability and Partition tolerance https://en.wikipedia.org/wiki/CAP_theorem https://en.wikipedia.org/wiki/CAP_theorem

likeabbas 8y ago

Where does FoundationDB fit with this?

majidazimi 8y ago

Why the hell does everyone make a banking example when they want to talk about transactions? BANKS RUN ON EVENTUAL CONSISTENCY, PERIOD. Another point worth mentioning is that, single transaction coordinator model is undervalued in community. Majority of systems have the following query pattern (sorted descending): 1. Single key read --> you don't need to contact coordinator 2. Single key write --> you don't need to contact coordinator. OCC with simple version number works here. 3. Multi-key asynchronous write (updating second, third keys using a pub/sub infrastructure) --> you don't need to contact coordinator in this case. 4. True multi-key transactions that should happen atomically --> need to contact coordinator If a single coordinator can process 20-30K/s transactions of category 4, then total throughput of the system would be around 300K queries per second which is sufficient for many workloads.

pritambaral 8y ago
> BANKS RUN ON EVENTUAL CONSISTENCY, PERIOD. Especially American banks. I can't think of any other retail banking market where banks abuse eventual consistency so bad that transfers take days to clear.

deleted 8y ago

[deleted]

dongxu 8y ago

TiDB developer here, 'This model is equivalent to the multiprocessor RDBMS—which also uses a single physical clock, because it’s a single machine—but the system bus is replaced by the network. In practice, these systems give up multi-region scale out and are confined to a single datacenter.' I don't think so, although Percolaotor has a single point of physical clock, but it is easy to eliminate the SPOF problem by using high-availability algorithms such as Raft or Paxos (Just like the design in TiDB). On the other hand, the strong consistency across multiple data centers, I think, without hardware devices such as TrueTime, it is difficult to have low latency and strong consistency while allowing writes happen in multiple data centers at the same time. The more realistic situation is that there is a primary data center (where both read and write occur), and multiple data centers guarantee high availability with strong consistency, we can achieve this goal by scheduling Paxos or Raft leader to the primary data center.