Supongo que podrían usar el filtro Bloom para verificar si no se toma la identificación. El filtro Bloom es un:
Estructura de datos probabilística de espacio eficiente, concebida por Burton Howard Bloom en 1970, que se utiliza para probar si un elemento es miembro de un conjunto
La consulta “¿Sale ID [matemática] x [/ matemática]” devuelve “posiblemente en el conjunto” o “definitivamente no en el conjunto”, es decir, son posibles coincidencias con falsos positivos pero no con falsos negativos.
- ¿Qué puede construir un desarrollador front-end y back-end en solo 2 semanas o un mes?
- ¿Cómo funcionan juntas las tecnologías front-end y back-end?
- Debe desarrollar un backend para una red social con solo Java, Phyton y Node.JS. ¿En qué partes del back-end escribirías en qué idioma?
- ¿Qué es un back-end?
- ¿Cuál es la forma más fácil para que un desarrollador de back-end cree una interfaz de usuario atractiva para sus páginas web?
Así es como probablemente podría funcionar:
Antes de que sus usuarios creen videos, necesita crear una matriz de bits vacía de [math] m [/ math] bits, todo configurado en [math] 0 [/ math]. También debe elegir [math] k [/ math] diferentes funciones hash, cada una de las cuales identifica el hash a una de las posiciones de matriz [math] m [/ math] con una distribución aleatoria uniforme. Esta constante [matemática] k [/ matemática] es típicamente menor que [matemática] m [/ matemática] y [matemática] m [/ matemática] es proporcional al número de elementos que se agregarán (en el caso de YouTube [matemática] 64 ^ {11} [/ matemáticas]). Esta elección de [matemática] k [/ matemática] y la constante de proporcionalidad de [matemática] m [/ matemática] están determinadas por la tasa de falsos positivos deseada del filtro.
Los filtros Bloom también tienen la propiedad inusual de que el tiempo necesario para agregar elementos o para verificar si un elemento está en el conjunto es una constante fija, [matemática] O (k) [/ matemática], completamente independiente del número de elementos que ya están en el set
Ahora, cuando alguien quiere crear un nuevo video, genera una identificación aleatoria. Luego, alimenta cada una de las funciones hash [math] k [/ math] con su ID y obtiene las posiciones [math] k [/ math] en su matriz de bits. Si alguna de estas posiciones [math] k [/ math] en su matriz de bits es [math] 0 [/ math], este ID definitivamente no se toma y puede usarlo, y para usarlo debe poner [math] 1 [/ math] a cada una de estas [math] k [/ math] posición a su conjunto de bits. Y si todas estas k posiciones en su matriz de bits son [math] 1 [/ math], entonces esta ID se “posiblemente toma” para que genere la nueva.
Hagamos un cálculo rápido. Wiki declara que para una probabilidad positiva falsa dada [matemática] p [/ matemática], la longitud del filtro Bloom [matemática] m [/ matemática] es proporcional al número de elementos que se filtran [matemática] n [/ matemática], suponiendo se utiliza el valor óptimo de [math] k [/ math]:
[matemáticas] m = – (n * ln (p)) / (ln (2)) ^ 2 [/ matemáticas]
Donde el número óptimo de funciones hash k se puede calcular como:
[matemáticas] k = m * ln (2) / n [/ matemáticas]
En el caso de YouTube, [math] n [/ math] es igual a [math] 64 ^ {11} [/ math], y digamos que quieren una probabilidad de falso positivo de [math] 0.01 \% [/ math], eso significa que es necesario usar [math] m = 1414504950550903128064 [/ math] bits, que es alrededor de 176813 petabytes y [math] k = 13 [/ math] funciones hash. Solo para ponerlo en perspectiva: en agosto de 2011, se informó que IBM había construido la matriz de almacenamiento más grande de la historia, con una capacidad de 120 petabytes. Por lo tanto, tener 11 caracteres y [matemáticas] 64 ^ {11} [/ matemáticas] espacio de identificación es poco práctico e imposible de almacenar en el filtro Bloom, pero como dijo Tom, es prácticamente imposible ejecutar identificaciones.
Debido a que es prácticamente imposible ejecutar ID’s, podríamos tratar de reducir nuestro espacio de ID a un valor que todavía es prácticamente imposible quedarse sin ID, pero es práctico usar el filtro Bloom.
Descubrí que usando [math] 64 ^ 7 [/ math] ID space y con los usuarios cargando 1 millón de videos por día (la respuesta de Rasty Turek a ¿Cuántos videos se han subido a YouTube?) Necesitaría alrededor de 12049 años para ejecutar ID, pero solo necesitará 84311065110619 bits para su filtro Bloom, que es de alrededor de 10 TB y eso no es nada para YouTube, y también necesita funciones hash [math] k = 8 [/ math].
Por lo tanto, al generar [math] 11 [/ math] ID de carácter, debe consultar el filtro Bloom solo con los primeros [math] 7 [/ math] caracteres de la ID recién generada.
