SBTB 2023: Ryan Wright, Streaming Graph Search with Quine.

SBTB 2023: Ryan Wright, Streaming Graph Search with Quine.

Recording: SBTB 2023: Ryan Wright, Streaming Graph Search with Quine.

[Music] nice to see everybody my name is Ryan Wright as Mary said I work at that dot um in 2014 I created uh the open source Library Quin and that's the subject of today's topic uh today's conversation about coin.io and especially using it for streaming Graph Search um so before we get started I feel like I should call out the elephant uh who's not in the room uh this is not a talk on llms um but maybe even a little bit more to the point this is a talk on not llms um because if you want to understand a complex new technology one of the best things you can do is understand its limitations and what it can't do and there's a lot of good research coming out right now about uh what llms can't do especially around graph related tasks um if you look a little closer there's some interesting hacks you might try to uh really shoehorn in some graph problems uh on your on your llm um but in truth we're learning that while these things can generate text and amazingly they're really not very good at reasoning and definitely not very good at graph-based reasoning so all the graph challenges that we've had before still remain highly relevant for uh for modern data pipelines still in the world of llms um those use cases run in so many different directions that we could probably do a whole talk on just things that we can do uh with streaming graphs um but in particular uh they fit nicely into pipelines for the sake of feature extraction to train other ml models to do complex event processing to find patterns on streams coming in do working on recommendation systems so that you can uh propose you know a related content related to something a user is looking at uh implementing different algorithms we'll hint on or talk about this in a little bit but uh incredibly powerful algorithms become very simple to apply uh when you take this streaming graph perspective entity resolution you want to combine multiple things because there's really supposed to represent one item uh and uh even on The Cutting Edge our team at that do has been working on new kinds of anomaly detection especially for categorical data that is enabled by streaming graphs under the hood so use cases just kind of run in every direction we'll look at a couple of them here um but really is if we step back for a moment and talk about streaming stream processing streaming data and graphs we can think about this in two different ways a lot of times streams and graphs they go together really nicely uh but they they're thought of as like the graph is kind of the railroad track that the data follows so if you're building a streaming data pipeline you're probably going to build some form of a graph probably a directed a cyclic graph so that your data can flow from its source through through all of your microservices to get to its end result um that's an example of the stream as the graph you know following the data follows the tracks and gets through to the other end um but another view of a graph in a data stream is really the data itself represents things we want to connect together the data itself is the graph and that's really what I want to start focusing on here right now um and then if there's time we'll flip this around and look in the other direction there's a common conception that graph data is a special kind of data some data is some data isn't graph data that's not true actually all data is graph data and when you take something like a Json object out of your data stream and you think about what that is supposed to represent it starts very naturally turning into a graph so in this case this first example is uh looking at a cybercity related task so what's happening on a machine what's happening on a computer well we've got a process it has an ID 3689 it is writing to a randomly named file uh in the root directory at a certain time so we can represent those things that we care about in a graph nodes and edges that lets us uh describe what this event is referring to we've got a node to represent process 3689 we've got a node to to represent the event in green that there was a right at a certain time and then there's a node to represent that random name file down at the bottom next event streams in through your pipeline all right it's related same process ID read event to the same file update the graph and we keep going same process ID now we've got a network event that process is sending data out the network so we create a node to represent the IP address in this case this is the local IP address that's bound to and uh include the time stamp on the event and we're building a graph out of the stream itself when we do that um it starts opening up the world of graph analysis and a whole lot of insight that we can gain for what's happening uh in the Stream because we're able to connect the dots and look at something Beyond just one event at a time we could even fold in a second kind of stream into this so here's a here's Network flow data maybe coming from a router or some some other component in the network saying I witness some kind of traffic from one IP address to another IP address great let's put that in the graph too we've kept a piece of what we had before but now let's have a node to represent uh HTTP Network traffic and then connect it to the external IP address that it was connected to that lets us start reasoning on a graph uh a graph built from the stream we can say something about process ID uh 3689 having this communication with an external IP address now because we've been able to take several events from the stream represent them in their graph and reason over that graph so now the real dream is to keep is to do that uh at large scale and get tools that make it really easy to express what you want and query what you want so I'm going to show you an example of uh using actually this Cipher query to analyze a stream uh that is built into a graph Cipher is a graph query language created by neo4j uh it's somewhat ubiquitous in the graph world and it's very squish so it's quite similar to SQL with the exception of that first match Clause so that match Clause think of that as asky art we're drawing a picture of a graph the things in parenthesis are trying to draw a little node and then the dashes and greater than less than signs are drawing arrows to connect them that's the pattern we're looking for and then we're adding some constraints down below it every time we find that sort of a pattern uh we're going to to trigger a certain kind of event so instead of uh trying to help imagine what this looks like I want to just show it sobody drop out of slides and over here I have a console which guaranteed will be hard to read but we don't need to do much of that uh this is the open source website so coin.io where you can go download and do uh literally exactly everything I'm doing here because I'm going to run Java djar I'm going to give it the Quin jar downloaded from the website I'm going to say dasr for recipe and I'm going to run the AP example so this is a recipe over on the right hand side you don't have to read this I just want you to know that it exists on coin.io a recipe built for doing exactly everything that I'll show you here let's go ahead and start this and run it that starts up Quin starts consuming from two different sources of data um so we've got our uh our Network Source we've got our uh local Event Source and over here on the here I'm going to shrink this down a little and I'm over here let's explore a little bit so we've got data that looks like what we were talking about we've got some network data there we've got some process data here uh by the way this is all synthetic data but it is based on a true story Quin grew up uh in its early days funded on a DARPA program aimed at some very hard cyber secur problems so it was created out of necessity to do this kind of analysis and others at scale uh when there're no other tools could really keep up so these kind of examples that we're looking at here we've got Network traffic uh we've got a process that had a read event to some file we can explore around and see what else is in in this data so there are other events here on this file there's other events connected to that process uh each of these is built out of incoming Json streams you don't have to understand this at this point I just wanted to show you that each of those streams is building something uh it's building into a big graph behind the scenes and I don't know if you caught it or not but over here on the left hand side we had a message printed out uh that message uh we're software people here we can assume that printing something to the console is sufficient to demonstrate realtime actions uh taking place this could be a slack message this could be an alert to another system but in this case it is the result of that Cipher query that I showed you earlier finding a complex pattern built up in the graph uh as it streams in in real time let me show you what that looks like so this is a link to all the relevant data that was a part of finding the pattern I'm going to arrange it a little bit so it's a little easier to see and understand this is what that Cipher query was looking for this is a process uh in this case Excel an Excel process that wrote to a temp file that file was later read and deleted by another process this process is named ENT CLE that process sent data out the network what we wanted to find in that uh graph that's built from the stream is suspicious activity where two process processes communicate through some secret back Channel and so in this case writing to a file reading and deleting from another process that is a very suspicious activity and it's very difficult to find because it's spread out in time uh these can come from different data sources that have to be merged together you have to hold on to the pieces as you go and if we want to we can even Explore around to understand the story a little bit better so this was a malicious spreadsheet that was uh emailed to the user they opened the malicious spreadsheet that caused it to read some of the users docs in their their private plans document as that data gets written into the temp the miscellaneous dotdata file it's started it's read and deleted by this n CLE process where did that come from well this process was started by an SSH process uh that SSH process itself get rid of that spawn one that SSH process receive data on a local network interface Port 22 uh that here let's collapse some of these things the other side of that communication here was an inbound connection from this IP address which also if we explore over here happens to be the same IP address that it sent data out to so the full story here is that this advanced persistent threat got into the system and then just sat quietly waiting and then when the email comes in for a spear fishing attack user opens it thinking nothing of it that causes it to grab some data covertly write it somewhere picked up by the AP deleted covered their tracks got the data out the door uh and all of this uh was spread out in time through streams through several different streams that have to be joined together to actually see the picture and tell the whole story so this is an example of searching the graph for that key underlying pattern that led us find this and then when we want to we can poke around and understand it a little bit better through exploration so why is this so hard to do uh as I mentioned we created this um over the last nine years now um out of necessity because we had to there weren't really good tools for doing this especially at scale and the reason is because if you try to do this you try to take a stream of data you try to assemble it together so that you've got the thing you're looking for coming out the other side you're you have to start with a stream and take one item out of the stream that's not what you're looking for so you've got to store it somewhere put it in a queue of unmatched events so you take your A's put them here your B's here your C's here store them locally um so that you can have them ready for the next event that comes through maybe the next event will match if it matches one of those ones that you're storing great now you've got new cues for those partial results so save your ab pairs here your BC pairs over there keep caches of those things on hand so that maybe you can join them to the third piece and you can put all these things together so meanwhile you're accumulating lots of state that you've got to manage for all these partial results that you're building and the typical approach is to to do this probably in Ram uh to hold these cues in memory and accept the fact that you've got limited memory so we'll just have a Time window we'll hold the last five minutes worth of data for example anything that's older than that well we'll just expire it out of the cach and throw it away the downside to this is that you'll lose results if your matches spread out further than your time window you'll never see those results and so lost results are often unex acceptible especially for that finding a needle in the hstack kind of a situation so okay well we can do something else too we could set up durable cues we could write them to disk key value stores are good at this we can take that data shove it into key value Stores um and then hold on to them for a longer period of time well now our problem is that the architecture of the system implemented in these key value stores is uh tightly coupled to the pattern that you want to find a product manager comes along and says I want to tweak this a little bit I want to change that you know well that's going to take 9 to 12 months we'll have to redesign the whole system in order to do that so this is the the underlying problem that has been dragging down our ability to take a stream of data put it together in a graph and search that graph is that either we accept uh loss data from time windowing or we spread out our patterns across the entire architecture this is what Quin is meant to solve so give that graph abstraction over the stream because it's the most expressive data abstraction eliminate time windows so we don't miss any results allow combinations of events anywhere in the graph over huge periods of time and allow us to update what we're looking for very easily without having to reconfigure the whole architecture that's why we made Quin so under the hood real quick how how it works and I don't have enough time to go into detail but I just wanted to mention mention um under the hood the graph itself can model anything but it's under the hood it has a graph computational model paired with it as well nodes in the graph are backed by actors asynchronous message passing is how queries are done how updates are done all of those pieces of the puzzle that happen behind the scenes uh are implemented uh uh with aa aa actors lots more to say about that but in order to distribute this uh we cut the edges nodes in the graph can get distributed across any number of machines in a cluster and uh we do so by cutting the edges as you see one Edge is really made up of two half edges and the edges are stored together with the nodes in Quin there's this fundamental design principle that uh is pretty essential for streaming data um but it inverts the database assumption so instead of saying it starts empty and we fill it up with data if you've got an infinite stream of data that's going to be problematic sooner or later in Quin all nodes exist we start with the assumption that every node that ever could exist does exist and what we're doing when we ingest data is we're doing what physicists call symmetry breaking we're creating some structure in the graph that is useful for representing what we want to represent um turns out all those extra nodes have no impact on the system we can Factor out a lot this is a conceptual design and it really it inverts a lot of typical assumptions that allows us to gain some big efficiencies on the backend behind the scenes all those real-time notifications were done with standing queries this is a query that just like you write a query you issue it you get a result back you can take that same query issue it to Quin it'll stay live and active and move itself push itself through the graph storing partial results along the way and when there's a new match that new match gets completed you get notified immediately so uh that's a bit about how coin Works under the hood and I want to come back to this slide from earlier um so as we're talking about you know the data is the graph building that building that graph out of our streaming data events um I want to I want to come back around and say when we when we have this perspective we've got this graph built out of streaming events those events and that graph that we've built can become the new railroad tracks the new stream itself and I want to show you an example of this in a second uh quick demo I'm going to [Music] run another recipe this recipe is an the ethereum tag propagation recipe it's also available on coin.io so if you'd like you can run this yourself um what this does is this connects to the live blockchain so we're going to test and see how good conference Wi-Fi really is today this connects to the live blockchain pulls in whatever ethereum transactions are happening right now uh while I'm speaking forms them into a graph so that we can then use them as the track on which to run events down so let's take a look let's grab a few notes here all right we've got a couple blocks these are ethereum blocks from the blockchain whatever is happening right now um live demos are always fun because who knows what's there three blocks we've formed a blockchain that's great every block is mined by a particular account now we take a second stream uh that isn't just the blocks but a second stream of transactions fold those things together uh and connect them together in the graph this is a few more transactions than we'd like to look at at the moment so what I'm going to do is undo that step back and limit to just three all right so we've got interesting this was a transaction that included the account that mined it but if we look at a transaction you can see it goes from one account into another account and this is what the structure of blockchain data looks like looking at mousing over any transaction we can see some of the details there we're not going to go into uh any depth on those um but everything that is happening now and is about the transactions happening on the blockchain gets represented here in the graph so it becomes available to us to to use for our other purposes those other purposes are I want to run a graph algorithm that lets me follow the money if there's some nefarious actor in here that I'm suspicious of I I want to know where does their money go maybe they're laundering it through the blockchain it spre spreads out to lots of accounts comes back together um maybe maybe I'm just curious who else they're associated with and so I want to understand what's happening there well let me find an account that has an interesting structure and again this is live data so I never really know what we're going to find um but here is two account or two transactions I'm going to take the one that's earliest in the chain and I'm going to right click it and just say mark this is Tainted this is just going to set a property on that particular node um but I left the console up because hopefully we'll see some notifications here as soon as we mark this is Tainted all right we saw quite a few I don't even know how many that was what just happened is a standing query behind the scenes that is watch watching for any tainted account uh and if it's tainted and there's a trac a transaction into some other account then go Mark that other account as tainted and record how far away it is from the original so what that does is it lets us if I can choose the right things here so the pink one is the one we marked as tainted you can see now it has this little popup property that say tainted equals zero and every outgoing transaction in this case only the next one also gets marked as tainted shows up in red now uh that's one hop away from the original account tainted equals one go further these are all the transactions coming out of there all of these are marked as tainted as well and as money moves through the blockchain uh if there are any more we'll see them and they'll show up here as it happens live you'll see more notifications coming out in the console cons about money moving through the blockchain and we're following that move through the graph so in this case we set a standing query to cause events to search the graph and watch for anything that is newly uh tainted account making a new transaction to any other account when that happens go trigger an algorithm propagation so update the the tainted tag keep track of how far away it is from the original this is an example of kind of using the data itself as the path as the stream on which uh we're uh we're doing our processing so here again these are just a couple examples um and uh there are plenty plenty more but I want to give a quick illustration of when you can actually do search on a graph built from streaming data you can get real-time notifications and propagate uh algorithms and other complex kinds of events so so these uh examples were all running on my laptop that's all well and good but you know they're small enough scale that I can you know reliably do this for a demonstration here um but just to help give a little color the team at that dot um Works uh with commercial Partners to help scale this to huge uh scales and so this is the result of uh a Blog um some testing that we did published in a blog post recently um uh where we're scaling up to a million events per second so that's a million events coming into the graph every second building up a very large graph very quickly um also with a standing query on that graph that is watching for a four node pattern so a patterns in the graph that show up occasionally built out of four different nodes and this is finding those inst streaming results out at about 21,000 events every second so a million events in build the graph monitor the graph for this particular pattern stream those results out um at 21,000 events per second while doing that uh all the numbers you see on the chart and down below are uh what happens the green line is throughput by the way so it's it's how many events are being ingested all the numbered events are what happens as we're pulling power cables uh partitioning the network and doing all the other kinds of reliability and uh and failure scenarios that you need to test and prove out for building highs scale clustered systems so um there's short links on a bunch of these slides that links to a blog post that goes into technical depth um uh I believe all that was done for something like 20 some dollars an hour uh worth of infrastructure so um if you'd like to know more I point you to the blog post um these are some of the reasons why last year when we open sourced this project uh it was voted the best open source project of the Year big thank you to the community of users um uh for their feedback and their input um we'd love to have uh have folks check it out uh give it a look see if it's useful in your project if you'd like here's a bunch of links that can help you do that uh coin.io is the website it is free and open source go download it play with it uh if it's useful let us know there's a slack channel in there as well um if you find it on GitHub and want to make contributions that would be awesome uh add stars there if you feel so kind and then there's a collection of links over on the right hand side where you can see everything we're doing with that um I think we have a couple minutes for questions uh and thank you very [Applause] much hello okay anyway you can hear me oh good thank you so thank you Ryan that's really engaging I'm I almost actually forgot to check the time too it's kind of really good so thank you and so now we have a couple more minutes before the next session so we can um you know have Ryan answer a few questions um does anyone have would like you know you have any questions here okay yeah Ryan thanks very much it's uh really impressive uh the uh question I have it's scaling this right uh in this case you show the scale of certain patterns but uh it's like anomal detection uh there are new patterns is coming in all the time right uh can you describe how you want to scale on uh the number of patterns not just kind of uh the data with the single uh pattern a single set of patterns yeah great question so uh from our perspective that uh scaling the number of patterns that you're looking for in a graph is uh a me a measure of how many standing queries are you running Uh current like concurrently while data is streaming in to build the graph and everything else um we've tested up around 100 uh standing queries um uh I don't know exactly where the limit is um part of the challenge of working with graph data is it often depends on the data itself and the use case um and so uh so depending on some of that uh your mileage may vary or your experience you know could be higher or lower than that particular number um but just so we've got at least some number to pin to the wall and help anchor some intuitions uh We've tested up to about 100 uh standing queries concurrently running great thank you any okay thank you I understand that that this uh this is a basically a database right you you're persisting all the events that that go through through the graph um can it be um the data base of reference uh can I query the database query your your uh your graph not with um cql but with regular SQL just just to just so I don't have to sort of duplicate the same data elsewhere in the relational database can can you handle that or is there a thought of handling that yeah great question uh you can um we we know of a bunch of users who do uh have that use case uh I didn't mention during the slides but the way the assistance works is it swappable on the back end so Quin uh Quin stores data um it can store data locally on the same machine even just in the same process uh or for large deployments we tend to uh store using Cassandra astrab uh sadb um you know those kind of tools on the back end uh for data storage behind the scenes um and so the durability characteristics of those systems is what Quin inherits and it's meant to it's meant to work in that swappable sort of fashion so depending on the use case you can choose if you want your data locally or you know saved in a a Cassandra cluster on the network for instance um but all that for uh if you want Quin to be the database of record for this yes you can anyone else have questions um you mentioned $20 um per hour something infrastructure Cost U can you break it down what is it exactly um yeah the scale experiments that we've done and the cost to scale it I don't actually remember all the details off the top of my head um but the uh the link near the bottom right corner that links to scale uh will take you to a blog post that goes in- depth for the architecture the implementation all of that um uh the cost for different configurations uh that sort of thing but it was maybe $26 an hour is what I was what I seem to be remembering but I want to point you to that blog post for details okay anyone else have questions no yeah no actually I have a question too so for ingestion right so can you actually work with like Kafka for example Kafka stream in Pulsar like that to for ingestion site yeah to injust data you define an injust query that connects to streaming sources so Kafka Kinesis Pulsar um all the typical streaming components um configure it to go read data out of those uh sources and a an inest query that takes like we looked at earlier that takes each record out of that Source builds it into a small little component in the graph and folds it together with everything else in the graph very cool thank you and the same is true by the way for uh all the the results here we were taking standing query results and just printing them to the console um but those can also be published to any of these streaming sources or published to slack and some other things like that so that Downstream events can take the results and do something else with them cool all right thank you very much thank [Music] you