Enfoque de 5 pasos para resolver problemas de diseño:
- Generación de casos de uso : reúna todos los casos de uso posibles
- Restricciones y análisis : cuántos usuarios, cuántos datos, etc.
- Diseño básico : diseño más básico. Pocos usuarios-caso.
- Cuellos de botella : encuentre los cuellos de botella y resuélvalos.
- Escalabilidad : gran cantidad de usuarios. 4 y 5 steploop. entrará hasta que obtengamos una respuesta satisfactoria
Diseña un servicio de acortamiento como Bitly
Caso de uso
- ¿Qué hace que NP-hard sea más difícil?
- Cómo resolver el problema de los módems (SPOJ.com - Problema EC_MODE) en SPOJ
- ¿Qué es un árbol de recursión?
- Cómo hacer que los algoritmos sean eficientes
- Si factoro números grandes en [matemáticas] O (n ^ 2) [/ matemáticas] ¿puedo ganar dinero con eso?
Caso de uso básico:
1. El acortamiento toma una URL y devuelve una URL corta.
2. La redirección toma una URL corta y redirige a la URL original.
3. URL personalizada.
4. Alta disponibilidad del sistema.
Casos de uso adicionales:
1. Analytics
2. Caducidad automática del enlace.
3. Eliminación manual de enlaces.
4. URL específica de la empresa.
5. UI o solo API
Análisis de requisitos / Matemáticas
Primero, necesitamos encontrar el patrón de uso.
Puede solicitar directamente estos datos al entrevistador o puede obtenerlos utilizando algunos datos que el entrevistador proporciona. Supongamos que el entrevistador dice que habrá mil millones de solicitudes por mes. Además, de estas 10% de veces, es una nueva solicitud y el 90% de las veces, es una redirección de la URL ya acortada. Anotemos los datos que obtenemos.
1. 1BN solicitudes por mes
2. 10% son para URL / acortamiento nuevos y 90% son para redireccionamiento.
3. Nuevas URL por mes es 100MLN
4. Solicitudes por segundo 1BN / (30 * 24 * 3600) = 385. Aproximadamente, puede asumir que 400 solicitudes por segundo.
5. Número total de URL almacenadas en 5 años. 5 * 12 * 100 MLN = URL 6BN en 5 años.
6. Supongamos que el espacio requerido por cada URL es de 500bytes.
7. Supongamos que el espacio requerido por cada código Hash para las URL correspondientes es de 6bytes de longitud.
8. Datos totales que necesitamos almacenar en cinco años. 3 TB para todas las URL y 36 gb para hashes
6,000,000,000 * 500 bytes = 3 terabytes
6,000,000,000 * 6 bytes = 36 gigabytes
9. Nuevas solicitudes de escritura de datos por segundo: 40 * (500 + 6): 20k
Diseño básico
Servidor web: proporcione el sitio web para el servicio Bitly donde los usuarios pueden generar la URL corta.
Servidor de aplicaciones: proporciona los siguientes servicios:
1. Servicio de acortamiento
2. Servicio de redireccionamiento
3. Clave = Función hash (URL)
Servidor de base de datos:
1. Realice un seguimiento de la asignación de hash a URL.
2. Funciona como una enorme Hash-Table almacena la nueva asignación y recupera la clave dada de asignación anterior.
Embotellamiento
1. El tráfico no es mucho
2. El almacenamiento de datos puede ser un problema.
Escalabilidad
Servidor de aplicaciones:
1. Comience con la máquina individual.
2. Pruebe hasta dónde llega.
3. Hacemos una escala vertical por algún tiempo.
4.Agregue balanceador de carga y un grupo de máquinas para manejar picos y aumentar la disponibilidad.
Almacenamiento de datos:
1. miles de millones de objetos
2. Cada objeto es pequeño
3. No hay relación entre los objetos.
4. son más que escribir.
5. 3 TB de URL y 36 GB de hash.
MySQL:
1.Ampliamente utilizado
2. Una tecnología madura
3. paradigmas de escala limpia (maestro / esclavo, maestro / maestro)
4.Utilizado por Facebook, Google, Twitter, etc.
5. La búsqueda de índice es muy rápida.
Mapeos:
1. Use solo la tabla MySQL con dos campos.
2. Cree un índice único en el hash que queremos mantener en la memoria para acelerar las búsquedas.
3. Escalado vertical de MySQL por un tiempo
4. Partición de datos en muchas particiones.
5. Maestro-esclavo (leer del esclavo y escribir al maestro).
6. Finalmente, particione los datos tomando el primer carácter del hash mod el número de particiones
” Resolución de problemas en estructuras de datos y algoritmos “, escrito en varios lenguajes como C, C ++, Java, C #, Python, etc. Número de diagramas para explicar varios conceptos. También contiene un capítulo de Diseño del sistema al final que brindará un enfoque sistemático para resolver los problemas de diseño en una Entrevista.
Algunos problemas que había discutido en el último capítulo son:
- ¿Cómo diseñarías Facebook? ¿Cómo diseñarías un poco? etc.
- También se discute cómo diseñaría un sistema de ascensor o un sistema de restaurante, etc.
Los enlaces de los libros en Amazon están abajo:
1. Resolución de problemas en estructuras de datos y algoritmos utilizando C
2. Resolución de problemas en estructuras de datos y algoritmos usando C ++
3. Resolución de problemas en estructuras de datos y algoritmos utilizando Java
4. Resolución de problemas en estructuras de datos y algoritmos con C #
5. Resolución de problemas en estructuras de datos y algoritmos usando Python