Transcription

Hello everyone, my name is Naren and in this session let's talk about system design for Uber, Lyft, Ola or Grab kind of taxi application services. Uber's technology may look simple but it is not. When a user requests a ride on the app, the driver allows to their place to take them to the destination. But behind the scene there are tons of service which is supporting the trip, terabytes of data has been used for this particular trip. Like any other startups, Uber, when it started, they had a monolithic architecture. That means they had a backend service, they had a frontend that is an application and a database and couple of real-time services only. This couldn't work well when Uber started to roll their service into different regions. Initially, the design was something like they used Python for the application servers, they used Python-based Celery framework for this asynchronous task, they had PostgreSQL to save the database. After 2014 and now Uber's architecture has evolved into something like service-oriented architecture. Now Uber won't just handle taxis but instead it also handles food and cargo. Everything is built into one system. Now the challenging thing for Uber or any cab aggregation platform is to meet the supply to the demand or demand to the supply. The main task for the backend of the Uber or any taxi aggregation platform is to serve the mobile traffic because without mobile phone it is pretty hard to run this service because everything works on GPS. The next thing is Uber's dispatch system acts like a real-time marketplace to match the rider to the cab. So that means it is clear that we need two different services in our architecture that is supply service and demand service. And here is the complete architecture for Uber or any taxi aggregation platform and you can see everything here. I have written all the major components over here. But instead of jumping right into explaining each and every component, I am going to concentrate much on this particular component over here that is called Disco or Dispatch Optimization. Let's talk about how this dispatch system works. Dispatch system works completely on map or location data. That means that we have to model our maps or location data properly. So now, since Aleth is spherical, it is pretty hard to do summarization and approximation just by using latitude and longitude data. And to solve this particular problem, what Uber uses is Google S2 library. What this library does is it takes the spherical map data and it divides this data into tiny cells of about say for example 1 km by 1 km cells. So when we join all these cells, we get the complete map. So each cell is being given a unique ID. That way it is a lot easier now to spread this data in the distributed system and store it easily. So whenever we want to access a particular cell, if we know the ID, we can easily go to the server where that particular data is present. We can use consistent hashing based on the cell ID. Also, S2 library can easily give you the coverage for any given cell. Say for example, we want to draw a circle on the map and we want to figure out all the supply available inside that particular circle. What we need to do is use S2 library and give the radius to it. So it will automatically filter out all the cells which contribute to that particular circle. That way we know all the cell IDs. So now we can easily filter the data which we need and also which belong to that particular cell. That way we have the list of supply available in that particular, in all the cells. That way we can filter out, we can calculate ETA etc. So when we want to match a rider to the driver or even if you want to show a number of cars which are available in your region, all we need to do is just the way I explained earlier, we need to draw a circle of about 2-3 km radius and list out all the cabs available using Google S2 library. Then what we need to do is, with the list of all the cabs available, we need to check for the ETA. How do we need to do is, say for example, so we found, say with this particular circle of about 2 km radius, say we found about 1 here, 1 here, 1 here, 1 here and 1 here. So these many cabs we found out in the nearby, in the 2 km radius. So what we need to do is, so we have to calculate ETA or the distance from the rider. Consider the rider is present here, in this way, the shortest distance we know obviously, we can calculate something like Euclidean distance, but this won't accurately give you the ETA because you can't just drive the cab from here to here directly, but instead you have to go through the connected road system like this, say if the road is something like this, so the cab should be driven using that road. So we have to find the ETA or the distance which is connected by the road. So that way we have to figure out all the ETA. So when we do that, maybe we might get 0.8 km and this could be our 2.5 km or 3 or 1, something like that. So now we know which cab is suitable or which are the cabs suitable for this particular rider. In the same order, we can send the notification to the driver and if the driver accepts, we can match the rider to the driver. Enough of explanation. Now let's jump into the system design and understand all the components which are needed to understand this batch optimization component. So now you can see over here, this is the supply, that means the cabs are the supply and this is the demand where the user request for the ride. So every 4 second runs, the cabs will be keep on sending the location data to the Kafka REST API and every call happens through the web application firewall and then it hits the load balancer and it goes to Kafka and it keeps updating the location by pushing it to Kafka and then it is consumed to different places and also a copy of location is also sent to the database and also to the dispatch optimization to keep the state machine, that means the latest supplies location, that is the latest location of the cab. So here we need a web application firewall and if you ask me the reason why, it's pretty simple for the security purpose. Here we can block the request from the blocked IPs or we can block the request from the bots or we can block the request from the regions where the Uber is still not at launch and then we obviously need a load balancer. A load balancer can be of different types, that's the hardware load balancer or software load balancer and also in the load balancer we can have different layers of load balancers, say layer 3, layer 4 and layer 7. Layer 3 works based on the IP based load balancer like all the IPv4 traffic go to this particular server, all the IPv6 traffic go to the different kind of server or in the layer 4 what we can do is we can do by DNS based load balancing and in the layer 7 it is application level load balancing and the Kafka REST APIs will provide the end point to consume all the location data for every cab. Say for example we have thousands of cabs running for a city and every four seconds we are sending a location, that means that in four seconds we will be having thousand hits or thousand location points being sent here and that data will be buffered and put into Kafka and then they were consumed to different components over here and also a copy of it is there in NoSQL when the ride is happening and latest location will be sent to Disco to keep the state machine updated. And also we have REST APIs and we will talk about these components later. So the important component is WebSockets and why do we need WebSockets? Unless like normal HTTP requests, WebSocket is really helpful in these kind of applications because we need asynchronous way of sending messages from client to the server and server to the client at any given part of the time. That means that we should have a connection established between a cab application to the server or from the user to the server. What happens is WebSockets keeps a connection open to all of the applications, the Uber's application and based on the changes happens in the dispatch system or any component in the server, the data will be exchanged to and fro between the application and the server. So the supply demand and the WebSocket component are mainly written in Node.js as Node.js is really good in asynchronous messaging and small messaging and also it is event-driven framework. So people these days are using Node.js for all these kind of requirements. So now let's jump into understanding the dispatch optimization component. So let's see how the dispatch system works. At Uber, dispatch system is built using Node.js. The advantage of using Node.js is asynchronous and event-driven framework. So the server can push the message or send the message to the application whenever it wants. Now the next question is how do we scale these servers? So this is the Disco component or dispatch optimization component. These are the different servers or the services which runs. So how do we scale this? To scale this, Uber uses something called RingPop. It has two functionalities. First one is it does consistent hashing to distribute the work between these servers. So when we say consistent hashing, we know that it needs a ring kind of structure. If you don't know about consistent hashing, you can check one more video which I have made about consistent hashing. It works similarly. So it uses consistent hashing to distribute the work between these workers and it also uses RPC call to make call from one server to one more server at times and I will explain in about few minutes why do we need to make a call from server to server. And along with doing this, it also uses something called Swing protocol that is Gossip protocol which helps every server knows the other server's responsibility. So for example, this server knows what is the responsibility of this server and what is the responsibility of this server. So every server has a specific responsibility even though they all do the same work, but the responsibility to compute for a specific location is assigned to each and every server. So now, why do we need Gossip protocol? So the advantage of Gossip protocol is we can easily add a server, we can easily remove the server in this ring. So that way when we add the server, the responsibility is distributed to this server and responsibility is reduced for other servers. That way everyone also knows that this guy is responsible for doing what work. Now, let's see how in real time when a user place a request for a cab or for a ride, how this function, this particular setup works. So if you know that WebSocket has a connection to the user and to the cabs, so when the user places a request for a ride, the request lands to the WebSocket and this WebSocket hands over the request to the demand service. Since the demand service knows the requirement of the cab or a ride, say I need a mini car or I need a SUV or I need a sedan or something like that. Or maybe like I need one seat or if in case of pool, I need two seats or I need a complete cab or something like that. So now the demand service requests the supply that I need a cab of this kind at this particular location. So what does supply service does is it knows the location of the user, that means the cell ID of the user's location on a map. As I have already explained, Google H2 library gives, breaks the earth into tiny cells, right, like say we have map of some region like this, it breaks the location into small, small cell. If the user is present here, that means that it knows the cell ID of that particular user. So the demand supplies the, gives the cell ID to the supplier. So based on the ID, what it does is it contacts one of the server in the ring of the servers. So in the consistent hashing, as you know, the work, the responsibility is equally distributed. That means that say we have about 10 cells in total, hypothetically it is millions of cells. Just to make the expression simpler, I'm dividing it into 10 cells. With 10 cells, the responsibility will be something like 1,2. The cell 1 and 2 will be handled by this guy, 3 and 4 here, 4, 5 and 6 here, 7 and 8 by this guy, and 9 and 10 by this guy. So say consider the user is requesting from the location cell 5, that means that the supply knows the 5 and hits the server and it requests the server here to find a cab for this guy, for the rider. What this guy does is, he requests the server so it figures out, it draws a circle in the map and figures out, say it draws a circle around it and figures out all the cells which is responsible, all the cells from which the cabs can be figured out, okay. And then it makes a list of all the cabs, it makes a list of all the cabs and then in that list it figures out the ETA for each and every cab using the map's ETA service and it sorts based on that. And with all this information it gives back that information back to the supply service and the supply service using the web socket sends the request to the first few cabs which is very near to the user and as soon as the driver accepts, whoever accepts first, that particular cab will be assigned to the rider. Sometimes it might happen that for a particular request, say for the rider is at the 5th cell, so the cells which we got is say 4 and say 7. In this case there are different kinds of cells available. So now what happens is the supply won't directly talk to each and every server, what it does is it handles the request to one server, that is probably this guy and then this server internally hands over the request to all the different other servers which is responsible to compute or to figure out the cabs, that is 4 and 7. So in that case what happens is the request will be placed here using RPC call and one more request will be placed using RPC call. So now once these guys figure out the cab's ETA and once these guys also figure out the cab's ETA and also the same with this server, they all respond back to the supply server service and the supply server takes care of notifying the driver and matching the demand with the supply. Next we need to add more servers to the existing dispatch optimization RINGPOP here. The reason is we need to handle the traffic from the newly added city. So we need to add more servers to the RINGPOP. Say for example we have added here and we have added two different servers. Now the responsibility of these servers are unknown. What RINGPOP does is it knows the all newly added cell IDs from this component and it distributes the responsibility of newly added cells to these new servers, that is probably cell number 11 and 12 you take care of it, cell number 13 and 14 you take care of it. Same way it works when we take down the server, it reshuffles the IDs or reassigns the responsibility of the computation of particular cell to one of the random server which is free. Now let's talk about geospatial design. As I have already explained, Google Heavy uses Google's S2 library to break the map into different cells and that is being used to easily locate the caps near to any particular rider's location. So that is the use of S2 libraries. So next about building maps or using maps in your application. Earlier Uber used to use Mapbox because of the Google's pricing strategy and etc. But now Uber is back to Google's APIs and maps. Now Uber Heavy uses Google's map framework in which it uses Google's maps to show on app and also uses Google's maps APIs to calculate the ETA from point A to point B, that is pick a point to the destination point and it uses Google's help to calculate the ETA. Earlier Uber used to do all its own. It used to repeatedly trace the cab's movements, GPS points and builds the road's network system on its own. And also it used to use the real-time speed and different information from the cab to calculate the ETA also. But now Uber has moved on and it uses Google's library Heavy. So the next thing is preferred access point. So if you know so many times, say for example there is a big campus in the city, say no matter how many times you book the cab from inside the campus, Uber always shows two more preferred access points. For example this is the entry and this is the exit gate of the campus. Usually Uber shows the preferred access point somewhere near to the entry exit. How did it learn? It learns based on the repeatedly Uber drivers or the cabs used to stop near the entry exit gates because they can't enter into the campus. So that is being learned by Uber and so it automatically shows to the customers that we can only pick up from these two points, we can't enter into the campus. So these are called as preferred access points. They use different algorithms and machine learning to automatically figure out these preferred access points. Now let's talk a little bit about how ETAs are calculated and why it is a very important component of Uber or any cab application service. Say for example a user is requesting a cab from this point. So the rider is requesting a cab from this point and the available cabs near the user is something like these three cabs, cab 1, cab 2 and cab 3. So now when a user requests for a cab, the demand service requests supply to figure out cabs for a rider. Now what this service does is it tries to figure out all the cabs which are nearby to this particular rider. So now it draws the circle and then it figures out there are three cabs which are free to take the service. But what happens now is it calculates ETA for all the cabs from the riders to these cabs by the road system and then it figures out the ETA for all the three different cabs. This always doesn't work because these could lead to bigger ETAs. Say for example one more cab which is about to finish a ride which is very near and the ride is, the trip is already happening. So this is a better way of selection than any of these three cabs as this trip is about to complete in a few minutes and this is much nearer to the rider. So Uber, what it does is it includes all the different factors like U-turn cost, turn cost, the traffic condition and everything to calculate the ETA and based on the different ETA, sometimes not just idle cabs, sometimes the cabs which are already serving the trip are also included to serve a particular rider. Now let's talk about database. Earlier Uber used to use RDBMS that is PostgreSQL database for operations. They used to save profile information, they used to save GPS points, everything in RDBMS. It couldn't scale as Uber rolled out service in different cities. Then they thought about new NoSQL kind of database that is built on top of MySQL, something called as SchemaList. When they are building this database, these are the points they consider. The first one is it should be horizontally scalable, that is you can linearly add the capacities in different part of cities into the network. Say in here you can see there are multiple nodes in different regions which are added and all together acts as one database that is SchemaList. So if you don't want to design, you can either use Dictable or Cassandra, MongoDB or any of that since they also behave the same way. And also different other consideration which they considered while building SchemaList was the write and read availability. As I have already mentioned to you that every four second runs the caps will be sending the GPS location to the Kafka REST API and those points were sent to Kafka for different processing and also points were written to NoSQL for record purpose and to figure out and also points were sent to state machines also. So it means that there is write-heavy application and also when user requests for a cap, all this latest cap information is also fetched from the DB to show to the customer on application. That means that there are tons of reads happening, there are tons of writes happening to this system. That means these systems should be heavily write-able and read-able systems. And these systems should never give downtime because we haven't heard Uber downtime even for a minute, right? Because every minute people will be requesting caps, people will be writing trips, etc. So we can't just say that we are doing some maintenance, now the database is not available. So the system should be always available no matter what you are doing. For example, you are adding nodes to the system, it should be available. You say for example you are taking backup of the storage, the system shouldn't go down. Say for example you are adding indexes to the system, then also your system should be up and running. So no matter what you do to the system, the system should be always up. So these are the points they kept in mind while building schema-less that is built on top of MySQL. So what Uber does is, when they roll out services in new cities, they try to build the data center near to it to give the seamless service. If not, always the nearest data center is selected and the data will be served from those locations. Now, let's talk about analytics. What is analytics? In simple words, it is making sense of the data which we have. Uber does that a lot because you need to understand about the customer, you need to understand the behaviors of the cab drivers, that's when you can optimize the system, that's when you can minimize the cost of operation and also make the customer satisfaction better. So now, let's see what are the different tools which Uber uses or different frameworks which Uber uses to do a lot of different analytics. As I have already mentioned, there is tons of GPS data flowing into the system from drivers and also a lot of information coming in from which belongs to the customers. All this data is saved either in NoSQL or RDBMS or sometimes in HDFS. If we are not saving the data directly to HDFS, what we can do is we can do a dump of all the data which we have on NoSQL and put it on to HDFS. And sometimes for the different kind of analysis, we might need the data in a real time that can be consumed from the Kafka. Now, let's talk about each and every component here. See, the Hadoop platform has a lot of analytical analytics related tools which we can make use of to build analysis on the existing data. So we can take a constant dump of the data which we have in the database to HDFS and use tools like Hive and BigQuery tools to get the data which we want from the HDFS. Next, the component maps or ETA components. What we can do is you consume the historical data along with the real time data. We can easily retrace the previous maps data which we have and then we can build new maps altogether or we can improve the maps data which we have now. And also, with the historical data and the real time information which is coming from the cab like traffic situation, the speed at which the cab is driving or the condition and everything, we can use this data to compute ETA. The dispatch system here, when there is a request for supply, these servers here contacts these components for ETA calculation. Now, Google also uses something like simulated artificial intelligence to calculate the ETA in accuracy and much faster. So the next component is machine learning or fraud detection. There are different kind of frauds happening on the system, say payment fraud, incentive abuse or usage of compromised account. There are different algorithms that are used to detect payment fraud where people are using stolen credit cards to offer trips in discounted price on different forums. Uber is taking care of that also. And there is incentive abuse mostly done by the cab drivers. Uber offers extra dollars when they finish, say for example, 25 rides in a day. What Uber's Uber driver does is they simulate the trip using fake GPS location apps and then they claim the incentives by doing nothing or by booking for a ride using another mobile phone of their own. What Uber does is to find out these kind of abusers. It uses historical trips altitude data and it retraces with the abused trips altitude and that way we can easily figure out that this particular trip was fake and Uber warns the driver that if they keep continuing, they will cancel their account and etc. And the next thing is compromised account. A lot of times hackers using phishing techniques gets the username and password of the customers and they use it to withdraw the money in the wallet and sort of things. How does Uber tackle that? It uses the historical behavioral data of the customer, like what is the usual location from which they used to book, what is the usual destination and the country of booking and etc. Based on this kind of information, Uber also uses machine learning techniques to figure out the usage of compromised accounts. Apart from that, to do real-time streaming distributed analysis, we can go with Spark or Storm framework to figure out the trending things happening in the system. After analytics, the very important thing is logging. Now we have a pretty much complex system over here and since Uber uses service-oriented architecture, all of these components are different services. That means they run independent of other systems. That means that if you want to track what's happening or if you want to debug what's happening in each and every service or the system, we need to have a strong logging mechanism. That means each logger in each and every service, what we can do is we can keep forwarding all the log lines to one Kafka cluster and from there we can have a platform which is built on top of Elasticsearch, Logstash and Kibana. So using Kibana, we can build dashboards which shows the total errors which are occurred, the system's health and etc. Not just Kibana, we can use Grafana also and there are a lot of different tools available which can gather the logs from different systems and show it in a beautiful dashboard. So now, let's talk about how to handle total data storage. Data center failure doesn't happen usually but when they happen, it's very difficult to handle the situation. How does Uber handle this situation? What Uber has done is, Uber has built a backup data center and that has all the components which we needed to run this show or to maintain the trips which is happening. What happens is, in the backup data center, Uber never copies the existing data into the backup center. Now you might think, without the data, how can the backup data center will help to handle that situation? What Uber has done is the very smart thing or the cool thing is, the driver's app itself act as the data source at the event of data center failure. Every time when there is a transaction or when there is an API call happening between the driver's app and the data center, it also keeps track of what level of knowledge it knows or what level of data it has in the driver's app with a state digest, kind of unique idea you can think of. Say for example, this data center went down. The next time, the app makes a call to this data center, it learns that this system is not available. Then, the backup data center kicks in and this application, the driver application, the rider application is now talking to the backup data center. Now this data center doesn't have any of the information for the trips which are happening. In this situation, the APIs in the backup data center learns that, I don't know the state information or I don't know what's happening with the trip now. Using the state digest which is present in this, it gives out all the data to this backup data center from the driver's application. That way, backup data centers now have all the information which is needed to finish the trip which is happening right now. Now when these things happen, the user or the driver will never know that there was a backup, there was a data center failure and there was a backup data center which is helping now to run the trip. Now that I think I have explained all the different components in the whole system like Uber's system design, most of this data was consumed from engineering.uber.com. I strongly suggest you to go through the Uber's blog and read each and every article because they give you a lot of information about all the components over here, not just here. I couldn't cover a lot of information which is there in engineering.uber.com. It was full of knowledge. I suggest you to read the engineering.uber.com or I will leave a lot of links in the description of this video. Please go through the links to better understand the system. Because of the time limit, I am not able to explain each and every component even to the depth but you can always learn from internet. If you like this video, please subscribe and hit the like button and please comment and share with your friends and I am always open for suggestions or if there is any correction need to be done in the system design or any other videos, please contact me. Thank you.