Scaling to Billions of Real-time Recomme...

scale.bythebay.io: Ajeet Grewal, Scaling to Billions of Real-time Recommendations Daily

Recording: scale.bythebay.io: Ajeet Grewal, Scaling to Billions of Real-time Recommendations Daily

you hey thank you guys for coming to talk and thank you for organizing this and inviting inviting me over here I'm a quick introduction my name is Ajith I am a manager on the recommendations team at Twitter we are a group of engineers and data scientists who are bobbing like a few different parts of the product if you guys have worked or if you get few guys used Twitter there's a there's who follow modules and there's there's very various different components on Twitter that are powered by this by this team today I'm gonna give you like a bit of an inside look into some of the components that we have that power many of the many of these systems so at a high level we'll do an overview of the different recommendation systems that we have in the first part the second part is going to talk about account recommendations and in the last part I will talk about the challenges associated with serving some of these recommendations in real time all right so recommendations why do we need recommendations at Twitter we want we want to enable our users to stay informed about the world and the recommendations plays a key role in here because there's just way too much information on the platform and the system and Twitter needs to do a lot of the heavy lifting to surface the content that the user is interested in so that they are finding relevant conversations or relevant people that they would be interested in hearing about and that's the job of recommendations we try to build some of these infrastructures that power/power these systems so what are the different surface areas that we that we work on this is the notifications tab so since twitter is inherently real time we notifications are a key part of keeping users informed about something that's happy on the platform and the this screen shows the notifications tab where you see a few recommendations that have been pushed to users another area that we work on is emails email recommendations which you see one of the type of emails here which is called highlights these are targeted to maybe a different set of users and they have slightly different goals we'll get into that in a little bit we talked about people recommendations and people recommendations so on on Twitter you follow an account and you get content into your home timeline and therefore we want users to follow high quality accounts that we think that they're interested in and therefore we want to build like a good user recommendation or account recommendation system and finally this is this is our explore tab which is which serves a slightly different purpose where we are surfacing content or conversations that may be of interest to a broad set of users even if we have and especially if we have low amount of signal for those users so for new users or for people who are coming back to the platform and who haven't put in a lot of time on figuring out what are the counts they want to follow this page is extremely useful all right so at a high level we have varied we have different recommendation types we have accounts we have tweets we have topics and then we power these different products wTF is again anyone guess what WTF is who to follow who to follow is one of the is what we call our account recommendation system Explorer is the screen that you guys just saw which is showing showcasing like the trends and topics of conversation on the platform and users consumer recommendations by going to these products the other channel that we have is when users are off platform and this is these are what we call the reactivation channels where we can send a user a push notification or an email and get them to come back onto the platform if we think that the content that we deliver is of significant value to the users all right cool so let's talk about like the overall and anatomy of a recommender at a high level what we want to do and this is the the reason we're talking about this is because there are many different as you know recommendation systems as you've seen in the past so there are some common patterns across all of these recommenders that we use consistently at a high level we need to generate candidates in some form and there are there may be different algorithms for generating these candidates we might generate candidates that are popular in the geolocation or we might generate candidates that are popular in your network that's the first step the second step is to rank and filter these before showing them to a user and often when you're starting off building a recommender system you want to rely on business rules to bootstrap your recommender system and for example some business rules that we have are if we want to send only one email a day or you want to send this email at a particular time these rules come in handy because they're they're kind of our product intuitions are kind of embedded in these rules and we can start to implement a recommender system based on these intuitions so essentially you start without any machine learning and the idea is to get to an experiment quickly all right which leads us to experimentation how many folks here just as a quick survey know what experimentation is or have done an experiment in the past all right so so what 50% I would say okay so experimentation is like an industry standard we do what we call a B tests where the the goal of an experiment is to determine a causal relationship between product changes and metrics what what do I mean by causal relationship so we want to make sure that some metric on the platform has increased because of a product change and this may not always be obvious if you just look at time series data and that's where experimentation comes in what are the metrics that we want to track so there are business metrics that any business would care about you care about Diu engagements on platform the money we are making we also care about some leading indicators for our products and we'll get into more of that in a second and finally we care about negative metrics like you know are we spending by spamming are we generating more spam or are we causing more users to opt out of push notifications for example so let's talk about leading indicators what are leading indicators and why are the important leading indicators are the first the first indicator in your experiment which is gonna which is going to be somewhat easy to move some of the business metrics that we have are often a little bit further removed from the product and a harder to move a good example is maybe DEA you right changing some ranking in some sub product may not directly be moving a big business metric like DEA you but how but you still need to make those product decisions so you rely on like the top level leading indicators there for example the trends a good business metric might be driving our conversation on the platform and this is this is probably harder to to move on every single experiment but a leading indicator maybe clicks on trends a better leading indicator would be engagement on the landing page of trends which is which is better because we are not optimizing for clickety-click petty things and sure so we have these leading indicators but how do we know whether these leading indicators are impacting the metrics that the business cares about and one of the patterns that we use a twitter across different recommendation systems is we keep longer-term hold back experiments so we'll we might do something like you know over a quarter or over an even longer period keep some have some use set of users on a different experience than others to measure like the impact over a larger period of time alright so coming back to the anatomy of a recommender so we generate candidates we want to do some ranking what often happens is that rules and heuristics get cumbersome to maintain for example you might have some rules that you know we want to show we have multiple different algorithm types and now we want to kind of figure out which algorithm is performing better and we might hand code a rule saying that you know what show krandalls from this algorithm more than another and wait some algorithm more than some other algorithm this might work and it's a good way to get your changes out unfortunately rules are suboptimal with respective metrics it is much better to frame it as an optimization problem to be solved using ml for example you can directly optimize maybe for the leading indicator saying that you know we'll just optimize for clicks and that's where what you want to do is you want to extract features from candidates you wanna build em you want to extract user actions you want to join those things and you want to construct a model that can be used in ranking and how do you determine what do you want to improve beyond improve your model do you want to improve improve your candidate generation you wanna improve what what do you improve when you work on these products improvements to any component can improve the overall metrics and the overall recommendation system and and also the one complication is that changes to one component can impact others for example adding more candidates with a different set of features will require you to retrain and maybe change your model latency change the change the behavior of the recommender system in general so what should we improve it varies by product you want to build intuition from your prior experiments that you have run and come up with newer experiments that that that that you want to test out in general a rule of thumb is that changes to your product give you much better winds in general then you know better candidate generation and that is a little bit better it gives you it's good to focus on that as compared to modeling and these are just general rules of thumb and I can maybe these are very specific to Twitter and our experience and we'll get into why in a little bit so what are the challenges for Twitter so on candidate generation in general at Twitter there's billions of potential candidates so the reason this this is the case is because Twitter is a public platform so every piece of content that we that is generated on the platform is a candidate recommendation to every user and what that means is you can pretty much think of it as a giant matrix where you have like the set of users on on one axis and the set of all the candidates being generate another axis and you want to put in a score for you wanna fill this matrix up obviously that's infeasible so you can't really rank everything so this is why you need to generate high quality candidates to start with another important challenge is feature generation so in our experiments most of our impactful features are edge based which is which is rather than so when you are recommending a candidate to a user you can generate many types of features you can generate candidate only features that hey this candidate is about this topic or you can generate user only features here this user in this cohort or this user is you know it has has logged in X number of days ago or whatever it is and then you can generate these edge features which are the user candidate pair features or user author pair features we've observed that those features are very expensive to compute in store but are also the most impactful alright so let's talk about account recommendations so in our beautiful flow chart of the all of recommendations that's the yellow box there it's the current recommendation dect what's the job for account recommendation so it's mainly to connect users on Twitter and the reason we need again recommendations here is because any user is a potential candidate recommendation to every user so we want Twitter wants to do the heavy lifting this is maybe different from some of the other other cases where you only you you only care mainly about like one way to do this would be to only care about like your address book or phone book or those kinds of users but in general the problem for Twitter is a slightly account recommendation problem for Twitter is slightly larger so for account recommendations there are many different product surfaces here is one this is the connect tab where you're showing a user a bunch of accounts that we think they want to follow you can see some context up top because they follow these accounts and we think that these additional accounts are good candles to follow what are the business metrics for for Twitter for this platform again the business metrics don't change that much by by sub product they were again BDA you engagement time spent on the platform and what are your leading indicators your leading indicators are mainly follows and mutual follows excuse me so as we are talking about there's a massive candidate space and most candidates are uninterested so generating high quality candidates is important follow graph doesn't change as frequently so excuse me the the follow graph doesn't change the swinging so one of the one of the algorithms that we use is we try to figure out what accounts users follow and based on that suggest additional accounts that they might want to follow the follow graph itself doesn't change so frequently so we can do a lot of processing offline how do we find interesting candidates address book is one signal there are others as we get into excuse me so for account recommendations your to hop follow neighborhood is an important is an important source of candidates that we want to recommend to a user in this case in the in the graph and it's good to kind of clear this terminology upfront is the user who we are recommending content to a follows the users b1 and b2 who in turn follows C and C is the candidate recommendation we call b1 and b2 your social context so basically we are saying who are the people that the people I follow follow there are lots of other techniques but in this case you can see that Anton is a candidate recommendation for me and the Anton would be the C in this case in in terms of the notation and Anton is followed by some social context nos Chan and Jung there are lots of other techniques that we can use to generate these recommendations for exams similar counts return determining strong ties between users and so on let's talk about mutual follows so suppose our product as a product we want to test the hypothesis that mutual follows drive engagement on the platform again a notation is a is a target user C is a candidate recommendation how do we generate how do we generate mutual follow candidates so what we can do is we can find all users who follow the target users so find all C's who already follow the a and then recommend C to a as a candidate unfortunately not all such accounts are interesting for example if I'm the user who's visiting Twitter and you show me everyone who follows me I might see recommendations which are just people trying to gain the follower count but I just follow spamming users so there might be some random account is following a bunch of other accounts and now all of a sudden that's a candidate recommendation for you so we need to find better candidates and this goes back to why candidate generation is an important step so how do we do that well what we can do is we can see if there is a social context for that C so if someone follows me I follow someone else who follows that person that might be a good signal because because that gives me a social context there is someone else who's done the work of understanding and following that user so we get to this triangular loop which is the a follows B B follows CC follows a and that's one algorithm to generate candidates for a given target user okay and here maybe you guys can take a picture but this is like a take-home puzzle how do we find all such triangles the the problem is framed in a slightly different way on the right basically for every social context B there's a bunch of users who follow this account there's a bunch of C's that B follows the real question is to figure out which of these M times and edges exist the framework here is we are working with on offline so we have like a MapReduce framework where we have a bunch of as input directed edges on Hadoop your output is to be output is to return all triangles so why is this not some nodes can have a very large in or out degree for example lady gaga i think is followed by about 100 million users today so how do you scale your your offline job to be able to handle such cases if you have a reasonable a good solution that you think works please DM me bonus question is how do you how do you efficiently update these graphs and yeah that's a bonus that's a bonus question so as we talked about follow the change slowly over time so suppose you have generated candidates yesterday and you have a delta graph today how do you merge and generate new candidates good all right so now you've you have some system for generating all these candidates based on triangular loops maybe you should start experimenting it before experimentation is good to understand what the coverage is what is our you you want to you want to basically go for high coverage experiments because those are the ones that if you do a good job of coverage and probability of engagement then you will have a higher impact on the entire platform a leading indicator here obviously is an outbound mutual follow which is someone is closing the loop of off follows as opposed to opening the loop which is a separate different but also interesting problem and once you once you satisfy that this is the right thing you start you add the candidate to the list of candidate selection algorithms for their treatment bucket one caveat is is let's talk about like the network effect that this that this introduces so on twitter are recommendations that we surface here are themselves users on the platform so an interesting dynamic here is if you change your algorithm for people if I change my algorithm to show different candidates in my in my recommender for me that might change my behavior but it might also change and impact the behavior of users who are in that who to follow module so we call this the the distinction here is there are engaged side and receiver side experiments and this is a common pattern in in other in other parts of the product as well a good question is why can't we or at least a non-trivial question is why can't we measure this entirely on the engage side so for example I want to see what the impact on the receivers receiver is why not just look at what the engages are doing and the answer for that is that the populations are different the kinds of people who will show up in the receiver on the receiver side are different and that's why you need to measure must measure that separately so as an example of what I mean by receiver side experiment in who to follow module if an experiment say if a receiver experiment says that you know what we are going to hold back on some receiver or some algorithm then maybe we will not show this particular candidate to any user on Twitter and then measure the impact on that user for example yep so this was an experiment that we actually ran I think a quarter of or so and we saw huge gains an engagement cool and now let's move on to real-time recommendations this is this is a slightly different track in the sense that we're going to be talking about a system that generates and some other trade-offs that we see while generating recommendations in real time all right so real-time notifications Twitter is a real-time product and push notifications are a channel for us to be able to deliver value to users in real time which means that latency in recommend matters an example here for while latency matters is suppose a user goes live on the platform we want to notify people who might be interested in that broadcast as soon as possible with low latency there's a natural trade-off between latency and relevance for push notifications how we frame it as internally as an optimization problem is given a budget of say one push notification or n push notifications per day how do we maximize the value that a to our business and to our users examples of such notifications we already talked about the broadcast example another example is is again if you look at the right we keep coming back to this graph but we want to notify the user a when n people that they follow say B 1 and B 2 engage with the same content C so this is what we call magic text which is a product we launched I think about three four years ago notation again is important and I apologize in advance for these slides that there's a lot of notation here so it might be going by a little fast I'll have time for questions later so the notation is a is the target user who's getting notified so if I am doing Twitter on my platform I get a push notification I am a B is the social context which is if I follow someone that person made some interaction and caused a push notification to me so that the person that I follow is what we call the social context and C is the candidate recommendation and these could be to its users and so on so what are the challenges here Twitter is a so how many of you have heard of the firehose cool yeah so a lot of you so twitter has what twitter has a firehose that is a service that we provide externally as well which is like the set of all tweets and engagements that happen on the platform we have a similar system internally so we get like an input stream of events which we the in in terms of notation is be engaged with C or the notation so for example user B tweeted C or user be followed user C so on what we want to do is you want to generate recommendations for a why is this challenging to do this in real time for every b2c event so so every b2c event is potentially interesting to all the followers of B sorry to other followers of B the error on the slides so the number of potential events is the number of is the size of the fire hose the number of events we see multiplied by the fan-out factor and the final factor on Twitter is very large in addition another challenge is graphs Q creates spiky behavior what do I mean by that so we talked about how lady gaga has like a lot of followers Katy Perry has a lot of followers so when these users generate content or engage with some content the number of people who are target users for those those people is very large so it generates a spike in the amount of potential candidates that we are generating this is also exacerbated by Spike eNOS in in real world event so in the real world in Twitter usage spikes when there's a real world event whether there is there is there's some news event there sports or whatever it is and these are inherently spiky there's not a uniform set of events happening over time in the world so that spike eNOS is exacerbated these systems have to deal with that spike eNOS as well so how do we generate recommendations for how do we generate these recommendations real time so well one option is a pull based solution what I mean by pull based solution basically given a user a so so we just loop over all users so say we know we know the entire set of users we know their push tokens we just loop over all these users and we look up we we keep track from the input stream we keep track of what are people engaging with then we loop over target users find out what the social context is doing generate a candidate recommendation and push this is this is this is this works this is actually we use variants of this in many places it the challenges here are you getting to low latency is very hard because if you so to get to low latency say you loop over all your users in one hour to get it to 30 minutes you have to double your QPS to downstream services and you can't keep doing that so if you want latency of few seconds you can't you can't do this fast loop you can do variants of this like maybe for some experiments you might set up a quick loop but in general for at scale this is this is a bit tricky and also other challenges are how do you store these graphs so the recommendation on the bottom is an important one to keep in mind so this is a push notification that was sent to a user you see that it follows that pattern of a engaged with B which a follows B 1 and B 2 which engage with C so this user follows now as a few other users who liked this photo that's the that's the kind of notification that we're trying to generate so how do we do this in real time like how do we generate this so one option is assume that you have infinite memory on some machine you can store the follow graph in local memory whenever you see a B to C event you look up all the A's that fall be and generate see as a candid recommendation so basically you do you look you keep the transpose of the follow graph and you you listen to incoming events fan it out to that transpose unfortunately or fortunately the follow graph is massive so we need to distribute right let's talk about cross partition so the so so the graph service that I'm describing here is over the next couple of slides is an in-house system that we built which is a multi-tenant graph partition graph system which solves some of these problems so the photograph is very large and very skewed we want to disable process across many nodes so how do you go about partitioning a graph a simple way to do it is to let is to partition by the target user so in our overall system what we want to do is we want some node to be responsible for a subset of target users and once we have that what we do is we partition our graph in in a way where we keep two types of partitions we try week so so on the right is an example the input graph is is is provided there as a simple input graph the lightly shaded nodes are the target users suppose there's only two types of partitions and even partition and an odd partition the even one is the row on the top the odd one is the row at the bottom and you're considering the graph and it's transpose the transpose is important because of fan-out so we want to look at both the graph and its transpose we partition by users such that we keep all the edges on both the forward graph and the transpose on the same node so in this case what that means is we will keep we will key the people who are who that subset of users follows we are partitioning by the lighter shades so all the users the green the even partition will keep all the users that that are followed by that that are followed by this user as well as the transpose which is all the users that follow this user that make sense good okay right and before we dive into what each machine does maybe let's say the font is kind of small but let's take a look at how all of this is kept in like how the overall system works so we have a proxy layer so the this cluster of machine there's a cluster of machines over which this partition follow graph is stored and we want this to also respond to graph queries and generate some real-time candidate candidates what is the graph query an example query is given here given a user a and a hashtag H who are the people that a follows who who have engaged with this hashtag and it's kind of hard to see but if you look at hashtag 49ers there is someone that I follow who's tweeting about this so that's that's the kind of query given an A and a C in in terms of our notation given an A and a C giving all the B's basically and each machine here so there's there's a proxy layer so what happens is since each machine is responsible for a subset of target users we need a proxying step where when a request comes in it figures out which machine is responsible for that target user redirects the query there runs the graphic only locally returns it back so that's the service side let's look at what is stored on an individual node so on this on this in this chunk the one so on the left on the left side what you see is there's an incoming stream of b2c engagement events and at the bottom there are recommendation candidates that effect out that is our fan-out pipeline that's a real-time recommendation pipeline on the far right you see the graph query processor this is the thing that's gonna return given any NSC give me give me all the social context the stuff in the middle is the graph so the purple square the purple rectangles are your real-time graphs that you are keeping in memory your the the green and the red chunks there are the graphs partition the follow graph with a partition photograph that you computed earlier often what we'll do is we'll compute these graph partitions offline and download them locally onto a machine and and start serving serving these requests so that's the overall setup each machine the the key the key part here is that each machine is responsible for only a small set of target users so coming back to the example for social context query is given a user hash tag pair a comma C an algorithm that this graph query processor runs is lookup all the B's that a follows and for each B check if C is in the engagement so look at the engagement graph which are the purple graphs kept in real-time and look at the look at the forward graph for a which is the green forward graph here for that for that set of user this is partitioned and returned all the people that a follows that have engaged with that hash tag and this is like a social context query another example is light notifications suppose B went live and now in this part we are we are focusing on the left-hand side right so we are looking at only the the fan-out pipeline so in this case suppose B goes live B to broadcast ID event shows up in the engagement event stream we look up the subset of users who follow B and who belong in this shot this is the red transfer was graph partition and we fan out the broadcast ID to those users and we write those recommendations in the queue this is a little bit harder so maybe I can go over this quickly but here so this is the magic recs event type fan-out where we where if K people like tweet we will generate a final recommendations so here again what we do is we look up here we here we have to look up both the forward graph and the reverse graph we given an incoming b2c event we look up all the users that follow me that's a transpose fan out then for each of those users we look up all the people that they follow which is the forward which is the forward lookup and then we find users among that forward lookup who ever engage with C and if it exceeds a threshold we write that event out this part is a bit dense but trust me it works and that's all that I have for today thank you all for patiently listening and do you have any questions fantastic Tom thank you start back here yes you also look at people the block users or there are muting them and how that will affect them these decisions yeah that's a great question there are in addition to all of - these kind of candidates they just don't send those out directly there are a lot of business rules in place so if a user has blocked another user we will not serve that user as a recommendation for example are muted we have like checks at the final layer to make sure that we are not sending such recommendations okay any more questions now so I have two questions first why as I did find a way suppose that you recommend a with a son Steve but they are you follow them already right or what people think they're so did you all have some like quickly ruin it you decide which one yeah we do have we do have filters so just like blocks there is a if you've already engaged if we've already shown you some content we don't need to keep showing you that content there is also the larger like we also in there also other rules are on fatigue so if you want to show you some recommendation we've shown that many times in the past we may not show that again and again to you so there is there's a few rules like that great thanks for the awesome talk do you guys do pure content basic operations and if not why not can you maybe clarify what do you mean by content-based recommendations so they say I'm off connected by user or degree is high and I'm interested yes so you're talking about something similar to collaborate a filtering or no this is surly so let's say there is no context like user connections but the content is relevant so I'm posting stuff about forty-niners right right so we do that we do that to some extent we are actively working to improve some of our systems there but a lot of the work on explore is targeting based on interests rather than graphs [Applause]