Uber - Questão de Entrevista de Design de Sistemas (Serviço de Partilha de Viagens)

Desenhar a Uber é uma das perguntas de entrevista de design de sistemas mais desafiadoras, porque é fácil ficar sobrecarregado com a multiplicidade de componentes e sobre-engenheirar a solução.

Neste design de sistema, vamos focar-nos nos fluxos principais que a maioria dos entrevistadores espera ver cobertos, bem como fornecer análises aprofundadas dos aspetos mais críticos do sistema.

Então, vamos começar.

Para os requisitos funcionais, queremos um pedido de viagem, para que os passageiros possam inserir a sua localização de recolha e destino, ver os motoristas próximos e receber estimativas de tarifa em tempo real.

Também deve haver correspondência de viagens, para que o sistema seja capaz de emparelhar eficientemente um passageiro com um motorista disponível que satisfaça os seus requisitos.

Deve haver rastreamento do motorista, para que, uma vez emparelhado, o passageiro possa rastrear a localização do motorista em tempo real, juntamente com a hora estimada de chegada.

E o sistema também deve suportar notificações push para coisas como atualizações de viagem, chegada do motorista, conclusão da viagem, promoções, etc.

E para os requisitos não funcionais, queremos escalabilidade, para que a plataforma seja capaz de suportar, sabe, mais de 100 milhões de utilizadores ativos diários, e deve ser capaz de escalar eficazmente e lidar com picos regionais de procura.

Também deve haver alta disponibilidade, e deve estar disponível 24 horas por dia, 7 dias por semana, garantindo um tempo de inatividade mínimo, pois o custo de mudança para os utilizadores é extremamente baixo.

E, finalmente, queremos baixa latência, pois a aplicação deve ter um bom desempenho mesmo em áreas com redes móveis fracas, porque queremos sempre fornecer interações rápidas e responsivas para garantir uma experiência suave globalmente.

O que não está coberto é o 'ride pooling', portanto, a implementação de serviços de 'ride pooling' onde vários passageiros partilham uma viagem não será abordada aqui.

Então, olhando para o modelo de dados,

temos uma tabela de passageiros, que simplesmente armazena informações sobre indivíduos que solicitam viagens.

Temos a tabela de motoristas, que novamente armazenará detalhes sobre os motoristas no sistema.

Teremos veículos, que rastreia os veículos associados aos motoristas.

Teremos tarifas, que armazenam informações sobre as opções de tarifa apresentadas a um utilizador.

Assim, podemos ter a tarifa base, que é o custo inicial de uma viagem antes de quaisquer encargos adicionais serem aplicados.

E depois também podemos ter talvez um multiplicador de aumento, que é um multiplicador dinâmico aplicado durante períodos de alta procura ou baixa disponibilidade de motoristas, e isso aumenta a tarifa para encorajar mais motoristas a ficarem disponíveis.

Também teremos viagens, que armazenam informações sobre viagens iniciadas pelos passageiros.

Então, terei a hora de início e a hora de fim, e depois também terei um estado, que pode ser solicitado, aceite, concluído ou cancelado.

E, finalmente, também teremos pagamentos, que lida com todos os detalhes de pagamento para viagens concluídas, então também terá um estado indicando se está pendente, concluído ou falhou.

E para um serviço de partilha de viagens como a Uber, acho que usar um tipo clássico de API RESTful para interagir com os dados funcionaria bem.

As APIs RESTful são simples, amplamente utilizadas, sem estado e suportam caching, o que a torna uma boa candidata para o nosso sistema.

E assim, a nossa API REST será composta por três 'endpoints' principais.

O primeiro será um POST para o 'endpoint' de estimativa de tarifas da API, e isso fornecerá estimativas de tarifa com base nas localizações de recolha e destino do passageiro.

Eventos enviados pelo servidor, 'web socket' e 'QUIC'.

