• Author / Uploaded
• Roman Edrroman

• Categories
• Muestreo (Estadísticas)
• Metadatos
• Estadísticas
• Aleatoriedad
• Archivo de computadora

Citation preview

El caso para el muestreo en sistemas de archivos muy grandes George Goldberg, Danny Harnik, Dmitry Sotnikov IBM Research – Haifa , { georgeg, dannyh, dmitrys } @ il.ibm.com Resumen: El muestreo ha sido durante mucho tiempo una herramienta destacada en estadística y analítica, ante todo cuando hay grandes cantidades de los datos están involucrados En el ámbito de los sistemas de archivos muy grandes (y almacenes de datos jerárquicos en general), sin embargo, el muestreo tiene principalmente sido ignorado y por varias buenas razones. Principalmente corriendo el muestreo en un entorno de este tipo presenta desafíos técnicos que hacen que todo el proceso de muestreo no sea beneficioso. En esto trabajamos demostramos que hay casos para los cuales el muestreo vale mucho la pena en sistemas de archivos muy grandes. Abordamos esto tema en dos aspectos: (a) el lado técnico donde diseñamos y implementar soluciones para un muestreo ponderado eficiente que también sea distribuido, de un solo paso y aborda múltiples aspectos de eficiencia; y (b) el aspecto de usabilidad en el que demostramos varios casos de uso en los que el muestreo ponderado sobre sistemas de archivos grandes es extremadamente beneficioso En particular, mostramos casos de uso con respecto a estimación de relaciones de compresión, pruebas y auditorías y fuera de línea recopilación de estadísticas sobre almacenes de datos muy grandes. I. I NTRODUCCIÓN El uso del muestreo para obtener resultados significativos y precisos. las estadísticas son abundantes en muchos aspectos de nuestras vidas y ha sido metódicamente utilizado durante al menos dos siglos. Encuestas sobre grandes poblaciones, experimentos científicos y mediciones físicas todos construyen abren el poder del muestreo aleatorio para estimar cifras en casos en los que revisar todo el espacio disponible es simplemente demasiado grande o demasiado caro para ser práctico. En el Reino de almacenamiento, el muestreo se ha utilizado típicamente en bases de datos como un medio para acelerar algunos de los análisis disponibles. En los sistemas de archivos, sin embargo, se ha evitado en gran medida el muestreo. Esto también es cierto para casos extremadamente grandes donde la cizalla el tamaño del sistema de archivos requiere considerar medios para acelerar El proceso de adquisición de análisis de los datos. También tiene para otros almacenes jerárquicos de datos heterogéneos, como objetos almacenamiento. Esta evasión no es casual ya que hay múltiples razones y desafíos que hacen que el muestreo en este entorno sea más duro y menos beneficioso En particular, los siguientes problemas surgen al intentar realizar estimaciones basadas en muestreo: • Mientras muestrea un subconjunto aleatorio de un espacio plano de elementos es sencillo (por ejemplo, muestrear un bloque de un volumen), un sistema de archivos no permite un acceso aleatorio verdadero a los datos ya que los archivos se encuentran en una compleja jerarquía estructura y el acceso a los datos es a través de un árbol de directorios. • La estructura jerárquica de los sistemas de archivos o el almacenamiento de objetos. y la alta varianza en tamaños de archivos, objetos y direcciones

