Scale By The Bay 2019: Rashmi Shamprasad & Ajit Koti, Finding Needles In Big Data Haystacks....
Rashmi Shamprasad I'm Rashmi Shamprasad, and joining me today is Ajit Koti. We are part of the data science and engineering team at Netflix and are here today to talk to you about finding needles in big data haystacks using finite state machine. Now, that title definitely sounds like a mouthful, so we're hoping to break it down during the course of the presentation and walk through it. So one of the areas that our team works on is around optimizing the signup flow for Netflix. So I'm going to start with an example from there. So let's say a user wanted to sign up for Netflix. They would typically start by landing on the home page. And here we give the user an option to kickstart the signup flow by clicking on the red button that you see on the screen
Now, this leads them through a sequence of steps, which involves selecting a plan, registering for some credentials with which they can log in later, and providing us with a method of payment before they can finish signing up. Now, this sequence of five steps is the path of least friction with which somebody could sign up for Netflix. But occasionally, we see that people might take a much longer path to get to the same point. And this might be because they changed their mind about which plan they wanted to have, or what method of payment they wanted to use to sign up for Netflix. Or even go back and forth between these options, essentially being stuck in a loop before they finish signing up. The worst case scenario is if somebody drops off in the signup flow midway. And so this is sort of a lose-lose situation, because Netflix loses on acquiring a new customer. And basically, the potential customer misses out on all the awesome content that we have
So we're hoping that doesn't happen too often. But for anybody who looks at this entire signup flow, even though if it's composed of five steps, in reality, the number of permutations that can be happening out there can be fairly large. And so this looks like a typical funnel for folks who are from the data space and who can relate better to it. looks like a funnel, but what we are trying to do is go a little bit farther and identify which are the steps in the funnel that are causing the most amount of friction. So this is one of the needles that we are trying to find in our data haystacks. Let me go through another example, this time for somebody who's already a member at Netflix. So they've been already watching a whole lot of content. And let's say they play Stranger Things, which is one of our titles
So one of the questions that we might be interested in asking is how did the user get here? Did they specifically search for Stranger Things and then decide to play the title? Or were they already watching the title midway, and they left off, and they were just picking up where they had left off? And so if you see the question in this scenario is very different, where we are aware of what the destination is, and we are trying to figure out what the origins were. There might be other cases where we are aware of what the origins are, and we are trying to figure out what the destination is. And so in a nutshell, if we had to summarize all of these scenarios and get the essence of them, the way I would like to put them is we have a bunch of milestones, and essentially we are trying to measure paths across these milestones. So all of these different problems could be abstracted out to that one statement. And so some of the challenges that we run into on the way while doing that is having to dig into multiple heterogeneous data sources, which could be spread across files, tables, elastic search indexes, what have you, because of all the data that's being logged by various services all across Netflix. And these logs tend to run terabytes or even petabytes at scale, and we have to dig through all of that to make some sense or gather some useful insights that are actionable. Anybody who's been in the data space long enough probably can relate to this the most. The moment you answer one question, you are immediately handed off another variation of the same question or minor tweaks to the same question, and we want new insights off of that
So this analysis tends to get pretty repetitive, given the fact that we run a large number of A-B tests all throughout the Netflix product. So there's that, and we might be just looking for opportunities in general to optimize the user experience, or for existing product features, we might just be interested in checking on the health of these features. So there are multiple reasons why we might be doing this analysis pretty repetitively, and so that's something we have to deal with all the time. More often than not, these questions are not only coming from engineers, but they're coming from data scientists, data analysts, product managers. And so you could imagine that the skill level of all of these various folks is pretty varied. So if you have to ask them to go and pull these insights yourself, some of them are going to run into a bunch of issues. And so these are all what make up our haystack, and we're trying to essentially tease out the needles from them and work through it. Some of the typical ways in which people have gone about doing this in the past is something as simple as just collecting up all of these milestones into maybe a single string, and then apply some simple wildcard matching
So for example, if on the left hand side what you see is a list of steps that the user went through, we would simply collapse it down into a single string, and then apply like a SQL-like wildcard matching to see if we got a match. So if we wanted to say how many people landed on the homepage and then eventually finish sign up, this would be one way of getting to that number. Now this is a good approach, and it's a pretty simple approach, but it quickly fails the moment you introduce more complex paths or more complex iterations as part of things that you want to seek out. So this doesn't work too well in that case. Also, it's only as good as the string can fit in memory. So if you have, you know, anomalously large number of steps, then that's not going to work too well for this. The other option is going down the path of analytical window functions, and this is something, you know, any data user is typically familiar with. So you could just filter down to the steps that you care about, and then apply functions like lead or lag to figure out what the previous and the next steps were, and this might get you the answers that you need
Again, works well for simple paths, doesn't work too well for more complex scenarios. Our third option could be, why not fit all of this into a graph data model? Seems like a very organic choice for us, for our dataset, given the milestones could feature as the vertices and the paths between these milestones could essentially be the edges. Now, seems like that would be a good fit, but where it starts getting tricky is where you have to maybe load up the adjacency matrix to talk about paths that are repeatedly traversed or some complex iterations or loops that you run into. Again, we would have to make significant investments in tooling or infrastructure that is a better get to handle graph data structures to make querying more efficient, and that is one other thing that users would have to get familiar with and know how to query. So given that none of these options were working out for us, we started talking about if we could put a framework together to meet all of these challenges, right? So in terms of requirements, we wanted to make sure that this framework could allow us to intuitively express these paths that we were looking for and be able to support complex iterations if we wanted to. We obviously wanted to work with multiple data sources, and it should scale really nicely as the volume of data grows. Ultimately, we want to make it easier for all those different types of users that I had talked about before for them to be able to use this. And we also wanted to play well with our existing scheme of tools and infrastructure
So with that in mind, we put together our framework and called it Conduit. And so what Conduit really does is it looks for milestones across essentially what it thinks of as events. So from Conduit's perspective, it's looking for really four pieces of information in an event. One, a name for the event so that it can identify it amongst all of this haystack of data. Two, an identifier so that we could uniquely identify the event. It's okay if your dataset does not organically have one. We could always generate one on the fly. There's the timestamp at which the event occurred
And the fourth thing that we care about is the entities or dimensions that the event has. So from our example, it could be a customer or a visitor or a device that against which we want to measure a path or a flow or figure out how these iterations work. When it came to figuring out, okay, how do we express these paths or flows, it seemed like regular expression notation was a really nice choice in terms of being able to express everything that we wanted to. It already offers us all of the constructs that we need to indicate sequences, alternates, quantifiers, and so regular expressions work really great. The only thing really that we had to do was build a new parser that could handle event names instead of the single character tokens that most regex parsers out of box support. So that's really what we had to build out. But this would be something that no one would have to learn as such, or even if somebody had to, there's plenty of resources out there that can teach you how regular expressions work. So rather than going ahead with our own DSL, we focused on regular expressions
Ultimately, looking through all of this big data, we want to gather some really high-level actionable insights. And so we need some quick ways in which we could summarize data or at least get to quick data points that are useful for summarization. So conduit offers a lot of hooks for that, and I'll get to that in a bit. But that's definitely something that we covered. To deal with the scale of data that we are running into today, which is essentially terabytes or even petabytes, it seemed obvious that we had to do this processing in a distributed fashion way to get results in a timely manner. And so we settled with Spark as our execution engine of choice, and it also happens to be our framework of choice for all our current ETL operations at Netflix. And we wanted to make it easy to use for all of those different users, so we offer conduit in two different flavors, one being a Scala API that you could theoretically just extend within your ETL, and the other option being a YAML-based config file that you could just tweak. So somebody could establish the file once for you, and you could keep making minor tweaks to it to get new insights as and when you wanted them
So these are a few things that we focused on while building our framework. So what I'm going to do is give you guys a really quick tour of what conduit is capable of doing, and for that we're going to use a very simple data set which just has these four pieces of information. We have the visitor navigation data with a timestamp, a GUID to identify the visitor, the country where they visited, and the page that they visited. And for our demo, we are going to be using Jupyter Notebooks running a Scala Spark kernel with Spark 2.3. So let me just quickly switch to the notebook. Sorry. So is everybody able to see this? Okay, cool. So this is our notebook
Really, it starts off by just adding the jar that we have compiled conduit in to the setup, and then we run a bunch of imports that we need for our data set, setting up the Spark session, and setting up our flow analyzer, which is going to analyze the flows that we care about and give us outputs. And I have some UDFs that I've set up just for display purposes, so I'm not going to get into the details of that. So let's start by looking at some examples. So Spark, by virtue of it being Spark, allows you to read a variety of data sources. So this also solved our problem where we had data spread across multiple data sources like tables, files, elastic search indexes, and because Spark is able to read all of that, we didn't have to make any investment in trying to do how would we read all of that data. So in this case, I'm just going to read a CSV file using Spark. And just to make sure that we read the correct file, I'm going to print the schema out, and we see that, okay, this is the same schema that we wanted to run the demo with. And let's look at some sample data to see what the dataset looks like
And so you see that there is a GUID that shows up which represents the visitor, the timestamp when they visited, the country, and the page. And now what we're going to do is basically annotate this dataset just so we can indicate to Conduit what is my event name, what is my timestamp, and given that we don't have an event ID, we'll generate one for this dataset. So we just did that and we cached the dataset. And so this is what the new visit data looks like with the annotations. So we have designated the page to be the event name, and we have generated an event ID now for the same dataset. So we have the dataset ready to go, and now we can just start asking a bunch of questions. So let's say the question that I wanted to ask was, how many people started on the home page, went to plan selection, and then finished sign up? Right? So really what the important piece of information that we want to say here is this is my path that I'm looking at. So we have home page followed by plan selection followed by any event, which is anything could have happened in between, and finish sign up
So what really Conduit is going to do is look for this sequence for across every code. And so every time it detects a new instance of a home page, it's going to detect a new instance of the flow as well. I'll get to the allow incomplete flows in a bit, but let's just set this metadata up, and we are going to feed the metadata and the original dataset into the flow analyzer. And so it identified that it's looking for these particular events in the expression. So if we did not have any wildcard matches to be done in the expression, Conduit is actually smart enough to just filter for the events that you care about, and so it can speed up the processing of the dataset even more. And now we are just going to print the dataset, and we get to know that three users started the flow, and three users finished it. And which means three users started on the home page, went through plan selection, and got all the way to finish sign up. Now there are a few important things that Conduit adds, which are useful generally for analysis
So I'm going to walk you guys through it. So this is the goal for which we analyze the dataset. For every instance of the flow that we were able to identify, we generate a unique flow identifier. So this helps in grouping all of the events that belong to that particular flow. We also add a sequence number in here, so that you know the exact sequence in which Conduit evaluated the events to come to the conclusion that this flow was complete. And then of course you have the event name, which is what we were looking for. And the end of flow indicator is useful for us to be able to indicate which is the event that makes up the end of flow, especially if you have open-ended flows. So let's say in this case I had a closed-ended flow which said, you know, finished sign up is the last step that I wanted to get to
But if you had open-ended flows and you didn't know what your last step was going to be, this helps you in a quick way to get to that last step. So the end of flow indicator would be set to true for the last event in the flow, but not so for the first event. So as you can see here, it's given us the list of steps that somebody went through between home page plan selection and finished sign up. And somebody else could have gone through. So in this, the first user went through eight steps, the second user actually went through just six. So as you can see, it's detected the different flows depending on what the user actually went through. Now, going back to this parameter that we had which says, allow incomplete flows equal to false. If I set this to true, this is particularly useful if you wanted to essentially measure drop-off or conversion rates from like the point of landing
So if I set this and then I reanalyze the data, we might get different results. So we see eight users started the flow, but only three made it all the way to the end. And so this helps you get that conversion rate, if you will, in terms of landings versus actual signups. So you could get to quick insights like that just by even making minor tweaks in the API and getting to the results that you need. And this also helps in cases. So let's see if we have, so in this case, the very first user, they went through home page plan selection, again, home page plan selection, and they went to registration and they logged out. Like they didn't go any further than that. So this would be an example of an incomplete flow
So this user started on the home page, but did not make it all the way through. So this is essentially what you could do. And there are other types of questions that you could ask conduit. So all you had to do was with the same data set, you could simply change the flow expression to match the question that you were asking for. So if you wanted to ask a question, like how many times does somebody visit the home page immediately followed by plan selection? All you had to do was just change the flow expression to say home page followed by plan selection and then say, basically use the regular expression quantifier of one or more. And that would be it. And it would analyze the exact same data. So and get you the results
So this is really the level of configuration that you need to do to get insights like these. If you wanted to make your matching even more stricter, say you wanted to specifically go after people who have run into friction in the signup flow, where they keep going back and forth between home page and plan selection and then move to finish signup, you could set the quantifiers to something like at least two times. And then that would give you matches based on that. So just minor tweaks to the expression, and you could get to the results that you were looking for. Now, when it comes to gathering summary statistics, let's see. So we have the same expression. We have the home page and we have finished signup as our last endpoint. And we want to allow incomplete flows
And we want to gather some summary statistics from here. So using the flow ID as our way to group the data set, we have basically been able to see that for somebody who finishes signup, they take up to eight steps at the most to finish signup. And at the very least, they take up to six steps to finish signup. But in cases where they do not make it all the way through signup, somebody is abandoned at the ninth step. So clearly, like somebody's taken that extra effort to go all the way, but abandoned somehow. So this can give you like those nuggets of information that you're looking for to deep dive and figure out like where could you be making optimizations to your process. This is just, you know, a very small sample of really what you could do with conduit. It has a ton of more features, but in the interest of time, this is how much I can go through
But I would like to have Ajit now to talk through how we build conduit and how all of this magic happens. Thank you, Rashmi. Hello, all. I am Ajit Kodi. I build distributed systems at Netflix. Today I plan to delve more into the design and architecture of conduit. There are plenty of well-known solutions which can parse a regular expression and find patterns in a string in a single processor systems. But there are few known solutions which can parse a string or regular expression and find patterns in a distributed way
Hence, while designing conduit, we kept these as our guiding principles. It should be easy to scale horizontally and find patterns across billions of events. It should be easy to debug and reason why a particular pattern did not match. It should be easy to enhance and add more features. And as a first step, I'd like to define a few building blocks of conduit. The first one is the regular expression. To simply put it, it's just a sequence of characters that define a search pattern. And I think of regular expressions as wild cards and steroids
The next building block is the abstract syntax tree. They are usually the result of a syntax analysis and also they have very less information regarding the real syntax compared to the past trees. Past trees are dense and have lot of information. Abstract syntax trees are also the central data structures that we use throughout. And due to the hierarchical nature, we also refer them as hierarchical syntax trees. The final building block we use is finite state machine. And a finite state machine is an abstract machine that can be in exactly one of the finite number of states at any given point of time. They can also change from one state to another state in response to external inputs
So here's our game plan. So as a first step, we want to parse the regular expression for a given path and construct the syntax tree. So we use Scalar's parser combinator to parse the regular expression and then construct the individual expressions. A parser combinator is just a higher order level function which can accept several parser as its input and return a new parser as its output. And also each parser parses a part of a regular expression. So we use these expression types to construct a syntax tree. Event to represent a token. Concat to join multiple expressions or to match either one of the expressions
A bounded repeat to represent one or more occurrences of a token or an expression. An unbounded repeat to represent zero or more occurrences of a token or an expression. Let's see how we use this construct to build a syntax tree. So let's take a regular expression that we used previously in the demo, which is home page followed by plan selection, followed by any event and then lastly should match finish sign up. So let's take a look at the example of the example of the example of the example of the example of the ! We also recognize that they have a natural hierarchy but they do have and we'll take a look into that in a moment. Note we can also build a RegXP engine without the ASTs but having however the ASTs make it much more simpler. As a first step, let's create the event expression for all the milestones which is home page followed by plan selection and then followed by finish sign up. We also create a repeat expression for any so that we can repeatedly match any given to it
And finally to construct the hierarchical syntax tree, we use the concat expression to join all of the expressions and then create the hierarchical syntax tree. Note that the hierarchical syntax tree we created is not very easy to evaluate. You could attempt but that will complicate the code instead if you could lower the abstractions, you could have, you could build a system which is more easy to understand and reason about and that's what we intend to do in our next step. We just convert the syntax tree into a finite state machine for easier evolution. A finite state machine represents a rejects and linearizes the rejects components into a graph producing A followed by B followed by C pattern and also it is easy to evaluate potential events. So the regular expression search algorithm that we use was originally outlined in Ken Thompson's 1968 paper. Before this, the search algorithms that were used used backtracking which when a partial pattern matched, they had to backtrack and that would lead to lot of storage and bookkeeping inefficiencies. And also executed slowly
So in the regular expression algorithm which is outlined in this paper, we could match multiple possibilities at a single point of time. So we'll soon see how we use some of these techniques outlined here to convert the hierarchical syntax tree we created into a finite state machine. There are two types of finite state machines, non-deterministic finite state machine and deterministic finite state machine. We use non-deterministic finite state machine because we don't know what all states we would have to match. So these are some of the constructs we use to construct the finite state machine. Except which consumes an event, fork which splits a transition into multiple transitions, a bounded repeat represents one or more occurrences of a transition and the unbounded repeat represents zero or more occurrences of a transition. And a matched and unmatched indicate if a pattern matched or did not match. We'll soon see how we use this constructs to build the state machine
We start with an except node which consumes a homepage event and if it matches, then we would transition to the next state which is the plan selection. If the event we get is not homepage, then we would transition to an unmatched state and the pattern matching halts. So let's say if we get after homepage, we get plan selection, then the next node we get, the next event we get is plan selection, then it would match and transition to the next state which is the unbounded repeat. The unbounded repeat has a fork at its one end and the fork has two ends, one which has got an any which can match any given event and the other end has a finished signup except node which can match the finish signup and transition to the matched state. If the event we get after plan selection is not finished signup, then the any except node would match it and would loop it back to the unbounded repeat node. If the event we get after plan selection is finished signup, then it would match and then transition to the matched state and we would have matched a pattern. So next step we will soon see how we evaluate the state machine across events. So if we have this dataset which has got homepage, plan selection, provide payment and finish signup, then we want to evaluate these events and then find the pattern
So we send the homepage event to the homepage except node which would match and transition to the next node which is the plan selection. The next event we get is plan selection, we send it to the plan selection except node which it would match and transition to the next state which is the unbounded repeat node. The next event here we get is provide payment, we send it to the current node which is unbounded repeat node and we send it to the fork and the fork simultaneously send to both any except node and the finish signup node. And in this case the any except node would match it and loop it back to the unbounded repeat node. The last event we get here is the finish signup event. The finish signup event sends it to the current node which is the unbounded repeat node and the unbounded repeat node redirects to the fork and the fork simultaneously sends it to both the any except node and the finish signup node. And in this case, the finish signup accept node would match it and transition to the next state which is the match and we have found a pattern. Let's take another look at another example where instead of plan selection if we received a login and then we send it to the plan select accept node, it would not match and the pattern matching will halt at that point of time
So as the next step let's see how we use the finite state machine to find patterns across billions of events. To scale the pattern matching, sorting horizontally we use Apache spark. So if we use our previous example the data set we used in a previous example we partitioned by GUID and also we sorted the partitions by timestamp or any other sorting criteria that defined by the user. Let's assume if we have a billion GUIDs then we'll have a billion partition and for each of the billion GUID partitions we would spawn a new state machine instance and evaluate the state machine. Note there are not a billion active state machines they're only active as many partitions are getting processed. Since we don't need to get all the events into the memory it's extremely fast and efficient to find patterns. The next step let's look into how FSM gets evaluated in spark. So let's zoom in and take a closer look at a particular task in spark
We would stream the events using using the map partition functionality one at a time and evaluate the state machine. The state machine would return us the next state which is either a valid state, a match state or an unmatched state state. If let's say we have and we have not reached end of the stream and then state and the next state machine we receive we receive from the state machine is a match state to violate the rest of the events we create a new new state machine to evaluate and find more patterns in the data set. Lastly if we have not reached the end of the stream and we have not received a match in in that case the whole flow would be marked or as unmatched. The last bit of optimization I want to talk about is we send the home let's say if we don't have any criteria in your regular expression path then we can do the optimization up front we can filter out any events which are not home page and not finished sign up and then improve the performance of FSM evolution. I've linked out a few papers and blocks which we found very helpful. I'd like to open up for any questions you may have. Also we are hiring if you are interested reach out to us
Thank you. Good question. Is time an important element of the analysis for your graph analysis here or is time you know the time aspect of moving between states not important? If it is important how would you represent that? So time is definitely one of the things that we consider for even just ordering the events so that they can be fed into the state machine. Sure. So to that extent it's important but we don't put any line boundaries within the state machine evaluation. With relation to previous online experiments. Right. We think of that to be a post processing operation
Right. Thank you. I think using the state machine trying to better is a fascinating idea but I'm just curious how complex journey do you guys have been experiencing fitting into this use case and then what if there's any other limitation because for example there are some journeys more extremely complicated than it is right? Yeah. So like yeah we have at least in our test we have tested more complicated with multiple repeats and multiple loops and repeats and stuff like that so we could handle it but I think if you have a large data set and then you have like super complex repeats and tools then the time will be more time required to process and stuff like that and more resources as we said that you don't have to hold a lot of stable memory and stuff like that so it's a 16 edition. Thank you. don't have to bring in all the events which we have to match into the memory so it still works out fine but it's just you can pull it slower than you typically want to do. If there's any other questions offline, thank you very much you've been in here. Thank you.