Então, olhando para o 'long polling', como funciona, o cliente solicita repetidamente atualizações ao servidor, mas o servidor mantém essa conexão até que novos dados estejam disponíveis.

E os parâmetros que terá incluirão a localização de recolha, que será um par de latitude e longitude, e o mesmo para a localização de destino.

E depois, simplesmente repetirá esse processo continuamente.

As vantagens são que é muito simples de implementar e funciona bem com o HTTP tradicional.

No entanto, as desvantagens são que há uma carga muito alta no servidor devido a pedidos repetidos, especialmente quando não há atualizações.

E pode ter uma latência muito maior do que algo como 'web sockets'.

Portanto, é melhor para cenários simples onde as atualizações em tempo real não são cruciais ou se o suporte a 'web sockets' é limitado.

Para os eventos enviados pelo servidor, funciona com o servidor a enviar atualizações para o cliente através de uma única conexão HTTP persistente.

Quanto às vantagens, é simples de implementar para comunicação unidirecional, neste caso, do servidor para o cliente.

E usa menos recursos do que os 'web sockets' para fluxos de dados simples.

No entanto, as desvantagens incluem comunicação apenas unidirecional; o cliente não pode enviar dados para o servidor através da mesma conexão.

E, portanto, isto é melhor para transmitir atualizações como mudanças de estado de viagens ou notificações, mas não é adequado para comunicação bidirecional.

Depois, olhando para os 'web sockets', isto funciona tendo uma conexão 'full duplex' persistente entre um cliente e um servidor, para que ambos possam enviar e receber mensagens em tempo real um para o outro.

As vantagens incluem ser em tempo real, comunicação bidirecional e ser ideal para rastrear a localização dos motoristas, bem como permitir atualizações instantâneas.

E tem baixa latência assim que a conexão é estabelecida.

E as desvantagens incluem que requer mais recursos e a escalabilidade pode ser complexa, sabe, especialmente se vamos lidar com milhares de conexões concorrentes.

E é melhor para atualizações contínuas de localização, notificações em tempo real e recursos de rastreamento de viagens.

E depois o 'QUIC', que significa Conexões de Internet UDP Rápidas.

Então, como isto funciona é que é um protocolo de transporte que oferece um estabelecimento de conexão e transferência de dados mais rápidos sobre HTTP/3.

É fiável, seguro e construído sobre UDP.

As vantagens incluem que tem menor latência do que os 'web sockets' devido à configuração de conexão mais rápida, e também tem multiplexagem sem bloqueio de 'head-of-line', tornando-o mais eficiente.

E as desvantagens, no entanto, incluem que é uma tecnologia mais recente e, portanto, menos suportada do que os 'web sockets', e pode ser complexo de implementar e depurar.

E, portanto, é melhor para aplicações que exigem conexões mais rápidas e resiliência contra perda de pacotes, algo como rastreamento de viagens.

E, embora a Uber use 'QUIC' no seu ambiente de produção devido ao seu desempenho superior em diversas condições de rede, é um tópico que eles aprofundam no seu blog de engenharia, que eu linkei abaixo.

Neste design de sistema, vamos usar 'web sockets' e a razão para isso é porque, num cenário de entrevista, por serem amplamente compreendidos, são fáceis de implementar e eficazes para demonstrar os conceitos-chave de comunicação bidirecional em tempo real, necessária para aplicações de partilha de viagens,

sabe, atualizações de localização de motoristas.

E, portanto, se quiser saber mais sobre estas técnicas, vou deixar um link para um vídeo abaixo onde aprofundo todas as quatro técnicas.

Então, voltando ao fluxo de atualização de localização do motorista, um motorista irá primeiro conectar-se ao 'gateway' da API.

O 'gateway' estabelecerá então uma conexão com o servidor 'web socket' do motorista, e depois o que acontecerá é que o servidor 'web socket' do motorista receberá atualizações de localização periodicamente, talvez a cada 10 ou 15 segundos, da aplicação do motorista.