tories, pueden causar una situación en la que la cantidad a granel de datos en el sistema reside solo en una pequeña porción de La investigación que conduce a estos resultados es parcialmente apoyada por el europeo Séptimo Programa Marco de las Comunidades (7PM / 2001-2013) bajo subvención acuerdo n 257019 - VISION Cloud Project. Los archivos. Como resultado, uno tiene que escanear los metadatos del repositorio completo para dar cuenta de toda la totalidad de los datos. En un sistema de archivos esto equivale a un costo total árbol de directorio transversal. • El costo de un recorrido completo del directorio en un sistema de archivos grande es prohibitivamente alto y además tal recorrido permite recopilar estadísticas precisas sobre metadatos, por lo tanto, dejando casi ningún beneficio en hacer una estimación usando muestreo. Los problemas antes mencionados crean una situación por la cual es no está claro que haya algún punto en el uso de muestreo aleatorio para análisis en la configuración de sistemas de archivos muy grandes. A. Nuestras contribuciones En este trabajo discutimos el caso para usar el muestreo como una media para lograr análisis significativos en una gran jerarquía almacenes de datos y sistemas de archivos en particular. Nuestras contribuciones abordar dos preocupaciones principales al hacerlo. 1) El primero es el aspecto técnico del muestreo. Formalizando la distribución de muestreo correcta en tales sistemas, idear ing e implementando algoritmos que realmente funcionan Este muestreo con una sobrecarga mínima. Producimos un interfaz general que se puede llamar durante cualquier recorrido de los metadatos y producir una breve lista de muestras archivos de acuerdo con la distribución deseada. Nuestro diseño aborda los desafíos de correr en un solo pase y en un entorno distribuido multiproceso. Estos son características cruciales ya que el rendimiento de la poligonal es altamente influenciado por correr de manera distribuida. 2) La segunda preocupación es identificar los casos de uso para los cuales El muestreo es realmente beneficioso. Nuestros casos de uso incluyen procesos que requieren una inspección profunda de datos (como estimación de las relaciones de compresión), pruebas y auditorías y recopilación de estadísticas fuera de línea en archivos muy grandes sistemas. Notamos que nuestro marco es general y su usabilidad trasciende mucho más allá del ámbito de los sistemas de archivos y es relevante a casi cualquier forma de almacenamiento, como almacenes de objetos, archivos y otros. Sin embargo, en este documento, nos centramos principalmente en nuestra implementación ción para el importante caso de uso de sistemas de archivos a gran escala (como el almacenamiento conectado a la red o un sistema de archivos en clúster). B. Casos de uso a) Alcance de la analítica :: El hecho de que hacemos muestreo limita los tipos de análisis que podemos soportar con éxito.

