Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

PulsarCast M.Sc Thesis - Scaling libp2p PubSub #266

Open
JGAntunes opened this issue Oct 12, 2017 · 26 comments
Open

PulsarCast M.Sc Thesis - Scaling libp2p PubSub #266

JGAntunes opened this issue Oct 12, 2017 · 26 comments
Labels

Comments

@JGAntunes
Copy link
Member

@JGAntunes JGAntunes commented Oct 12, 2017

Greetings everyone!

I’m João Antunes, a grad student (M.Sc candidate) at the University of Lisbon, a full-time Software Engineer at YLD and one of the co-organizers of SINFO for the last 3 years. David Dias introduced me to the IPFS project a little more than a year ago and since then I've been following its developments and contributing to the JavaScript implementation with the chunks of free time I could find.

Now that I finished all my courses, I'm thrilled to share that I managed to excite and convince my Thesis advisor to let me pick IPFS and libp2p PubSub for my research. My goal is to scale IPFS PubSub to hundreds, if not thousands, of millions of participants 🙌🏽 with the hopes of getting some massing real-time games fully distributed. I'll be fortunate enough to be advised by David Dias(@diasdavid - Protocol Labs) and Luís Veiga(INESC-ID + University of Lisbon).

The timeline for M.Sc will encompass two major deliveries:

  • The first happening in the beginning of January (5th), also known as the project checkpoint, where I deliver the state of the art, literature review and proposed solution for the architecture to be built.
  • The second to be delivered in October 2018, where I deliver the full thesis, report and result.

Over the last couple of months, I've getting more and more familiar with IPFS internals and its API. I've tested it with a just a small PoC, a cli based chat app. I've also been reading the literature that I could find about distributed PubSub. Thank you for the compreensive list available at research-pubsub, I'll share new papers I find and my notes in the end too.

I'm currently working on porting Curvatron to IPFS and exploring the open source game space to find the perfect candidate to test my PubSub topologies and strategies. So far, my search lead me to agar.io, but I'm open to more suggestions.

I would love to get to know everyone involved and interested in this particular piece of work, share any relevant research or even just thoughts! I'm sure we'll be able to generate some relevant and healthy discussion around the P2P PubSub topic.

@nicola
Copy link
Member

@nicola nicola commented Oct 13, 2017

Hey @JGAntunes,
awesome to read your drive in this p2p space :)
Decentralized Pubsub is going to be fundamental in designing the next generation of p2p apps.
I really look forward to your work, of course providing help or resources if needed - I encourage the whole community to do so!

It would be great if you could document here your steps of your research, so that we can all follow what is going on :) (I tried to attemp something like this during my masters: https://github.com/nicola/decentralized-research/issues)

I will check in here often :)

@whyrusleeping
Copy link
Member

@whyrusleeping whyrusleeping commented Oct 15, 2017

Hey @JGAntunes, Welcome! Take a look at the recent writeup by @vyzo here: libp2p/research-pubsub#17

@JGAntunes
Copy link
Member Author

@JGAntunes JGAntunes commented Oct 27, 2017

Thanks everyone!

@nicola so far I'm catching up on literature, while also integrating the current floodsub implementation on Curvatron (for those interested - https://github.com/JGAntunes/curvatron - it's still in early stage, I'll make sure to share some more tangible results once I have them 😄), but I'll make sure to share as much as possible here! Thanks for the support 👍

@whyrusleeping thanks for pointing that out! Haven't read the whole RFC but I'll give it a more thorough look the next few days 👍

@dasilvacontin
Copy link

@dasilvacontin dasilvacontin commented Oct 28, 2017

Hi @JGAntunes! Very briefly: I'm interested in multiplayer games and game networking in general. I'm currently building ag-drift (not related to ipfs) on my free time, planning to release an MVP soon and move on.

I'm currently at IPFS day Barcelona trying to see how I could apply this technology. Looking forward to your progress! :)

@JGAntunes
Copy link
Member Author

