friends algorithm rewrite

Because of user-invites and same-as we need a) a more flexible way to represent relations between feeds, and b)
the ability for modules to express aspects of those relationships. (and I think same-as will have many uses: same-as for pubs and same-as for groups)

This is the last piece to user-invites, it's been simmering away in my mind a bit, then I can start putting it all together. In this post I'll write about representing relationships, and I'll write about splitting into modules once I've figured that out...

representing relationships

requirements:

• ability to represent feeds as being the same, i.e. zero hops between them.
• express nuanced relationships, including following, unfollowing, blocking, following but not replicating thier foafs.

The next step is a data structure to represent the possible relationships:

{
  id: <id>, //your id.
  follows: {
    <id:a>: {<id:b>: <hops> || [<hops:in>, <hops:out>], ...} //a 2 level map, representing A follows A
  },
  blocked: {
   <id:b>: {<id:a>: <boolean>} //not, reverse style: b<-[blocks]-a
  }
}

code, and more detailed documentation: ssb-friends#rewrite

the follow graph is separated from the block graph, as it was in the original friends plugin that @paul wrote, and not the rewrite that I did later. Also, I realized it's better to put the graph of blocks in reverse. In the actual algorithms, we want to quickly get everyone who's blocked someone - so it's easier to store it in reverse, on the other hand, we want to see who someone follows not who follows them.

This can represent following someone but not their friends by saying A:{B: [1, 2]} which means A follows B, B will have a hops of 1, but any one B follows will have hops 3 (unless they are followed more directly by someone else).

Basically, this is a way to make a weighted directed graph, and then the shortest paths are calculated across that graph, and the nodes reachable with a fixed distance (hops) are replicated.

Additional idea: feeds can publish their hops setting: then you'll be able to reason about wether they probably see your messages (if you are within their hops range).

contact messages, user invites, and same-as should all use different message types to express their meaning. currently, I'm only intending to use whole numbers weights, but decimals will also work. This data structure is just about representing the relationships, not how the are expressed as messages. If you were to implement something like @mix's "actual-friends" proposal, you could apply whatever clever algorithm you liked, it just has to output this datastructure.

hey @dominic can you make a couple of things clearer for me :

• does <id:a> mean my identity <id> , but version a of it
• what is <hops:in> and <hops:out>
  • does "in" mean "I declare this person to be a distance of 1 hop from me"
  • I just didn't undestand this sentence at all really:

    This can represent following someone but not their friends by saying A:{B: [1, 2]} which means A follows B, B will have a hops of 1, but any one B follows will have hops 3 (unless they are followed more directly by someone else)

The idea of weighting sounds good. I've been noticing how and where I have been using follows. Often I want to be able to mentions someone easily so I have to follow them, which seems wrong.
Often there's a new person who I guess is in a minority and I want to ensure they're replicated reliably, so I follow them - but I don't really know if we're going to be 'friends' ...

I think it could be interesting to collect ways people are using follows to hack different needs

Thumbs up for the data structure to represent relationships, but I'd also like to know what is <hops:in> and <hops:out>