Todavía hay un amplio y útil alcance de análisis que puede se logrará en base al muestreo. En general, apoyamos cualquier medida que puede describirse como un promedio o suma sobre local 978-1-4799-5671-5 / 14 / $ 31.00 c ⃝ 2014 IEEE Página 2 pruebas, donde local significa una función que se puede calcular en un Granularidad relativamente pequeña del conjunto de datos, como en un solo archivos o en partes de archivos. Nuestras garantías son estadísticas y Asegurar que cualquier fenómeno que sea notable en el sistema de archivos será detectado en la muestra con muy alta probabilidad (el los parámetros exactos están vinculados al tamaño de la muestra). Describimos estos conceptos más formalmente en el Apéndice A. b) Los beneficios del muestreo: el muestreo aleatorio es benoficial en que permite inspeccionar muchos menos datos durante el analisis. Dicho esto, hay configuraciones donde el Los beneficios reales no siempre son claros. Como se mencionó anteriormente, el El proceso de muestreo probablemente implica iterar todos los elementos en los datos set (recorrido completo del árbol de directorios), y durante tal pase muchos de las estadísticas se pueden calcular con una sobrecarga insignificante. Entonces, por ejemplo, para responder una consulta como "¿cuál es el tamaño total de imágenes jpeg en el sistema de archivos "una lata transversal completa simplemente mantenga un contador y responda esta consulta con precisión. En Por otro lado, hay otros casos que hacen que el muestreo sea muy atractivo y estos son el foco de nuestro trabajo. Por ejemplo, si la consulta involucrada requiere leer realmente los datos en los archivos desde el disco, luego recopilar estos datos es mucho más agotador que ejecutar un recorrido y puede convertir una tarea factible en una escaneo de datos completo inviable. Describimos varios ejemplos específicos de los beneficios de nuestro marco de referencia. Estos son solo la punta del iceberg en términos de aplicaciones: 1) Estimación de las relaciones de compresión: compresión para archivo sistemas está ganando popularidad y hay varios tales ofertas actuales de compresión incorporada para archivos a gran escala sistemas (por ejemplo, [22], [20], [15]). Una herramienta para predecir el beneficio. de usar dicha compresión en un archivo (actualmente) sin comprimir El sistema sería altamente beneficioso. Desde la migración de un muy El sistema de archivos grandes en forma comprimida es prohibitivamente largo En cuanto al tiempo y los impuestos en términos de uso de la CPU (tanto durante compresión y durante la descompresión), es primordial comprender cuánto hay que ganar antes de decidir seguir adelante con la migración. Además, la estimación precisa La relación de esta relación de compresión puede resultar valiosa financieramente a través de una planificación más estricta de la capacidad de un sistema comprimido. La estimación de la compresión por muestreo se estudió recientemente. en [11], pero este trabajo no fue suficiente para proporcionar una práctica implementación para sistemas de archivos a gran escala (pero más bien enfocados

en la interfaz de bloque o una lista dada de objetos). En nuestro trabajo nosotros implementar un recorrido distribuido eficiente con herramienta de muestreo que culmina ejecutando una estimación de compresión basada en la muestra elegida. El principal atractivo de este método es la cantidad mínima de datos reales que deben leerse desde el disco para la estimación, pero logra una precisión de sonido garantías El rendimiento está directamente relacionado con el tiempo de el recorrido con una sobrecarga muy pequeña para muestreo y Se requiere una sobrecarga constante de menos de un minuto para leer los bits de los archivos de muestra elegidos del disco y evaluar compresión sobre ellos. En la Sección IV presentamos precisión y pruebas de rendimiento de nuestra implementación. Por ejemplo, estimamos con precisión la relación de compresión en 1.8TB por leer solo 320 MB de datos mientras requiere solo el 3% del tiempo de ejecución de evaluación exhaustiva altamente distribuida. Nuestro La solución se está integrando actualmente como una evaluación del cliente y herramienta de dimensionamiento para un producto de compresión prominente, y en De hecho, esta aplicación fue la motivación original para este estudio. 2) Mecanismos de prueba y auditoría: en el anterior ejemplo, el cuello de botella estaba leyendo principalmente datos del disco (y también comprimiéndolo). En otros escenarios, la cantidad de los datos pueden no ser excesivos, pero el procesamiento que tiene sufrir es muy pesado. Ejemplos son varios análisis y algoritmos de aprendizaje como procesamiento de video o agrupamiento algoritmos En dicho entorno, se minimiza el conjunto de archivos. que requieren procesamiento es una optimización valiosa. Un ejemplo es para auditorías que requieren cálculos pesados. ción El muestreo siempre ha jugado un papel clave en la auditoría, y por ejemplo, verificar ese contenido de TV de ciertos tipos (por ejemplo, anuncios) no excede un cierto porcentaje de la el tiempo de emisión puede ser difícil de lograr de manera exhaustiva y puede beneficiarse enormemente del muestreo. Otra área de relevancia está en probando el éxito de los algoritmos. Por ejemplo, un caso de uso Lo que hemos explorado es la prueba de los algoritmos de voz a texto. Dados varios algoritmos y un gran conjunto de datos, la elección de el mejor algoritmo no está claro y generalmente es la única forma para verificar el resultado de dicho algoritmo de traducción es para un ser humano para escucharlo y traducirlo. Entonces el cuello de botella aquí no es el algoritmo de texto a voz sino la cantidad de datos que un humano revisa. En este caso de uso, los archivos son ponderada de acuerdo con su duración de grabación (contada por tiempo o por el número de palabras grabadas) y la muestra permite que un revisor humano revise un número fijo de grabaciones unidades de tiempo y producir una estimación de la tasa de éxito de Un algoritmo de voz a texto. Tenga en cuenta que para la tarea específica de probando la tasa de éxito de los algoritmos, nuestra estimación resulta ser sea especialmente estricto para algoritmos altamente exitosos. Esto es ya que la varianza de un algoritmo muy exitoso es muy pequeña (ver discusión en la Sección B).

