5 ms·

Cross shard transactions at 10M requests per second

86 points by makmanalp 8y ago

peter_d_sherman 8y ago
The idea of creating an abstraction layer over thousands of MySQL nodes is a novel one, and should be commended. I like the idea a lot, and by DropBox's scale and success, it must work well. I would be interested in a granular point-by-point comparison between this layer and native MySQL replication. In other words, if someone were to rewrite MySQL replication such that it did everything that this abstraction layer did (in addition to replication), what would it need to do? Now (and this is strictly academic/theoretical), I'm curious what would be necessary to modify in the abstraction layer if the abstraction layer was to support a whole bunch of disparate SQL databases underneath it, i.e., Postgres, SQLite, SQL Server, Oracle, etc. (No, that wouldn't be practical, but it would be an interesting exercise to really learn where the gotchas might be where working with different SQL dialects...)
- elvinyung 8y ago
  Vitess [1] is a similar kind of abstraction layer that's compatible with the native MySQL wire protocol. It also supports atomic cross-shard transactions using 2PC. [1] https://vitess.io/ https://vitess.io/
  - jbyers 8y ago
    Notably, from that site: "Vitess has been serving all YouTube database traffic since 2011, and has now been adopted by many enterprises for their production needs." (I work at Google, but not on Vitess or YouTube)
  - dalyons 8y ago
    Does anyone know of a vitess equivalent for Postgres? I’d love to use it
    - elvinyung 8y ago
      Citus seems to be doing pretty well.
    - segmondy 8y ago
      You can make one, it's open source. You just have to rewrite the MySQL pieces to work for Postgres.
    - ddorian43 8y ago
      Yugabyte is trying to do it but by using the storage-api (and not a proxy)
  - tahara 8y ago
    Vitess is a bit less of an application abstraction layer in the sense of Edgestore, Tao, and others, and more of an operational abstraction that hides physical sharding and taking the pain out of repartitioning to accommodate new capacity. I've had some opportunity to work with the Vitess (now PlanetScale) folks on some other databases-related work and it's a great community and product so I would definitely encourage people to check it out.
- jfim 8y ago
  > The idea of creating an abstraction layer over thousands of MySQL nodes is a novel one, and should be commended Twitter did it eight years ago with Gizzard. See http://highscalability.com/blog/2011/12/19/how-twitter-stores-250-million-tweets-a-day-using-mysql.html http://highscalability.com/blog/2011/12/19/how-twitter-store... and https://blog.twitter.com/engineering/en_us/a/2010/introducing-gizzard-a-framework-for-creating-distributed-datastores.html https://blog.twitter.com/engineering/en_us/a/2010/introducin...
- gregwebs 8y ago
  It seems like you are looking for TiDB? It is deployed as a single MySQL compatible database that transparently partitions data so that writes scale horizontally. TiDB is actually the MySQL compute layer. TiKV is the underlying distributed Key-Value store that different protocols can be implemented on (one company made a TiKV-backed Redis). Disclaimer: I work on this database. https://pingcap.com/docs/ https://pingcap.com/docs/ https://tikv.org/ https://tikv.org/
- aptxkid 8y ago
  Adding abstraction over MySQL is not novel. Facebook did it many years ago https://www.usenix.org/system/files/conference/atc13/atc13-bronson.pdf https://www.usenix.org/system/files/conference/atc13/atc13-b...
- ignoramous 8y ago
  AWS DynamoDB is built on top of MySql according to this post: https://news.ycombinator.com/item?id=13173927 https://news.ycombinator.com/item?id=13173927 Amazon's Sable is built on top BerkeleyDB, acc to this: https://news.ycombinator.com/item?id=17595644 https://news.ycombinator.com/item?id=17595644
amenghra 8y ago
I have witnessed first hand companies who decide to do cross-shard transactions when in fact they don’t really need it. For example, imagine that you have a distributed key-value store. You want to users (on different shards) to either both be able to see a piece of content or neither. You can achieve this by allocating a key on either shard (or a third shard), writing a reference to each user’s shards. If all of those writes succeed, you can write to the new key which was allocated. If any writes fail, you can bail and your data is consistent. Wrap the above logic in a nice library and your service will scale horizontally.
- aaronbwebber 8y ago
  Then you are just forcing your application to deal with the dangling reference in the case of a failed "transaction". The whole point of TPC is not to have to deal with that complexity. Whether that complexity is actually difficult to deal with is a whole other question, I could easily believe that for some applications it's not but apparently for Dropbox it's worth implementing TPC to avoid dealing with it.
  - amenghra 8y ago
    Yes and no. You end up with a weaker api, eg you can’t perform atomic updates across shards. But you can create data atomically, perhaps build atomic counters, etc. Giving up some flexibility in the types of atomic operations you can do for a simpler architecture is sometimes worth it.
    - heavenlyblue 8y ago
      This also does not work well when two different processes try to do the modification at the same time. Or otherwise this does not work for entities that will be changed.
- tahara 8y ago
  For us (Dropbox), the threshold ended up being multiple product teams having to implement ad-hoc two-phase commit over their datatypes and burning engineer hours not to implement it but to prove that they had gotten it right and to handle the clean up after any unsuccessful writes. You're right that most systems probably don't need 2PC, which is why Edgestore didn't include it until now. As mentioned in the post, we finally felt that we had reached the right balance of tradeoffs to justify the API-level primitive.
elvinyung 8y ago
Ok, while we're at this, I think that the most important part of the post was this: > Edgestore data was already well-collocated, which meant that cross-shard transactions ended up being fairly rare in practice—only 5-10% of Edgestore transactions involve multiple shards. What if performant cross-shard transactions is a red herring, and the thing that we should be looking more into is reliable automatic data colocation to avoid performing cross-shard transactions as much as possible? There's decent amount of academic research around this, with projects like SWORD [1] and Schism [2] that study shard load balancing as a problem of hypergraph partitioning. It seems like this might be worth incorporating into commercial distributed database projects. [1] http://www.cs.umd.edu/~amol/papers/edbt13.pdf http://www.cs.umd.edu/~amol/papers/edbt13.pdf [2] http://www.vldb.org/pvldb/vldb2010/papers/R04.pdf http://www.vldb.org/pvldb/vldb2010/papers/R04.pdf
- tahara 8y ago
  Thanks for the references -- will take a look. Edgestore's API is set up to shepherd users into good collocation patterns by default, and a lot of work over the past year or two went into improving collocation and educating users about best practices. The collocation efforts were actually orthogonal to implementing cross-shard transactions, but they were obviously very beneficial.
  - elvinyung 8y ago
    Thanks -- just curious, am I correct to interpret this to basically mean that thus far, the performance of the system basically relies on users to explicitly define colos nicely within their application-level data model? For some reason this reminds me of something like the entity group concept in Google's Megastore [1]. [1] http://cidrdb.org/cidr2011/Papers/CIDR11_Paper32.pdf http://cidrdb.org/cidr2011/Papers/CIDR11_Paper32.pdf
    - tahara 8y ago
      There is somewhere between where we are today and a completely uncollocated free-for-all where the system would fall over. There's a separate axis of the rate at which users request transactions (with locks) versus non-transactional writes using optimistic concurrency control that would come into play sooner. Our guidance is therefore that users try to reserve transactions for when there's correctness critical reasons why two objects need to be updated together and rely on asynchronous primitives to handle "eventually consistent" mutations.
bufferoverflow 8y ago
Dropbox is very easy to shard though, the users are mostly independent. Take something like Facebook, and it becomes much much harder - anybody can friend anybody, anybody can message anybody, anybody can like or comment on public posts.
- tahara 8y ago
  That's what we thought, too. (Un)fortunately(?) that's not the case anymore given our product offerings :)

