Post on 22-Jan-2016
Sistemas de Archivos Distribuidos
Definición
Un sistema de archivos distribuidos, (DFS), es una implementacióndistribuida del clásico modelo de tiempo compartido de un sistemade archivos, donde varios usuarios comparten archivos y almacenanrecursos.
Conceptos de base
Sistema Distribuido: colección de máquinas interconectadas por una red de comunicación.
Máquina: puede ser una estación o un mainframe
Recursos locales: recursos con los que cuenta la máquina
Recursos remotos: el resto de las máquina y sus recursos
Servicio: software ejecutándose en una o más máquinas que proporcionan un tipo particular de función
Servidor: software de servicio en una sola máquinaUn servidor es un proceso que implementa servicios
Cliente: proceso que puede invocar un servicio a través de un conjuntode operaciones que forman su interfaz de cliente
Características
DFS proporciona servicios de archivos a clientes
Clientes, servidores, y dispositivos de almacenamiento se encuentrandispersos entre las máquinas de un sistema distribuido
Diversidad de clientes y de archivos
Desempeño:tiempo para satisfacer varias peticiones de servicio.
convencional:tiempo acceso disco + tiempo procesamiento CPU
DFS:sobrecarga debido a la estructura distribuida
Principales componentes
Servicio directorio resolución nombres, añadir y borrar archivos
Servicio autorización eficiencia y/o lista de control de acceso
Servicio transacción admón. de concurrencia y duplicidadarchivos básico lectura/escritura archivos y atributos
Servicio sistema admón. de dispositivos, caché y bloques
Nombramiento y Transparencia
Nombramiento:mapeo entre objetos lógicos y físicos
usuario = objetos lógicos de datossistema = objetos físicos
Transparencia“esconder” el lugar de la red donde se encuentra el archivo (file replication)
Nociones de Nombramiento
- Transparencia de la ubicación
- Independencia de la ubicación
Importante diferencias dos nociones relacionadas que involucranmapeo de nombres dentro de los DFS
Independencia de ubicación vs
transparencia estática de la ubicación
“Divorciar” datos de la ubicación
Transparencia estática de ubicación proporciona a losusuarios una forma conveniente de compartir datos
La independencia de la ubicación separa la jerarquía de nombres de la jerarquía de los dispositivos de almacenamientodentro de la estructura de la computadora.
Esquemas de nombramiento
1. Archivos son nombrados a partir de una combinación delhost y de un nombre local, (por ejemplo windows )
2. Proporcionar un medio para “atar” directorios remotos a directorios locales, (por ejemplo NFS )
3. Una sola estructura de nombres global se encarga de nombrartodos los archivos del sistema
Técnicas de implementación
Se requiere de una forma de realizar un mapeo entre un nombre dearchivo y su ubicación física.
Métodos posibles:duplicidad, caching local, o ambos
Posibles técnicas:introducción de identificadores independientes de la ubicación
Montaje de archivos
Una operación de montaje del cliente ata un sistema de archivosremoto a la jerarquía del sistema de archivos del cliente
El punto de montaje generalmente es una hoja de la jerarquía quecontiene un subdirectorio vacío.
Montajes son operaciones privilegiadas que pueden realizarse en tresdiferentes instantes:
Montaje explícitoMontaje de booteoAutomontaje
Desventaja: requiere conocimiento de la localización de los servidores
Registro de servidores
Útil en el caso de un sistema con múltiples servidores que proporcionan el mismo servicio de archivos.
Servidor puede localizarse de dos formas:
1. Servidores se registran en un servicio de registro2. Clientes realizan un broadcast de una petición de automontaje
Estas dos formas son esencialmente un protocolo de resolución de nombres o direcciones.
Algunas veces el montaje de archivos se hace en forma de cascada,un sistema de archivos montado puede contener subdirectorios montadosde otros directorios.
Acceso de archivos remotos
Mecanismo servicio remoto:peticiones de acceso son pasadas al servidor,servidor realiza el accesosus resultados son regresados al usuario
El compartir archivos significa que varios clientes pueden tener accesoal mismo archivo al mismo tiempo, para lo cual:
1. se tienen que hacer coincidir operaciones de acceso2. se tienen que intercalar operaciones de acceso
La primera implica que existen diferentes copias del mismo archivo, mientras que la segunda implica el intercalar a múltiples granularidades de operaciones de acceso de datos.
Tipos acceso a datos
Acceso remotoningún dato del archivo es dejado en la máquina del cliente
Acceso cacheuna pequeña parte de la información es almacenada en lacaché local
Acceso de download/updownTodo el archivo es bajado para poder consultarlo o
modificarlo localmente
Características coherencia datos
• Todas las copias son idénticas en todo el tiempo
• Copias son percibidas como idénticas tan solo en algunos puntos en el tiempo
• Usuarios siempre leen los datos más recientes en las copias
• Operaciones de escritura siempre son realizadas “inmediatamente” y sus resultados son propagados
Tipos operaciones
Simple RW (Lectura/Escritura)Cada operación de lectura y escritura es un acceso independiente de tipo petición/respuesta al servidor
TransacciónUna secuencia de operaciones lectura/escritura es tratadacomo una unidad fundamental de acceso a archivo
SesiónUna sesión consiste de una secuencia de transacciones y deoperaciones simples de lectura/escritura, con semánticas adicionales asociadas con la sesión de acuerdo a la aplicación
Concurrencias de espacio y tiempo en acceso de archivos
espacio acceso acceso accesotiempo remoto cache carga down/up
RW simple no es un verdadero control controlDFS coherencia coherencia
transacción control concurrencia coherencia y coherencia yconcurrencia concurrencia
sesión no aplicable no aplicable ignora el compartir
Semántica de los archivos compartidos
Semántica UnixEl resultado de una escritura es propagado al archivo y a sus copias, de tal forma que las lecturas regresarán el último valor del archivo.
Semántica TransacciónResultados escritura son almacenados en una zona de trabajoy “dados de alta” (committed) al final de la transacción
Semántica SesiónEscritura a un archivo son realizadas en una copia de un archivoy el resultado se convierte en permanente solo al final de lasesión
Control de la versión
Ignorar el conflictoUna nueva versión es creada sin importar lo que pasó
Solución del conflicto de versiónSuponer que la información modificada en la versión tentativano está ligada con la información de la nueva versión actual.
Solución del conflicto de serialización Suponer que los datos modificados en la versión tentativafueron modificados por la nueva versión actual.
Características principales
Archivos son identificados con una copia que reside en la máquinaservidora, pero se tienen copias en diferentes sitios
Modificación de una copia debe reflejarse en los cachés, (consistencia caché).
Granularidad del dato caché varía desde varios bloques de un archivo hasta un archivo entero.
Usualmente más datos caché son traídos en la caché en el caso de unapetición, previendo futuras peticiones de acceso
Ubicación de la caché
Problema: dónde almacenar los datos caché, (disco o mem. principal)
La caché de disco tienen una ventaja sobre el caché de memoria principal: la disponibilidad
Ventajas caché memoria principal sobre caché de disco:
1. Permite que las estaciones sean diskless2. Datos pueden accederse más rápidamente3. Tecnología actual va dirigida a memorias menos caras y más grandes4. Los caches del servidor estarán en memoria principal independientemente de dónde se localizan los cachés de los usuarios
Políticas de actualización de caché
Objetivo: escribir bloques de datos modificados en la copia maestra localizada en el servidor
Dos políticas:
1. Escribir los datos en la copia maestra tan pronto como sean modificados los de la memoria caché
2. Modificaciones son escritas en la caché y tiempo después son escritas en la copia maestra.
2.1 Un bloque es transferido cuando sea sacado de la caché del cliente2.2 La información es actualizada cuando se va a cerrar el archivo
Consistencia
Objetivo:Decidir cuando una copia local en la caché es consistentecon la copia maestra, (y por lo tanto puede ser usada).
Dos enfoques:
1. Enfoque iniciado por el cliente
2. Enfoque iniciado por el servidor
Otro enfoque el servidor juega un papel más activo. Servidor es notificado cuando un archivo es abierto y su modo, (lec/esc). Deesta forma puede actuar en caso de que sea abierto en modos conflictivos desactivando el caché de uno.
Comparación entre caching y servicio remoto
Un substancial número de accesos remotos puede manejarse eficientemente por elcaché local cuando se usa caché.
Overhead total de la red es menor en el caso de caché que en el de servicio remoto
Rutinas acceso en el servidor pueden optimizarse si se sabe que las peticiones siempreconsisten en segmentos de datos grandes y contiguos, en lugar de accesos random abloques de datos
El problema de consistencia es más grave en caché
Ejecución de caché requiere de máquinas que cuenten con discos locales o memoriasprincipales muy grandes
En caché, debido a que la información entre cliente y servidor es transferida en masa,más que en respuesta a necesidades específicas de una operación de archivos, la interfaz de bajo nivel es muy diferente de la interfaz de alto nivel.
Servicios statefull vs stateless
El servidor da un seguimiento a cada archivo que es accedido porcada cliente, o proporciona bloques de información conforme estosson solicitados por el cliente sin conocimiento del uso que se le da a dichos bloques.
Dos tipos de escuelas de pensamiento de acuerdo a lo anterior:
1. Servidores statefull, (con estado)Los servidores deben conservar información delestado de los clientes entre las solicitudes
2. Servidores stateless, (sin estado)Los servidores no deben guardar ninguna informacióndel estado del cliente
Ejemplos de estado de información
• Archivos abiertos y sus clientes
• Descriptores y manejadores de archivos
• Apuntadores de posición actuales
• Información de montaje
• Status local
• Llaves de sesión
• Caché o buffer
Comparación stateless vs statefull
Ventajas stateless Ventajas statefull
Tolerancia a fallas Mensajes solicitud más cortosNo necesita llamadas open/close Mejor desempeñoNo se desperdicia el espacio del Es posible la lectura adelantadaservidor en tablasNo existe límite para el número Es más fácil la idempotenciade archivos abiertosNo hay problemas si un cliente Es posible el cierre de falla archivos
Características de implementación de un servidor archivos statefull
Requerimiento de idempotencia
Mecanismo de bloqueo de archivos
Sesión de manejo de llave
Consistencia caché
Réplica de archivos
Se dispone de varias copias de algunos archivos, donde cadacopia está en un servidor de archivos independiente.
Razones de justificación del servicio:
1. Aumentar la confiablilidad de respaldos independientes de cada archivo
2. Permitir el acceso al archivo aunque falle un servidor de archivos
3. Repartir la carga de trabajo entre varios servidores
Implementación de la réplica
c
s1
s2
s3
c
s1
s2
s3
s1
s2
s3
c
1
2
3
cliente
servidor
AhoraDespués
Después
Grupo
Réplica explícita Réplica retrasada Réplica a través un grupo
nombresimbólico
direcciones binariasmúltiples (para s1,s2,s3)
cachafas 1.14 2.16 3.19toto.c 1.2.1 2.43 3.41
Protocolos de actualización
Objetivo: dada una lectura de un archivo replicado, por parte devarios clientes, estos deben obtener el valor más reciente-mente modificado.
Algoritmos:
1. Réplica de la copia primaria2. Algoritmo del voto3. El voto con fantasmas4. Actualización de propagación de Gossip
La réplica de la copia primaria
Uno de los servidores se denomina como primario y el resto sonsecundarios
Actualizaciones se envían al primario
Primario realiza cambios y envía comandos a secundarios para querealicen la misma modificación.
Lecturas se pueden hacer de cualquier copia, primaria o secundaria
Las transacciones atómicas
• La ejecución de un conjunto de operaciones en cada transacción es toda o nula
• La ejecución de una transacción que es intercalada con la ejecución de otras transacciones es indivisible
• La actualización de un objeto replicado es atómica
• Atomicidad es el objetivo principal de las transacciones atómicas
• Aislamiento y durabilidad son secundarios en el sentido que son necesarios para soportar atomicidad
Elementos de un sistema de procesamiento de transacciones
• Proceso del cliente– Inicia el proceso de transacción
• Encargado de la transacción– Realiza la transacción
• Administrador– Se asegura de la consistencia de una ejecución concurrente
de una transacción
• Encargado de los objetos– Responsable de interactuar con el servicio de archivos para
efectuar operaciones
Seriabilidad, (introducción)
Transacciones consisten de una secuencia de operaciones que pueden leer o escribir en objetos de datos
Para diferenciar una lectura concurrente de una escritura exclusiva se utiliza un lock compartido y un lock exclusivo respectivamente
Locks deben liberarse después de operaciones y antes del final de una transacción
Transacción bien formada: sigue la convención anterior para cada acceso de lectura/escritura en un objeto compartido
Operaciones en diferentes transacciones están en conflicto entre ellas si son escritura-escritura, escritura-lectura o lectura-escritura en un objeto compartido.
Todas las operaciones en un conjunto de transacciones son intercaladas para formaruna lista a ejecutar
Una lista legal es aquella que impide conflictos de locks, para lo cual se fija en elorden interno de las operaciones en cada transacción
No todas las listas legales provocaran resultados consistentes o se completaran
Solo son interesantes las listas legales que se terminen y produzcan resultadosconsistentes
Una lista es seriable si el resultado de sus ejecución es equivalente al de una listaserial.
Una lista serial es una lista legal especial que es formado ejecución secuencial estricta.
La seriabilidad de listas seriales asegura el requerimiento de consistencia, (la basede datos es transferida de un estado consistente a otro estado consistente)
El asegurar la consistencia es responsabilidad del encargado de transacciones ydel administrador
Protocolos de control de concurrencia
• Bloqueo a dos fases
• Ordenamiento a base de estampillas de tiempo
• Control de concurrencia óptimo
Existen tres posibles enfoques para solucionar el problema de controlde concurrencia, dependiendo si la inconsistencia puede prevenirse,evitarse o si la consistencia puede ser validada.
Bloqueo a dos fases
Transacción es dividida en dos fases:1. Una fase de bloqueo (lock) de los objetos2. Una fase de liberación de los objetos
Caso extremo: se bloquean todos los objetos al principio de la transacción y los libera al final de esta.
La seriabilidad es trivial ya que todas las listas son listas seriales
Método no muy aceptado ya que ignora la concurrencia y el conceptode compartir los archivos.
Ordenamiento estampas de tiempoOrdenamiento operaciones conflictivas basado en el tiempo en el que un objeto compartido es bloqueado por primera vez
Si cada encargado de objetos sigue el orden de las estampillas para ejecutar las operaciones, la ejecución de transacciones satisface las condiciones de seriabilidad.
Cuando una operación sobre un objeto compartido es invocada, el objeto registra la estampilla de la transacción invocada.
Si después se requiere otra operación sobre el mismo objeto:
si la transacción tiene una estampilla más grande que la del objetose permite que la operación se lleve a cabo, (y se registra la nueva estampilla)
si la transacción tiene una estampilla más chica se debe de abortar
Transacciones jóvenes (estampilla grande), deben esperar por viejas, (estampillas chicas),y viejas transacciones deben morir y reinicializarse cuando se confrontan a una transacción más joven
Protocolo definido a partir acciones a tomar cuando el administrador recibe un mensaje de lectura, escritura, abortar o completar de parte del encargado de las transacciones:
lectura: operación lectura no entra en conflicto con otras lecturas
escritura: operación tiene conflictos con lectura y escritura
abortar: abortar operación lectura no tiene efecto en otras transacciones
completar: el completar una operación se lleva a cabo cuando se completa con éxito la fase atómica
Ejemplo protocolo
RD
WR Tminintentos de escritura
abortar efectuar la tentativa de escritura
RD
RDWR Tmin
WR Tmin
lecturas en espera
borrar transacción de la lista de espera
no se pudo completar una espera de lectura
abortar transacciones
esperarOKabortarlectura
escritura
abortar
completar
Control concurrencia óptimo
Algo 2PL es un enfoque pesimista: evita que se produzcan errores de seriabilidad
Algo estampillas es menos pesimista y a veces deja que las transaccionesprocedan libremente
Se puede permitir una transacción entera complete y valide su transacciónantes de hacer su efecto permanente;
esto asume la existencia de copias de los objetos compartidos en cada unode los sitios de transacción
Protocolo basado en las acciones que una transacción atómica debe realizar: ejecu-ción, validación y actualización
Cada transacción ti tiene asignada una estampilla TSi al principio de la transacción y una estampilla TVi al final de la transacción
Cada objeto Oi registra el tiempo en el que completó una operación de lecturao escritura como RDj o WRj respectivamente
Ri : conjunto objetos de datos leídos en una transacción ti durante fase ejecuciónWi : conjunto objetos de datos escritos en la misma transacción ti
Transacciones serán serializadas con respecto a las estampillas TVi de las transiciones válidas.
Las acciones a realizar en las diferentes fases son:
I. Fase de ejecución Inicia cuando se recibe un principio de transacción del cliente local Espacio privado de trabajo es creado en cada transacción Copias objetos con su número de versión son leídos en el espacio de trabajo, donde se van a realizar actualizaciones locales Aborto transacción se traduce en borrar la transacción en el espacio de trabajo Fin de transacción de parte del cliente significa una solicitud de completar por parte del cliente.
II. Fase validación. La validación de consistencia mutua entre ti y tk se verifica de acuerdo a:
1. Validación de ti rechazada si Tvi < TVk, todas las transacciones deben de serializarce con respecto a TV2. Validación de ti es aceptada si no traslapa a ninguna tk. ti ya fue serializada con respecto a tk
3. La fase de ejecución de ti traslapa con la fase de actualización de tk y tk completa su actualización antes de TV. Validación de ti es aceptada 4. La ejecución de la fase de ti traslapa con la validación y fases de actualización de tk, y tk completa su fase de ejecución antes de TSi. Validación
si R Wi k
t es aceptada si (R W ) y (W W )i i k i k
fase ejecución fase validación fase actualización
rechazar conflicto conflicto aceptar
TVk
TVi TVi TVi TVi
aceptar si no hayconflicto r-w y w-w
aceptar si no hayconflicto r-w