3) Análisis fuera de línea de las distribuciones del sistema de archivos :: El uso los casos hasta ahora consideran situaciones en las que el directorio completo el recorrido no fue el cuello de botella en el sistema sino que es la lectura y el procesamiento de datos, que es la tarea más pesada. En En este caso de uso consideramos los beneficios en situaciones donde el El recorrido es el eslabón más pesado de la cadena. Hay varios métodos para tratar análisis en directorios tan grandes, por ejemplo por distribución de la poligonal [17], o haciendo solo un recorrido parcial [13] (un enfoque que puede poner en peligro precisión pero funciona bien en muchos casos). La deficiencia de estos enfoques es que las consultas en cuestión deben ser definido antes de ejecutar el recorrido para recoger el derecho estadísticas durante el recorrido. Alternativamente, uno puede recoger todos los metadatos para cada uno de los millones de registros y consultar estos metadatos sin conexión (por ejemplo, poniendo todos los metadatos en una base de datos separada), pero para sistemas muy grandes esto puede resultan ser una sobrecarga excesiva. En cambio nuestro mecanismo complementa cualquier enfoque de recorrido rápido creando un corto "Boceto" del conjunto de datos, del cual se pueden deducir numerosos estadísticas y consultas una vez finalizada la travesía. Una travesía de un sistema muy grande puede tomar muchas horas y quizás días Página 3 y analizándolo uno puede aprender varias propiedades como tipos de archivos populares, bibliotecas o propiedades de archivos. En muchos casos, basado en este primer análisis, uno quisiera refinar la consulta, pero esto requeriría un nuevo recorrido para recopilar nuevas estadísticas. Usando muestreo ponderado, uno puede recolectar una lista relativamente corta de archivos de muestra, que se ponderan según los parámetros clave. Por ejemplo, de acuerdo con la longitud del archivo o cualquier otra información relevante medida. Ahora se pueden ejecutar estadísticas y mediciones en el lista corta, que proporciona resultados demostrablemente precisos, pero sin que requiere un recorrido adicional del conjunto de datos. Demostramos esta metodología al escanear una vida real conjunto de datos de 17.5 millones de archivos, con 7.25 TB de datos y analizando algunas de sus propiedades fuera de línea, finalmente comparando estos resultados a los números exactos de exploración completa. La apelación es mantener incluso una lista relativamente grande (digamos de 100,000 muestras) sigue siendo un orden de magnitud menor que administrar todos de los metadatos del sistema de archivos, pero proporciona una precisión extrema estimaciones C. Trabajo relacionado El muestreo ha sido durante mucho tiempo una herramienta central en estadísticas (ver, por ejemplo [14]). En el mundo del almacenamiento ha sido principalmente empleado en bases de datos. Hay muchas obras que intentan para estimar los tamaños de las consultas mediante muestreo para optimizar operaciones de bases de datos. Algunos ejemplos que consideran uniforme el muestreo sobre los elementos de la base de datos son [9], [10], [8], [5], [3]. En

en general, la interfaz proporcionada por la base de datos es mucho más amigable para distribuciones de muestreo que la de los sistemas de archivos. Debería ser Sin embargo, señaló que también en las bases de datos, el muestreo uniforme puede causar dificultades, como se señaló en [4], principalmente porque el los elementos son demasiado finos y no se correlacionan bien con la forma en que los datos se almacenan en el back-end. En el contexto de sistemas de archivos y estructuras de datos jerárquicos. en general, el muestreo y el análisis en general se vuelven más difíciles conseguir. De hecho, existe una tendencia a modificar el diseño de sistemas de archivos para admitir una estructura diferente a su manejo de metadatos [16], [19] (y así lograr un análisis más rápido en metadatos) o una estructura completamente diferente [21]. El muestreo aleatorio ponderado se estudió en [7] (ver también referencias dentro). Mientras que el de las formas de muestreo utilizadas aquí se ajusta a nuestro marco, los algoritmos subyacentes difieren de la nuestra, y en particular utilizamos muchas más invocaciones de la función de aleatoriedad que nuestra técnica (ver discusión en Sección III). Análisis en sistemas de archivos muy grandes donde se estudió en [13] y en [17]. Ambos trabajos consideran solo análisis en metadatos de los archivos (a diferencia del contenido, como el ejemplo de compresión). El primer trabajo aborda el largo tiempo para hacer un recorrido completo del directorio haciendo un recorrido parcial al azar en el árbol (y por lo tanto no puede tener garantías de precisión en el estadística). El segundo trabajo mejora la velocidad transversal al distribución más inteligente Tenga en cuenta que nuestro trabajo es complementario a ambas técnicas, y se pueden aplicar sobre estas más rápido atravesar. Finalmente, la estimación de la compresión se estudió en [6] y [11]. El primer papel muestreó partes de cada archivo que equivale a peor rendimiento que nuestro método y sin precisión garantías El segundo artículo sienta las bases para nuestro La precisión garantiza la compresión, pero no proporciona interfaz para trabajar de manera eficiente con el sistema de archivos. II E STIMATION VIA S UESTREO - P RELIMINARIES El objetivo principal de este trabajo es apoyar la estimación. mediante muestreo sobre un gran conjunto de datos. Como se describe en el uso sección de casos, existe una amplia motivación para reducir el tamaño de los datos disponibles que pueden reducir las E / S de disco, la CPU y el tiempo para obtener estadísticas (por nombrar algunos recursos). Sin embargo, al azar muestrear archivos en un sistema de archivos conlleva una dificultad inherente porque normalmente se accede a los datos a través de un árbol de directorios (algunos sistemas de archivos tienen otros medios de acceso a los datos, como el recorrido del nodo i, pero estos también están sujetos a algunos de las dificultades que se describirán en la siguiente sección). El problema con los árboles de directorios es que la mayoría de los archivos posiblemente puede residir en un solo subdirectorio, y encontrar esto El subdirectorio puede requerir una exploración completa del árbol de directorios. Incluso más aún, una observación clave es que el muestreo aleatorio ingenuo de