E depois enviará isso para a fila de localização.

E, portanto, os servidores 'web socket' do motorista são escalados horizontalmente para lidar com um grande número de conexões concorrentes.

E, portanto, é o serviço de localização que irá então retirar essas notificações da fila de localização.

E, portanto, o próximo tópico em que precisamos aprofundar são as técnicas de indexação geoespacial, e estas são formas pelas quais seremos capazes de identificar motoristas que estão perto de passageiros.

E, portanto, vamos analisar três técnicas. A primeira é o 'geohashing', que basicamente codifica a latitude e a longitude numa curta cadeia alfanumérica.

E, portanto, tem este sistema de grade, que divide o mundo numa grade de células, permitindo pesquisas de proximidade, e quanto mais longa a cadeia, mais granular a pesquisa se torna.

E as vantagens incluem que é muito simples de implementar, é bom para consultas de áreas retangulares, mas as desvantagens incluem que há tamanhos de células variáveis em diferentes latitudes devido à curvatura da Terra.

'Quadtrees' é outra abordagem, e é uma estrutura de árvore hierárquica que divide o espaço em quatro quadrantes recursivamente, e as vantagens disto incluem que é eficiente para dados dinâmicos e também é adaptável a densidades de dados variáveis.

o que será muito útil se pensarmos, sabe, numa cidade como Nova Iorque que pode ter muitos passageiros e motoristas a tentar corresponder.

enquanto que em áreas rurais não há tanto.

No entanto, as desvantagens incluem a sua implementação mais complexa e pode ser menos eficiente para grandes conjuntos de dados.

E a última é a indexação H3.

E este é o índice espacial hierárquico hexagonal da Uber.

E, portanto, usa mosaicos hexagonais para uma melhor uniformidade espacial.

As vantagens incluem a redução da distorção e é eficiente para consultas de vizinhos mais próximos K.

No entanto, as desvantagens incluem ser mais complexo e pode exigir um esforço adicional para integrar.

E, portanto, para este design de sistema, acho que é bom mostrar ao entrevistador um conhecimento dos três.

E se quiser aprofundar a indexação H3, acho que isso pode ser muito útil.

Mas para este design de sistema, vamos manter o geohashing pela sua simplicidade e desempenho suficiente para as necessidades da nossa aplicação.

Então, de volta ao fluxo de atualização da localização do motorista. Então, novamente, o serviço de localização irá retirar a mensagem da fila.

E converterá as coordenadas GPS para um geohash e, em seguida, atualizará a cache de localização.

E, portanto, isto pode ser um armazenamento de dados em memória, como o Redis com indexação geoespacial para acesso rápido aos dados.

E depois também poderíamos ter políticas de expiração para remover motoristas inativos da cache de localização.

E, portanto, este fluxo é crucial porque queremos saber onde estão todos os nossos motoristas e ser capazes de armazenar esses dados de forma eficiente.

De modo que, quando os nossos passageiros começarem a tentar corresponder, estejamos apenas a escolher motoristas que estejam próximos.

Então, o próximo fluxo que vamos analisar é o fluxo de pedido de viagem do utilizador.

Então, o passageiro abrirá a aplicação de partilha de viagens no seu dispositivo móvel e, em seguida, a aplicação iniciará uma conexão com o servidor websocket de viagens através do gateway da API.

E, portanto, este gateway ajudará a estabelecer esta conexão com o serviço websocket do passageiro, o que permitirá a comunicação em tempo real para atualizações como mudanças de estado da viagem e rastreamento da localização do motorista.

E, portanto, o gateway também realizará autenticação, autorização e implementará limitação de taxa.

E, portanto, quando o passageiro se conecta ao serviço websocket do passageiro, ele subscreverá um tópico específico num message broker.

Por exemplo, isto poderia ser implementado com algo como o Kafka que está associado a esse passageiro.

