Consistent Hashing - 2

Remember in consistent hashing, each shard has a big range of hash values to map objects. With this set-up data load may not balanced among different shards.

Instead of having one big range for each shard, what about adding marker to split the big range of hash values into smaller chunks and those smaller hash range will assign to different shards on different server. Thus helping with load balancing, but How?

Lets we have 20 objects to store and I still have 4 shards available each having different range of hash values equal in length. But may be out of 20 objects 14 are mapped to Shard 0 and rest are equally distributed to 1, 2 and 3. Unbalanced, Is not it? This is the case where smaller hash range can help a lot in load balancing.

Consistent hashing can use multiple markers for shards for mapping several smaller range of hash
values instead of one big range.

It will have two positive effects:

1. When the new shard is to be added, that shard will get more objects from all existing shards in the server, instead of just few from neighboring shards.Similarly, One of the existing shard is to be removed all objects that shard was holding will evenly distributed to all existing shards.

2. The overall distribution of data will be fairly even. - Helps with load balancing,

On my next entry, I will discuss another exciting design problem. Stay tune! See you soon!!

Consistent Hashing - Swift Rings

You remember our exciting startup FADU bakery shop. We have been working with great Desi brain :P. Recently our engineering team organised a DESIGNathon. It was amazing. Let's talk about what we have designed.

"A shard scheme for KEY-VALUE storage system"

Lets list out the features that our design would supports.

1. Amount of data to be stored - 100TB. Data will keep growing with the rate of 1TB/day.
2.Machine storage capacity - 72GB RAM and 10TB Secondary storage. Bare Minimum machine needed to store 100TB data would be 10.
3. We will begin with 20 Machines and machines will be added in future.
4. All key value data will be independent and query will be based on key.

Observations:

The data grows at 1TB/day.  This implies we are genrating data that would feel the storage of one machine(10TB) in 10 days. We try to keep storage utilization <=80. Under this assumption we would add new machine every 8 days.

One way for shard is that the data within the shard will fit on single machine only. In our case. data is growing with faster pace. In this  case if we have fix number of shards, data within the shard will keep growing and exceed our machine capacity ie 10TB mark. So in our case shards will have to increase with time.

Sharding strategy :

Lets begin with fix number of shard S. For every key calculate the Hash value of the key using some hashing mechanism and store the data to shard corresponding to shard number H%S. Where H is the computed hash value of the data key and S is the number of shards. But in our case data is growing faster and we will have to increase number of shard as data grows. So in this case the new Shards count becomes S+1. The H%(S+1) changes for every key causing us to relocate each key data in our data store. Duh! this gonna be extremely expensive and undesirable :(.

Do we have better strategy to avoid this undesirable behavior ?? How we handle the case when a shard goes down and we need to redistribute the data on remaining shards???

Yes, Consistent Hashing will rescue us. So, What the heck is the consistent hashing?

Consistent hashing maps data to same shard, as far as possible. It means when a new shard is added, Its takes its share of object from all other shards and when it removed its objects are shared among remaining shard.

Consistent Hashing based strategy:

It also hash the object key but instead of geting the mapped value for each object each shard is assigned a range of hash values to store the objects. Now we will map each shard to range of hash values.

Range of hash value for each shard:( Below is just example, Hashvalue are generally bigger)

Shard	Range of Hash Values
Shard 0	0000…~3fff…
Shard 1	3fff… ~7fff…
Shard 2	7fff…~bffd…
Shard 3	Bffd… ~ffff

Mapping of objects to different shards.

Object	Hash Value	Shard Mapped To
Music 1	4b4s…	Shard 1
Music 2	Ecb2…	Shard 3
Music 3	5082…	Shard 1
Image 1	B5e7…	Shard 2
Image 2	9433…	Shard 2
Image 3	1213…	Shard 0
Movie 1	69db…	Shard 1
Movie 2	C4ab…	Shard 3

Diagrammatically we can see this as follow:

Now if I add additional shard the only change, each shard will get a new range of Hash values. Any object whose hash value is within the range of current shard will remain in same shard. For objects whose hash value is not within the range of its current shard will be mapped to another shard. But the number of such objects are very few using consistent hashing algorithm compare to basic hashing algorithm.


Lets add another shard. The below diagram re-illustrate the point.

Notice How only Movie 2 and music 2 are mapped to new Shard4 and image 1 need to mapped to Shard 3. If we used basic hash mapping then we would most likely have to recalculate the mapping for all objects and remap them accordingly. Imagine how expensive that is for million of objects.

On my next entry, I will talk about some improvement over this design. Stay tune ... :)

Circuit breaker- IN NUTSHELL

Recently our client FADU bakery shop decided to limit the caching to minimal to cut the cost in software system. Uhh! The web application is no more responsive now :(. In our web app several of pages are populated with the data retrieved from services deployed on external server. With the minimal caching, most of the hits to pages will causes round-trip to the services. This connection to services is configured with timeout period of 60 sec and if the service doe not respond in this duration web page will assume either the service in unavailable or some exception.

Moreover, if service call fails, user could be forced to wait for 60 sec before an exception occur and resources such as memory, connections and threads could exhausted preventing other user to connect to system.

Adding more web servers and load balancing may delay the point at which resource become exhausted but it will not solve the problem.

Is not it be dreamy if there is something that handle the failure more elegantly? This is where the circuit breaker comes in play where we wrap the logic to connect to service and retrieve data.

Circuit breaker is a pattern that wraps the failure prone resource call and monitor for error. Circuit breaker comes with three states as the implementation is stateful. The states are close, Open and Half-open. Initially the circuit breaker is in closed state and passed all request to wrapped object. Many request to object may fails and once failure reaches the threshold count in fixed interval the circuit will move to open state where it returns default response or error to caller without actually calling to wrapped object. This prevents from overloading the already failing resource. While after some time the failure may recover. The recovery is handled externally, possibly by restoring or restarting the failure component or repair the network or other ways. Now, we need a mechanism to detect if the failure is recovered. This is where the third state called half-open state comes in play. This is reached after some duration of failure. At this time again the request is sent to wrapped object but the result of call is important. If the call is successful the wrapped object is recovered and the circuit breaker moved to closed state again! If the call is fails the timeout is reset and circuit move to open state.

There are some standard open source implementation like Apache Camel, Microsoft API for circuit breaker or Netflix implementation are available. If you are accessing the resources that likely to fail wrap the resource to circuit breaker and enjoy the responsiveness even in case of failure. Is not it magical?

Scaling webservices- Its easy!!

Just recently i was asked to develop a massively scalable webservice for a client called FADU Bakery shop ;). I am also a software developer like you who does less but only i know!!. I explored the concepts involved in making a web service scalable and i am just trying to sharing it with you. Have fun and hope you like it. Your comment is always welcomed!!

When we talk of scalability it involves:

1. Application server scaling.

2. Database server scaling.

3. Memory scaling- Cache and MQ.

I am trying to explore each concepts respectively.

Application server scaling by cloning:

Usually our application servers are hidden behind a black box called load balancer. This load balancer evenly distribute the load onto the group of hidden app server with high probability using the intelligent algorithm based on time-stamp or loads. That means if User Mrs Ssoni interact with your service for the first time she may be served by server 5 and in second request is served by server 2 and may be in third request it again come to server5.

