Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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?

share|improve this question
2  
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
add comment

1 Answer

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 grow more slowly than demand on the system.

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.

share|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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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