[TODO] 0. Find a template for the PhD proposal

That is straight forward. The task is just to look at other students PhD proposals also at some major conferences and see what kind of structure they use. A very common structure for papers is Jennifer Widom’s structure for writing a good research paper. This or a similar template will help to make the proposal readable in a good way. For this blog article I will follow Jennifer Widom more or less.

1. Write an Introduction

Here I will describe the use case(s) of a distributed graph data base. These could be

• indexing the web graph for a general purpose search engine like Google, Bing, Baidu, Yandex…
• running the backend of a social network like Facebook, Google+, Twitter, LinkedIn,…
• storing web log files and click streams of users
• doing information retrieval (recommender systems) in the above scenarios

There could also be very other use cases like graphs from

• biology
• finance
• regular graphs 
• geographic maps like road and traffic networks

2. Discuss all the related work

This is done to name all the existing approaches and challenges that come with a distributed graph data base. It is also important to set onself apart from existing frameworks like graph processing. Here I will name the at least the related work in the following fields:

• graph processing (Signal Collect, Pregel,…)
• graph theory (especially data structures and algorithms)
• (dynamic/adaptive) graph partitioning
• distributed computing / systems (MPI, Bulk Synchronous Parallel Programming, Map Reduce, P2P, distributed hash tables, distributed file systems…)
• redundancy vs fault tolerance
• network programming (protocols, latency vs bandwidth)
• data bases (ACID, multiple user access, …)
• graph data base query languages (SPARQL, Gremlin, Cypher,…)
• Social Network and graph analysis and modelling.

3. Formalize the problem of distributed graph data bases

After describing the related work and knowing the standard terminology it makes sense to really formalize the problem. Several steps have to be taken: There needs to be notation for distributed graph data bases fixed. This has to respect two things:
a) the real – so far unknown – problems that will be solved during PhD. In this way fixing the notation and formalizing the (unknown) problem will be kind of hard.
b) The use cases: For the web use case this will probably translate to scale free small world network graphs with a very small diameter. Probably in order to respect other use cases than the web it will make sense to cite different graph models e.g. mathematical models to generate graphs with certain properties from the related work.
The important step here is that fixing a use case will also fix a notation and help to formalize the problem. The crucial part is to choose the use case still so general that all special cases and boarder line cases are included. Especially the use case should be a real extension to graph processing which should of course be possible with a distributed graph data base. 
One very important part of the formalization will lead to a first research question:

4. Graph Query languages – Graph Algebra

I think graph data bases are not really general purpose data bases. They exist to solve a certain class of problems in a certain range. They seem to be especially useful where information of a local neighborhood of data points is frequently needed. They also often seem to be useful when schemaless data is processed. This leads to the question of a query language. Obviously (?) the more general the query language the harder to have a very efficient solution. The model of a relational algebra was a very successful concept in relational data bases. I guess a similar graph algebra is needed as a mathmatical concept for distributed graph data bases as a foundation of their query languages. 
Remark that this chapter has nothing much to do with distributed graph data bases but with graph data bases in general.
The graph algebra I have in mind so far is pretty similar to neo4j and consists of some atomic CRUD operations. Once the results are known (ether as an answer from the related work or by own research) I will be able to run my first experiments in a distributed environment. 

5. Analysis of Basic graph data structures vs distribution strategies vs Basic CRUD operations

As expected the graph algebra will consist of some atomic CRUD operations those operations have to be tested against all different data structures one can think of in the different known distributed environments over several different real world data sets. This task will be rather straight forward. It will be possible to know the theoretical results of most implementations. The reason for this experiment is to collect experimental experiences in a distributed setting and to understand what is really happening and where the difficulties in a distributed setting are. Already in the evaluation of graphity I realized that there is a huge gap between theoretical predictions and the real results. In this way I am convinced that this experiment is a good step forward and the deep understanding of actually implementing all this will hopefully lead to:

6. Development of hybrid data structures (creative input)

It would be the first time in my life where I am running such an experiment without any new ideas coming up to tweak and tune. So I am expecting to have learnt a lot from the first experiment in order to have some creative ideas how to combine several data structures and distribution techniques in order to make a better (especially bigger scaling) distributed graph data base technology.

7. Analysis of multiple user access and ACID