86 points by makmanalp 8y ago

The idea of creating an abstraction layer over thousands of MySQL nodes is a novel one, and should be commended. I like the idea a lot, and by DropBox's scale and success, it must work well. I would be interested in a granular point-by-point comparison between this layer and native MySQL replication. In other words, if someone were to rewrite MySQL replication such that it did everything that this abstraction layer did (in addition to replication), what would it need to do? Now (and this is strictly academic/theoretical), I'm curious what would be necessary to modify in the abstraction layer if the abstraction layer was to support a whole bunch of disparate SQL databases underneath it, i.e., Postgres, SQLite, SQL Server, Oracle, etc. (No, that wouldn't be practical, but it would be an interesting exercise to really learn where the gotchas might be where working with different SQL dialects...)

elvinyung 8y ago
Vitess [1] is a similar kind of abstraction layer that's compatible with the native MySQL wire protocol. It also supports atomic cross-shard transactions using 2PC. [1] https://vitess.io/ https://vitess.io/
- jbyers 8y ago
  Notably, from that site: "Vitess has been serving all YouTube database traffic since 2011, and has now been adopted by many enterprises for their production needs." (I work at Google, but not on Vitess or YouTube)
- dalyons 8y ago
  Does anyone know of a vitess equivalent for Postgres? I’d love to use it
  - elvinyung 8y ago
    Citus seems to be doing pretty well.
  - segmondy 8y ago
    You can make one, it's open source. You just have to rewrite the MySQL pieces to work for Postgres.
  - ddorian43 8y ago
    Yugabyte is trying to do it but by using the storage-api (and not a proxy)
- tahara 8y ago
  Vitess is a bit less of an application abstraction layer in the sense of Edgestore, Tao, and others, and more of an operational abstraction that hides physical sharding and taking the pain out of repartitioning to accommodate new capacity. I've had some opportunity to work with the Vitess (now PlanetScale) folks on some other databases-related work and it's a great community and product so I would definitely encourage people to check it out.
jfim 8y ago
> The idea of creating an abstraction layer over thousands of MySQL nodes is a novel one, and should be commended Twitter did it eight years ago with Gizzard. See http://highscalability.com/blog/2011/12/19/how-twitter-stores-250-million-tweets-a-day-using-mysql.html http://highscalability.com/blog/2011/12/19/how-twitter-store... and https://blog.twitter.com/engineering/en_us/a/2010/introducing-gizzard-a-framework-for-creating-distributed-datastores.html https://blog.twitter.com/engineering/en_us/a/2010/introducin...
gregwebs 8y ago
It seems like you are looking for TiDB? It is deployed as a single MySQL compatible database that transparently partitions data so that writes scale horizontally. TiDB is actually the MySQL compute layer. TiKV is the underlying distributed Key-Value store that different protocols can be implemented on (one company made a TiKV-backed Redis). Disclaimer: I work on this database. https://pingcap.com/docs/ https://pingcap.com/docs/ https://tikv.org/ https://tikv.org/
aptxkid 8y ago
Adding abstraction over MySQL is not novel. Facebook did it many years ago https://www.usenix.org/system/files/conference/atc13/atc13-bronson.pdf https://www.usenix.org/system/files/conference/atc13/atc13-b...
ignoramous 8y ago
AWS DynamoDB is built on top of MySql according to this post: https://news.ycombinator.com/item?id=13173927 https://news.ycombinator.com/item?id=13173927 Amazon's Sable is built on top BerkeleyDB, acc to this: https://news.ycombinator.com/item?id=17595644 https://news.ycombinator.com/item?id=17595644

amenghra 8y ago

I have witnessed first hand companies who decide to do cross-shard transactions when in fact they don’t really need it. For example, imagine that you have a distributed key-value store. You want to users (on different shards) to either both be able to see a piece of content or neither. You can achieve this by allocating a key on either shard (or a third shard), writing a reference to each user’s shards. If all of those writes succeed, you can write to the new key which was allocated. If any writes fail, you can bail and your data is consistent. Wrap the above logic in a nice library and your service will scale horizontally.

aaronbwebber 8y ago
Then you are just forcing your application to deal with the dangling reference in the case of a failed "transaction". The whole point of TPC is not to have to deal with that complexity. Whether that complexity is actually difficult to deal with is a whole other question, I could easily believe that for some applications it's not but apparently for Dropbox it's worth implementing TPC to avoid dealing with it.
- amenghra 8y ago
  Yes and no. You end up with a weaker api, eg you can’t perform atomic updates across shards. But you can create data atomically, perhaps build atomic counters, etc. Giving up some flexibility in the types of atomic operations you can do for a simpler architecture is sometimes worth it.
  - heavenlyblue 8y ago
    This also does not work well when two different processes try to do the modification at the same time. Or otherwise this does not work for entities that will be changed.
tahara 8y ago
For us (Dropbox), the threshold ended up being multiple product teams having to implement ad-hoc two-phase commit over their datatypes and burning engineer hours not to implement it but to prove that they had gotten it right and to handle the clean up after any unsuccessful writes. You're right that most systems probably don't need 2PC, which is why Edgestore didn't include it until now. As mentioned in the post, we finally felt that we had reached the right balance of tradeoffs to justify the API-level primitive.

elvinyung 8y ago

Ok, while we're at this, I think that the most important part of the post was this: > Edgestore data was already well-collocated, which meant that cross-shard transactions ended up being fairly rare in practice—only 5-10% of Edgestore transactions involve multiple shards. What if performant cross-shard transactions is a red herring, and the thing that we should be looking more into is reliable automatic data colocation to avoid performing cross-shard transactions as much as possible? There's decent amount of academic research around this, with projects like SWORD [1] and Schism [2] that study shard load balancing as a problem of hypergraph partitioning. It seems like this might be worth incorporating into commercial distributed database projects. [1] http://www.cs.umd.edu/~amol/papers/edbt13.pdf http://www.cs.umd.edu/~amol/papers/edbt13.pdf [2] http://www.vldb.org/pvldb/vldb2010/papers/R04.pdf http://www.vldb.org/pvldb/vldb2010/papers/R04.pdf

tahara 8y ago
Thanks for the references -- will take a look. Edgestore's API is set up to shepherd users into good collocation patterns by default, and a lot of work over the past year or two went into improving collocation and educating users about best practices. The collocation efforts were actually orthogonal to implementing cross-shard transactions, but they were obviously very beneficial.
- elvinyung 8y ago
  Thanks -- just curious, am I correct to interpret this to basically mean that thus far, the performance of the system basically relies on users to explicitly define colos nicely within their application-level data model? For some reason this reminds me of something like the entity group concept in Google's Megastore [1]. [1] http://cidrdb.org/cidr2011/Papers/CIDR11_Paper32.pdf http://cidrdb.org/cidr2011/Papers/CIDR11_Paper32.pdf
  - tahara 8y ago
    There is somewhere between where we are today and a completely uncollocated free-for-all where the system would fall over. There's a separate axis of the rate at which users request transactions (with locks) versus non-transactional writes using optimistic concurrency control that would come into play sooner. Our guidance is therefore that users try to reserve transactions for when there's correctness critical reasons why two objects need to be updated together and rely on asynchronous primitives to handle "eventually consistent" mutations.

bufferoverflow 8y ago

Dropbox is very easy to shard though, the users are mostly independent. Take something like Facebook, and it becomes much much harder - anybody can friend anybody, anybody can message anybody, anybody can like or comment on public posts.

tahara 8y ago
That's what we thought, too. (Un)fortunately(?) that's not the case anymore given our product offerings :)