Scaling Services with Shard Manager
engineering.fb.com
engineering.fb.com
> The concept of using sharding to scale services is not new. However, to the best of our knowledge, we are the only generic sharding platform in the industry that achieves wide adoption at our scale.
In typical Facebook engineering parlance they have to claim to be the first ones ever to do it. Fragile egos over there.
Putting hubris aside, I think it's great that a decade or so into large scale computing we're starting to see patterns emerge for scaling stateful systems and be able to build good generic solutions to them. This is sorely needed especially on the control plane side which historically hasn't gotten the attention that data planes have.
0 - https://www.usenix.org/system/files/conference/osdi16/osdi16...
1 - https://blog.acolyer.org/2016/12/02/slicer-auto-sharding-for...
https://blog.twitter.com/engineering/en_us/a/2010/introducin...
The key advantage of Gizzard is that it divides the data into key ranges and treats it as a shard. If a shard is too hot, it can dynamically adjust the size of the range. Gizzard also acts as a traffic routing layer that sends requests to the right server and coordinates data replication.
Shard Manager (SM) uses fixed-size shards and uses shard migration to reduce load on hot servers. Unlike Gizzard, SM focuses on being a control plane service and client traffic does not flow through SM. That functionality is delegated to Facebook’s separate traffic routing framework. SM supports more generic sharding applications and uses add/drop shard protocol to coordinate state migration. Gizzard focuses on data store applications and requires write operations to be idempotent and commutative in order to support state migration.
SM started in 2011. To our knowledge, SM probably predated the other systems, but we were so excited in 2016 when noticing the publication of the GS paper. We learned a lot from that paper about both the similarity and difference, which will be further explained below. With SM’s hundreds of diverse applications running on hundreds of thousands of servers, we speculate that SM might be the largest deployment in the industry according to published numbers.
One advantage of GS is that it does not divide the key space into fixed “shards” ahead of time. In other words, the “shards” are transparent to applications. Internally, GS can dynamically merge or split “shards” and move “shards” around to balance the load as needed. This is more flexible than SM’s approach, which divides the key space into fixed shards. SM can move shards around to balance the load, but currently does not merge or split shards.
On the other hand, to enable shard merge or split, GS hashes application keys into its internal 64-bit random key space, which is then internally divided into “shards”. This approach means that it is hard to support certain constraints, e.g., preference for key locality, which are important for some of our user-facing global applications. In addition, to our knowledge, SM supports a wider range of load-balancing constraints by leveraging a generic constraint solver, which allows us to more easily introduce new constraints or change the load balancing algorithm.
Facebook infrastructure takes a layered but fully integrated approach, which enables SM, as one layer of an integrated stack, to offer more out-of-the-box functionalities. For example, SM is integrated with our cluster management system called Twine via TaskControl; see details in https://engineering.fb.com/data-center-engineering/twine/. This allows SM to better manage shard availability in the face of planned and unplanned infra churns, including container rolling upgrades, maintenance operations, and hardware failures.
There are certainly more similarities or differences among SM, GS, Azure Service Fabric, and Apache Helix, beyond what we can describe here. We hope to publish a paper in the future to dive more deeply into these topics.