One important fact of a distributed graph data base that was not in the focus of my research so far is the part that actually makes it a data base and sets it apart from some graph processing frame work. Even after finding a good data structure and distributed model there are new limitations coming once multiple user access and ACID  are introduced. These topics are to some degree orthogonal to the CRUD operations examined in my first planned experiment. I am pretty sure that the experiments from above and more reading on ACID in distributed computing will lead to more reasearch questions and ideas how to test several standard ACID strategies for several data structures in several distributed environments. In this sense this chapter will be an extension to the 5. paragraph.

8. Again creative input for multiple user access and ACID

After heaving learnt what the best data structures for basic query operations in a distributed setting are and also what the best methods to achieve ACID are it is time for more creative input. This will have the goal to find a solution (data structure and distribution mechanism) that respects both the speed of basic query operations and the ease for ACID. Once this done everything is straight forward again.

9. Comprehensive benchmark of my solution with existing frameworks

My own solution has to be benchmarked against all the standard technologies for distributed graph data bases and graph processing frameworks.

10. Conclusion of my PhD proposal

So the goal of my PhD is to analyse different data structures and distribution techniques for a realization of distributed graph data base. This will be done with respect to a good runtime of some basic graph queries (CRUD) respecting a standardized graph query algebra as well as muli user access and the paradigms of ACID. 

11 Timetable and mile stones

This is a rough schedual fixing some of the major mile stones.

• 2012 / 04: hand in PhD proposal
• 2012 / 07: graph query algebra is fixed. Maybe a paper is submitted
• 2012 / 10: experiments of basic CRUD operations done
• 2013 / 02: paper with results from basic CRUD operations done
• 2013 / 07: preliminary results on ACID and multi user experiments are done and submitted to a conference
• 2013 /08: min 3 month research internship  in a company benchmarking my system on real data
• end of 2013: publishing the results
• 2014: 9 months of writing my dissertation

For anyone who has input, knows of papers or can point me to similar research I am more than happy if you could contact me or start the discussion!
Thank you very much for reading so far!

Summary of Google Pregel

The methodology is heavily based on Bulk Sychronous Parallel Model (BSP) and also has some similarties to MapReduce (with just one superstep). The main idea is to spread the data over several machines and introduce some supersteps. For each superstep every vertex of the graph calculates a certain function that is given by the programmer.
This enables one to process large graphs which are distributed over several machines. The paper describes how to use Checkpoints to increase fault tolerance and also how to make good use of the Google File System in order to partition the graph data on the workers. The authors mention that smarter hashing functions could help to distribute the vertices not randomly but rather in a way they are connected on the graph which could potentially increase performance.
Overall the goal of Google Pregel seems to enable one to process large graph data and gain knowledge from it. The focus does not seem to increase the usage of the calculation power of the distributed system efficiently. In stead it rather seems to create a system that makes distribution of data – that will not fit into one machine – possible at a decent speed and without much effort for the programmer by introducing methods for increasing fault tolerance.

Summary of Signal Collect

Signal Collect as a system is pretty similar to Google Pregel. The main difference is that the authors introduce a threshold score which is used to decide weather a node should collect its signals or weather it should send signals. Using this score the processing of algorithms can be accelerated in a way that for every super step only signals and collects are performed if a certain threashhold is hit.
From here the authors say that one can get rid of the superstep model and make the entire calculation asynchronous. This is done by introducing randomization on the set of vertices on which signal and collect computations have to be computed (as long as the threasholdscores are overcome)
The entire system is implemented on a single machine but the vertices of the compute graph are processed by different workers (in this setting Threads). All Threads are able to share the main memory of the system which makes message passing of Signal and Collect computations unnecessary. The authors show how the increasing number of workers actually antiproportionally lower the runtime of the algorithm in the asynchronous setting. They also give evidence that different scheduling strategies seem to fit the needs for different graphs or algorithms.

Discussion of Pros and Cons