Então, poderia usar um hash do ID do passageiro para criar um nome de tópico único e seguro.

E isto poderia facilitar a entrega de notificações personalizadas em tempo real a esse passageiro, como a aceitação da viagem por um motorista.

Então, o passageiro poderia então enviar um pedido POST com as suas localizações de recolha e destino para o endpoint de estimativa de tarifas da API no serviço de viagens através do gateway da API.

Para obter uma lista de todas as tarifas para diferentes pontos de preço, então poderia ser economia, Uber XL.

E, portanto, isto poderia então utilizar um serviço de mapeamento de terceiros como o Google Maps ou o Mapbox para gerar a melhor rota entre as localizações de recolha e destino.

E, portanto, as tarifas poderiam então ser calculadas para diferentes viagens, como eu disse, Uber economia, XL, com base em vários fatores, incluindo distância, tempo, condições de tráfego, fatores de procura, sabe, preços de pesquisa dinâmica.

E depois poderia armazená-lo numa base de dados.

E, portanto, aqui, uma base de dados SQL como o PostgreSQL poderia ser uma boa opção, pois suporta os princípios ACID.

Ou seja, atomicidade, consistência, isolamento, durabilidade, para garantir que as transações são processadas de forma fiável.

O que é crucial para operações financeiras como cálculos de tarifas e atualizações de estado da viagem.

E, portanto, o utilizador será então apresentado com as opções de tarifa disponíveis.

E, em seguida, quando um passageiro selecionar uma tarifa preferida, isso enviará um pedido POST para o endpoint de pedido de viagens da API para o serviço de viagens.

O que criará uma nova entrada de viagem na base de dados com o estado 'criado'.

E também pode implementar algum bloqueio otimista ou pessimista na base de dados para evitar entradas de viagem duplicadas ou atualizações conflitantes durante o tráfego intenso.

Uma mensagem pode então ser enviada para a fila de atribuição de motoristas para processamento.

E esta fila desacopla a criação da viagem da atribuição do motorista, o que melhorará a fiabilidade e a escalabilidade do nosso sistema.

Então, o serviço de atribuição de motoristas irá então retirar mensagens da fila de atribuição de motoristas.

E usará então o geohashing para converter as coordenadas de recolha do passageiro num geohash.

Que, novamente, é uma estrutura de dados espacial hierárquica que codifica localizações geográficas numa curta string alfanumérica.

Então, usará o prefixo do geohash para encontrar motoristas na vizinhança imediata.

E, portanto, pode rapidamente restringir os motoristas potenciais pesquisando dentro de uma célula geohash específica.

E se não forem encontrados motoristas suficientes, pode então expandir a pesquisa para geohashes vizinhos.

E pode continuar este processo até que um número suficiente de motoristas seja identificado.

é identificado o número de motoristas candidatos.

E assim, os motoristas são priorizados usando o seu algoritmo de pontuação, talvez com base em fatores como a proximidade ao passageiro, tipo de veículo, compatibilidade, estado do motorista, etc.

E poderíamos também usar um bloqueio distribuído, algo como um bloqueio baseado em Redis, para garantir que o pedido de viagem seja oferecido a um motorista de cada vez, para evitar que vários motoristas aceitem a mesma viagem.

E assim, enviará um pedido de viagem ao motorista de maior prioridade primeiro.

Então, poderíamos utilizar um serviço de notificação para enviar notificações push, como o Firebase Cloud Messenger para Android ou o Apple Push Notification Service para iOS.

E poderíamos definir um tempo limite de talvez 15 segundos para o motorista responder.

Portanto, se o motorista aceitar, o estado da viagem é atualizado em conformidade.

Caso contrário, se não houver resposta ou se for recusado, poderíamos então libertar o bloqueio e prosseguir para notificar o próximo motorista na lista.

E depois repetir esse processo até que a viagem seja aceite ou a lista esteja esgotada.