@JGAntunes JGAntunes commented Nov 13, 2017

@dasilvacontin awesome! I've been working on my free time on - https://github.com/JGAntunes/curvatron - to understand the constraints around multiplayer games. Most of this is quite new to me, as I never guessed multiplayer synchronisation would turn out to be such a pain 🤦‍♂️

Been reading a bit about synchronising multiplayer games and other gamedev "lingo" (e.g. https://www.reddit.com/r/Overwatch/comments/3u5kfg/everything_you_need_to_know_about_tick_rate/ and https://gamedev.stackexchange.com/questions/6645/lag-compensation-with-networked-2d-games) and working around simple solutions for Curvatron, it has been mostly a work in progress but I'm getting somewhere (hopefully)

peek 2017-11-13 01-40
This is running locally but tested it out remotely with relative success synchronisation wise.

There's a lot of stuff though that I'm not even considering here nor have I investigated anything around it, such as consensus around game state (something that would be trivial with a server based solution).

@whyrusleeping
Copy link
Member

@whyrusleeping whyrusleeping commented Nov 13, 2017

I found this paper pretty insightful in the past: http://web.cs.wpi.edu/~claypool/courses/4513-B03/papers/games/bernier.pdf

Its by one of valves lead network engineers and discusses various strategies of interpolation for multiplayer realtime video games.

@JGAntunes
Copy link
Member Author

@JGAntunes JGAntunes commented Jan 27, 2018

Hey everyone! It's been a while since my last update (my bad...) so, here it is 🎉.

Over the past few months I've been working on the initial report due to this month where I tackled:

  • State of the art and literature review
  • Proposed solution

I've successfully delivered it and I'm now working on its presentation, due to the beginning of next month. Hopefully, after that, I'll be able to share and open source all the work I've done so far. Including the relevant systems I've addressed, proposed solution, etc. Something I'm really looking forward to 😄

After all of this, I'll start developing the solution itself 🙌 due to October.

Once again thanks for all the help and pointers everyone provided so far! Hope to be able to share all of this with you in the upcoming weeks 😄

@JGAntunes
Copy link
Member Author

@JGAntunes JGAntunes commented Feb 16, 2018

Hey everyone!

What's new

So, great news, I just open sourced the first part of my work (and consequently all that will follow) 🎉 You can check it out over here - https://github.com/JGAntunes/pulsarcast.

You can read the full report here and the presentation here. So far I've already collected valuable feedback from my presentation, listed here, but I would sure be glad to hear what everyone thinks and it would be definitely helpful for my final report due to October.

As for the solution itself (section 4 of the report), you'll notice we've moved the focus of it to a more reliable system, focusing on giving persistence, consistency and delivery guarantees. Over the next months we'll work on having a pub-sub PulsarCast module for IPFS, so stay tuned 😄 I'll try to leave regular feedback here so that everyone that's interested can follow the work accordingly.

Next steps

I've started looking into ways of building a solid test harness for PulsarCast as per #280 and JGAntunes/pulsarcast#26. This is probably what I'll be looking at for the next two weeks. Let me know if you have/know something that might help 😄

Help

Besides the report feedback and the test harness I'll be on the lookout for more recent relevant work in the pub-sub field, so if you have knowledge of papers or research that might help me, please, send it my way 🙌

And that's it! See you in a few weeks 👋

@vyzo
Copy link

@vyzo vyzo commented Feb 16, 2018

@JGAntunes you may be interested in this: https://github.com/vyzo/gerbil-simsub
This is gossipsub, the next iteration in libp2p pubsub implementation; this is work in progress, and the Go implementation should be complete before you start your protocol implementation (per your report schedule), so you may want to take it into account.

@daviddias daviddias changed the title P2P PubSub M.Sc Thesis PulsarCast M.Sc Thesis - Scaling libp2p PubSub Feb 19, 2018
@daviddias daviddias added the pubsub label Feb 20, 2018
@JGAntunes
Copy link
Member Author

@JGAntunes JGAntunes commented Feb 26, 2018

Hey @vyzo! Really sorry for the late reply. Thanks for pointing that out, gossipsub looks quite interesting. I'll make sure to give it a thorough look the next couple of days. Btw, would love to know a bit more about libp2p/research-pubsub#17 (I assume this is a different proposal from gossipsub right?), has there been any implementation of it already?

@diasdavid has pointed out a number of times that I should speak with you, since you've been doing quite an awesome work on the pub-sub front of libp2p and ipfs 😄. So, any feedback on the solution itself, or relevant literature on pub-sub systems that could help me out (or even any generic advice to be honest 😄) would be very much appreciated.

Thank you very much once again!

@vyzo
Copy link

@vyzo vyzo commented Feb 26, 2018

Hi @JGAntunes !

The Go gossipsub implementation is progressing, there is an open pr now: libp2p/go-libp2p-pubsub#67

The libp2p/research-pubsub#17 proposal is more of an endgame proposal, with the epidemic optimizations we would like to implement on top of gossipsub (with the next iteration, tentatively dubbed episub). Epidemic optimizations don't work well when you have many or random sources, so it's a more specialized protocol. Gossipsub is designed to be a general purpose, scalable protocol with good robustness and latency properties.

If I may offer some advice, I would point you to focus on the reliability/persistence part of pubsub, and not so much into building the overlay. gossipsub is a lot more scalable than floodsub, and it should serve you well as an overlay basis.

We can also arrange a call if you woud like to discuss.

@JGAntunes
Copy link
Member Author

@JGAntunes JGAntunes commented Mar 2, 2018

Thanks for the overview @vyzo, would love to schedule a quick call to discuss this if you have time. Tomorrow my availability won't be that much, but after that almost any day will suit me. Feel free to reach me out via e-mail to me(at)jgantunes.com so we can arrange something 👍

@JGAntunes
Copy link
Member Author

@JGAntunes JGAntunes commented Aug 6, 2018

Greetings everyone!

I know I've been lacking a proper update for a while. So, to everyone following the work happening here, I hope these next few lines make up for my lack of feedback over the past couple of months 🙏

What's new

I've setup a test harness using containernet. It's in a very early stage but it works for my needs right now, as it allows me to run any kind of docker image, including my custom JS-IPFS and IPFS images. Hopefully in a near future I'll have some time to document, modularise and publish all of this in NPM accordingly, as I think it might be useful to more people 😄 meanwhile feel free to drop in any feedback you might have. I must confess I'll probably won't have much time to address it but I promise you won't be left without an answer 👍

More importantly, work as started on the actual javascript implementation of Pulsarcast. Again, it's a WIP and so far it has been just coding the spec. Has always, feel free to drop in and leave some feedback 🙌 I know it's a bit shy on documentation for now 🙈, but I promise to work on that SOON™.

Next steps

The focus right now is to Javascript the hell out of js-pulsarcast! 🙌 Once that is done (or mostly done, since "Javascripts" are never done), some adjustments will need to happen to reduce the memory footprint of our test-harness, as we're hopping to be able to spin up a few hundred IPFS nodes to be able to get some meaningful data.

And that's it, hopefully this time it won't be too long before I drop some lines here 🙈

@JGAntunes
Copy link
Member Author

@JGAntunes JGAntunes commented Dec 4, 2018

Hey everyone 👋

Work hasn't stop in JS Pulsarcast implementation, meanwhile we hit a point where we're successfully sending RPCs across nodes, with successful publish and subscribe and event dissemination 🙌 all using the Kademlia DHT beneath. Here's a gif illustrating the procedure with 2 nodes. The integration of the module with js-ipfs isn't perfect still but I think you can get the picture.

peek 2018-11-14 00-49 1

Meanwhile we're now facing some challenges around persisting the events. Currently these use the IPLD dag-cbor format and we're storing them in the DHT which, afaik, behind the scenes only stores these in memory (however it seems to be possible to use other data storage mechanisms(?)). This is fine for searching and retrieving specific events, however, seems to me I'll be incapable of performing any IPLD kind resolution to these objects since these aren't actually stored using the IPFS IPLD instance (and consequently don't use IPFS' block service), am I correct? By looking at the code seems like it isn't common practice for libp2p modules to access properties of the IPFS instance such as IPLD. Is there any suggested approach for this? CC @daviddias maybe you can shed some light on this, or point me in the right direction :)

@daviddias
Copy link
Member

@daviddias daviddias commented Dec 4, 2018

@jacobheun, @vasco-santos, @jhiesey wanna check in with @JGAntunes on this topic?

@vasco-santos
Copy link
Member

@vasco-santos vasco-santos commented Dec 5, 2018

Hey @JGAntunes

Your work seems really exciting 😀I will check it deeper in the following days.

Meanwhile we're now facing some challenges around persisting the events. Currently these use the IPLD dag-cbor format and we're storing them in the DHT which, afaik, behind the scenes only stores these in memory (however it seems to be possible to use other data storage mechanisms(?))

We recently added support for the datastore in js-libp2p-kad-dht using js-libp2p libp2p/js-libp2p#270. This way, we can now store the DHT data in a datasore (if no datastore is provided, we store in a MemoryDatastore).

however, seems to me I'll be incapable of performing any IPLD kind resolution to these objects since these aren't actually stored using the IPFS IPLD instance (and consequently don't use IPFS' block service), am I correct?

Yes, the DHT values are stored in the provided datastore (or memory) and not in the blockstore.

By looking at the code seems like it isn't common practice for libp2p modules to access properties of the IPFS instance such as IPLD. Is there any suggested approach for this?

libp2p should be completelly independent of ipfs, and consequently do not depend on it (only the other way).

I think there were some discussions regarding IPLD resolution in the libp2p, but I am familiar on how we should target it. Do you have any context on this @jacobheun

@jacobheun
Copy link

@jacobheun jacobheun commented Dec 11, 2018

By looking at the code seems like it isn't common practice for libp2p modules to access properties of the IPFS instance such as IPLD. Is there any suggested approach for this?

@JGAntunes that's correct, it's currently not common practice as libp2p is meant to be used separately from IPFS so we're trying to avoid tightly coupling those two. It sounds like you want to potentially pass in the ipfs instance to the pulsar cast module, correct? You can create a custom libp2p in the js-ipfs creation https://github.com/ipfs/js-ipfs/blob/v0.34.0-pre.0/examples/custom-libp2p/index.js. If you need to customize what's sent to pulsarcast that could be an option. If you have more details on what you're looking to do we can see if there's a better option or a potential update we can make to libp2p to better support that kind of injection.

The only ipfs specific modules libp2p has right now use the ipfs http client to query existing ipfs node apis.

@JGAntunes
Copy link
Member Author

@JGAntunes JGAntunes commented Dec 12, 2018

Thanks for the overview @vasco-santos and @jacobheun. So what I was really looking for is just a way to access the IPLD instance (and have IPLD resolution) in a libp2pmodule (pulsarcast in this specific case). I could just pass it to the module when I'm instantiating it, but wanted to make sure if there was any approach you would recommend (or if I could/should avoid this).

Again, thank you for taking the time to help me out 🙏

@jacobheun
Copy link

@jacobheun jacobheun commented Dec 12, 2018

Yeah, passing it into the module is the way to go for now. Looking forward to seeing it in action! :)

