GitHub desarrolla su propio motor de búsqueda de código en Rust
GitHub ha creado su propio motor de búsqueda de código llamado Proyecto Blackbird, desarrollado desde cero en Rust. La decisión de crear su propio motor se debió a que las soluciones disponibles en el mercado no cumplían con los requisitos de escala en los que GitHub opera.
El motor de búsqueda de código de GitHub ofrece funciones específicas para búsquedas de código, como búsqueda con identificadores, puntuaciones, subcadenas, expresiones regulares y comodines. Además, es capaz de realizar consultas globales en 200 millones de repositorios y de indexar cambios de código en cuestión de minutos. Con un clúster que cuenta con 5184 vCPU, 40 TB de RAM y 1,25 PB de almacenamiento de respaldo, el índice de búsqueda de código de GitHub es el más grande de su tipo. Además, puede manejar una carga de consultas de 200 solicitudes por segundo en promedio e indexar más de 53 mil millones de archivos fuente.
Código de indexación
Para indexar los documentos, GitHub utiliza índices que son claves para listas ordenadas de ID de documentos. Por ejemplo, para la búsqueda por lenguajes de programación, se escanean los documentos para detectar en qué lenguaje están escritos y se les asigna una identificación de documento. Luego, se crea un índice invertido donde el lenguaje de programación es la clave y la lista de ID de documentos donde aparece el lenguaje de programación es el valor.
N-gramas
El motor de búsqueda de código de GitHub utiliza un tipo especial de índice invertido llamado índice de n-gramas. Este índice permite encontrar subcadenas de contenido y es fundamental para implementar la funcionalidad “buscar mientras escribe”. Los n-gramas son secuencias de n caracteres o palabras extraídas de un texto determinado. Por ejemplo, en la indexación de 3 gramos, la palabra “Python” se divide en “pyt”, ”yth”, ”tho” y “hon”. Estos n-gramas se indexan en una estructura de datos que se asocia con la ubicación del documento donde ocurren.
Almacenamiento direccionable de contenido
GitHub utiliza una técnica llamada almacenamiento direccionable de contenido para reducir el espacio de almacenamiento y eliminar contenido duplicado. En lugar de guardar los datos según el nombre del archivo o la ubicación, se almacenan en función de un hash único generado por el contenido. Esto se logra mediante funciones hash como MD5, SHA-1, SHA-2 y SHA-256. El almacenamiento direccionable de contenido garantiza la integridad de los datos y permite acceder a diferentes versiones de los mismos. Esta técnica también es utilizada por las CDNs para almacenar en caché y distribuir datos de manera eficiente en todo el mundo.
Con el desarrollo de su propio motor de búsqueda de código y el uso de técnicas innovadoras como el almacenamiento direccionable de contenido, GitHub continúa mejorando la experiencia de búsqueda y navegación en su plataforma, brindando a los desarrolladores herramientas más eficientes y precisas para encontrar el código que necesitan.
GitHub revoluciona el almacenamiento de datos con su sistema único
GitHub, la plataforma líder en alojamiento de repositorios de código, ha implementado un sistema de almacenamiento de datos revolucionario que ha reducido significativamente el tamaño total de los datos y ha mejorado la escalabilidad del sistema.
Después de la compresión, el índice completo ahora ocupa solo 25 TB, lo que representa aproximadamente una cuarta parte de los datos originales. Esto incluye todos los índices, incluidos los índices ngram y todo el contenido único comprimido. El almacenamiento de contenido direccionable ha sido clave para lograr esta reducción de tamaño.
Una de las ventajas del nuevo sistema de almacenamiento de GitHub es su capacidad para escalar horizontalmente. Los datos se distribuyen entre fragmentos de manera uniforme según el ID del objeto de blob de Git. Esto permite manejar más consultas por segundo (QPS) al distribuir las consultas entre fragmentos y distribuir los datos entre discos para aumentar el espacio de almacenamiento. Además, el tiempo de indexación de datos se ha reducido gracias a la optimización de los recursos de CPU y memoria de los hosts individuales.
Almacenamiento de código
Git, el sistema de control de versiones utilizado por GitHub, almacena sus datos basados en el hash de contenido como objetos blob en un almacén de objetos. Este almacén de objetos funciona como una tabla de base de datos clave-valor, donde cada objeto tiene un ID único que se utiliza para recuperarlo.
Aunque Git está diseñado principalmente para almacenar código, también puede almacenar otros tipos de datos no estructurados, como documentos, archivos de configuración, imágenes, PDF, entre otros. La clave única de cada dato (ID de objeto blob) permite su fácil recuperación.
En el almacén de objetos, los blobs representan datos sin procesar y no contienen metadatos como nombres de archivos, nombres de repositorios o información de propietarios. Esta información se almacena en árboles, que se combinan con los objetos blob para crear una jerarquía de archivos en un repositorio.
Código de ingesta e indexación
GitHub ha desarrollado un sistema eficiente para la ingesta e indexación de código. A través de un diagrama de alto nivel, se puede apreciar cómo funciona este proceso.
Con este nuevo sistema de almacenamiento de datos, GitHub ha logrado optimizar el rendimiento y la eficiencia de su plataforma, brindando a los usuarios una experiencia mejorada al trabajar con repositorios de código y otros tipos de datos no estructurados.
La tecnología detrás de la nueva búsqueda de código de GitHub
GitHub ha implementado una nueva función de búsqueda de código que utiliza tecnología avanzada para mejorar la eficiencia y la velocidad del proceso. En este artículo, exploraremos cómo funciona esta tecnología y cómo ha optimizado el sistema de búsqueda de GitHub.
Eventos y rastreadores de ingesta
Cuando se produce un cambio en un repositorio de GitHub, se genera un evento que se envía a través de Kafka. Este evento notifica a los rastreadores de ingesta del motor de búsqueda para que puedan procesar el cambio. Los rastreadores extraen símbolos del código, crean documentos y los almacenan en fragmentos a través de Kafka.
El sistema utiliza la codificación delta para reducir el tamaño de los índices de búsqueda. En lugar de almacenar todo el archivo, solo se guardan los cambios en el código. Esto acelera tanto el proceso de indexación como las consultas, evitando cálculos innecesarios del archivo completo. Esto es especialmente útil en un sistema donde el contenido cambia constantemente.
Optimización del orden de ingesta
El motor de búsqueda de GitHub optimiza el orden en el que se ingieren los archivos para aprovechar al máximo la codificación delta. Esto se logra mediante la creación de fragmentos de indexación que contienen índices de n-gramas con documentos. Estos fragmentos se compactan para agrupar índices más pequeños en índices más grandes, lo que permite realizar consultas eficientes antes de que el contenido se descargue al disco.
El proceso de indexación tiene una capacidad impresionante de publicar alrededor de 120,000 documentos por segundo. La indexación de 15.5 mil millones de documentos lleva aproximadamente 36 horas. Sin embargo, gracias a la indexación delta, que reduce la cantidad de documentos rastreados en más del 50%, el tiempo de indexación se reduce a solo 18 horas.
La optimización del orden de ingesta y la codificación delta
Para determinar el orden de ingesta óptimo y evaluar la similitud entre repositorios, GitHub ha desarrollado una nueva estructura de datos llamada filtro geométrico. Esta estructura de datos probabilística utiliza la aleatorización y la aproximación para almacenar y consultar datos de manera eficiente, incluso con cierto margen de error. El filtro geométrico construye un gráfico que representa los repositorios y calcula un árbol de expansión mínimo para determinar el orden de ingesta óptimo.
Aprendizajes sobre el diseño del sistema
Almacenamiento direccionable de contenido
GitHub utiliza el almacenamiento direccionable de contenido basado en hash para almacenar datos duplicados de manera eficiente. Este enfoque consiste en almacenar solo una copia original de los datos en la base de datos, mientras que las copias duplicadas apuntan a la misma ubicación de almacenamiento. Esto se logra mediante la generación de hashes únicos del contenido de los datos y utilizando estos hashes como claves en un sistema de almacenamiento basado en hash.
Fragmentación basada en hash
GitHub fragmenta los datos de manera uniforme utilizando una fragmentación basada en hash. Esto garantiza que los datos se distribuyan de manera equitativa entre los fragmentos, lo que facilita el acceso y la recuperación eficiente de los mismos. Además, esta técnica permite que las consultas se distribuyan uniformemente entre los nodos del clúster, evitando la sobrecarga en algunos nodos específicos.
Árboles para almacenar datos jerárquicos
Git utiliza la estructura de datos de árbol para almacenar la jerarquía de archivos en un repositorio. Los árboles son ideales para almacenar datos jerárquicos, ya que modelan de forma natural las relaciones entre padres e hijos. Esto facilita la navegación, la búsqueda y la clasificación de los datos con una latencia mínima.
En resumen, la nueva tecnología de búsqueda de código de GitHub utiliza una combinación de técnicas avanzadas, como la codificación delta, el filtro geométrico y la fragmentación basada en hash, para mejorar la eficiencia y la velocidad del proceso de búsqueda. Estas innovaciones demuestran el compromiso de GitHub con la mejora continua de su plataforma y su capacidad para satisfacer las necesidades de sus usuarios.
Sistemas de archivos: una solución eficiente para almacenar datos no estructurados
En el mundo del almacenamiento en la nube, existen diferentes enfoques para almacenar datos, como archivos, bloques y objetos. Sin embargo, cuando se trata de datos no estructurados con una clave única, el almacenamiento de objetos es la opción ideal.
GitHub, por ejemplo, utiliza el almacenamiento de objetos para almacenar no solo código, sino también imágenes, documentación y archivos PDF. Estos tipos de datos no siguen una estructura específica, por lo que el almacenamiento de objetos se adapta perfectamente a este caso de uso.
Una de las ventajas de los almacenes de objetos es que los datos se pueden acceder fácilmente a través de HTTP y compartir a través de redes de entrega de contenido. Esto permite almacenar y compartir datos heterogéneos como videos, archivos de audio e imágenes de manera eficiente.
Desacoplando módulos del sistema con una cola de eventos/agente de mensajes
En el caso de GitHub, se utiliza Kafka como intermediario de mensajes para desacoplar los módulos de rastreo e indexación. Este enfoque arquitectónico estándar permite un diseño de sistema flexible y débilmente acoplado.
La cola de eventos actúa como un adaptador entre los diferentes módulos del sistema, permitiendo una comunicación asincrónica sin bloqueo. Esto significa que los módulos no necesitan estar listos para procesar eventos simultáneamente, lo que facilita la escalabilidad y la eficiencia del sistema.
Explorando la arquitectura de mensajería en tiempo real de Slack
Si estás interesado en conocer más sobre arquitecturas de sistemas en tiempo real, te invitamos a leer nuestro estudio de caso sobre la arquitectura de mensajería en tiempo real de Slack. En este artículo, analizamos cómo Slack utiliza diferentes tecnologías para ofrecer una experiencia de mensajería fluida y confiable.
Aprende sobre diseño de sistemas distribuidos a escala web
Si deseas profundizar en los fundamentos del diseño de sistemas a gran escala, te recomendamos nuestra ruta de aprendizaje “De cero a dominio de la arquitectura de software”. Esta ruta consta de tres cursos diseñados para llevarte paso a paso desde los conceptos básicos hasta convertirte en un profesional en el diseño de sistemas distribuidos a escala web.
En estos cursos, aprenderás sobre arquitectura de software, infraestructura en la nube y diseño de sistemas distribuidos. Te proporcionaremos una experiencia de aprendizaje estructurada que te permitirá adquirir los conocimientos necesarios para diseñar sistemas similares a los utilizados por plataformas como YouTube, Netflix y ESPN.
Fuente de información: Ingeniería GitHub
¡No dudes en contactarme si tienes alguna pregunta! Si este contenido te resultó útil, te agradecería que lo compartieras para que más personas puedan beneficiarse de él.
¡Hasta la próxima! ¡Saludos!
