Friday, May 11, 2018

In large social engineering graphs, there are updates of about 86,400 operations per second. Even if we keep the journal in a cloud database where there is no restriction to storage, fetching and updating states on the graph may take a long while. In such case, we can take snapshots of the graph and pin those against timestamps for consistency. Next, we separate the snapshot, replay and consistency checks as offline activities. In such cases, it becomes important to perform analytics on dynamic graphs instead of static graphs. The store-and-static-compute model worked because updates were batched and then graph processing applied on static snapshots from different points in time. It worked so long as the graph modifications were less frequent than static processing. With dynamic graph processing, we need a new framework. One such framework proposed was GraphIn which introduces a new programming model called Incremental-Gather-Apply-Scatter. In the gather phase, incoming messages are processed and combined into one message. In the Apply phase, vertices use the combined message to update their state. In the scatter phase, vertices can send a message to their neighbors along their edges. 

This framework divides the continuous stream of updates into fixed size batches processed in the order of their arrival.  

If the updates were recorded in the table as described by the tuple above, there would be a range of entries over which the updates are pending and would need to be applied to the graph. The completed updates are available for analysis and they can also be aged and archived. Although there may be billions of rows of entries, we can apply window functions with 'over' clause in sql queries to work on the equivalent of fixed size records from batches but in a streaming manner. 

For example: 

SELECT COUNT(*)  

OVER ( PARTITION BY hash(u.timestamp DIV (60*60*24)) partitions 3 ) u1 

FROM graphupdate u; 

Full discussion : https://1drv.ms/w/s!Ashlm-Nw-wnWtkxOVeU-mbfydKxs 

No comments:

Post a Comment