• From the text above it seems very obvious that Signal Collect with its Asynchronous Programming model seems superior. But – in opposite to the authors – I have hidden to mention the drawbacks of one small but important detail. The fact that all the workers share a common knowledge which they can access due random access in main memory of the machine allows their model to be so fast while being asynchronous. It is not clear how to maintain this speed with a real distributed system. So in this way Signal Collect only give a proof of concept that an abstract programming model for graph processing exists and it enables fast distribution in theory.
• Pregel actually is a real frame work that can really achieve distribution of large data to clusters of several thousand machines which for sure is a huge pro.
• Signal Collect proposes to be more general than Pregel since Pregel can only respect one vertex type and edges are stored implicitly. Whereas Signal Collect is able to store RDF Graphs. I personally understand that Signal Collect can only send signals from one vertex to another if and edge exists and is also not able to add or remove edges or vertices. In this sense I still think that Pregel is the more general system. But I guess one can still argue on my point of view.
• Pregel’s big drawbacks in my opinion are that the system is not optimized for speed. As already discussed in the last meeting of the reading club Map Reduce – with its one Superstep attitude – is able to start Backup tasks towards the end of the computation in order to fight stragglers. Pregel has to wait for those stragglers in every superstep in order to make synchronous Barriers possible.  
• Another point that is unique with Pregel is the deep integration with Google File System (btw. I am almost through the google file system paper and even if you already know of the idea it is absolutely worthwhile reading it and understanding the arguments for the design decisions of the google file system). So far I am not sure weather this integration is a strong or a weak point. This is due to the fact that I can’t see all the implications. However it gives strenght to my argument that for a distributed system some things like network protocols and file systems should be considered since they seem to have a strong impact on the entire system. 
• Both systems in my opinion fail to consider partitioning of the graph and a different network protocol as an important task. Especially for Pregel I do not understand this since it already has so much network traffic. Partitioning the graph might increase start up Traffic on the one hand but could increase overall traffic on the long term. 

Outlooks and personal thoughts:

I am considering to invite the authors of both papers to next weeks reading club. It would be even more interesting to discuss these and other questions directly with the guys who built that stuff. 
Also I like Schegi’s idea to see what happens if one actually runs several neo4j servers on different machines and just use a model similar to Signal Collect or Pregel to perform some computations. In this way a programming model could be given and research on the core distribution framework – relying on good technologies for the workers – could be done.
For the development of the first version of metalcon we used memcached. I read a lot that memcached scales perfectly horizontal over several machines. I wonder how an integration of memcached to Signal Collect would work in order to make the asynchronous computation possible in a distributed fashion. Since random access memory is a bottleneck in any application I suggest to put the original memcached paper on our reading list.
One last point to mention is that both systems still don’t seem to be useful as a technology to built a distributed graph data base which enables online query processing.

Summary

First take away which was well known is that there is a certain stack of Google papers and corresponding Apache implementations:

1. Google File System vs Apache Hadoop filesystem
2. Google Big Table vs Apache HBase
3. Google Map reduce vs Apache Hadoop
4. Google Pregel vs Apache Giraph

The later ones are all based eather on GFS or HDFS. Therefore we agreed that a detailed understanding of GFS (Google file system) is mandatory to fully understand the Map Reduce implementation. We don’t want to commonly discuss GFS yet but at least think everyone should be well aware of it and give room for further questions about it on next weeks reading club.
We discussed map Reduce’s advantage of handling stragglers over Pregel’s approach. In map reduce since it is a one step system it is easy to deal with Stragglers. Just reassign the job to a different machine as soon as it takes to long. This will perfectly handle stragglers that occure due to faulty machines. The superstep model in pregel has – up to our knowledge – no clear solution to these kind of Stragglers (to come up with a strategy to handle those would be a very nice research topic!) On the other hand Pregel has another kind of Stragglers that come from super nodes. There are some papers that are fixing those problems one of them is the paper that will be read for next week.
We had the discussion that partitioning the data in a smart way would make the process more efficient. We agreed that for Map Reduce and Pregel where you just want to process the graph on a cloud this is not the most important thing. But for a real time graph data base the partitioning of data will most certainly be a crucial point. Here again we saw the strong connection to Google File System since the Google File system does a lot of the partitioning in the current approaches.
Achim pointed out that Microsoft also has some proprietary products. It would be nice if someone could provide more detailed resources. He also wished that we could focus on the problems first and then talk about distributing. His solution was to make this top down.
We also discussed if frameworks that use map reduce to process large graphs have been compared with Pregel or Apache Giraph so far. This evaluation would also be a very interesting research topic. For that reason and to better understand what is happening when large graphs are processed with map reduce we included the last two papers for reading.

Feedback from you guys

After the club was over I asked everyone for suggestions and I got some usefull feedback:

