How Google Search works ?

Like any other search engines, Google uses some special algorithms to generate search results. Google shares the general facts about these algorithms, but the specifics are their secret. This helps Google remain competitive with other search engines available and reduces the chance of someone finding out how to abuse the system as whole.

Google uses spider or crawlers - automated programs that crawl over millions of pages on web. Also like other search engines, Google maintains a large index of keywords  and metadata like where these words can be found and linking for the same. Google uses unique algorithm(called PageRank- assigns each page a relevancy score) to rank search results, which in turn determines the order Google displays results on search result webpage.

Spider does the search engine's grunt task. It scan the web pages and creates the indexes of keywords. It also scans pages and does categorization. Once a spider has visited a web page, it follows the links from that page to other pages. It continue to crawl from one site to next, which implies the search engine's index become more comprehensive and robust with time.

The relevancy score-PageRank for a page depends on few factors:

• The frequency and location of keywords within the page.
• How long the webpage has expired.
• The number of other Webpages linked to the page in question.

lets understand it with an example where we are searching for the term "Dreaweaver".

 

As more pages link to Adobe's Dreamweaver page, the Adobe's PageRank increases. When Adobe's page rank is higher than the other, it shows up the top of the Google search result page. Since Google uses links to a webpage as an attribute to calculate relevancy score, its not easy to cheat the system. The genuine way to make sure your web page is high up on Google's search result is to provide great content to users so that they will link back to your page.The more links your page will gets, the higher the relevancy score will be.

Google uses lots of tricks to prevent people from cheating the system and get higher score. For example - as a Web page adds links to more sites, its voting power decreases. A Web page that has a high PageRank with lots of outgoing links can have less influence than a lower-ranked page with only one or two outgoing links.

Useful resources:
https://www.google.com/insidesearch/howsearchworks/thestory/

What happened when you type URL in browser and press ENTER ?

Here are the simplest steps followed when you time URL in browser and press ENTER -