@mix @andrestaltz to clarify: hops:in is the weight you give to your connection with them, and hops:out is the weight to give outgoing connections from that node. (so if you wanted to replicate someone, but not their friends you could do [1, 3] that would set them at 1 hop away from you, but their friends at 3 extra hops away, probably out of range. normally, it would just be {A:{B:1}} which is the same as {A: {B: [1,1]}}

TL;DR - this is excellent for affording reason-able boundaries

This feature would make it much easier to maintain reason-able (an algorithm that can be resonably reasoned about) social/data boundaries.

Some of the takeaways from my experiment in maintaining an understandable boundary was that

1. You can't follow friends who follow alot of people

unless

1. You reduce your hops down to 1.

What you are proposing would allow one to have more granularity with which FoF you'd be willing to forgoe this for... e.g. if someone follows very few people and all the people you know that they follow are values-aligned, you'd be happy to take on faith data replicate. I might follow someone I trust who has hundreds of friends, but I don't want to replicate their hundreds of friends as it's less reasonable to assume there is a tight bond with all of those links...

by <id> I mean that a feed id goes there. when I give it a label, I like <id:a> or <id:out> that is just to emphasize that they are different values. follows: {A:{B: 1}} just means A follows B (whoever they are).

Wether following means "friendship" is a human layer interpretation. It just means you choose to replicate them, and are willing to advertise that. (btw, I definitely recommend being able to put any kind of relationship message in a private message, but that doesn't need to be modeled in the relationships data structure.

@noffle if you (A) had your hops set to 2, declaring someone (B) to be 3 hops would put them just outside your reach. If someone (C) followed you (A), this person (B) would be 3 hops from them (C). If C had hops=3, then it would include B. If you set it to 99, it would be well out of reach of reasonable hops settings.

@noffle the hops just the shortest path, except when you follow you can set what "length" that connection is. C->B is 3 hops, because the two possible paths are C->A-->B (length: 3), and C->D--->B (length: 4) so the answer is 3.

your comment has made me think that maybe you should [1,-1] to say, replicate them, but ignore their friends. (although, someone else might provide a different path to those feeds)

Thanks for the clarification, I think in:out makes sense to configure the graph in details. I would have named it something else than in, out though, not sure exactly what

I don't support the idea of putting -1 with semantics of "Infinity" though, because it kind of breaks the math. in=1 and out=-1 would add up to 0 and it would mean "this friend is ... me". Now I couldn't anymore add the weights and check the distance, I would need to check the semantics of a particular weight item.

I suppose you were thinking about an easily transportable value (through the network), and Infinity doesn't work in JSON, but we could agree that the data structure should have [1, Infinity] but the serialized messages that make that up could be something else, maybe even a string 'infinity'

@Erik it's not that hard, all you need is a width first search.

@andrestaltz if we supported negative hops, it would mean that A follows B, B -1 follows C, and it would look like A same-as C! (because 1 + -1 = 0). B should not be able to speak for A like that unless it's something that A explicitly opts into. Theirfore I think negative hops shouldn't be allowed.

[1,-1] now means follow, but do not explore paths to their follows. [1,0] means follow, but treat their friends as your friends. (You may not want this, but it can be expressed by the data structure).

@andrestaltz in anycase, because follows interacts with blocks, it's not as simple as just adding together the weights along the shortest path, anyway, so checking for -1 as a special meaning isn't too big a deal.

@Erik that is true, but it doesn't matter because the graph is not very big. If you are replacating the 2nd hop out, it's only gonna be a few thousand nodes, if you replicate 1 hop, then a few hundred. Also, when edges are added (or paths getting shorter), it's possible to update the hops table without retraversing the entire graph. The graph only needs to be fully recalculated when edges are removed (or paths getting longer).

My inclination is towards visual examples for I LOVED your example :

C->D--->B

because what you're illustrating is distances from people.

What if there was a bytewise type distance so your could represent things like :

Treat any Friend of A as a friend of mine

{ follows: A: [1, 0] } or { follows: A: [1, undefined] }

I don't care about A's friends

{ follows: A: [1, null] }

I met A, but they're not that close

{ follows: A: [2, 0] }

This would be great for someone I met at a conference .. and aquintance. Specifically I want this so that in user interfaces I can have the oft pined after "filter view by open-ness filter". So on quiet days I can connect with people who are genuinely 1 hop from me, and it doesn't need to include some people who are nice but I'm not yet intimately close to.

@Cy re:circles that is what "private-groups" will do. Since ssb is pull based, the only way to restrict what other people can see is to use encryption. I'm gonna start on these encrypted groups once user-invites is ready (this friend graph thing being the last major part of that)

@mix yup, also a visualization that explicitly shows weights as lengths excludes negative weights because you can't have a negative length! Also, note: undefined is not a valid json value, so we want to avoid using that in a thing we will want to serialize.

Okay, I get it now and I agree -1 doesn't make sense for the weights.

Friend distance could also make sense for prioritizing replication, right? E.g. "sync with friends at distance 1 first with maximum possible bandwidth, then sync with friends at distance 2 with throttled bandwidth" sort of like Torrent leeching prioritization. cc @Piet

I was working on this, taking the tests that I had made before, calculating a hops object following the rules described above. the hops object is just a map of feed id to minimum path length to that node... {<id>: <hops>,...} but when I started on code to incrementally update the graph, I found problems. It's necessary to update incrementally, because there are many follow messages and retraversing the entire graph on each one really slows down initial sync performance (fixed that previously in commit c9099afa03dea7608c2fc0c1559a85eb832c6714 on ssb-friends)

Anyway so the problem I found is that if we have the [in, out] pairs, that needs to be reflected in the hops. We need to remember that if a new shorter path to a known peer with a different out length is found, that it applies the out length... but it's too late to think clearly about this now...

after fairly rigorious testing, and banging my head against the wall trying to get it to work... I realized that I've designed it wrong. Separating out the blocks was actually a bad idea: I eventually discovered an obsecure edge case were sometimes following someone causes blocks unreplicate some others. The previous way things were modeled this was representable, but the new design! Now I'm thinking about how to combine both ideas...

Okay, the friends rewrite was a bit more involved than I had intended. But I've gotten it about as elegant as I think I can, and now I have a somewhat better understanding of what I already did. I rewrote it, then I realized I had bugs, then while trying to fix those bugs, I realized I had the algorithm basically right before (the first rewrite). Well, I'm gonna have to write up everything about this tomorrow. Then I still have to do the bit about merging partial graphs (from the different ways of expressing follow/same-as/invites)

So, I continued that rewrite, then realized I had a fundamental error: when I added same-as support, the code became order dependant! If your same-as device blocked someone, it might still include their friends. This is not what I wanted. Yeah, so I'm not having much fun working on this... It's been 4 months since I started user-invites. I havn't just been working on this, so I have made progress with other things, I guess that is a consolation.

The approach I had been using was to expand the traversal from the starting point (your main identity) to each reachable feed in a width first traversal. In the original where this worked, each expansion added 1 to the hop count of a feed.
It also represented the block distance: the hop count of the feed that blocked. This worked because it always expanded closer feeds first. But when I added same-as support, in certain situations, such as chained same-as, you could have a feed that was actually closer (because of same-as) expanded after a more distant one.

One idea would be to expand the feeds in the order of their hop count, but I decided to try another design first: keep another data structure representing the reverse follow graph: who is followed by who, so that when an edge is added (or removed) from a peer, you can just recalculate their weight. I think this might work, but need to build my intuitions about it by implementing and testing it.

@iago oh, I'm definitely not under the illusion that this algorithm is ideal in any way. It's just something that is evolving slowly. but also: I'm endevoring to make the replication decisions as open as possible - it should be relatively easy to replace this algorithm with a different policy. you might like @mix 's actual-friends proposal

update: I was finding problems with my backlink based algorithm, so I decided to try the other idea: traverse links in order of hop-length. That worked, but was using a sorted array. Okay so there is an data structure for this: a Heap. On the wikipedia page, I read the line:

Heaps are also crucial in several efficient graph algorithms such as Dijkstra's algorithm

Oh yeah I should have read that. On that page I read:

What is the shortest way to travel from Rotterdam to Groningen, in general: from given city to given city. It is the algorithm for the shortest path, which I designed in about twenty minutes. One morning I was shopping in Amsterdam with my young fiancée, and tired, we sat down on the café terrace to drink a cup of coffee and I was just thinking about whether I could do this, and I then designed the algorithm for the shortest path. As I said, it was a twenty-minute invention. In fact, it was published in ’59, three years late. The publication is still readable, it is, in fact, quite nice. One of the reasons that it is so nice was that I designed it without pencil and paper. I learned later that one of the advantages of designing without pencil and paper is that you are almost forced to avoid all avoidable complexities. Eventually that algorithm became, to my great amazement, one of the cornerstones of my fame.

Dang, now I feel dumb.
Months fumbling around with this problem and Dijkstra came up with it in 20 minutes!

Although, the problems we are describing is slightly different. In the end, we only care about the distance to the node, not the path. But... that isn't a very big difference.

some notes: relative proportions of contact messages, follow, unfollow, and block:

{ follow: 82147, unfollow: 7239, block: 651, count: 472830 }

follow messages are 17% of all messages! I think the unfollow number is a bit higher than it would be, because in patchwork it is very easy to hit follow then unfollow then follow again.

Thoughts: I need an efficient way to process changes to the follow graph incrementally. The current code takes ~200 ms to traverse the graph. That's good if it's one time, but if you have to recalculate that on every follow that becomes very slow. If you do that just 5 times, it's blocked the CPU for 1 second.

Adding an edge is easy, because adding an edge only makes paths to other nodes shorter. But removing an edge (also adding a block) is harder.

Some observations: If you block or unfollow someone that you previously followed, some feeds may be further away now. But one thing we know for sure: feeds that were already closer than the blocked feed do not change - The shortest path to a node cannot go through a more distant node! So a block means we only need to recalculate more distant nodes.

Hmm, so we take feeds that the blocked feed follows, and check if their distance has changed. If they had another edge from a feed at a lower distance than the blocked feed, then we know that edge doesn't change. Otherwise, we remove that node?

What is the time complexity of your algorithm?

As for your problem, without having fully understood the details, maybe you can split the graph into nodes that can never be touched by unfollow/block and the ones that can, and only run your algorithm on the path that can be affected. That would work well, unless the block is in a central part of the graph, but still should be much better than doing the whole graph.

@arj yes. One observation is that when you remove an edge, paths can only stay the same or get longer. So nodes that are already closer than that node was cannot be affected. Only nodes followed by the removed node may be affected...

Update: turns out dynamic shortest paths is an open problem (now I don't feel so bad about not solving it) this stackoverflow thread links to various papers.

I think I'm making progress.

my current approach: when making a negative edge (block) from A to B, first collect the set that are "downstream" from B. to get this, traverse the graph starting from B, and collect all nodes that are reachable from B, and have a higher distance than B. (also, take into account that an edge from a->b has distance[b] == distance[a]+edge.value. These are the nodes who's distance may be altered by removing A->B.

Then, collect all the nodes which edges into this set (to make this fast, we keep a copy of the graph with all edges reversed). This is the set of possible sources, from which you may still be able to reach into the modified set. Delete all recorded distances for the modified set. Load the source set into dijkstra's algorithm and run it again.

Still some edge cases it seems though...

Today I've been working on the tests more. Yesterday I got it working... but it was still quite slow, because it was applying the heavy update algorithm each time. I needed to detect the cases where there weren't gonna need to be any changes, and skip those. This seems to be working. Needs more testing.

@nichoth yes I am aware of A but the difference between Dijkstra's algorithm and A is that A* needs a heuristic. That makes sense if you are using it to find a shortest path on a ~2D space, because you can use as-the-crow-flys distance as the heuristic. (if I recall, the heuristic may underestimate, but must not over-estimate)... The peers arn't mapped to any kind of flatish space... so I'm not sure what a suitable heuristic for this would be.

update: it's working with the actual contact messages from my ssb log, including updates, comes out the same as the traversal, the incremental update comes out the same as traversing the entire graph - and completes in 1 second!

Woot! Great! Looking forward for user invites and all these other modular achievements in between :)

update: tidied up code for legibility and wrote documentation http://github.com/dominictarr/traversable

really needs illustrations of how the algorithm works in various situations.

Next is actually attaching this to ssb!

Okay, I have this wired in and the scuttlebot tests are all passing (had to make a few changes in various things that depended on ssb-friends, will tidy up next)

Okay, this is now just about ready. It feels like I've been standing up a lot of dominos and I'm about to tip them all over. This enables user-invites and pubs-as-second-device (which means gossip gets to be refactored, and you'll prioritize connecting to friends!) and it allows same-as to work nicely. and we can also use this to implement blocklists.

Am just deciding what the new ssb-friends api should look like. Hmm, how it interacts with other things:

The friends plugin uses hooks into auth (to prevent blocked peers from connecting) and, and createHistoryStream (to prevent blocked peers requesting feeds that have blocked them) ebt has it's own copy of the block data, so ssb-ebt uses friends.stream() (this is a somewhat awkward api, that @arj
recently found a bug in)

There were several other places that used friends.get and then checked wether one id was following another. since the internal data structure has changed, it was obvious to decouple this: now they just call isFollows({source,dest}, cb)

hmm, patchcore, and theirfore patchwork, uses friends.stream to copy the follow graph into the front end. This is a bad idea performance-wise, but I want to get this deployed asap, so I think the right move is to make friensd.stream backwards compatible. (note: patchless just uses friends.get when it needs to know who follows who, rather than at startup, which is much faster)

Nice work @Dominic!

This is a bad idea performance-wise, but I want to get this deployed asap, so I think the right move is to make friensd.stream backwards compatible

Yeah, that's probably best for now. I am really keen to drop the patchcore dependency in Patchwork and handle all of that stuff more efficiently when I next get some time to go deep.

Exciting!

I'd love to have a look at the changes if you do a PR.

thought: if you have the shortest paths from some point in a graph, if you have a path from X and to Y, you also have a lower bound for the path length between X and Y. The path between shortestPath(X, Y) can't be smaller than shortestPath(you, Y) - shortestPath(you, X), because if there was a shorter path between X and Y, then the path from you to Y would go through X first to take advantage of that.

This could be useful to show who will stop replicating someone if you block them, for example.

I have publish ssb-friends@3.0.2, including the updated algorithm. I made it a major version, so that it's a manual update, but it should be fully backwards compatible with current clients. I've beening using this and tested it in patchless. Please test in your client. You might see a couple of old feeds on the fringes of your network appear, pretty sure this is because there was some order dependent bugs in the old code.

Everything is in place again and I can go back to working on user invites

Excellent, can you push to github as well?

Hmm... I added it in my copy of #patchbay-dev by bumping it's direct dependency in the pkg.json. I also let sbot reindex all the stuff for good measure. Mostly everything seems to work as expected.

One thing I noticed was this log message, which I'm not sure how significant it is or how much more awesome the new api is? ssb-friends: stream legacy api used

One weird thing I noticed was this: patchbay doesn't show me being friends with soapdog, althouhg patchfoo does, using the same sbot server instance.. i'm not sure if patchfoo does the contact state lookup by itself or if it uses the plugin api though (cc @cel). I followed him 5 month ago, the message is %Nfr6H0Y...

I'm not sure if I should be worried about the dependency graph as in do I need to patch the deps of the deps before it will acutally use the new code all the way?!

patchbay@7.13.1 /home/cryptix/ssb/patchbay
├─┬ patchcore@1.28.0
│ └── ssb-friends@2.4.0 
├─┬ scuttlebot@11.3.3
│ └── ssb-friends@2.4.0 
├─┬ ssb-chess@2.2.8
│ └─┬ scuttlebot@10.2.1
│   └── ssb-friends@2.4.0 
└── ssb-friends@3.0.2

I assumed by upgrading patchbays deps, and it requiring and loading the plugin in its sbot server / background-process.js, this will lead to just that one being present but maybe pcore needs to be bumped as well...

cc @mix et al #patchcore

disregard the question about warning legacy. I now read %CYipxlk... and assume it's about that friends.stream(). I just wondered because stream is such a general term wrt ssbs numerous apis..

@dominic / @mix : downgrading to v2 brings back my friends. another example of a missing key would be @3a/8VgfLqnmmqO3mf0al1piEbKqvg1LqRoNd2pcsLLo=.ed25519, which is gone when I bump to v3.

I didn't try to bump pcore to v3 yet as I'm stretched on time - would love to help with a fix or better diagnosis but just a vague testing report so far...

One thing I noticed is that the ssb-friends doesn't bump it's index version and is still and 2. I manually re-indexed everything by blowing away .ssb/flume before running v3 so this shouldn't be the issue here. Not sure if this will be a problem for people upgrading, though..

haven't had time to explore this yet. thanks for keeping me looped in

also: https://github.com/ssbc/ssb-friends master is still at 9d6f311d4a971a07371e01b7ff601c44d092aa64 / 1 after v2.4

@dominic: can you push the new code?

@cryptix, sorry! pushed 3.1.0

@cryptix I checking and my result is that you are following @SoapDog.

> sbot friends.get --source @p13zSAiOpguI9nsawkGijsnMfWmFd5rlUNpzekEE+vI=.ed25519 --dest @gaQw6z30GpfsW9k8V5ED4pHrg8zmrqku24zTSAINhRg=.ed25519
true

Also, in 3.1.0 the index version is 4. ping me if this is still a problem?

hey @dominic

i tried again with 3.1.1 and I still have missing connections. The above command gives me null on v3..

I ran sbot friends.createFriendStream | sort -u on both versions.

$ wc -l sorted_v*
  6681 sorted_v2.json
  5612 sorted_v3.json

• sorted_v2.json
• sorted_v3.json

is there something else I can give you or you want me to run to debug this further?

also: am I correct that the flume state idx in v2 is called friends.json and in v3 it's contacts2.json ?

I just saw f678f25540b98c06674ee6c4b867c34f9513bd2c / v3.1.2

What is fixed in there looks like it could have caused my problem. If it doesn't, I'll open an issue in github for more visibility/notify.

@cryptix btw, I fixed some more bugs in 3.1.3

@dominic

Looks like the bug is gone for me:

$ wc -l v*.json
  14894 v2.json
  14894 v3.json

okay, nice! I just tried 3.1.3 and can no longer produce the issue I had before!