los archivos pueden terminar dando una aproximación extremadamente inexacta. Esto se debe al hecho de que los tamaños de archivo pueden ser muy diversos. La investigación (por ejemplo, [6], [24]) ha demostrado que, en gran escala sistemas de archivos, los archivos pequeños representan una gran cantidad de archivos pero solo una pequeña porción de la capacidad total (en algunos casos 99% de los archivos representaron menos del 10% de la capacidad). Asi que el muestreo aleatorio de la lista completa de archivos puede generar un conjunto de muestra con un número desproporcionado de archivos pequeños que en realidad tienen muy poco efecto en la capacidad general. Es por lo tanto claro que los archivos deben ser muestreados de acuerdo a su capacidad para garantizar una buena analítica. El enfoque natural en este caso es muestrear archivos con probabilidad de acuerdo a su longitud. Es decir, un archivo de 2 MB de longitud tiene el doble de probabilidades de ser elegido que un archivo de longitud 1 MB. Sin embargo, hay una sutileza. aquí: esta linealidad en la probabilidad es para cada elección de un archivo en el conjunto de muestra (y no para una sola opción). A continuación describimos la distribución a la que apuntamos en nuestro muestreo, una distribución que nos permite probar declaraciones sobre la precisión de la estimación. Nosotros complementamos con un modelo para generalizar el tipo de estadística para el cual Podemos lograr garantías de precisión. A. Notación básica A lo largo del artículo consideramos un sistema de archivos con N archivos (sin pérdida de generalidad, esto podría ser elementos en cualquier tipo de conjunto de datos, como objetos en un almacén de objetos o columnas en una base de datos). A cada archivo i ∈ { 1 , ..., N} se le asigna un peso w i y denotar por W= norte ∑ i=1 wi El peso total en el sistema. Es instructivo pensar en el peso como el tamaño del archivo, pero esto se puede generalizar a numerosos Diferentes medidas. Página 4 B. La distribución muestral Nuestro objetivo es muestrear archivos M en el sistema con el propiedad de que cada muestra se toma de manera uniforme al azar de todos los archivos cuando se ajusta de acuerdo con el peso del archivo w i . Por ejemplo, si w 1 = 1000 yw 2 = 200, entonces cada muestra es cinco veces más probable que sea el primer archivo que el segundo archivo. Sin embargo, tenga en cuenta que esto no significa que el primer archivo sea cinco veces más probabilidades de ser parte del conjunto de muestras, ya que este conjunto contiene M puntos y la proporción de cinco solo se mantiene para un solo punto de salida del M . Más precisamente, la probabilidad de que un archivo i aparece en el conjunto de la muestra tiene una distribución muy cerca de la