@JGAntunes
Copy link
Member Author

@JGAntunes JGAntunes commented Dec 27, 2018

Hello again @jacobheun @vasco-santos @daviddias 👋

Sorry to be a pain but a couple more questions popped my mind while I was working on this. I was hoping you could help me out, or at least provide me with some pointers if I'm heading the right direction.

After your comments I was considering not using the IPLD instance and rely on the Kademlia DHT only. However I'm at a crossroad right now. pulsarcast relies heavily on Kademlia lookup operations to build its dissemination trees, specifically I'm relying on its k-bucket implementation to get the closest peer to a specific key locally (without running any queries). The pubsub events I'm creating are valid IPLD nodes with links to other events and topics which then I'm storing in dag-cbor in the DHT (same goes for topics). With that said, I'll frequently need to resolve events to its parents, topics, etc. which would make IPLD resolution quite handy. If I were to use IPLD to store and retrieve objects I would need it to store some kind of information of the object in the DHT that I could use later on directly (and query the routing table based on it).

Looking into how IPLD uses the DHT, seems like the block service uses bitswap which then uses provide and this consequently calls the DHT provide. From what I looked into, seems to me that what the provide mechanism essentially does is storing a special key based on the value of what we want to provide and the provider id(?). Faced with this I'm not really sure I would be able to reconstruct such key in order to query the routing table (and build our dissemination tree).