• We should prepare more than one paper
• google hangout in combination with many people in the room is a little hard (introduce everyone in the beginning or everyone brings a notebook or group of people should sit in front of one camera)
• We need more focus on the paper we are currently discussing. Understanding problems should be collected 1 or 2 days before we meet and be integrated into the agenda.
• We need some check points for every paper. everyone should state: (what do i like, what do i not like, what could be further research, what do i want to discuss, what do i not understand) 
• We need a reading pool where everyone can commit

New Rules

In order to incoperate the feedback from you guys I thought of some rules for next weeks meeting. I am not sure if they are the best rules and if they don’t work we will easily change them back.

• There is a list of papers to be discussed (see below)
• At the end of the club we fix 3-6 papers from the paper pool that are to be prepared for next week
• before the club meets everyone should commit some more papers to the pool that he would like to read the week after (you can do this on the comments here or via email)
• If more people are in the same room they should sit together in front of one camera
• Short introduction of who is there in the beginning
• use the checkpoints to discuss papers
• no discussions of brand new solutions and ideas. Write them down, send a mail, discuss them at a different place. The reading club is for collectively understanding the papers that we are reading.

Last but not least. The focus is about creating ideas and research about distributed real time graph data base solutions. That is why we first want to understand the graph processing stuff.

Reading tasks for next week

for better understanding the basics (should not be discussed)

• Google File System

To understand Pregel and another approach that has not this rigid super step model. The last paper introduces some methods to fight stragglers that come from graph topology.

• Signal Collect
• Google Pregel
• HipG: Parallel Processing of Large-Scale Graphs

And finnaly two more papers that discuss how map reduce can be used to process large graphs without a pregel like frame work.

• Pegasus Paper
• Design Patterns for Efficient Graph Algorithms in MapReduce

More feedback is welcome

If you have some suggestions to the rules or other remarks that we havn’t thought of or if you just want to read other papers feel free to comment here in this way everyone who is interested can contribute to the discussion.

Making Mozilla is great!

So this is actually why Mozilla thinks making Mozilla is great and what their motivation is. They think firefox enables them to change the way the web is developed. If they don’t like something they won’t implement it. So you clearly see one asset of Firefox is being in the gate keeper position. And being there is valuable in its own. That is probably one of the reasons why Google put so much effort on chrome and android. Both products go very deep and make google a gatekeeper giving them tons of power to steer developments in the “right” direction. 

Look at the feature!

Bobby pointed out that if you want to contribute to Mozilla are Gecko you should not even consider to follow a top down approach. He said that it is impossible to understand 7 mio. lines of (fast changing) code. He rather suggests to look at the specific feature you want to develope and  look at the documentation. You should play around and get it running. In my own experience that is on of the things that makes the difference betweed some coder and an amazing hacker. If you are really able to hack your things in an entire system without overview of the entire thing then your “in business”

Tests are awesome!

Ok that was the most interesting take away. Bobby said that tests are important not only so you can see that your code works properly and that you can check that your code doesn’t interfere with others. But tests are also great so if people change their parts they can check your feature will still work with their. He said your tools won’t continue working for longer than a couple weeks unless you provide tests so others see their plugins don’t destroy your work… Metalcon was only 40’000 lines of code and pretty manageable but we already saw weired things getting messed up once we checked in some code at some other point. To quote Bobby: 

If you check in some new lines you can smoke test them but if you check them in and 200 test lamps go green it feels good. More importantly. A huge community will make new stuff so if you didn’t write a test within a month your new feature might not work…

• $10 bn revenue / quartal ==> more than $100 mio. / day!!!
• 90 Mio Google+ users
• over 60% of plus users engage daily with it and over 80% weekly!
• 350 Mio active Gmail users
• Youtube makes $5 bn revenue
• 700’000 android devices installed daily
• 250 Mio. Android devices in total!
• 11 bn downloads from the android market
• chrome is growing (sadly no numbers) But in an interesting (on its own) blog post of reddit you can see 42% of reddit users use chrome (which might not be representative)
• Google apps has 5000 new businesses signing up per day (among them: harvard, berkley, states (like wyoming), and a major bank bbva >100’000 employees) ,…)
• 1 mio. Google+ pages have been created by brands (it is mentioned that there exists a sales team (I knew it all the time (-: )

Larry points out again:
Like I always said: “Emerging highest quality products can generate huge new businesses for Google on the long term. Just like search. And we have a ton of experience monetizing those products over time!”
But have a look for yourself and listen to the annual report!