PREGEL : Graph Framework

PREGEL 

This paper talks about Pregel: a large graph processing framework designed by google.The paper first highlights the main problems in processing large graphs and then talks about how pregel works.One of the advantage with Prgel is that pregel programmes can be scaled automatically and programmer can concentrate on the algorithm they implement without worrying about fault tolerance and other mechanism. In short Pregel is a simple,flexible yet powerful framework that will find its usage in distributed social networks and other large graph processing applications.

Summery:
1)As the size of network is increasing, there representation is becoming more and more difficult with billions,trillions of nodes.This paper provides a computation model for processing these large graphs.
2)Pregel is inspired from Valiants Bulk Synchronous Programming model.
3)It focuses on message passing instead of remote reads.
4)Author provides a model of computation . Input to pregel is a large graph with each vertex identified by an ID.A sequence of supersterps are followed until algorithm terminates.
5)Paper provides C++ API and examples which can be written using pregel like PageRank,Clustering,Shortest Path.
6)The network is used only for sending messages and therefore communication overhead is significantly reduced.
7)Experiments that shows how graph scales with changes in number of vertices.

Cons :
1)Author describes fairly complex system and leaves out many details.
2)Not much experiments provided.
3)Talk about Map Reduce but nowhere they have provided evaluation on the two.
4)What will happen in case of Master failure was not answered.

F1 : A Distributed Database

 F1 : A distributed Database

The paper talks about Google’s F1. F1  is a  a massive relational database management system, that helps run company’s online ad system .Though the paper calls the database Hybrid but I feel it is much more relational than NoSQL-style . The System is built  atop spanner and adds in new key features, including distributed SQL queries, transactionally consistent secondary indexes, asynchronous schema changes including database reorganizations, optimistic transactions, and automatic change history recording and publishing. The paper is beautifully written and maintains the flow. As goggles Full Adword business is running on F1 so I feel its surely  is a powerful System.
Though technical issues remains ,as with new technology but the future seams quiet upbeat for the new Database.

Summery :

Google's F1 is a distributed relational Database Management System that  helps run companies online Ad systems.F1 combines high Availability and Scalability of NoSQL systems as well as Consistency and Usability of Traditional SQL Database . F1 is built atop Scanner.f1 is fault tolerant ,globally distributed and supports both OLAP and OLTP.F1 has Database schema similar to RDBMS with some extensions like support for hierarchical data , protocol buffer and both local and global Indexing.Paper Highlights the problems with the traditional ORM tools and uses a new stripped down API avoiding antipatterns of ORM . F1 supports both NoSQL and SQL interface giving flexibility to user to select the one suitable for his application. Spanner stores records and Data and F1 gives you access to those records through query processing. In short F1 is a Powerful System that combines the best of both worlds(SQL and NoSQl) and remove the negative.
Some Points :
1)Global Indexing cause Scaling problem for large Transections.
2)There is no mention of security .
3)Single rows usually avoids 2PC . What happens if Connection is lost .

Database Sharding

DATABASE SHARDING 

=) Database Sharding -> Share Nothing partitioning scheme for large database. 
=) Breaking your database into small chunks called and spreading them across a number of distributed servers.
=) Vertical scaling*adds more CPU and storage resources to increase capacity. Scaling by adding capacity has limitations: high performance systems with large numbers of CPUs and large amount of RAM are disproportionately more expensive than smaller systems.

=) Acc to Wikipedia Sharding refers to Horizontal Partioning . Which Means keeping the rows of database in separate table rather then creating a separate column. As table are distributed and kept in separate db total no of rows in table are reduced.
=) Concept : take a large database, and break it into a number of smaller databases across servers.
=) Improved Scalablity.

The general purpose database requirements that are a fit for sharding include:

• High-transaction database applications
• Mixed workload database usage
  • Frequent reads, including complex queries and joins
  • Write-intensive transactions (CRUD statements, including INSERT, UPDATE, DELETE)
  • Contention for common tables and/or rows
• General Business Reporting
  • Typical "repelating segment" report generation
  • Some data analysis (mixed with other workloads)

* Steps to determine if we need sharding :
1)Identify Transection intensive tables.
2)Determine volume of Txn
3)Determine Volume associated with different Squeries : Select,Insert,Update
4)Understand Hierarchy
5)Understand Schema : to check if evenly Spread.

In the Bookstore example, the Primary Shard Table is the 'customer' entity. This is the table that is used to shard the data. The 'customer' table is the parent of the shard hierarchy, with the 'customer_order' and 'order_item' entities as child tables. The data is sharded by the 'customer.id' attribute, and all related rows in the child tables associated with a given 'customer.id' are sharded as well. The Global Tables are the common lookup tables, which have relatively low activity, and these tables are replicated to all shards to avoid cross-shard joins.

Another general example  :
Suppose you have an application where no of user counts is huge around 10 users per sec or even more .. Due to single entity update rate too fast and so some serialised write might stack up and timeout.
How to reduce contention :
Break the counters into N counters
when you want to increment a counter you pick one of the shard at random and increment. If you want to know total counter add all values.




Reference : 1)MangoDB
2)Wikipedia
3)Codefeatures

Eventual Consistency

What i got from the Post by Werner Vogels on Consisency

Distribution Transparency : To the user of the system it appears that there is only one system.

Consistency : Client Point of View
4 components :
1)Storage System
2)Process A : A process that writes to and reads from a Storage System
3)Process B&C : 2 process indepandent of process A . Reads and Writes to SS.
Client Side consistency is how and when client sees update made to data object in storage System.
If A updates
1)Strong Consistency : Once update is compleate any subsequent access will return updated value.
2)Weak Consistency : The system does not guarantee that subsequent accesses will return the updated value. A number of conditions need to be met before the value will be returned. Often this condition is the passing of time. The period between the update and the moment when it is guaranteed that any observer will always see the updated value is dubbed the inconsistency window.
3)Eventual Consistency: The storage system guarantees that if no new updates are made to the object eventually (after the inconsistency window closes) all accesses will return the last updated value. The most popular system that implements eventual consistency is DNS, the domain name system. Updates to a name are distributed according to a configured pattern and in combination with time controlled caches, eventually of client will see the update.

Server Side :
N : No of nodes that store replica of data
W:No of node that needs to ack the reciept of update before the update is received
R:The no of nodes that are contacted when data abject accessed through read operation
If W+R > N

Problem here is if 3 nodes are write and 2 fails then system has to fail the write as otherwise system will become unavailable.

In distributed storage systems that need to address high-performance and high-availability the number of replicas is in general higher than 2. Systems that focus solely on fault-tolerance often use N=3 (with W=2 and R=2 configurations). Systems that need to serve very high read loads often replicate their data beyond what is required for fault-tolerance, where N can be tens or even hundreds of nodes and with R configured to 1 such that a single read will return a result. For systems that are concerned about consistency they set W=N for updates.

R=1 W=N optimise Read
R=N W=1 very fast write