1. Browser checks cache; if requested object is in cache and is fresh, skip to #9
2. Browser asks OS for server's IP address
3. OS makes a DNS lookup and replies the IP address to the browser
4. Browser opens a TCP connection to server (this step is much more complex with HTTPS)
5. Browser sends the HTTP request through TCP connection
6. Browser receives HTTP response and may close the TCP connection, or reuse it for another request
7. Browser checks if the response is a redirect (3xx result status codes), authorization request (401), error (4xx and 5xx), etc.; these are handled differently from normal responses (2xx)
8. If cacheable, response is stored in cache
9. Browser decodes response (e.g. if it's gzipped)
10. Browser determines what to do with response (e.g. is it a HTML page, is it an image, is it a sound clip?)
11. browser renders response, or offers a download dialog for unrecognized types

         Also, there are many other things happening in parallel to this (processing typed-in address, adding page to browser history, displaying progress to user, notifying plugins and extensions, rendering the page while it's downloading, pipelining, connection tracking for keep-alive, etc.).

Useful links:

http://igoro.com/archive/what-really-happens-when-you-navigate-to-a-url/

Useful watch:

Switching to HTTPS- It's easy!

For a back-end developer switching to HTTPS is fairly straightforward in practice. The basic steps are as follows:

1. Purchase an SSL certificate and a dedicated IP from hosting company like godaddy.com
2. Install and configure the SSL certificate. Ask Hosting company for help.
3. Perform a full back-up of your site in case you plan to revert back,
4. Configure any hard internal links within website, from HTTP to HTTPS.
5. Update any code libraries, such as JavaScript, Ajax or any third-party plugin, if needed.
6. Update htaccess applications, e.g: Apache Web Server. LiteSpeed, NGinx Config and your internet service manager function to redirect HTTP traffic to HTTPS.
7. Update your CDN's SSL setting, if any,
8. Implement 301 redirects on a page-by-page basis.
9. Update any link used in marketing automation tools, such as email links.
10. Set up HTTPS site in Google Search Console and Google Analytics. 

For a small website switching will be fairly straightforward, as some of the above points won’t apply in scenarios such as code libraries and CDNs. However, for a larger site, this is hardly a non-trivial event and should be managed by an experienced webmaster.

HTTP Vs HTTPS - Why one should Care?

Until recently, HTTPS was really used only by eCommerce sites for some specific pages like payment, login pages. Recent Google's announcement about HTTPS as a ranking signal and there failure could mean ranking will take a hit.

And that would mean less traffic and less business.

So, first of all, What exactly HTTP'S' means??

HTTP stands for Hypertext transfer protocol that enables communication( exchange message) between different system on internet. It is used for transferring data from a web server to a browser to view the web page.

HTTP ( note that no 's' on the end) data is not secure/encrypted and it can be intercepted by third parties between  hops(routers) to gather data being transfer between two systems.

HTTPS is the secure version of HTTP and involves the use of an SSL certificate  where SSL stands for secure socket layer, which creates a secure encrypted connection between server and browser.  It offers a base level web security.

Using HTTPS, the computer devices agree on a code between them and then they scramble the message using this code so that no one in between can read the message. The code is used on Secure Socket Layer(SSL) also known as Transport Layer Security to send message back and forth. .This keeps message safe from hackers/interceptors.

SSL certificates contain the computer owner's - public key.

The owner shares the public key with anyone who needs it. Using this shared public key other user encrypt messages to the owner. The owner share the public key using SSL certificate. The owner does not share private key to anyone.

HTTPS uses asymmetric public key Infrastructure(PKI). PKI uses two key to encrypt communication known as public key and private key. Anything encrypted with the public key can only be decrypted by the private key.

As names suggest, the private key should keep strictly protected and should be accessible by the owner of private key.The private key remains securely ensconced on the web server. The public key is intended to be distributed to anybody and everybody. Recipient's Public key is used to encrypt the message and the decryption key is recipient's private key.

Though private and public keys are related mathematically, it is not be feasible to calculate the private key from the public key. In fact, intelligent part of any public-key crypto system is in designing a relationship between two keys.

This is all for current entry. We will discuss the process of switching to HTTPS in next entry.

Enjoy Reading!!

Design a Batch processing system

There are numerous batch oriented application in place today that can leverage on-demand processing, including claims processing, large scale transformation, media trans-coding and multi-part data processing work.

Batch processing architectures are often synonymous with highly variable usage patterns that can significant usage peak ( month end processing) followed by significant period of under-utilization.

There are numerous approaches to building a batch processing architecture. In this entry we will discuss a basic batch processing architecture that supports job scheduling, job status inspection, upload raw data, outputting job result and reporting job performance data.

Users interact with the Job Manager application which is deployed on an Amazon Elastic Computer Cloud (EC2) instance. This component controls the process of accepting, scheduling, starting, managing and completing batch jobs. It also provides access to final results, job and worker statistics, and progress information.

Raw job data is uploaded to Amazon Simple Storage Service (S3), a highly-available and persistent data store.

Individual job tasks are inserted by the Job Manager in an Amazon Simple Queue Service(SQS) input queue on the user's behalf.

Worker nodes are Amazon EC2 instances deployed on an Auto-Scaling group. This group is a container that ensures health and scalability of worker nodes. Worker nodes pick up job parts from the input queue automatically and perform single tasks that are parts of the list of batch processing steps.

Interim result from worker nodes are stored in Amazon S3.

Progress information and statistics are stored on the analytics store. This component can be either an Amazon SimpleDB domain or a relational database such as an Amazon Relational Database Service(RDS) instance.

Optionally, completed tasks can be inserted in an Amazon SQS queue for chaining to a second processing stage.

Design content and media sharing system

Media sharing is one of the hottest markets on internet. Customers have a staggering appetite for placing photos and video on social networking sites and sharing their photo/video in custom online photo/video albums.

The growing popularity of media sharing means scaling problem for site owners who face ever-increasing storage and bandwidth requirements and increased go-to-market pressure to deliver faster than the competition.

In this entry we will discuss an example of a highly available, durable and cost effective media sharing and processing platform using amazon web service.

Sharing content file involves uploading media files to online service. In this configuration, an elastic load balancer distributes incoming network traffic to upload servers, a dynamic fleet of Amazon Elastic Compute Cloud (Amazon EC2) instances. Amazon CloudWatch monitors these servers and Auto-Scaling manages them, automatically scaling EC2 capability up or down based on load. In the above diagram, a separate end-point to receive media upload was created in order to off-load this task from the website's servers.

Original uploaded files are stored in Amazon Simple Storage Service (Amazon S3) , a high available and durable storage service.

To submit a new file to be processed, upload web servers push a message into a Amazon Simple Queue Service (Amazon SQS) queue. This queue acts as a communication pipeline between file reception and file processing components.

The processing pipeline is a dedicated group of Amazon EC2 instances used to execute any kind of post processing task on the uploaded files ( eg. video transcoding, image resizing etc). To automatically adjust the needed capacity, Auto Scaling manages this group. We can use Spot instances to dynamically extend the capacity of the group and to significantly reduce the cost of file processing.

Once the processing is completed. Amazon S3 stores the output files. Original files can be stored with high durability.

Media related files can be put in a relational database like Amazon Relational Database Service (Amazon RDS) or in key-value store like Amazon SimpleDB.

A third fleet of EC2 instances is dedicated to host the website front- end of media sharing service.

Media files are distribute from Amazon S3 to end user via Amazon CloudFront offers low latency delivery through a worldwide network of edge locations.

Design a high available and fault tolerant system

Most of the higher level services provided by Cloud provider like Amazon (Amazon Simple Storage Service-S3, Amazon SimpleDB, Amazon Simple Queue service-SQS, Amazon Elastic Load Balancing-ELB etc) have been built with fault tolerance and high availability in mind. Services that that provides basic infrastructure, such as Amazon Elastic Compute Cloud(EC2) and Amazon Elastic Block Storage(EBS), provides specific features, such as availability zones, elastic IP addresses, and snapshots that a fault tolerant and high available system must take advantage of it and use it correctly. Just moving into the cloud does not make system fault-tolerant or high available.

In this entry we will discuss a design of fault tolerant and high available system.

Design Overview:
Load Balancing is an effective way to increase the availability of a system. Instances that fail can be replaced seamlessly behind the load balancing system while other instance continue to operate. Elastic Load Balancing can be used to balance across instances in multiple availability zones of a regions.

Amazon EC2 is hosted in multiple locations world wide. The locations are composed of regions and Availability zones. Each region is a separate geographical area. Each region has multiple, isolated locations known as Availability zones. Amazon EC2 provides you the ability to place resources, such as instances and data in multiple locations. Resources are not replicated across regions unless you do so specifically.

Availability zones(AZs) are distinct geographical locations that are engineered to be insulated from failures in other availability zones. By placing Amazon EC2 instances in multiple availability zones, an application can be protected from failure at a single location. It is important to run independent application stack in more than one AZ , either in same region or another region.If the application fails in one zone application continue running in another zone. When you design such system you need to understand the zone dependencies.

Elastic IP addresses are public IP addresses that can be problematically mapped between instances within a region. They are associated with AWS account and not with specific instance or lifetime of instance. 

Elastic IP can be used to work around host or availability zone failure by quickly remapping the address to another running instance or replacement instance that's just started. Reserved instances can help guarantee that such capability is available in another zone.

Valuable data will not be stored stored only on instance storage without proper backups, replications or ability to recreate the data. Amazon Elastic Block Storage (EBS) offers persistent off-instance storage volume that are about an order of magnitude more durable than the on-instance storage. EBS volumes are automatically replicated within a single availability zone. To increase durability further, point in time snapshot can be created to store data on volumes in Amazon S3, which is then replicated to multiple AZs. While EBS volume are tied to a specific AZ, snapshot is tied to a region. Using a snapshot, you can create new EBS volume in any of the AZs of same region. This is an effective way to deal with disk failure or other host level issues, as well as with the problems effecting the AZ. Snapshot are incremental, so its better to hold on to recent snapshots.

This is all about our high available and fault tolerant system. Keep Reading!!

Message sync protocol for messaging service

Using conventional back end systems for our messaging service like WhatsApp causes lag in performance and data usages- especially on networks with costly data plans and limited bandwidth. To fix this, we need to completely re-imagine how data is synchronized to device and change the way data is processed in the back end.

In this entry we will discuss a new sync protocol for messaging service that will decrease a non media data usage by 40% . By reducing the congestion on the network, we will see an approximately 20% decrease in the number of people who experience when trying to send messages.

Initially we started with pull based protocol for getting the data down to client. When client receives a message, it first receive a light weight push notification indicating new message is available. This trigger the app to send the server a complicated HTTPS request and receives a very large JSON response with the updated conversation view.

Instead of above model, we can move to push based snapshot and delta model. In this model client retrieve there initial snapshot of there message using HTTPS pull request and then subscribe to delta updates which are immediately pushed to the client through MQTT - a low power, low bandwidth protocol, as messages are received. As a result, without ever making the HTTPS request, the client can quickly display up-to-dated view. We can also remove the JSON based encoding for messages and delta updates.  JSON is great if we need a flexible, human readable format for transferring data without lot of developer overhead. We can replace to Apache Thrift from JSON. Switching to Thrift from JSON allows us to reduce our payload size by roughly 50%.

On server side, messaging data has traditionally been stored on spinning disks. In the pull-based model, we would write to disk before sending a trigger to Client to read from disk. This giant storage tier would serve real time message data as well as the full conversation history. But one large storage tier does not scale well to synchronize recent messages to the app in real time. In order to support synchronization with scaling we need to develop some faster sync protocol to maintain the consistency between the App Client and long term storage. To do this, we need to be able to stream the same sequence of updates in real time to App Client and to storage tier in parallel on a per user basis.

Our new Sync protocol will be totally ordered queue of messaging updates( new message, state change for messages  read etc...)  with separate pointers into the queue indicating the last update sent to your App Client and the traditional storage tier. When successfully sending a message to disk  or to your phone, the corresponding pointer will be advanced. When your phone(Client) is offline, or there is a disk outage, the pointer stays in place while new messages can still be en-queued and other pointers will advanced. As a result, long disk write latency do not hinder Client's real time communication and we can keep Client and the traditional storage tier in sync at independent rates.

Following the common sequence of operations using our brand new Message sync protocol.


1. Our ordered queue contains 5 updates and has 2 pointers:

• The Disk pointer signals traditional disk storage is up-to-date and received update with sequence id 104.
• The App/Client pointer indicates our App is offline and last received update was with sequence id 101.

2. Shagun sends me a new message, which is enqueued at the head of my queue and assigned a sequence id 105.

3.Then our message sync protocol sends the new message to traditional disk storage for long term persistence and the disk pointer is advanced.

4. Some time later my phone comes online, the client/App pings the queue to activate the App pointer.

5. The messing sync protocol sends all missing updates to client/App and the App pointer is advanced to indicate our App is up-to-date.

Effectively, this queue based model allows:

• The most recent messages are immediately sent to online apps and to the disk storage tier from from protocol's memory.
• A week's worth of messages are served by the queue's backing store in the case of disk outage or App being offline for a while.
• Older conversation history and full inbox snapshot fetches are served from traditionally disk storage tier.

Design a messaging service, like WhatsApp

This entry will discuss a high level design for messaging service, like WhatsApp. Following are the list of features our messaging service is going to support.

List of features:

1. At WhatsApp scale, lets say we need to handle around 10 Billions message sends per day and 300 Millions users. Assuming each message on average  has 160 characters, implies 10B * 160  =  1.6TB data per day , not including message metadata. If messaging service provision for 10 years, we are looking at 10*1.6B*365 ~~6 Petabytes.

2. Messaging service will support only 1:1 plain text conversations and should be extendable to add group conversations.

3. Messaging service will only handle messages less than 64Kb in size.

4. Messaging service will have low latency, high consistency and availability. Consistency has higher priority than availability.

Design Strategy :

The messaging service will expose following APIs to clients.

1. SendStatus sendMessage(senderId, receipientIds, message, ClientMessageId) : This API will be idempotent. If the client retires the message, the message will not be added twice. One way to handle this by generating a random timestamp based ID on the client which can be used to avoid the same message being  sent repeatedly. Ordering of the messages will be maintained. Means, If I send message A, and then message B, then A should always appear before B. We can use server side timestamp based approach to handle this. The parameter used in the sendMessage API is self descriptive.

Returns: SendStatus -> Status of the sendMessage Request as enum.

2. ConversationList fetchConversation(userId, offset, messageCount, lastUpdatedTimeStamp):
This API will be used to fetch and show conversations in a thread. Think of this as view you see when you open the WhatsApp. For a user, we would only want to fetch few messages in one API call at a time(Lazy Loading). The offset and messageCount parameters are used to handle this.

In most cases, our API calls are made by the users who are active on messing services. As such, they already viewed conversations till a certain time stamp and only looking for updates after the time stamp. To handle the clients which are data sensitive we are using lastUpdatedTimeStamp Param.

Returns: ConversationList{
                     List<Conversation> conversations;
                     boolean isDBupdate;
                }
     

              Conversation {
                    int conversationId;
                    List<UUID>participantIds;
                    String snippet;
                    long lastUpdatedTimeStamp;
              }

Following is the high level component diagram for the messaging system.

             

Client (Mobile App/ Browser etc) calls sendMessage API for writing a message. Application server will interpret the API call and calls database to do following. 

•  Put in the server time stamps to handle ordering of message.
•  Figure out the conversation to which the message should be appended based on the participants. 
•  Figure out if the recent message exists with the clientMessageId.
•  Store the message in database.

Similarly to read conversations, client calls fetchConversation API. Application server interprets the API call and queries the database for the recent conversations.  

Message is going to be very write heavy. Unlike photos, videos etc which are written once and consumed a lot of times by lot of clients, message are written once and consumed by the participants once. For the write heavy system with a lot of data, RDBMS usually do not perform well as every write is not just an append to a table but also an updates to the multiple indices which might required locking and hence might interfere with reads and other writes. However, there are NoSQL databases like HBase, cassandra where writes are cheaper. 

With NoSQL, we need to store data in denormalized form. Every user would have his/her own copy of message box.  That means we will store two copies of the message, one for each participant for every message send for 1:1 conversation.

To increase the efficiency we can use Caching. This is however not as easy as it seems as one of our feature is to ensure high consistency. Most distributed caching system are good with availability and eventually consistent., but not tight consistent.

Lets consider the situation if the user messages and conversations are spread across machines then it causes trouble because the changes are not atomic. Consider the case when messages for a user are on one machine and conversations are on another. When a message is added, the update request is sent to server with messages and server with conversation for this user. There could be a period when one server has processed the update but other has not. If changes through servers are not atomic, the whole system is not atomic anymore. 

One way to resolve is to make sure that the caching for a user completely resides on one server. The same server can also have other users, but user assigned to exactly one server for caching. To further ensure consistency, all the writes for that user should be directed through this server and this server updates its cache when the write is successful on database before confirming success.

For messaging service, every bytes waste has very real impact on the experience of application. By sending less data and reducing HTTPS fetches, messaging service receives updates with low latency and high reliability. In the subsequent entry we will extend the design to improve performance and data usages. Meanwhile, take care and Enjoy learning!!

URL Shortening service like, bit.ly - 2

This is the continuation of URL shortening design. In this entry we will explore different expect of our proposed design.

In the proposed design, we are optimizing for consistency over availability and we agreed to choose a NoSQL database which is highly consistent like HBase or Cassandra. HBase maintains a table called metatable, that points which key is present at which machines. HBase distribute keys based on the load on machines, they called it region servers. Cassandra inherently use consistency hashing for sharding. Since total data in our case is few TBs, we don't need to think about sharding across data centers. NoSQL has single machine failure handling inbuilt. A NoSql database like HBase would have availability issue for a few seconds for the effected keys, as it tries to maintain strong consistency.

We can also use LRU caching strategy to add performance since most URL's  are accessed for only a small amount of time after creation. Also, if the shortened URL goes viral, serving it through cache will reduce the chances of overloading the database. We can go with Redis or Memcached for caching.

To shard the data across databases, we can use integer encoding of  the shortened URL to distribute data among our database shards. Let's we assign values from 0 to 61 to characters a to z ,A to Z and 0 to 9, we can compute the integer encoding of the shortened URL. We will use consistent hashing to ensure we do not have to rehash all data if we add a new shard in future.

To add fault tolerance, we can use a scheme called Master-slave scheme for shards, wherein one machine called master process all writes and there are slaves machines which just subscribe to all the writes and keep updating itself. In an event when the master goes down, one of the slave can take over and start responding to the write queries. The slaves are to serve read requests.  

URL Shortening service like, bit.ly

In this entry we will design a URL shortening service. Lets begin with list of features.


Features:

URL shortening service will take a URL and return a much smaller URL. This short URL will have the capability to redirect to original URL. User can also pick the custom URL. What if two user try to shorten the same URL.

Assume 100 Million URL new URLs added each month to the system. Average lifetime of a shortened URL is 2 weeks and as per rule 20% of URLs creates 80% of traffic. So as per assumption, we may receive around 1 Billion queries in a month. ~400 queries per second == 360 read requests and 40 write requests. In 5 years we will need to shorten 100 Million * 12*5  ==6 Billion.

We will use (a-z A-Z 0-9) to encode our URL. Lets x be the minimum number of characters used to represent 6 Billion URLs, then x will be smallest integer such that x^62  > 6* 10^9 (where 62 are total characters including a-z A-Z 0-9) == log(6*10^9) to base 62 ==6. So x=6.

Data flow for read write request would contain a shortened URL and original URL. Shortened URL will take 6 bytes whereas the original URL will take 500 bytes.

Based on above data, Write data request per second  = 40*(500+6)
                                    Read data request per second  = 260*(500+6) bytes.



URL shortening service is latency sensitive. High latency on URL shorten er is as good as failure to resolve the request. Shortening service should have high consistency and availability.

Design Strategy:

We will define two APIs :

shortURL(url) - Store the URL mapping and return hash(url).
redirectURL(hash) - Redirect to URL_MAPPING[hash]

Basically we try to build a system that serve a huge HashMap.

High level design for write operation is as follow

And the high level design for read operation as similarly, as follow

We can use list of salt to handle the case where two separate URL get shorten to same URL(collision). Directly encoding URL to base_62 will allow a user to check if a URL has been shortened already or not, reverse engineering can lead the user to the exact same function used, this should be avoided. To avoid this, we will introduce randomization If two users shortened the same URL, it should result in two separate shortened URL . Encoding to base_62 also would not be suitable for a production environment because it will leak information about the database. For example, patterns can be learnt to compute the growth rate (new URLs added per day) and in worst case, can copy the whole database.

To add high availability, simplest thing we could do is to have multiple stateless app servers. They do not store any data(stateless) and all of them behave exact same way when up. If one of them goes down, we still have other app server to keep site running.

Load balancer is a black box that store meta data about the app server and delegate the client request to least overloaded active server. 

Our URL shortening service is simple key-value lookup (Given the hash, give me the corresponding URL). IF the size of the data is too small to fits on a single machine's main memory SQL with indexing is clear winner which has next to zero maintenance. If your index fits in RAM, its best to go with standard SQL solution. In our case, 

Write request per month = 100 Million

Average size of URL = 500 bytes.

System Provisioning for = ~5years

Implies, Space Required : 500bytes * 100M* 12*5 = 3TB 

3TB data can fit on single machine's hard disk, but index might not. Storing all data on single machine will make our read write operations very slow. (Page swap for indices) because when when we make access to SQL index frequently, that SQL index gets cached in RAM as a page. If we host the system on a single server machine due to large number of page swapping and limited RAM, page swaps(disk traversal) will increase and thus performance will degrade.  Given that the read latency is critical for shortening service we can not store the data on a single machine. So, A SQL solution will have sharding overhead. However, most NoSQL solution are built with the assumption that data does not fit on a single machine and hence support sharding builtin.

Since we are building a consistent shortening service with high availability, we will choose a NoSQL database like HBase.

We will discuss the database schema and other details for shortening service in subsequent entry. See you soon.

Design an E-commerce website like flipkart.com

In this entry we will discuss a design for E-commerce website like Flipkart. Before going into the design details, following are the list of Features.

List of Features:

1. User can sign-up, sign-in,search a product,view categories, view products,add a product to the cart, check out  products, add product to wishlist, share wishlist and what not...Here we will divide the list of features into following high level user stories:

• Customer/User related stories eg cart, wishlist etc.
• Admin related stories eg: ON/OFF a new product, canceling an order, adding offers etc. This all features will be wrapped into a Admin portal.
• Product search and categorization related stories.
• The system should support 1 Million requests per second.
• The system should be high scaling and availability.

In this design our focus would be on Customer/User Related tasks and Product search and categorization related tasks. Our system should support 10,000 customer/second and should be able to serve 100 Million products over different categories.

For product search, we can use Solr- an open source enterprise search platform with cache.Whenever a product request comes, load balancer will search a product in Solr, if the product exist detail of the product returned without querying the database. We are going to cache 40% of our product in Solr. Assume each of our products is of 10MB including image,description and other metadata.100Million product would be approx 1000TB or more, So we need to cache 400TB data in Solr. Considering a machine can store 10TB data in hard disk,  we will need 140 machine for data and 100 machine to add redundancy.

Design Strategy:

To build high scaling application with ~zero downtime ~high availability one of our strategy would be to use Microservice based approach. Microservices is an approach to application development where a large application is built as a suite of granular services. Each service supports a specific business goal and uses a simple, well-defined interface to communicate with other services. High level design is as follow:

In above design, we are storing the session state at the client and and session data in in-memory database using session-service. The shopping cart for each user is stored as a restful resource on the server.

If you have your data sharded across multiple databases. lot of HTTP server, Cache server responding the request, you need to have a provisioning server to auto scale the capacity dynamically by setting up servers as need or removing in case of reduced load. In this case its better to go full stateless and leave the shopping cart with client session. Then once user hits check-in, shopping cart should be persisted on database. The key about the rest is that every request the client makes has to contains all data to identify itself. I would suggest reading about  OAuth.

Design a taxi-aggregator like Ola

This entry will discuss a high level design for Ola App. Following are the feature our application is going to support.

List of Features:
1. The cab will be visible to user only if the distance between cab and user is <2Kms.
2. Maximum 10 Cabs will be visible to the user.
3. Number of cab our system will integrate : 1 Millions.
4. User per second : 10 Millions/ Second.
5. Low latency and high availability is our primary goal.

Design Strategy:

To scale the application and handle all the load one strategy would be to user Microservice based design approach. Microservices is an approach to application development where a large application is built as a suite of granular services. Each service supports a specific business goal and uses a simple, well-defined interface to communicate with other services. High level design is as follow

Using this approach, our design inherently will have all the benefits of Microservice. For detail regarding Microservice, do visit our entry on Microservice.

Algorithm

 "The cab will be visible to user only if the distance between cab and user is <2Kms."

Pseudo code: