<br><br><div class="gmail_quote">On Fri, Nov 18, 2011 at 9:28 PM, Aphyr <span dir="ltr"><<a href="mailto:aphyr@aphyr.com">aphyr@aphyr.com</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
<div class="im">On 11/18/2011 11:50 AM, Jeroen van Dijk wrote:<br>
</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div class="im">
And I also didn't include the riak user list for this reply:<br>
<br>
<br>
On Fri, Nov 18, 2011 at 7:04 PM, Aphyr <<a href="mailto:aphyr@aphyr.com" target="_blank">aphyr@aphyr.com</a><br></div><div class="im">
<mailto:<a href="mailto:aphyr@aphyr.com" target="_blank">aphyr@aphyr.com</a>>> wrote:<br>
<br>
    Depending on whether you think it will be more efficient to store<br>
    the graph or its dual, consider each node a vertex and write the<br>
    adjacency list as a part of its data. You can store whatever<br>
    weights, etc. you need on the edges there.<br>
<br>
    Don't use links; they're just a thin layer on top of mapreduce, so<br>
    there's really not much advantage to using them. Links are subject<br>
    to the HTTP header lengths too, so storing more than a thousand on<br>
    any node is likely to break down.<br>
<br>
<br>
Thank you for this suggestion. Also thanks for the warning on not using<br>
links for what I want. So you are saying each vertex will have a list of<br>
the other vertices that it is connected to? And save each edge as<br>
key/value pair? Or are you saying each vertex should embed the adjacent<br>
edges, meaning duplicated edges?<br>
</div></blockquote>
<br>
Depends on whether you want to store the graph or its dual. If you're dealing with a sparse DAG where the input keys are likely to be vertex names, the natural choice is to store each vertex as an object in riak and each outbound edge from it as a property of that vertex.<br>

<br>
/users/user1:<br>
  owns: [item1, ...]<br>
  follows: [user2, ...]<br>
<br>
Of course, this method doesn't work well when you need to follow edges in reverse, so you may need to store the reciprocal relationship on target nodes:<br>
<br>
/items/item1:<br>
  owner: user1,<br>
<br>
/users/user2:<br>
  followed-by: [user1, ...]<br>
<br>
and so forth. That requires two writes and potentially lossy conflict resolution strategies, e.g. a follows b but b is not followed by a. We use processes which walk the graph continuously and enforce relationship integrity as they go. We have a social graph of several hundred million objects stored this way in Riak, and it works reasonably well.<br>

<br>
Naturally, you'll want to choose an encoding which is fast and space-efficient for a large dataset. Depending on your needs, JSON, protocol buffers, or fixed-length record entries might be work well.<br>
<br>
Also consider the depth of traversals you'll need to perform. It may be best to use a graph database like neo4j for deep traversals. You could store your primary dataset in Riak and replicate only the important graph information to a graph DB via post-commit hooks. That would solve the reciprocal consistency problem (at the cost of replication lag), and could reduce the amount of data you need to put into the graph DB.<br>

<br>
Given that Linkedin has this problem, you might look into their tools as well.<br>
<br></blockquote><div><br></div><div>Thanks for your detailed reply. I'm very happy to hear that you are using Riak for a similar use case. My dataset will be of a similar magnitude. It will be a graph where edges have properties (e.g. user 1 rates item x with 2 stars), but I think saving these edges as separate objects will work. I'll use post-commit hooks to get all this data in a graph database (probably Neo4j) and use this for graph traversing.</div>
<div><br></div><div>A side question Kyle, how do you make sure the graph database is always (eventually) consistent with Riak? E.g. how do you correct potential errors during the post-commit hooks for instance? And say this database gets corrupt how do you recover this graph database and get it in sync again with Riak?</div>
<div><br></div><div>Cheers,</div><div>Jeroen</div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><div> </div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">