distribución binomial con M ensayos y probabilidad de éxito wi W . A saber, el archivo i obtiene el valor k i ∼ B ( M, w i W ) (para ser exactos, nuestro algoritmo genera una distribución multinomial con ensayos M y N categorías con probabilidades w 1 W , ···, w N W , una distribución que tiende a la colección de distribución binomial como N y M crecer). Tenga en cuenta que el valor k i es un número entero (no solo 0 y 1) para que el i- ésimo archivo tenga asignada una variable aleatoria k i para que el el archivo i no está en la muestra si k i = 0 y de lo contrario aparece en la muestra k i veces. Como resultado, un solo archivo puede aparecer más de una vez en la muestra y esto es muy intuitivo ya que en caso que un solo archivo es tan grande que su capacidad es igual, digamos, 1 2 de la capacidad total, entonces nos gustaría aproximadamente la mitad de los puntos de muestra para pertenecer a este enorme archivo. Nos referimos a la distribución que estamos muestreando como el multinomio ponderado distribución. en el Apéndice A damos una explicación más rigurosa de estadísticas que se pueden obtener mediante muestreo ponderado y qué Hay algunas garantías que se pueden obtener. III. T HE S UESTREO M ÉTODO Hasta ahora hemos discutido el marco general, su aplicación aplicabilidad y definió la distribución en los archivos que pretendemos muestra. Esta sección está dedicada a los algoritmos y métodos. que desarrollamos para llevar a cabo el muestreo parte sobre un sistema de archivos (u otro conjunto de datos). Desde la distribución está bien definido y lo suficientemente simple, seleccionando un subconjunto aleatorio de archivos de una colección dada es bastante sencillo ejercicio de programación Sin embargo, una vez que tengamos en cuenta la escala del conjunto de datos y la interfaz a los archivos, entonces las cosas se vuelven menos obvio y necesita ser diseñado con más cuidado. En esto respete nuestro diseño e intento de implementación para optimizar todo los factores involucrados en el proceso, aunque en algunos casos de uso Esto puede ser un exceso porque algunos de los recursos que optimizar para podría ser abundante y no plantear ningún problema. Todavía, Hay otros casos, por ejemplo, cuando el árbol de directorios está en el caché o los metadatos se administran en SSD rápidos en los que el rendimiento de las herramientas de muestreo puede convertirse en un cuello de botella si no diseñado cuidadosamente (consulte la Sección IV-B para ver un ejemplo de este tipo). Dado que nuestro trabajo tiene como objetivo abordar el alcance más amplio posible, Abordamos todos los recursos lo mejor que pudimos. En el En la siguiente sección describimos la interfaz que proporcionamos con una lista de requisitos clave y consideraciones de proceso de muestreo A. La interfaz y las consideraciones clave

