Thread

dijkstra ftw!

damn right! 🕺🏻 How much slower would this be with standard (non-native graph db) nostr relays? Probably many orders of magnitude.

yeah, non-graph indexes won't get you that kind of speed. i've actually added the required index that could enable any and all kinds of relations between events, pubkeys, and pubkeys and events (so it's bidirectional you search either direction linearly). the actual graph walk operation like this requires a custom query to scan the vertex table. i have actually already put the vertex table in there btw. it happens to be a neat optimization for p tag searches, so it's used now in the badger event store. the benefit of using the k/v store is that i can skip things that a full graph search engine might do. for one thing i could skip the whole graphql parse and just write specific calls that produce outputs like that there. i'm not sure what other indexes might be useful. i was thinking about relay URLs maybe deserving an index, i think there is other elements of the data set that qualify as unique keys and therefore can become nodes in a graph.

Here’s my first pass at a data model (I was previously using the word schema when I should have been using the phrase data model) for a neo4j-nostr relay: https://www.notion.so/Data-Model-for-a-Neo4j-Nostr-Relay-2b30dd16b665800fb16df4756ed3f3ad

I included NostrRelay nodes although I think they could be optional.

i'm not gonna dip into the pool of full implementation of custom graph traversal algorithms using a custom key/value store right now but i have in my mind ideas about how it can be done and some of the ways it can be optimized for a given task. simulation is an area of programming i haven't done an awful lot, but one time i was given a "skill test" for a job with the Ignite project, building a scaffolding system for Cosmos dApp chains, and i quite enjoyed creating a deterministic random number generation and a procedure by which the seed modified the parameters of the model, and it plays it out until it hits a terminal state, and then prints a report of the action that occurred (it was an alien invasion simulation, a little like a variant of Conway's Game of Life, seed it randomly and then using rules, elaborate the system's changes until it reaches a terminal point or forever loop that does not escape. graphs are powerful tools for modeling this kind of phenomenon, and graph indexes like what i described are very likely along similar lines of structure and content as required to scale up to model any system, given the parameter set. so, it seems like a very powerful tool, and from what i've seen done especially with 3d modeling, it is possible to create realtime simulations that rapidly change with new input. i figure there is probably dozens of algorithms developed for creating this kind of fast traversal to do it in real time. speeding up the evaluation of changes driven by user input such that within milliseconds after updates you can query other parts of the graph that got affected and immediately render the result (such as, the dynamic changes of a trust score in a cluster of nodes).

When you say graph algos using a KV store, do you mean you’re gonna make a graph database out of a KV store that’s a truly native graph db, meaning it benefits from index free adjacency? I was recently looking for examples of those and found HelixDB, a native graph db that uses LMDB as its underlying storage engine. Could be a candidate for a native graph db nostr relay. Pretty new though, not sure whether it’s fully functional, unlike neo4j which is very well established.

i think so, but i'm not sure i fully understand that. i just made a pair of tables, one is event/pubkey/kind and a byte flag that indicates the event is authored by the pubkey, or it points to that pubkey, or that pubkey points to it, and then the second is pubkey/event/kind, a forward and reverse lookup so i figure you would then follow an edge-inwards path so pubkey a, and pubkey b, then trace each one to the next, so it would alternate pubkey->event->pubkey->etc and it would explore the first level of each, looking for the event on each vector, and iterate depth, until it finds the common points that exist between them, discarding longer ones when it finds shorter ones. so i think that technically is index free adjacency because it is a scan on a linear, lexicographically sorted table, that consumes nodes as it passes, skipping them if already seen on the path, and the computation time would be some factor of the number of vertexes on each, by the depth between them, and each node on the path would contribute some factor to the number of keys that must be iterated. once the shortest midpoints are found, you would have the path unwrapped that's just my naive conception of the algorithm. i imagine that even in a graph in the millions that path lengths would be between 1 and maybe 10-12 or so, on the outside. keep in mind also that the kv store is going to keep all of the graph indexes in memory during the operation so once the as yet unknown path points are found, and the common node is discovered, the remainder of iteration is going to likely be mostly in memory. i need to fix the index order. kind is the first thing that must match, and putting it first groups all vectors of that type in one table.

I’ve always known intuitively that graph dbs were more performant than non graph dbs for certain algos like shortest path. It wasn’t until recently that I realized that some graph dbs are “native” and some are not native, it’s the native graph dbs that give the performance boost, and IFA is the defining feature of native graph dbs. It’s worth understanding the difference between native and non-native graph dbs; there are a lot of “graph databases” that are non-native and probably don’t even deserve the name. As far as I can tell, a clear definition of graph dbs doesn’t even exist outside the context of native graph dbs. I still don’t understand it well enough to read what you just wrote and be able to determine whether that achieves IFA or not. Building an IFA graph db from scratch (with or without a KV store) is a big endeavor. HelixDB that I mentioned earlier is funded by y-Combinator and probably still not feature rich or stable enough to use for a nostr relay. In the long term, I’d love to see multiple native graph db nostr relay implementations. Maybe one (or more) on neo4j, one using HelixDB, maybe one that’s built on top of a completely custom native graph db. In the short term, I’ll be overjoyed to see us go from 0 to 1 native graph db nostr relay asap. Neo4j is probably the best bet for doing it quickly without reinventing the wheel, given its long track record and wide user base. And the sooner we can get that first one going, the sooner we can motivate people to build out more!

Indeed. That's why I made a driver. I'm not likely to beat neo4j with a hand rolled version any time soon. I spent 2 days trying to implement the signature optimization libsecp256k1 uses, and failed. But I did at least implement 64bit limbs. Fastest pure go signature library, https://git.mleku.dev/mleku/nostr has it, I just popped it and all general purpose nostr libraries. They are stable now, and optimized to the gills. I love that stuff but I can't make progress on it without a lot less business to attend to. So for now, I'll just use the best in class when I can.

Cool 👍🏻 Hopefully the neo4j relay data model I put together looks reasonable?

Yeah, gonna be starting to implement that this afternoon