Upgrade to Pro — share decks privately, control downloads, hide ads and more …

Ringpop by Uber

Ringpop by Uber

Jeff Wolski of Uber presented at the San Francisco Riak Meetup about Ringpop, their home-grown, distributed application-layer sharding framework.

Here is that presentation. Thanks again Jeff!

Basho Technologies

April 09, 2015
Tweet

More Decks by Basho Technologies

Other Decks in Programming

Transcript

  1. WHAT IS RINGPOP? • Ringpop is an implementation of a

    membership protocol. • Ringpop maintains a consistent hash ring of its members. • Ringpop offers forwarding as a convenience. • Ringpop is open source software.
  2. WHAT IS RINGPOP? • Ringpop implements a variation of the

    SWIM gossip protocol. • Ringpop gossips over TCP. • Ringpop computes membership checksums to perform full-sync operations. RINGPOP AS A MEMBERSHIP PROTOCOL A B C
  3. WHAT IS RINGPOP? • Ringpop uses farmhash as its hashing

    function. • Ringpop uses a red-black tree for its ring. • Ringpop adds a uniform number of replica points per node. RINGPOP AS A CONSISTENT HASH RING A A A C C C B B B
  4. WHAT IS RINGPOP? • Ringpop has codified a handle or

    forward pattern. • Ringpop uses tchannel as its transport. • Ringpop’s forwarding is transparent to the developer. RINGPOP FORWARDING
  5. HOW DOES RINGPOP WORK? Ringpop bootstraps itself with a bootstrap

    file or host list. No multi-cast, yet. The first node has no one to join. It exists as a 1- node cluster. The second node starts up and queries the same bootstrap list. This time it finds A. A and B exchange info. They form a 2- node cluster and hash their addresses along the ring. A [“127.0.0.1:3000”, “127.0.0.1:3001”, “127.0.0.1:3002”] JOIN A B [“127.0.0.1:3000”, “127.0.0.1:3001”, “127.0.0.1:3002”] JOIN A B RINGPOP FORMING A CLUSTER
  6. HOW DOES RINGPOP WORK? C decides to join and now

    we have a 3- node cluster. Each of them ping one another periodically. A receives a request and hashes the shard key. It uses the handle or forward pattern to determine where the request should be processed. A decides to forward the request to B. BB C A PING PING PING A POST /123 dest = A.lookup(123) if (dest == A) handle(123) else forward(dest, 123) RINGPOP FORWARDING REQUESTS
  7. HOW DOES RINGPOP WORK? If C crashes or is down

    for maintenance, pings will fail and other members of the ring will notice. Whoever notices will transition between the 3 states above. C is removed from the ring. A and B continue to ping one another. BB C A PING PING PING alive suspect faulty A B PING C RINGPOP DETECTING FAULTS
  8. WHAT CAN YOU BUILD WITH RINGPOP? • Stateful HTTP long-poll

    services. • Client/server sync services. • Actor model-like systems. • Rate limiters. • Geospatial services. • Aggregate counting services. • Overlay routing services. RINGPOP HAS BEEN USED TO BUILD: Photo Caption 10px #B0B0B8 nemo enim ipsam voluptatem quia voluptas sit aspernatur aut odit aut fugit, sed quia consequuntur.
  9. HOW MIGHT ONE EXTEND RINGPOP? • Enable actor model-like systems.

    • Support replication. • Guarantee reliable background operations. RINGPOP CAN BE EXTENDED TO: Photo Caption 10px #B0B0B8 nemo enim ipsam voluptatem quia voluptas sit aspernatur aut odit aut fugit, sed quia consequuntur.
  10. HOW MIGHT ONE EXTEND RINGPOP? Ringpop bootstraps itself with a

    bootstrap file or host list. No multi-cast, yet. The first node has no one to join. It exists as a 1- node cluster. The second node starts up and queries the same bootstrap list. This time it finds A. A and B exchange info. They form a 2- node cluster and hash their addresses along the ring. A [“127.0.0.1:3000”, “127.0.0.1:3001”, “127.0.0.1:3002”] JOIN A B [“127.0.0.1:3000”, “127.0.0.1:3001”, “127.0.0.1:3002”] JOIN A B RINGPOP AS AN ACTOR-LIKE SYSTEM
  11. HOW MIGHT ONE EXTEND RINGPOP? Ringpop bootstraps itself with a

    bootstrap file or host list. No multi-cast, yet. The first node has no one to join. It exists as a 1- node cluster. The second node starts up and queries the same bootstrap list. This time it finds A. A and B exchange info. They form a 2- node cluster and hash their addresses along the ring. A [“127.0.0.1:3000”, “127.0.0.1:3001”, “127.0.0.1:3002”] JOIN A B [“127.0.0.1:3000”, “127.0.0.1:3001”, “127.0.0.1:3002”] JOIN A B RINGPOP WITH REPLICATION
  12. HOW MIGHT ONE EXTEND RINGPOP? Ringpop bootstraps itself with a

    bootstrap file or host list. No multi-cast, yet. The first node has no one to join. It exists as a 1- node cluster. The second node starts up and queries the same bootstrap list. This time it finds A. A and B exchange info. They form a 2- node cluster and hash their addresses along the ring. A [“127.0.0.1:3000”, “127.0.0.1:3001”, “127.0.0.1:3002”] JOIN A B [“127.0.0.1:3000”, “127.0.0.1:3001”, “127.0.0.1:3002”] JOIN A B RINGPOP WITH RELIABLE BACKGROUND OPERATIONS
  13. HOW HAS RINGPOP DEALT WITH BAD NODES? Flap damping is

    a technique used to suss out bad nodes and evict them from a cluster. We detect flaps by storing membership update history and penalize a node when a flap is detected. When the penalty exceeds a suppress limit, the node is damped. RINGPOP FLAP DAMPING B is a bad node if its behavior is erratic and it intermittently fails to respond to ping requests. A B PING
  14. RINGPOP FLAP DAMPING Ringpop bootstraps itself with a bootstrap file

    or host list. No multi-cast, yet. The first node has no one to join. It exists as a 1- node cluster. The second node starts up and queries the same bootstrap list. This time it finds A. A and B exchange info. They form a 2- node cluster and hash their addresses along the ring. A [“127.0.0.1:3000”, “127.0.0.1:3001”, “127.0.0.1:3002”] JOIN A B [“127.0.0.1:3000”, “127.0.0.1:3001”, “127.0.0.1:3002”] JOIN A B
  15. THAT’S IT! Presented by Jeff Wolski <[email protected]> IF YOU ARE

    INSPIRED BY ANY OF THE CONTENT IN THIS TALK, GET MORE INSPIRATION FROM: AMAZON DYNAMO BGP ROUTE FLAP DAMPING CONSISTENT HASHING FARMHASH RINGPOP SWIM GOSSIP PROTOCOL TCHANNEL