Ssoni always get the same result of her same request independent of which server she lands on. That gives us the first golden rule of scaling -'Every server should have same code base and should not store user data like profile pic or session data'. Otherwise imagine if Ssoni has checked some milk bread on server1 but in second request server is changed and the the milk-bread is not in her basket :(.

So what next... where to store this user data?

One among many solution is to store this user data in a centralize data storage accessible to all the application server or store this user data by scaling the memory of load balancer. It could be a database in load balancer or the persistence cache like redis or memcached. Please dont use the file based caching more frequently as it make auto scaling and cloning pain.

So far so good...But what about deployment on multi server?

How do you assure that the code changes is effectively on all app server. Dont worry this is tricky problem and already solved by multiple tools like Capistrano or you can write own script for that to show you are not lazy as me.

Now we are serving the same codebase from all app servers, we can now create an image file from one of these servers (AWS calls this AMI - Amazon Machine Image.) Use this AMI as a “super-clone” that all your new instances are based upon. Whenever you start a new instance, just do an initial deployment of your latest code and you are ready! Is not it simple enough...?

#database and memory will be in next blog ... soon!!

#Names are virtual.

Microservices

Microservices are the software architectural style derived from various traditional architectural styles and design principles like SOA, Single responsibility principle. This is the more recent term which promotes implementing applications as a set of simple, granular, independently deployable services. It captures a number of best practices and hypotheses about scalable software development practice of organizations like Heroku, Netflix, or Amazon to name few.

                       

How Microservices are different from  traditional architecture style?

Let’s assume we are developing an application .Fortunately we are lucky like Facebook or Flipkart team and the application become huge success and grow more complex over time. The complexity creates challenges in development and maintenance. There are two essential strategies to manage the development problem: either our team can keep everything together: a monolith system or team can divide a project into smaller pieces: microservices.

The traditional monolithic system approach generally have a single code base containing all application logic, File and DB storages. All programmers contribute to same code base. This approach is initially simpler and inter module refactoring is easy as the application is altogether integrated. But in longer run when we have to scale the application we have the option of replicating the monolith on multiple servers. This sometimes causes wastage of resources .Scaling requires scaling of entire system rather than the part that needs only requisite resources. Complex black box intermediary between client and server generally called Load balancers is needed. Changing the code is also sometimes frustrating as the small changes in application required entire monolith to rebuild, test and deploy.

The new concept of development called microservices is not a completely new concept. It is just a more robust and sometime complex form of previous known well practices.

                                    Fig: Differentiate monolithic and microservices architecture

In short for microservice base application:

 

Generally the microservices are written in different language following different frameworks. It helps in writing performance sensitive code in a lower level language and other with modern language with high abstractions. Microservices are independently scalable and deployable. Generally, Application are divided into microservices based on business functionalities. We create the replica of at microservices level. These services are developed and maintained by different teams and sometimes different companies.

It enforce a separation of responsibility in healthy ways, make it easier to onboard new developers, enable you to choose different languages and technologies for different microservices, and can help prevent a problem in one part of your code from bringing down the whole system as each microservices are independent entity.

Webservices (Rest, Restful,SOA) and Microservices

SOA

SOA is an architectural style with focuses on services. But what you may call services is differs based on opinions and that is a whole different big topic.

Websevices :

Webservices are the subset of SOA uses internet related technologies like HTTP, FTP with messaging protocol like XML,SOAP.

RESTful:

RESTful is a subset of Webservices that uses HTTP as communication protocol. There are certain standard in development that relevance to creating URLs. Restful was more restrict form of REST Implementation where a resource would have a unique URI and it would be managed through CRUD operations mapped to HTTP verbs  Create = PUT, Read = GET, Update = POST, Delete = Delete.

The exact difference between REST and RESTful is vague and a debatable topic.

Microservices:

This is a recent terminology and a subset of SOA. It promotes implementing applications as a set of simple independently deployable services in contrasts with SOA where a set of complex services are needed to build complex system typically requires intelligent enterprise bus for communication.

Advantages of microservices:

·         Simple, focuses on doing single things right.

·         Enable to develop each service using the most suitable tool and technology.

·         Inherently loosely coupled.

·         Enables multiple development teams for continuous independent delivery, allowing frequent release keeping the rest of system up and running.

Disadvantages of microservices:

·         Brings a lot of operation overhead like load balancers, messaging layers to glue the services, insurances of all the services remain up, do not run out of disk spaces or deadlock.

·         Needs a very robust release and deployment automation.

·         Absence of open source tools and framework to support microservices. It needs significant investment in custom scripting to manage these services before writing a line of code that delivers business value.

·         Collaborating services needs to agree the contracts with both side needs to exchange the same message format and understand the same semantic of messages. A change in the syntax /semantics on one side causes this change to be understandable to all other services. That sometimes causes changes in many services.

·         Microservices implicitly implies distributed computing and Distributed computing is complex.

Conclusions:

Definitely we should consider the microservice based architecture as a part of scaling the project but at the same time we should consider challenges inherent in running multiple services which implies multiple codebases. Each service causes overhead, and though overhead can be reduced by an order of magnitude by running in a PaaS environment, but still need to configure monitoring and alerting and similar services for each microservice. Microservices also make testing and releases easier for individual components, but incur a cost at the system integration level. We need to plan for system behavior if one of the services goes offline.

Overall, though, a considered strategy of decomposing your application into smaller pieces will allow you to make better technology choices, give your team more flexibility, independence and can give you more ways to maintain availability with high probability.

 I am developing a demo app based on microservice  and will post in next blog soon. Stay tuned!!