La interfaz del proceso de muestreo debe intercalar con un recorrido completo del conjunto de datos disponible (en nuestros ejemplos esto es un recorrido completo del árbol de directorios. Implementamos tres procesos. eso puede ser llamado por cualquier recorrido de iterador sobre archivos: 1) Inicia la muestra: Inicializa las estructuras de datos (se llama una vez al principio del recorrido). 2) Actualizar muestra: llamado para cada archivo durante el recorrido, toma como entrada el peso del archivo, su id y cualquier adicional metadatos que están disponibles. Este proceso es seguro para subprocesos y puede ser llamado por múltiples procesos en paralelo. 3) Proceso posterior: finalice y muestre la lista de muestras. En general, se espera que sea el momento de ejecutar el recorrido dominará el tiempo del proceso de muestreo. Sin embargo, intentamos hacer la sobrecarga del proceso de muestreo Lo más mínimo posible. La filosofía se aplica a los principales recursos de memoria y utilización de CPU. Otra nota digna las consideraciones incluyen: • Aleatoriedad: elegir una distribución aleatoria naturalmente requiere el uso de generación aleatoria. Si bien esto es no es un recurso pesado, observamos que es un límite uno cuando varios procesos se ejecutan simultáneamente (ver Sección III-B). Por lo tanto, intentamos usar solo la misma cantidad aleatoriedad como realmente se requiere. • Cerraduras multiproceso y comunicación - multiprocesamiento es un habilitador crucial para mejorar los recorridos de directorio (ver [17])) y, por lo tanto, es compatible con varios subprocesos necesidad. Queremos nuestro soporte de multiprocesamiento para tener el menor impacto posible y evitar un notable ralentizar debido a la sincronización de múltiples procesos. • Conocimiento de caché: otro factor crítico en la velocidad de un El recorrido es el contenido de su caché. Como se ve en la Sección IV Si el árbol de directorios o partes de él están en caché, esto permite tremenda aceleración Es crucial que el muestreo (o análisis) se abstendrá de memoria extensa uso para evitar desalojar esos datos útiles de la memoria caché. B. La técnica central Dado que el proceso de muestreo es parte de una iteración sobre el archivo y aceptar un archivo a la vez, el primer enfoque natural es tomar una decisión independiente por archivo de si el archivo debe o no debe incluirse en la muestra (y en caso afirmativo, ¿cuántas veces debería estar en la muestra? los El problema es que para generar una distribución binomial por cada archivo, uno debe lanzar una moneda sesgada varias veces por archivo (suponiendo que el sesgo correcto se conoce de antemano). Existen Hay varias formas de abordar esto, pero la conclusión es que el cantidad de lanzamientos de monedas (llamadas a la función de aleatoriedad) necesita ser al menos el peso total W del sistema de archivos. Si el peso es la longitud de un archivo, la mejor optimización sería para contar la longitud en trozos de tamaño 4KB (tamaño de página típico

de sistemas de archivos modernos). Entonces, la cantidad de llamadas aleatorias termina en torno al número de trozos de 4KB en todo sistema de archivos Tal cantidad grande de llamadas aleatorias puede ser muy exigente para el sistema (ver Figura 2 en la Sección IV). Página 5 En su lugar, adoptamos un enfoque diferente, que requerirá exactamente M llama a la función de aleatoriedad (recuerde que M es el número de muestras) Describimos esta técnica central ahora, bajo el supuesto de que W se conoce de antemano. En Sección III-C ampliamos nuestra implementación al caso de que W no se conoce de antemano. Nuestra técnica primero realiza un paso de preprocesamiento que selecciona las "posiciones" aleatorias elegidas para la muestra de antemano. Durante el recorrido, mapeamos nuestros puntos elegidos en reales archivos, tal como los encontramos. En pocas palabras, el preprocesamiento considera todo el sistema de archivos como un espacio secuencial plano que abarca el rango entre 1 y W y elige M al azar ubicaciones dentro de este rango (simplemente llamando a la aleatoriedad función M veces). Cuando se ejecuta el recorrido real, un contador se mantiene la cantidad de capacidad que se ha encontrado lejos (por todos los archivos vistos hasta este punto de la poligonal). Cuando llega un nuevo archivo, el contador avanza según el tamaño de archivo, por ejemplo, del punto D al punto D + w . Ahora si alguno de los M puntos de muestra preseleccionados pasó a residir en el área abarcada por este archivo, este archivo se agrega a muestra. Si hubiera más de un punto de muestra entre D y D + w , el archivo se agrega varias veces (de acuerdo con número de esos golpes). A continuación se muestra un pseudocódigo que implementa la técnica. Muestra de núcleo ( M, W ): Preparar: 1) escogerán aleatoriamente M números entre 1 a W . Póngalos en una matriz Sample_Index 2) Ordenar los números M en Sample_Index 3) Mantener un contador D de bytes de datos escaneados para lejos. Inicialice a 0 (eventualmente debería llegar a W ). 4) Mantener un contador k de puntos de muestra manejados hasta aquí. Inicializar a 0 (eventualmente debería alcanzar M) Traverse: revisa todos los archivos del sistema (cualquier lista o la orden es suficiente). Para cada archivo i en el recorrido: 1) Incremente D por w i (el tamaño del archivo) 2) Si D> Índice de muestra [ k ] entonces a. Agregue el archivo a la lista de muestra segundo. k ++ do. Si k = M entonces termina re. Else goto 2

