I was recently asked as an exercise to design a scalable graph.

My first intuition was how to seperate the graph and distribute it (sharding,consistent hashing..etc)

Turns out my thinking was on the wrong line, I know what scalability is, but it seems it is a bit hard to think about it pragmatically.

What is the pragmatic way of thinking about scalability. I know I need high-availability, replication, fault tolerance, but what are some of the common patterns/paradigms needed to implement these key points?

| improve this question | | | | |
  • 3
    graph can mean a lot of things. Are you talking about an object graph, a line graph, or something else? – Caleb Apr 15 '13 at 16:09
  • What makes you think that distributing your graph is not a pragmatic approach? – Mike Apr 15 '13 at 16:12
  • @Caleb talking about an object graph – Stan R. Apr 15 '13 at 16:23
  • Scalability has nothing to do with high availability, replication or fault tolerance. While there are many applications that might require some/all of the above to be acceptably scalable, they are 4 completely different topics. Perhaps you can narrow down the problem so a more focused answer can be given. – Dunk Apr 16 '13 at 15:29

I think scalability is really about having the ability to add capacity by adding components (hardware, typically) without any individual component becoming ever more loaded as system demand increases. In other words, in a scalable system there is no bottleneck component that will ultimately limit performance and throughput. Instead, performance and throughput ideally remain constant or at least shrink more slowly than demand on the system grows.

You are right to keep concepts like fault-tolerance and high-availability (and their implementation via replication) in mind, but I see them as more concerned with reliability than scalability. While often implemented together, they are two different things.

In your graph example, what is it that needs to scale?

  • Is it access to the graph (large numbers of simultaneous users)?

  • Regarding access, is it write access that needs to scale, or just read access?

  • Is it the size of the graph itself (e.g. large numbers of nodes like Facebook's social graph)?

  • What about complexity? Does each node need to support arbitrarily large numbers of connections?

  • Does each node (and therefore the system as a whole) need to hold arbitrarily large amounts of data?

These are some pragmatic issues that need to be addressed when one talks about scalability. Like most design challenges, it's really all about breaking the problem down into the core issues that need to be addressed.

Lastly, I see techniques like asynchronous programming as contributing to efficiency, but not scalability. Unless you are doing something major like replacing a quadratic algorithm with a linear one, efficiencies alone will not help much with scalability (see Amdahl's Law). They will help with the cost of scalability (a very pragmatic issue), but not with the potential for it.

| improve this answer | | | | |
  • I see techniques like asynchronous programming as contributing to efficiency, but not scalability -- In general, better efficiency is going to make for better scalability, all other things being equal. – Robert Harvey Apr 16 '13 at 14:43
  • Excellent answer. Questions about scale, for me, always track back to system parameters around use (must be resilient, fast lookup, fast write, etc) and on which dimensions you can expect growth (amount of unique transactions, size of transactions, amount of stored data, data volatility, etc). – dietbuddha May 4 '15 at 3:27

Answer to this question can get very complicated if you need to support parallel requests while you need to split single request across multiple processing nodes.

There are 2 types of scaling,

  1. Vertical
  2. Horizontal

For Vertical scaling (adding more CPU power / adding more memory).

  1. Since the operation happens in single process, one of the consideration is about how to distribute the operation into different threads and combine the results.

  2. If parallel requests needs to be processed then concurrency is also comes into play. And if the single graph is modified by multiple parallel requests this could very complicated, and you may need to think about a scenario like this,

If the graph has Node A,B and C where C has links to both A and B, and parallel requests wants to change A and B, then concurrency issue happens on C. One way to sort it is to determine which nodes are affected by each request and queue the conflicting requests, or just to merge the changes. But this depends on your graph

For Horizontal scaling (happens in multiple processes in different physical processing nodes), and when it comes to the graph processing you can improve processing in different ways,

1. Split your request across processing nodes to improve performance (load balancing) where one request is processed by one node

and the requirements are,

  • Store your object graph in a persistent storage such as a database so that each processing node can read it.

  • Locking of the sections in the persistent storage based on the graph (similar to parallel requests of the single process) so that parallel writes does not happen and hence the graph is not getting stuffed.

2. Split request across nodes so that given request is processed by multiple processing nodes

  • All the steps done for the load balancing

  • Split the processing into multiple sections, and distribute over the different processing nodes

  • Combine the results of the results once the processing is completed

| improve this answer | | | | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.