So, I guess what I'm asking is, are these assumptions around the block service usage of the DHT correct? If so, I guess there couldn't be a way that my usage of the DHT to build the dissemination tree could fit together with using IPLD? Finally, this is just me wondering, any particular reason why IPLD is bound to the block service? Is this by design? Just because it feels like the resolution mechanisms around DAG Nodes could easily be separate from the way these same nodes are fetched.

For now I'm considering just using the DHT directly and build a simple resolution mechanism on top but I wanted to run this by you and get your opinion first, as I might be missing something.

Again, thank you very much for your help! 👍

@daviddias
Copy link
Member

@daviddias daviddias commented May 20, 2019

Hi @JGAntunes! Following up on your questions here.

Today, IPLD (aka the way the way that IPFS thinks about Graph Linked Data) only sees the DHT, Block Service and Bitswap as ways to get blocks back. A Block is a Graph Node serialized.

So when you do dag.get(someCid) to get a Graph node, if you don't happen to have the node, it will use the connections available and the DHT to find it.

When you publish that Graph Node through PubSub, PubSub will redistribute it through the interested peers, however, it will not store that Graph Node directly, the PubSub communications do not have any awareness of IPLD (yet), they just treat a message content as data to deliver.

@JGAntunes
Copy link
Member Author

@JGAntunes JGAntunes commented May 28, 2019

