Sistemas de Archivos
Distribuidos
Definicin
Un sistema de archivos distribuidos, (DFS), es una implementacin
distribuida del clsico modelo de tiempo compartido de un sistema
de archivos, donde varios usuarios comparten archivos y almacenan
recursos.
Conceptos de base
Sistema Distribuido: coleccin de mquinas interconectadas por una red
de comunicacin.
Mquina: puede ser una estacin o un mainframe
Recursos locales: recursos con los que cuenta la mquina
Recursos remotos: el resto de las mquina y sus recursos
Servicio: software ejecutndose en una o ms mquinas que
proporcionan un tipo particular de funcin
Servidor: software de servicio en una sola mquina
Un servidor es un proceso que implementa servicios
Cliente: proceso que puede invocar un servicio a travs de un conjunto
de operaciones que forman su interfaz de cliente
Caractersticas
DFS proporciona servicios de archivos a clientes
Clientes, servidores, y dispositivos de almacenamiento se encuentran
dispersos entre las mquinas de un sistema distribuido
Diversidad de clientes y de archivos
Desempeo:
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
resolucin nombres, aadir y borrar archivos
Servicio autorizacin eficiencia y/o lista de control de acceso
Servicio transaccin admn. de concurrencia y duplicidad
archivos bsico
lectura/escritura archivos y atributos
Servicio sistema
admn. de dispositivos, cach y bloques
Nombramiento y Transparencia
Nombramiento:
mapeo entre objetos lgicos y fsicos
usuario = objetos lgicos de datos
sistema = objetos fsicos
Transparencia
esconder el lugar de la red donde se encuentra
el archivo (file replication)
Nociones de Nombramiento
Importante diferencias dos nociones relacionadas que involucran
mapeo de nombres dentro de los DFS
- Transparencia de la ubicacin
- Independencia de la ubicacin
Independencia de ubicacin
vs
transparencia esttica de la ubicacin
Divorciar datos de la ubicacin
Transparencia esttica de ubicacin proporciona a los
usuarios una forma conveniente de compartir datos
La independencia de la ubicacin separa la jerarqua de
nombres de la jerarqua de los dispositivos de almacenamiento
dentro de la estructura de la computadora.
Esquemas de nombramiento
1. Archivos son nombrados a partir de una combinacin del
host 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 nombrar
todos los archivos del sistema
Tcnicas de implementacin
Se requiere de una forma de realizar un mapeo entre un nombre de
archivo y su ubicacin fsica.
Mtodos posibles:
duplicidad, caching local, o ambos
Posibles tcnicas:
introduccin de identificadores independientes de la ubicacin
Montaje de archivos
Una operacin de montaje del cliente ata un sistema de archivos
remoto a la jerarqua del sistema de archivos del cliente
El punto de montaje generalmente es una hoja de la jerarqua que
contiene un subdirectorio vaco.
Montajes son operaciones privilegiadas que pueden realizarse en tres
diferentes instantes:
Montaje explcito
Montaje de booteo
Automontaje
Desventaja: requiere conocimiento de la localizacin de los servidores
Registro de servidores
til en el caso de un sistema con mltiples servidores que proporcionan
el mismo servicio de archivos.
Servidor puede localizarse de dos formas:
1. Servidores se registran en un servicio de registro
2. Clientes realizan un broadcast de una peticin de automontaje
Estas dos formas son esencialmente un protocolo de resolucin de
nombres o direcciones.
Algunas veces el montaje de archivos se hace en forma de cascada,
un sistema de archivos montado puede contener subdirectorios montados
de otros directorios.
Acceso de archivos remotos
Mecanismo servicio remoto:
peticiones de acceso son pasadas al servidor,
servidor realiza el acceso
sus resultados son regresados al usuario
El compartir archivos significa que varios clientes pueden tener acceso
al mismo archivo al mismo tiempo, para lo cual:
1. se tienen que hacer coincidir operaciones de acceso
2. 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 mltiples granularidades
de operaciones de acceso de datos.
Tipos acceso a datos
Acceso remoto
ningn dato del archivo es dejado en la mquina del cliente
Acceso cache
una pequea parte de la informacin es almacenada en la
cach local
Acceso de download/updown
Todo el archivo es bajado para poder consultarlo o
modificarlo localmente
Caractersticas coherencia datos
Todas las copias son idnticas en todo el tiempo
Copias son percibidas como idnticas tan solo en algunos
puntos en el tiempo
Usuarios siempre leen los datos ms recientes en las copias
Operaciones de escritura siempre son realizadas
inmediatamente y sus resultados son propagados
Tipos operaciones
Simple RW (Lectura/Escritura)
Cada operacin de lectura y escritura es un acceso
independiente de tipo peticin/respuesta al servidor
Transaccin
Una secuencia de operaciones lectura/escritura es tratada
como una unidad fundamental de acceso a archivo
Sesin
Una sesin consiste de una secuencia de transacciones y de
operaciones simples de lectura/escritura, con semnticas
adicionales asociadas con la sesin de acuerdo a la aplicacin
Concurrencias de espacio y tiempo en acceso de
archivos
espacio
tiempo
acceso
remoto
acceso
cache
acceso
carga down/up
control
coherencia
control
coherencia
RW simple
no es un verdadero
DFS
transaccin
control concurrencia coherencia y coherencia y
concurrencia concurrencia
sesin
no aplicable
no aplicable
ignora el
compartir
Semntica de los archivos compartidos
Semntica Unix
El resultado de una escritura es propagado al archivo y
a sus copias, de tal forma que las lecturas regresarn
el ltimo valor del archivo.
Semntica Transaccin
Resultados escritura son almacenados en una zona de trabajo
y dados de alta (committed) al final de la transaccin
Semntica Sesin
Escritura a un archivo son realizadas en una copia de un archivo
y el resultado se convierte en permanente solo al final de la
sesin
Control de la versin
Ignorar el conflicto
Una nueva versin es creada sin importar lo que pas
Solucin del conflicto de versin
Suponer que la informacin modificada en la versin tentativa
no est ligada con la informacin de la nueva versin
actual.
Solucin del conflicto de serializacin
Suponer que los datos modificados en la versin tentativa
fueron modificados por la nueva versin actual.
Caractersticas principales
Archivos son identificados con una copia que reside en la mquina
servidora, pero se tienen copias en diferentes sitios
Modificacin de una copia debe reflejarse en los cachs,
(consistencia cach).
Granularidad del dato cach vara desde varios bloques de un
archivo hasta un archivo entero.
Usualmente ms datos cach son trados en la cach en el caso de una
peticin, previendo futuras peticiones de acceso
Ubicacin de la cach
Problema: dnde 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 diskless
2. Datos pueden accederse ms rpidamente
3. Tecnologa actual va dirigida a memorias menos
caras y ms grandes
4. Los caches del servidor estarn en memoria principal
independientemente de dnde se localizan los cachs
de los usuarios
Polticas de actualizacin de cach
Objetivo: escribir bloques de datos modificados en la copia maestra
localizada en el servidor
Dos polticas:
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 despus
son escritas en la copia maestra.
2.1 Un bloque es transferido cuando sea sacado de
la cach del cliente
2.2 La informacin es actualizada cuando se va a
cerrar el archivo
Consistencia
Objetivo:
Decidir cuando una copia local en la cach es consistente
con 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 ms activo. Servidor es
notificado cuando un archivo es abierto y su modo, (lec/esc). De
esta forma puede actuar en caso de que sea abierto en modos
conflictivos desactivando el cach de uno.
Comparacin entre caching y servicio remoto
Un substancial nmero de accesos remotos puede manejarse eficientemente por el
cach 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 siempre
consisten en segmentos de datos grandes y contiguos, en lugar de accesos random a
bloques de datos
El problema de consistencia es ms grave en cach
Ejecucin de cach requiere de mquinas que cuenten con discos locales o memorias
principales muy grandes
En cach, debido a que la informacin entre cliente y servidor es transferida en masa,
ms que en respuesta a necesidades especficas de una operacin 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 por
cada cliente, o proporciona bloques de informacin conforme estos
son 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 informacin del
estado de los clientes entre las solicitudes
2. Servidores stateless, (sin estado)
Los servidores no deben guardar ninguna informacin
del estado del cliente
Ejemplos de estado de informacin
Archivos abiertos y sus clientes
Descriptores y manejadores de archivos
Apuntadores de posicin actuales
Informacin de montaje
Status local
Llaves de sesin
Cach o buffer
Comparacin stateless vs statefull
Ventajas stateless
Ventajas statefull
Tolerancia a fallas
No necesita llamadas open/close
No se desperdicia el espacio del
servidor en tablas
No existe lmite para el nmero
de archivos abiertos
No hay problemas si un cliente
falla
Mensajes solicitud ms cortos
Mejor desempeo
Es posible la lectura adelantada
Es ms fcil la idempotencia
Es posible el cierre de
archivos
Caractersticas de implementacin de un servidor
archivos statefull
Requerimiento de idempotencia
Mecanismo de bloqueo de archivos
Sesin de manejo de llave
Consistencia cach
Rplica de archivos
Se dispone de varias copias de algunos archivos, donde cada
copia est en un servidor de archivos independiente.
Razones de justificacin 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
Implementacin de la rplica
Rplica a travs un grupo
Rplica retrasada
Rplica explcita
s1
s1
1
s1
Despus
cliente
2
s2
s2
s2
Ahora
3
Despus
s3
s3
s3
servidor
Grupo
cachafas 1.14 2.16 3.19
toto.c
1.2.1 2.43 3.41
direcciones binarias
nombre
simblico mltiples (para s1,s2,s3)
Protocolos de actualizacin
Objetivo: dada una lectura de un archivo replicado, por parte de
varios clientes, estos deben obtener el valor ms recientemente modificado.
Algoritmos:
1. Rplica de la copia primaria
2. Algoritmo del voto
3. El voto con fantasmas
4. Actualizacin de propagacin de Gossip
La rplica de la copia primaria
Uno de los servidores se denomina como primario y el resto son
secundarios
Actualizaciones se envan al primario
Primario realiza cambios y enva comandos a secundarios para que
realicen la misma modificacin.
Lecturas se pueden hacer de cualquier copia, primaria o secundaria
Las transacciones atmicas
La ejecucin de un conjunto de operaciones en cada
transaccin es toda o nula
La ejecucin de una transaccin que es intercalada con la
ejecucin de otras transacciones es indivisible
La actualizacin de un objeto replicado es atmica
Atomicidad es el objetivo principal de las transacciones
atmicas
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 transaccin
Encargado de la transaccin
Realiza la transaccin
Administrador
Se asegura de la consistencia de una ejecucin
concurrente de una transaccin
Encargado de los objetos
Responsable de interactuar con el servicio de archivos
para efectuar operaciones
Seriabilidad, (introduccin)
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 despus de operaciones y antes del final de una transaccin
Transaccin bien formada: sigue la convencin anterior para cada acceso de
lectura/escritura en un objeto compartido
Operaciones en diferentes transacciones estn 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 formar
una lista a ejecutar
Una lista legal es aquella que impide conflictos de locks, para lo cual se fija en el
orden interno de las operaciones en cada transaccin
No todas las listas legales provocaran resultados consistentes o se completaran
Solo son interesantes las listas legales que se terminen y produzcan resultados
consistentes
Una lista es seriable si el resultado de sus ejecucin es equivalente al de una lista
serial.
Una lista serial es una lista legal especial que es formado ejecucin secuencial
estricta.
La seriabilidad de listas seriales asegura el requerimiento de consistencia, (la base
de datos es transferida de un estado consistente a otro estado consistente)
El asegurar la consistencia es responsabilidad del encargado de transacciones y
del administrador
Protocolos de control de concurrencia
Existen tres posibles enfoques para solucionar el problema de control
de concurrencia, dependiendo si la inconsistencia puede prevenirse,
evitarse o si la consistencia puede ser validada.
Bloqueo a dos fases
Ordenamiento a base de estampillas de tiempo
Control de concurrencia ptimo
Bloqueo a dos fases
Transaccin es dividida en dos fases:
1. Una fase de bloqueo (lock) de los objetos
2. Una fase de liberacin de los objetos
Caso extremo: se bloquean todos los objetos al principio de la
transaccin y los libera al final de esta.
La seriabilidad es trivial ya que todas las listas son listas seriales
Mtodo no muy aceptado ya que ignora la concurrencia y el concepto
de compartir los archivos.
Ordenamiento estampas de tiempo
Ordenamiento 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 ejecucin de transacciones satisface las condiciones de seriabilidad.
Cuando una operacin sobre un objeto compartido es invocada, el objeto registra la
estampilla de la transaccin invocada.
Si despus se requiere otra operacin sobre el mismo objeto:
si la transaccin tiene una estampilla ms grande que la del objeto
se permite que la operacin se lleve a cabo, (y se registra la nueva estampilla)
si la transaccin tiene una estampilla ms chica se debe de abortar
Transacciones jvenes (estampilla grande), deben esperar por viejas, (estampillas chicas)
y viejas transacciones deben morir y reinicializarse cuando se confrontan a una
transaccin ms 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: operacin lectura no entra en conflicto con otras lecturas
escritura: operacin tiene conflictos con lectura y escritura
abortar: abortar operacin lectura no tiene efecto en otras transacciones
completar: el completar una operacin se lleva a cabo cuando se completa con
xito la fase atmica
Ejemplo protocolo
OK
abortar
esperar
lectura
lecturas en espera
RD
WR
Tmin
intentos de escritura
escritura
efectuar la tentativa de escritura
abortar
borrar transaccin de la lista de espera
RD
abortar
RD
WR
Tmin
WR
Tmin
no se pudo completar una espera de lectura
completar
abortar transacciones
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 transacciones
procedan libremente
Se puede permitir una transaccin entera complete y valide su transaccin
antes de hacer su efecto permanente;
esto asume la existencia de copias de los objetos compartidos en cada uno
de los sitios de transaccin
Protocolo basado en las acciones que una transaccin atmica debe realizar: ejecucin, validacin y actualizacin
Cada transaccin ti tiene asignada una estampilla TSi al principio de la transaccin
y una estampilla TVi al final de la transaccin
Cada objeto Oi registra el tiempo en el que complet una operacin de lectura
o escritura como RDj o WRj respectivamente
Ri : conjunto objetos de datos ledos en una transaccin ti durante fase ejecucin
Wi : conjunto objetos de datos escritos en la misma transaccin ti
Transacciones sern serializadas con respecto a las estampillas TVi de las
transiciones vlidas.
Las acciones a realizar en las diferentes fases son:
I. Fase de ejecucin
Inicia cuando se recibe un principio de transaccin del cliente local
Espacio privado de trabajo es creado en cada transaccin
Copias objetos con su nmero de versin son ledos en el espacio de trabajo,
donde se van a realizar actualizaciones locales
Aborto transaccin se traduce en borrar la transaccin en el espacio de trabajo
Fin de transaccin de parte del cliente significa una solicitud de completar por
parte del cliente.
II. Fase validacin.
La validacin de consistencia mutua entre ti y tk se verifica de acuerdo a:
1. Validacin de ti rechazada si Tvi < TVk, todas las transacciones deben
de serializarce con respecto a TV
2. Validacin de ti es aceptada si no traslapa a ninguna tk. ti ya fue
serializada con respecto a tk
3. La fase de ejecucin de ti traslapa con la fase de actualizacin de tk y
tk completa su actualizacin antes de TV. Validacin de ti es aceptada
si Ri Wk
4. La ejecucin de la fase de ti traslapa con la validacin y fases de
actualizacin de tk, y tk completa su fase de ejecucin antes de TSi.
Validacin ti es aceptada si (Ri Wk ) y (Wi Wk )
TVi
rechazar
fase ejecucin
aceptar si no hay
conflicto r-w y w-w
conflicto
TVk
fase validacin
TVi
aceptar si no hay
conflicto r-w
conflicto
fase actualizacin
TVi
TVi
aceptar