E assim, novamente, o bloqueio é usado aqui para garantir que, a qualquer momento, apenas um motorista detenha o bloqueio para o pedido de viagem, para que não tenhamos vários motoristas a aceitar a mesma viagem.

Então, quando um motorista aceita uma viagem, isto enviará um pedido PUT ao serviço de viagens para confirmar a aceitação da viagem.

O pedido inclui o token web JSON do motorista no seu cabeçalho de autorização, que contém o ID do motorista e outras reivindicações de autenticação, e isto garante que apenas motoristas autenticados podem aceitar pedidos de viagem.

Podemos então atualizar o estado da viagem na base de dados de 'criado' para 'aceite', e depois realizar a atualização como uma transação atómica para evitar condições de corrida e garantir a integridade dos dados.

E então o serviço de viagens pode criar uma mensagem que inclui que o motorista aceitou a viagem, e incluir o nome do motorista, foto de perfil, informações do veículo e tempo estimado de chegada.

E assim, o ID do passageiro é incluído na resposta da atualização da base de dados, permitindo que o serviço de viagens construa o tópico Kafka do passageiro usando esse método seguro de hashing do ID do passageiro.

O serviço de websocket do passageiro já está subscrito ao tópico do passageiro no Kafka, que foi estabelecido quando a aplicação do passageiro se conectou e autenticou.

E assim, esta conexão websocket persistente é então usada para enviar essa notificação para a aplicação do passageiro em tempo real.

Então, aqui está a arquitetura completa. Espero que faça muito mais sentido aqui.

Gosto de tê-lo numa única imagem para que possa ter esta imagem mental, para que sempre que vá a uma entrevista, tenha esta imagem mental que pode traçar.

Hum, pode precisar de ouvi-lo uma ou duas vezes, mas espero que, quando o rever, faça sentido.

E assim, esperamos ter aprofundado o suficiente para que, independentemente do que o seu entrevistador lhe apresentar, consiga lidar com qualquer uma das suas principais perguntas e ter sucesso nessa entrevista.

Então, em termos de pontos de discussão adicionais, poderíamos falar sobre escalabilidade.

Então, poderíamos falar sobre escalar o cluster Redis de localização.

Assim, poderia usar o cluster Redis para particionar dados por região ou ID de motorista, e configurar configurações de réplica mestre com o Redis Sentinel para failover.

Depois, há também a escalabilidade da base de dados PostgreSQL.

Para escalabilidade de leitura, poderia implementar réplicas de leitura e balanceamento de carga para operações de leitura. E para escalabilidade de escrita, talvez usar particionamento ou sharding como uma opção viável.

E também poderia escalar os servidores websocket usando sessões persistentes ou balanceamento de carga ao nível do TCP.

Hum, e depois talvez otimizar o uso de recursos e implementar mecanismos de heartbeat para garantir uma gestão de conexão adequada.

E depois, em termos de segurança, para autenticação e autorização, poderia usar autenticação baseada em tokens, como JWTs, e impor controlo de acesso baseado em funções.

E para a encriptação de dados, pode encriptar dados em trânsito usando TLS e SSL, e em repouso nas bases de dados também.

E depois, para monitorização e registo, se pensar em monitorização de sistema, poderia usar ferramentas como Prometheus e Grafana para métricas em tempo real, CPU, memória e latência, bem como implementar verificações de saúde e ferramentas de monitorização de aplicações para monitorizar o desempenho do servidor.

E finalmente, poderia ter um sistema de registo centralizado, para agregar registos com a stack ELK ou Graylog, e talvez empregar registo estruturado, por exemplo, usando JSON, e configurar alertas para eventos críticos.

Então, espero que tenha tirado algum proveito disto. Se quiser ver o artigo completo, está em techprep.app.

E se puder gostar, subscrever e partilhar com um amigo, se lhe foi útil, ajuda muito o canal. E espero que...