Thanks @daviddias. Yeah, eventually I concluded that this was expected behaviour and as so currently pulsarcast only depends on libp2p and consequently on the DHT to publish and store events, I opted for leaving IPLD as a dependency out of the equation (at least for now).

As for the IPLD like resolution planned for pulsarcast I might just create built-in methods to do this internally, still have to look into it.

@daviddias
Copy link
Member

@daviddias daviddias commented Mar 30, 2020

For everyone following this thread, check out:

@JGAntunes please present this at an IPFS Community Call (sent you an email! //cc @alanshaw) :D

@JGAntunes
Copy link
Member Author

@JGAntunes JGAntunes commented Mar 31, 2020

Thanks @daviddias 😄

I know it has been a while since I shared updates here but I'm now running through the final reviews of my M.Sc. thesis and hopefully will be presenting it soon 🤞 still don't know much details around it, given the current situation we're living, but I'll keep everyone posted in case there's anyone interested in attending 😅

Meanwhile feel free to check the projects @daviddias linked, those are the core of the work I've done 🙏

As for the presentation, let's do it! 👍

@momack2
Copy link
Contributor

@momack2 momack2 commented Apr 1, 2020

@daviddias
Copy link
Member

@daviddias daviddias commented Jun 23, 2020

@JGAntunes huge congratulations for delivering your M.Sc and graduating with flying colours!!! 👏🏽👏🏽👏🏽👏🏽👏🏽

Looking forward to the public edition of the presentation at PL Research Talks and to share it with the whole IPFS & libp2p communities!!

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
9 participants
You can’t perform that action at this time.