Muy buenas, me llamo Miguel y hoy les traigo un post.
Índice
Una guía de preparación para la entrevista de diseño de sistemas
En la industria tecnológica actual, comprender el diseño de sistemas es más importante que nunca. Con las aplicaciones cada vez más grandes, es importante diseñar patrones arquitectónicos que sean eficientes y confiables.
Ahora, el diseño de sistemas es a menudo un requisito para conseguir el trabajo de ingeniería de software de sus sueños.
Hoy, repasaremos los principios de diseño del sistema mediante el diseño de Instagram
y TinyURL
.
Este artículo cubrirá:
- Cómo diseñar
TinyURL
. - Cómo diseñar
Instagram
. - Recursos adicionales.
Cómo diseñar TinyURL
TinyURL
es un servicio web de acortamiento de URL que crea alias más cortos para URL largas. Al hacer clic en el enlace corto, los usuarios son redirigidos a la URL original.
Este servicio es útil porque los enlaces cortos ahorran espacio y permiten a los usuarios escribir URL largas más fácilmente.
Al diseñar una aplicación similar a TinyURL
, hay algunos requisitos funcionales y no funcionales a considerar.
Requerimientos no funcionales:
- El sistema debe tener una alta disponibilidad. Si el servicio falla, todos los enlaces cortos no serán funcionales.
- La redirección de URL debe ocurrir en tiempo real con una latencia mínima.
- Los enlaces abreviados no deben ser predecibles de ninguna manera.
Requerimientos funcionales:
- Cuando se le da una URL, nuestro servicio generará un alias más corto de la URL original. Este nuevo enlace se acortará ampliamente para que se pueda copiar y pegar fácilmente.
- El enlace corto debe redirigir a los usuarios al enlace original.
- Los usuarios deben tener la opción de elegir un enlace corto personalizado para su URL.
- Los enlaces cortos vencerán después de un período de tiempo predeterminado, pero los usuarios pueden especificar el tiempo de vencimiento.
Nuestro sistema tendrá una gran cantidad de lecturas. Habrá una gran cantidad de solicitudes de redirección en comparación con los nuevos acortamientos de URL.
Supongamos una proporción de 100: 1
entre lectura y escritura.
Suponiendo que tendremos 500 millones de nuevos acortamientos de URL por mes con una proporción de lectura / escritura
de 100: 1
, podemos esperar 50 mil millones
de redirecciones durante el mismo período:
100 * 500 M => 50 B
¿Cuáles serían las consultas por segundo (QPS) para nuestro sistema? Nuevos acortamientos de URL por segundo:
500 millones / (30 días * 24 horas * 3600 segundos) = ~ 200 URL / s
Teniendo en cuenta la proporción de lectura / escritura
de 100: 1
, las redirecciones de URL por segundo serán:
100 * 200 URL / s = 20 K / s
Supongamos que almacenamos cada solicitud de acortamiento de URL (y el enlace acortado asociado) durante cinco años.
Dado que esperamos tener 500 millones de URL nuevas cada mes , la cantidad total de objetos que esperamos almacenar será de 30 mil millones:
500 millones * 5 años * 12 meses = 30 mil millones
Supongamos que cada objeto almacenado tendrá aproximadamente 500 bytes (solo una estimación aproximada; profundizaremos más adelante). Necesitaremos 15 TB
de almacenamiento total:
30 mil millones * 500 bytes = 15 TB
Para las solicitudes de escritura, dado que esperamos 200 URL
nuevas cada segundo, el total de datos entrantes para nuestro servicio será de 100 KB
por segundo:
200 * 500 bytes = 100 KB / s
Para las solicitudes de lectura, dado que esperamos redirecciones de aproximadamente 20.000 URL
por segundo, el total de datos salientes para nuestro servicio sería de 10 MB
por segundo:
20 K * 500 bytes = ~ 10 MB / s
Si queremos almacenar en caché algunas de las URL activas a las que se accede con frecuencia, ¿cuánta memoria necesitaremos para almacenarlas?
Si seguimos la regla 80-20
, lo que significa que el 20%
de las URL generan el 80%
del tráfico, nos gustaría almacenar en caché estas URL activas.
Dado que tenemos 20.000
solicitudes por segundo, recibiremos 1.700
millones de solicitudes por día:
20K * 3600 segundos * 24 horas = ~ 1.7 mil millones
Para almacenar en caché el 20%
de estas solicitudes, necesitaremos 170 GB
de memoria:
0,2 * 1,7 mil millones * 500 bytes = ~ 170 GB
Una cosa a tener en cuenta aquí es que, dado que habrá muchas solicitudes duplicadas (de la misma URL), nuestro uso de memoria real será inferior a 170 GB
.
Podemos utilizar API REST
para exponer la funcionalidad de nuestro servicio. A continuación, se muestra un ejemplo de las definiciones de las API para crear y eliminar URL sin servicio:
createURL(api_dev_key, original_url, custom_alias=None, user_name=None, expire_date=None)
Parámetros:
-
Api_dev_key
(string
): la clave de desarrollador de API de una cuenta registrada. Esto se utilizará para limitar a los usuarios en función de su cuota asignada. -
Original_url
(string
): URL original que se acortará. -
Custom_alias
(string
): clave personalizada opcional para la URL. -
User_name
(string
): nombre de usuario opcional que se utilizará en la codificación. -
Expire_date
(string
): fecha de vencimiento opcional para la URL abreviada.
Devuelve (string
): una inserción exitosa devuelve la URL acortada. De lo contrario, devuelve un código de error.
deleteURL(api_dev_key, url_key)
Los url_key
es una cadena que delimita la URL abreviada que debe eliminarse. Volverá una eliminación exitosa URL Removed
.
Veamos algunas observaciones sobre los datos que estamos almacenando:
- El servicio necesita almacenar miles de millones de registros.
- El servicio es de mucha lectura.
- Cada objeto es pequeño (menos de
1K
). - No existen relaciones entre cada registro, excepto el almacenamiento, que el usuario creó con los enlaces cortos.
Para el esquema, necesitamos una tabla para almacenar información sobre las asignaciones de URL y otra base de datos para los datos del usuario que creó los enlaces cortos.
El mejor tipo de base de datos para usar sería un almacén de base de datos NoSQL como DynamoDB o Cassandra, ya que estamos almacenando miles de millones de filas sin relaciones entre los objetos.
La pregunta más importante para nuestro servicio es cómo generar una clave corta y única cuando se le da una URL. El enfoque que veremos hoy es codificar la URL real.
Podemos calcular un hash único (por ejemplo, MD5
, SHA256
, etc.) de la URL dada. Luego, el hash
puede codificarse para su visualización.
Esta codificación podría ser base36
([a-z ,0–9]
) o base62
([A-Z, a-z, 0–9]
). Si sumamos +
y /
, podemos usar la codificación Base64
.
Una pregunta razonable sería: «¿Cuál debería ser la longitud de la clave corta? ¿6
, 8
o 10
caracteres?»
- Usando la codificación
base64
, una clave de seis letras daría como resultado64⁶ = ~ 68,7
mil millones de cadenas posibles. - Usando la codificación
base64
, una clave de ocho letras daría como resultado64⁸ = ~ 281
billones de cadenas posibles - Con
68,7
mil millones de cadenas únicas, supongamos que las claves de seis letras serían suficientes para nuestro sistema.
Si usamos el algoritmo MD5
como nuestra función hash
, producirá un valor hash de 128 bits
. Después de la codificación base64
, obtendremos una cadena con más de 21
caracteres (ya que cada carácter base64
codifica seis bits
del valor hash
).
Ahora solo tenemos espacio para ocho caracteres por tecla corta. ¿Cómo elegiremos entonces nuestra llave?
Podemos tomar las primeras seis (u ocho) letras para la clave. Esto podría resultar en la duplicación de claves. Para resolver eso, podemos elegir algunos otros caracteres de la cadena de codificación o intercambiar algunos caracteres.
Posibles obstáculos al adoptar este enfoque:
- Si varios usuarios ingresan la misma URL, obtendrán el mismo enlace corto.
- Partes de la URL se pueden codificar como URL.
Soluciones alternativas:
- Para resolver algunos de estos problemas, podemos agregar un número de una secuencia a cada URL de enlace corto. Esto lo hace único incluso si varios usuarios proporcionan la misma URL.
- Otra posible solución es agregar la identificación del usuario a la URL de entrada. Esto no funcionaría si el usuario no hubiera iniciado sesión y tendríamos que generar una clave de unicidad.
Inevitablemente, necesitaremos escalar nuestra base de datos, lo que significa que tenemos que particionarla para que podamos almacenar información sobre miles de millones de URL.
Particionamiento basado en rango: podemos almacenar las URL en particiones separadas según la primera letra de su clave hash. Entonces, guardamos todas las URL con la primera letra de su clave hash
siendo A
en una partición y así sucesivamente.
Este enfoque es problemático porque conduce a servidores de bases de datos desequilibrados, creando una carga desigual.
Particionamiento basado en hash: con el particionado basado en hash
, podemos tomar un hash
del objeto que se almacena y luego calcular qué partición usar. La función hash
distribuirá aleatoriamente los datos en diferentes particiones.
A veces, este enfoque conduce a particiones sobrecargadas, que luego se pueden resolver usando hash consistente.
Nuestro servicio debería poder almacenar en caché las URL a las que se accede con frecuencia. Podemos hacer esto a través de una solución como Memcached
, que puede almacenar URL completas con hash
respectivos.
¿Cuánta memoria caché deberíamos tener? Al principio, podemos comenzar con alrededor del 20%
del tráfico diario y ajustar según los patrones de uso.
Según nuestras estimaciones anteriores, necesitaremos 170 GB
de memoria para almacenar en caché el 20%
del tráfico diario.
¿Qué política de desalojo de caché deberíamos utilizar? Debido a que queremos reemplazar un enlace con una URL más popular, podemos usar la política de uso menos reciente (LRU) para nuestro sistema.
Hay tres lugares donde podemos agregar una capa de equilibrio de carga a nuestro sistema:
- Entre clientes y servidores de aplicaciones.
- Entre servidores de aplicaciones y servidores de bases de datos.
- Entre servidores de aplicaciones y servidores de caché.
Al principio, podríamos simplemente usar un enfoque Round Robin que distribuye las solicitudes entrantes por igual entre los servidores. Esto es fácil de implementar y no genera gastos generales.
Para manejar este problema, se puede desarrollar una solución de balanceador de carga más inteligente que ajuste periódicamente el tráfico según su carga.
Diseñando Instagram
Instagram es una plataforma de redes sociales que permite a los usuarios compartir fotos y videos con otros usuarios. Como muchas otras plataformas de redes sociales, los usuarios pueden compartir su información de forma pública o privada.
Hoy, diseñaremos una versión simple de Instagram en la que los usuarios pueden compartir fotos, seguir a otros usuarios y acceder al servicio de noticias. Consiste en las mejores fotos de las personas a las que sigue el usuario.
Al diseñar una aplicación similar a Instagram, hay algunos requisitos funcionales y no funcionales a considerar.
Requerimientos no funcionales:
- El servicio debe tener una alta disponibilidad.
- La latencia aceptable del sistema debe ser de alrededor de
200
milisegundos para las noticias. - El sistema debe ser altamente confiable, de modo que nunca se pierda ninguna foto o video en el sistema.
Requerimientos funcionales:
- El usuario debe poder realizar búsquedas basadas en títulos de fotos o videos.
- El usuario debe poder cargar, descargar y ver fotos y videos.
- El usuario debería poder seguir a otros usuarios.
- El sistema debería poder generar una fuente de noticias mostrada que consta de las mejores fotos y videos de las personas a las que sigue el usuario.
Algunas cosas que no estarán dentro del alcance de este proyecto son agregar etiquetas a las fotos, buscar fotos con etiquetas, comentar fotos, etiquetar usuarios, etc.
- Supongamos que tenemos
500
millones de usuarios totales con1
millón de usuarios activos diarios. -
2
millones de fotos nuevas cada día,23
fotos nuevas cada segundo. - Tamaño medio de archivo de foto
=> 200 KB
. - Espacio total requerido para un día de fotos.
2 M * 200 KB => 400 GB
- Espacio total requerido durante
10
años:
400GB * 365 (días al año) * 10 (años) ~ = 1425TB
En un nivel alto, el sistema debería poder ayudar a los usuarios a cargar sus medios y a otros usuarios a poder ver las fotos.
Por lo tanto, nuestro servicio necesita servidores para almacenar las fotos y videos y también otro servidor de base de datos para almacenar los metadatos de los medios.
Si bien podríamos adoptar un enfoque sencillo al almacenar el esquema anterior en un sistema de gestión de bases de datos relacionales (RDBMS
), surgirían algunos desafíos al usar una base de datos relacional, especialmente al escalar la aplicación.
Podemos almacenar el esquema anterior con pares clave-valor
utilizando una base de datos NoSQL
.
Los metadatos de las fotos y videos pertenecerá a una mesa en la que el key
sería el PhotoID
y value
sería un objeto que contiene PhotoLocation
, UserLocation
, CreationTimestamp
, etc.
El key
de la UserPhoto
tabla sería UserID
, y el value
sería la lista de los PhotoIDs
que posee el usuario, que se almacenarán en diferentes columnas. Este patrón será similar al de la UserFollow
tabla.
Las fotos y videos se pueden almacenar en un almacenamiento de archivos distribuido como HDFS.
Estimemos cuántos datos se incluirán en cada tabla y cuánto almacenamiento total necesitaremos durante 10
años.
Suponiendo que cada int
y dateTime
es de cuatro bytes, cada fila en la tabla del usuario va a ser de 68 bytes:
UserID (4 bytes) + Nombre (20 bytes) + Email (32 bytes) + DateOfBirth (4 bytes) + CreationDate (4 bytes) + LastLogin (4 bytes) = 68 bytes
Si tenemos 500
millones de usuarios, necesitaremos 32 GB
de almacenamiento total:
500 millones * 68 ~ = 32 GB
Cada fila de la tabla de fotos tendrá 284 bytes:
PhotoID (4 bytes) + UserID (4 bytes) + PhotoPath (256 bytes) + PhotoLatitude (4 bytes) + PhotLongitude (4 bytes) + UserLatitude (4 bytes) + UserLongitude (4 bytes) + CreationDate (4 bytes) = 284 bytes
Si se cargan 2
millones de fotos nuevas todos los días, necesitaremos 0,5 GB
de almacenamiento durante un día:
2M * 284 bytes ~ = 0.5GB por día
Durante 10
años, necesitaremos 1,88 TB
de almacenamiento.
Cada fila de la tabla UserFollow
constará de 8 bytes
. Si tenemos 500
millones de usuarios y cada usuario sigue una media de 500
usuarios, necesitaríamos 1,82 TB
de almacenamiento para la tabla UserFollow
:
500 millones de usuarios * 500 seguidores * 8 bytes ~ = 1,82 TB
El espacio total requerido para todas las mesas durante 10
años será de 3,7 TB
:
32 GB + 1,88 TB + 1,82 TB ~ = 3,7 TB
La carga de fotos suele ser un proceso lento porque van al disco, mientras que las lecturas son mucho más rápidas. La carga de usuarios consumirá todas las conexiones disponibles debido a la lentitud del proceso.
Por lo tanto, las lecturas no se pueden servir cuando el sistema está cargado con solicitudes de escritura. Para manejar este cuello de botella, podemos dividir las lecturas y escrituras en servidores separados para que el sistema no se sobrecargue.
Esto nos permitirá optimizar cada operación de manera eficiente.
Debido a que la aplicación enfatiza la confiabilidad, no podemos perder ningún archivo. Por lo tanto, almacenaremos múltiples copias de cada foto y video para que incluso si un servidor muere, el sistema puede recuperar los medios de un servidor de copia.
Este diseño se aplicará al resto de componentes de nuestra arquitectura. Tendremos múltiples copias de los servicios ejecutándose en el sistema de modo que incluso si un servicio muere, el sistema seguirá funcionando.
Crear redundancia en el sistema nos permite crear una copia de seguridad en medio de una falla del sistema.
Un posible esquema para la fragmentación de metadatos es la partición basada en PhotoID. Si podemos generar PhotoID
únicos primero y luego encontrar un número de fragmento PhotoID % 10
, los problemas anteriores se habrán resuelto.
En este caso, no necesitaríamos agregar ShardID
con PhotoID
, ya que PhotoID
en sí será único en todo el sistema.
¿Cómo podemos generar PhotoIDs
? Aquí, no podemos tener una secuencia de incremento automático en cada fragmento para definir PhotoID
porque primero necesitamos conocer PhotoID
para encontrar el fragmento donde se almacenará.
Una solución podría ser dedicar una instancia de base de datos separada para generar ID de incremento automático. Si nuestro PhotoID
puede caber en 64 bits
, podemos definir una tabla que contenga solo un campo de ID de 64 bits
.
Entonces, cada vez que nos gustaría agregar una foto en nuestro sistema, podemos insertar una nueva fila en esta tabla y tomar esa identificación como nuestro PhotoID
de la nueva foto.
¿No sería esta base de datos generadora de claves un único punto de falla? Sí, lo sería. Una solución alternativa para eso podría ser la definición de dos bases de datos de este tipo, una que genere ID con números pares y la otra con números impares.
Para MySQL, el siguiente script puede definir tales secuencias:
KeyGeneratingServer1: auto-increment-increment = 2 auto-increment-offset = 1 KeyGeneratingServer2: auto-increment-increment = 2 auto-increment-offset = 2
Podemos poner un equilibrador de carga frente a estas dos bases de datos para realizar un Round Robin entre ellas y lidiar con el tiempo de inactividad.
Ambos servidores pueden estar desincronizados, y uno genera más claves que el otro, pero esto no causará ningún problema en nuestro sistema.
Podemos extender este diseño definiendo tablas de identificación separadas para usuarios, comentarios de fotos u otros objetos presentes en nuestro sistema.
El servicio necesitaría un sistema de entrega de fotografías a gran escala para entregar datos a los usuarios a nivel mundial.
Podríamos acercar el contenido a los usuarios utilizando servidores de caché que están distribuidos geográficamente.
¡Bien hecho! Ahora, deberías tener una buena idea de cómo diseñar una aplicación como Instagram y TinyURL. Otras buenas aplicaciones para cubrir son Dropbox, Facebook Messenger, YouTube, Uber backend, Twitter y más.
Aprender los estándares de la industria del diseño de sistemas a través de ejemplos del mundo real lo empoderará no solo en las entrevistas sino también en el trabajo.
Para comenzar, hemos compilado una lista de glosario de los conceptos básicos de diseño de sistemas que debe conocer:
- Escalabilidad (horizontal frente a vertical).
- Balanceo de carga.
- Almacenamiento en caché.
- Partición de datos.
- Índices.
- Proxies.
- Redundancia y replicación.
- SQL frente a NoSQL.
- Hash consistente.
- Sondeo largo frente a WebSockets frente a eventos enviados por el servidor.
- Teorema de CAP.
- Patrones de diseño del sistema (es decir, método de fábrica, observador, constructor, estado, etc.).
Feliz aprendizaje. Gracias por leer este post.
Añadir comentario