3) De lo contrario, continúe con el siguiente archivo y pase a 1 Cabe destacar que, si bien se toman decisiones aleatorias antes del recorrido, los archivos se determinan solo durante el transversal, y de hecho un orden diferente de la transversal producirá Una lista diferente de archivos. C. Manejo del tamaño del sistema de archivos desconocido: muestreo de una pasada Nuestra técnica central (así como los otros enfoques que mencionado en la Sección III-B) supone el conocimiento de la tamaño total W del sistema de archivos antes de que comience el proceso. Esta es una suposición razonable en muchos entornos, ya que los sistemas de archivos normalmente mantienen el contador de su tamaño actual (y número de archivos) y este contador se puede consultar directamente (por ejemplo con el comando df). Sin embargo, estos contadores se mantienen solo para la raíz del sistema de archivos y contar todos los archivos en el sistema, mientras que nuestro análisis a menudo quisiera centrarse en un tema específico subárbol o familia de archivos (por ejemplo, archivos de una lista parcial de tipos de archivo). En tales casos, la única forma de calcular W es en realidad ejecute el recorrido completo en el directorio en cuestión, y sobrecarga que es inaceptable (ya que típicamente la transversal es la parte más pesada de todo el proceso). En esta sección describimos nuestra solución para correr con tamaño desconocido Utiliza la técnica CoreSample de Sección III-B como su componente básico y emplea algunos métodos convencionales del ámbito de los algoritmos de transmisión. El proceso general se describe en el siguiente pseudocódigo: Muestra ( M ) • Sea S 1 un tamaño de segmento inicial con el guarantea que S 1 0 it sostiene que P rob [ | F - F | > ε ] < 2 e - 2 Mε 2 (b−a)2 La prueba es un resultado directo de la desigualdad de Hoeffding [12], al considerar las posiciones en los archivos como el azar básico variables a la mano. La abstracción de mirar f ( i, j ) como un medir las posiciones dentro de un archivo (en lugar de considerar un medido definido en archivos) es muy útil para simplificar el análisis (aunque para muchos de los casos de uso interesantes f es solo una función de su archivo i y no de la posición j ). los Se omite la prueba formal. a) Uso del teorema 1: tenga en cuenta que el teorema 1 requiere un limitado en el rango de la función f y de hecho si la varianza de f es excesivo, entonces la precisión de la estimación no puede Estar garantizado. En aplicaciones es típicamente posible considerar medidas que están delimitadas en el rango [0 , 1] (como visto en todos los ejemplos en la Sección A). Entonces el teorema las garantías son del siguiente tipo: al tomar 5000 muestras para una función con f ( i, j ) ∈ [0 , 1] se garantiza que el sesgo de estimación excederá 0 . 028 con probabilidad como máximo Número de Confianza Hoeffding Poisson Muestras Nivel Inclinación ( ε ) Inclinación ( ε ) 5000 10 - 3 0,028 0.0048 5000 10 - 6 0,038 0.0076

10000 10 - 3 0,019 0.0033 10000 10 - 6 0,027 0.0052 CUADRO II C OMPARACIÓN ENTRE UTILIZANDO EL LÍMITE H OBSERVACIÓN ( TEMA 1) CON b - a = 1 VS . UNA ESTIMACIÓN DE P OISSON PARA EL CASO DE QUE f ( i, j ) ES UNA PRUEBA B ERNOULI CON PROBABILIDAD p = 0 . 01. ES EVIDENTE QUE CUANDO ES POSIBLE USAR LA ESTIMACIÓN P OISSON (B ERNOULI PRUEBAS CON BAJA PROBABILIDAD ) ENTONCES LAS GARANTÍAS DE PRECISIÓN SON MUCHO MEJORES QUE EN EL CASO GENERAL . 1 1000 y se sesgará en más de 0 . 038 solo con probabilidad menos de 1 en un millón. En general, la probabilidad de que un la estimación se sesgará en más de ε decae exponencialmente como el número de muestras M crece. El hecho de que ε es cuadrado significa que para reducir el sesgo por un factor de k uno necesita aumentar el número de muestras en k 2 (por ejemplo, reducir a la mitad la inclinación requiere 4 veces más muestras). Un caso especial interesante es que todos los valores de f son 0 o 1, y que esto ocurre con baja probabilidad. Por ejemplo, el caso de uso de prueba (Sección I-B2) espera una baja probabilidad de errores ( f ( i, j ) = 1) o de lo contrario el método que se está probando es muy mal. En este caso, usar el Teorema 1 no proporciona suficientes garantías de precisión (por ejemplo, garantizar un sesgo de ± 0 . 028 para valores dentro de 0 . 05 simplemente no es útil. los La razón de esta deficiencia es que el Hoeffding subyacente La desigualdad ignora la varianza de las variables aleatorias disponibles y usa su rango para dar el peor de los casos vinculado a la varianza. En este caso importante, vale la pena usar una aproximación del promedio ponderado usando la distribución de Poisson - esto la aproximación se conoce como "la ley de eventos raros" o "la ley de los números pequeños ”(véase, por ejemplo, en [18], capítulo 4.2). En la Tabla II damos un ejemplo numérico de la precisión. eso puede garantizarse cuando se usa el Teorema 1 y cuando se usa Una estimación de Poisson con probabilidad de error p = 0 . 01. As visto que las garantías proporcionadas con este límite son mucho más estrictas y haga que el método sea atractivo en estos rangos también