--Kyle<br>
<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div><div></div><div class="h5">
I'm guessing you mean the former, because that makes sense to me. So you<br>
would save a graph assuming users and items like the following key/value<br>
pairs:<br>
<br>
//Vertices<br>
user1: properties<br>
user2: properties<br>
item1: properties<br>
<br>
//Edges<br>
user1-owns-item1: properties<br>
user1-follows-user2: properties<br>
user2-follows-user1: properties<br>
<br>
To be able to find the available edges, each vertices would need to<br>
reference the keys of the edges. Is this what you mean?<br>
<br>
If so, one more question about a possible problem. Say I have an item<br>
with many many outgoing edges, so it needs to embed these references.<br>
This would make it really costly to fetch this item from Riak I assume,<br>
even if you are only interested in normal properties. Wouldn't that mean<br>
you will have to save the properties seperately from the edges<br>
references to it feasible?<br>
<br>
Did I grasp what you were proposing Kyle?<br>
<br>
Thanks,<br>
Jeroen<br>
<br>
    --Kyle<br>
<br>
<br>
    On 11/18/2011 07:38 AM, Jeroen van Dijk wrote:<br>
<br>
        Hi all,<br>
<br>
        I'm currently evaluating whether Riak would fit as the main<br>
        storage of<br>
        my current project, a social network. The reason I am attracted<br>
        to Riak<br>
        and less to a Graph database as main storage is that I want the easy<br>
        horizontal scalability and multi-site replication that Riak<br>
        provides.<br>
        The only thing I doubt is whether the key-value/link model of<br>
        Riak is<br>
        flexible enough to be able to store a property graph<br></div></div>
        (<a href="http://arxiv.org/abs/1006.__2361" target="_blank">http://arxiv.org/abs/1006.__<u></u>2361</a><br>
        <<a href="http://arxiv.org/abs/1006.2361" target="_blank">http://arxiv.org/abs/1006.<u></u>2361</a>>). I am not asking whether the<div class="im"><br>
        querying/graph traversing will be easy; I'm probably going to use a<br>
        graph database or a Pregel like platform (e.g.<br>
        <a href="http://www.goldenorbos.org/" target="_blank">http://www.goldenorbos.org/</a>) for that problem. I guess my main<br>
        question<br>
        is whether it would be easy/feasible to import and export a property<br>
        graph in and from Riak? Has someone done this before?<br>
<br>
        I realize the above might be too specific, so here are two more<br>
        questions that I think are relevant:<br>
<br>
        - Is there a known upper limit of links that can be stored (I<br>
        don't want<br>
        to add them all at once so 1000 per request is fine,<br></div>
        <a href="http://lists.basho.com/__pipermail/riak-users_lists.__basho.com/2010-March/000786.__html" target="_blank">http://lists.basho.com/__<u></u>pipermail/riak-users_lists.__<u></u>basho.com/2010-March/000786.__<u></u>html</a><br>

        <<a href="http://lists.basho.com/pipermail/riak-users_lists.basho.com/2010-March/000786.html" target="_blank">http://lists.basho.com/<u></u>pipermail/riak-users_lists.<u></u>basho.com/2010-March/000786.<u></u>html</a>>)<div class="im">
<br>
        - Is there a way to add meta data to links (edges)? E.g. weigths and<br>
        other attributes.<br>
<br>
        Any other ideas or advise are also highly appreciated.<br>
<br>
        Cheers,<br>
<br>
        Jeroen<br>
<br>
<br>
<br></div>
        ______________________________<u></u>___________________<br>
        riak-users mailing list<br>
        <a href="mailto:riak-users@lists.basho.com" target="_blank">riak-users@lists.basho.com</a> <mailto:<a href="mailto:riak-users@lists.basho.com" target="_blank">riak-users@lists.<u></u>basho.com</a>><br>
        <a href="http://lists.basho.com/__mailman/listinfo/riak-users___lists.basho.com" target="_blank">http://lists.basho.com/__<u></u>mailman/listinfo/riak-users___<u></u>lists.basho.com</a><br>
        <<a href="http://lists.basho.com/mailman/listinfo/riak-users_lists.basho.com" target="_blank">http://lists.basho.com/<u></u>mailman/listinfo/riak-users_<u></u>lists.basho.com</a>><div class="im"><br>
<br>
<br>
<br>
<br>
<br>
______________________________<u></u>_________________<br>
riak-users mailing list<br>
<a href="mailto:riak-users@lists.basho.com" target="_blank">riak-users@lists.basho.com</a><br>
<a href="http://lists.basho.com/mailman/listinfo/riak-users_lists.basho.com" target="_blank">http://lists.basho.com/<u></u>mailman/listinfo/riak-users_<u></u>lists.basho.com</a><br>
</div></blockquote>
</blockquote></div><br>