domingo, 26 de junio de 2011

técnicas de validación (optimistas)

      Los protocolos anteriores, que podemos clasificar como pesimistas, comprueban que la operación que la transacción se dispone a hacer es válida antes de modificar el elemento en la base de datos. Los protocolos de control optimistas, por el contrario, presuponen que todas las operaciones se van a efectuar en orden correcto, y por tanto no controlan la validez de las operaciones realizadas hasta que la transacción termina, en la llamada fase de validación o certificación.

        La forma de implementar estos protocolos es hacer que las transacciones lleven a cabo sus modificaciones en un espacio particular, al que se han copiado previamente los datos que la transacción vaya a necesitar. Si al final del proceso, los datos resultantes son válidos, se pasan del espacio particular a la base de datos.
   Con esto tenemos que los protocolos de bloqueo optimistas tienen tres fases bien diferenciadas:
Fase de lectura/ejecución: En ella las transacciones leen cuantos elementos necesiten de la base de datos, pero realizan las modificaciones en un espacio particular, como ya hemos señalado.
Fase de certificación/validación: Se verifica que los resultados de la transacción no violan la seriabilidad. De ser así (el resultado no es correcto), la transacción reinicia (como las modificaciones eran en un espacio aparte de variables, no hace falta deshacer. Simplemente se descartan estas variables).
Fase de escritura/confirmación: Llegados a este punto, aplicamos las actualizaciones de la transacción a la base de datos.
Fases de la ejecución de una transacción a) pesimista, b) optimista


 Referencias Bibliograficas


CONTROL DE CONCURRENCIA MULTIVERSION

    MVCC (Multi version concurrency control) es una técnica de concurrencia optimista en donde ninguna tarea o hilo es bloqueado mientras se realiza una operación en la tabla, porque el otro hilo usa su propia copia (versión) del objeto dentro de una transacción.

        Obviamente la implementación interna de este algoritmo es distinta en cada motor de bases de datos, a grandes rasgos se podría decir que el MVCC internamente lo que hace es identificar cada transacción con un numero univoco y a cada registro de la tabla, con un numero de versión, donde cada transacción trabaja con su copia y si se modifica un registro de una tabla, el contador de versión del registro se incrementa. 

      Si 2 transacciones modificaron la misma tabla, se hace un mergue de ambas tablas combinando las últimas versiones de cada registro. Si las 2 transacciones, modificaron exactamente el mismo registro, entonces en ese caso, cuando se realice el commit, el registro que finalmente queda, corresponde a la ultima transacción en realizar una modificación sobre ese registro.

      De esta manera se logra que una lectura no bloquee una transacción de escritura y que una transacción de escritura tampoco bloquee una transacción de lectura.

         Un ejemplo seria, cuando hago un SELECT, puedo simultáneamente hacer un UPDATE y cuando hago un UPDATE puedo hacer simultáneamente un SELECT, algo que en el isolation habitual de las bases de datos, no es posible.

       Es muy habitual usar este tipo modelo de concurrencia para evitar los famosos “deadlocks” que suelen ocurrir en bases de datos con mucha demanda.
Sin embargo, MVCC no debe ser usado en cualquier ocasión, ya que tiene un overhead muy importante.

      Todo el manejo de versionado tiene un alto costo, ya que las versiones de registros se copian y almacenan en tablas o estructuras físicas temporales que luego se descartan. 

     A medida que las operaciones de escritura sobre la base de datos cobran relevancia sobre las operaciones de lectura, y por otro lado, nuestras lecturas son largas, los beneficios de usar MVCC aumentan, ya que reducimos los bloqueos.

      Es fundamental la existencia de un alto grado de paralelismo en nuestra aplicación. MVCC es por definición, un modelo muy escalable y donde mejor se ven sus ventajas, es en escenarios de alta demanda.




































      La principal diferencia entre multiversión y el modelo de bloqueo es que en los bloqueos MVCC derivados de una consulta (lectura) de datos no entran en conflicto con los bloqueos derivados de la escritura de datos y de este modo la lectura nunca bloquea la escritura y la escritura nunca bloquea la lectura.

     En general la idea básica es que cuando una transacción modifica un dato, se crea una nueva versión del mismo, pero se guarda la anterior. De este modo, al acabar la ejecución de las transacciones, se puede utilizar para cada una de ellas la versión de los datos “que hace la ejecución correcta”, es decir, que hace la ejecución serializable. Lógicamente, estas técnicas requieren más espacio de almacenamiento para guardar las diferentes versiones.

Referencia Bibliograficas
http://manuales.gfc.edu.co/postgres/es/mvcc.html
http://ocw.uc3m.es/informatica/diseno-y-administracion-de-bases-de-datos/teoria/Tema4_6%28Administracion_Concurrencia%29.pdf
http://grimpidev.wordpress.com/2011/02/08/control-de-concurrencia-multiversion-mvcc/

Marcas de Tiempo

           Una marca de tiempo es un identificador único que el SGBD crea para identificar una transacción, basada en la mayoría de los casos en el momento en que se inician. Se pueden, por tanto, ordenar las transacciones cronológicamente según su marca de tiempo.

       Este método se basa en marcas de tiempo para ordenar las transacciones. El plan resultante de esta ordenación será equivalente a un plan en serie con las transacciones ordenadas según sus propias marcas de tiempo.

     Esto es una diferencia fundamental conforme a los métodos anteriores, en los que los planes serializables lo eran a algún plan serial que se pueda construir con los protocolos de bloqueo. En este caso sabemos a qué plan serial se correspondería el plan serializable resultante de aplicar ordenación por marcas de tiempo.
 
      El método consiste en dejar al sistema organizar las operaciones libremente, pero al ejecutar una operación verifica que esta no contradice el orden de seriabilidad. Por lo tanto se dice que es un método optimista.

      En lugar de determinar el orden entre las transacciones en conflicto en función del momento del acceso a los elementos, determinan por adelantado una ordenación de las transacciones.
 
     Este sistema asocia a cada elemento un par de variables; MARCA_LECTURA (MTR) y MARCA_ESCRITURA (MTW), en las que se escribirá el valor de la marca de tiempo de una transacción que las consulte.
      De esta manera, la MARCA_LECTURA (X) será igual a la marca de tiempo de la ultima transacción que haya leído con éxito el elemento X.
 caracteristicas:
• El interbloqueo es imposible.
• Una marca de tiempo es un identificador único asociado a cada transacción
• Las actualizaciones físicas se retrasan hasta la Confirmación de las transacciones. No se puede actualizar

Referencias Bibliograficas

TECNICAS DE BLOQUEO (4) Protocolo de bloqueo en dos fases

En él, todas las operaciones de bloqueo preceden a la primera operación de desbloqueo de la transacción. El proceso se puede así dividir en dos fases; la fase de bloqueo y de desbloqueo. Si se permite la conversión entre bloqueos, las conversiones de bloqueos de lectura a bloqueos de escritura son en la primera fase y las de bloqueos de escritura a lectura en la segunda.
         Cualquier transacción que después de liberar un bloqueo adquiere otro siempre corre el riesgo de producir resultados incorrectos. Esto es, siempre es posible definir una segunda transacción que pueda ejecutarse concurrentemente con la primera de manera tal que la ejecución intercalada o concurrente de ambas no sea serializable y por ende no correcta. Se define el siguiente teorema:
Teorema: Si todas las transacciones obedecen las siguientes reglas:
a) Antes de operar sobre cualquier objeto la transacción debe adquirir primero un bloqueo sobre ese objeto; y
b) Después de liberar un bloqueo la transacción no adquiere ningún otro bloqueo  Entonces, todas las ejecuciones intercaladas de esas transacciones son serializables.
         Una transacción que obedece las reglas a) y b) se dice que satisface el protocolo de bloqueo en dos fases. Las dos fases son una fase creciente durante la cual los bloqueos son adquiridos, y una fase decreciente durante la cual los bloqueos son liberados.

 Su principal ventaja es que garantiza la seriabilidad, lo que no se consigue usando simplemente bloqueos.
Como inconvenientes podemos citar varios:
• Bloquea los elementos que podrían ser desbloqueados tras su uso ocupados hasta la segunda fase, impidiendo que otras transacciones que los necesiten los utilicen. Esto hace que el rendimiento de este protocolo se degrade conforme aumenta el grado de concurrencia;
• No permite todos los planes serializables posibles.
• La implementación de este este bloqueo depende del programador, que puede no realizar su tarea convenientemente.





Bloqueo en dos fases básico, conservador, estricto y riguroso

Son variaciones del bloqueo en dos fases. Se detallan a continuación:
Conservador o estático
    Requiere que una transacción bloquee todos los elementos a los que tendrá acceso antes decomenzar a ejecutarse. Una vez bloqueados, no habrá conversión de bloqueos de lectura a escritura.
     Si no es posible bloquearlos todos, la transacción no bloqueará nada y esperará a poder bloquear todos los elementos necesarios en su totalidad.
Su principal ventaja es que no sólo garantiza la seriabilidad, sino que evita el interbloqueo de transacciones.
   Como principal inconveniente, en la práctica, es muy difícil saber quéelementos serán necesarios durante la transacción antes de que esta comience, si no imposible. es interesante destacar que, al tener que esperar a poder bloquear todos los elementos que la transacción necesite, este protocolo reduce la concurrencia.

Estricto
    La transacción no libera ninguno de sus bloqueos de escritura antes de confirmarse o abortar.
     Este tipo de bloqueo garantiza planes estrictos en cuanto a recuperabilidad (recuperable es un plan que, una vez confirmada la transacción, no será necesaria deshacerla). Sin embargo, puede sufrir interbloqueos.

Riguroso
     Es una versión más restrictiva del estricto. Similar al anterior, pero además tampoco libera los bloqueos de lectura. Es más fácil de implementar.

Referencias Bibliograficas 

TECNICAS DE BLOQUEO (3) Bloqueo Exclusivo


Si una transacción T mantiene un bloqueo exclusivo sobre algún objeto (digamos un registro de la base de datos), entonces ninguna transacción distinta T, puede adquirir un bloqueo de ningún tipo sobre ese objeto hasta que la transacción T libere su bloqueo.
         El bloqueo exclusivo provee la base para resolver el problema de actualización perdida planteado anteriormente. Para hacer uso de este tipo de bloqueo se define un protocolo llamado protocolo PX que dice:
         Protocolo PX: Cualquier transacción que intente actualizar un registro R debe primero ejecutar un XFIND R para obtener direccionabilidad sobre el registro y para adquirir el bloqueo exclusivo sobre él. Si el bloqueo no puede ser adquirido en ese momento la transacción entra a un estado de espera.







 Referencia< Bibliograficas
http://ict.udlap.mx/people/carlos/is341/bases10.html
http://dircompucv.ciens.ucv.ve/generador/sites/administracion-de-bd/archivos/Integridad.pdf

TECNICAS DE BLOQUEO (2) Bloqueos de lectura/escritura

         El sistema de bloqueos binarios es simple pero demasiado restrictivo, ya que no permite que dos transacciones que van a leer el mismo fragmento de datos (A) lo hagan simultáneamente, cuando en realidad, no puede haber problemas en varios lectores simultáneos. 

    Los bloqueos de lectura/escritura hacen más débil la restricción permitiendo la siguiente compatibilidad de bloqueos.
         En realidad son una ampliación de los bloqueos binarios,
tenemos que el bloqueo puede tener tres posibles posiciones:

             *.-  libre
              *.-   bloqueado para lectura,  
               *.-   bloqueado para escritura.


            De esta forma, más de una transacción puede tener un mismo elemento de datos bloqueado para lectura, pero sólo una para escritura. Si una transacción quiere escribir en ese elemento, habrá de esperar a que el bloqueo quede libre (cualquiera que sea el tipo de bloqueo), y a continuación, bloquearlo para escritura.

             Si quiere leer, sólo tendrá que esperar si el elemento está bloqueado para escritura. Se dice por tanto, que el bloqueo de lectura es compartido y el de escritura exclusivo. Tendremos por tanto tres operaciones; bloquear_escritura(X), bloquear_lectura(X) y desbloquear(X).

          El sistema debe hacer cumplir las siguientes reglas para usar los bloqueos de lectura/escritura:
    1.-Una transacción T debe emitir la operación bloquear_lectura(x) o bloquear_escritura(X) antes de que se realice cualquier operación leer_elemento(X) de T.
    2.- Una transacción T debe emitir la operación bloquear_escritura(X) antes de que realice cualquier operación escribir_elemento(X) de T.
    3.- Una transacción T debe emitir la operación desbloquear(X) una vez que se hayan completado todas las operaciones leer_elemento(X) y escribir_elemento(X) de T.
    4.- Una transacción T no emitirá una operación bloquear_lectura(X) si ya posee un bloqueo de lectura (compartido) o de escritura (exclusivo) para el elemento X.
    5.- Una transacción T no emitirá una operación bloquear_escritura(X) si ya posee un bloqueo de lectura (compartido) o de escritura (exclusivo) para el elemento X.

    TECNICAS DE BLOQUEO (1) Bloqueos binarios

    BLOQUEOS BINARIOS
             La forma más simple de bloquear es utilizar bloqueos binarios. basta con un vector de la siguiente forma: <referencia al dato bloqueado, booleano, referencia a la transacción que lo bloquea> donde el booleano es en sí el indicador del bloqueo.
    Donde cada transacción debe solicitar el bloqueo de cada fragmento de datos A que vaya a utilizar antes de acceder a él (sea para leerlo o escribirlo), mediante una operación bloquear(A).
             Se caracterizan por tener dos valores posibles; bloqueado y desbloqueado. Cada elemento de la base de datos tiene un bloqueo distinto. El bloqueo señala si una transacción está operando sobre el elemento o está libre para que se pueda operar con él. De esta manera se impide que dos o más transacciones estén operando sobre un mismo elemento al mismo tiempo.
             Deberá liberar todos los bloqueos, mediante una operación desbloquear(A) de modo que otras tareas puedan tomarlos. Este sistema de bloqueos tiene una implementación muy simple, ya que solo requiere mantener una tabla que indica qué partes de los datos está bloqueada y por qué transacción.

    Usando bloqueos binarios
             Cuando se usan bloqueos, una transacción ha de usarlos mediante las funciones bloquear_elemento y desbloquear_elemento, cumpliendo las siguientes reglas:



    1. Una transacción T debe emitir la operación bloquear_elemento(x) antes de que se realice cualquier operación leer_elemento(X) i escribir_elemento(x).
    2. Una transacción T debe emitir la operación desbloquear_elemento(X) después de haber completado todas las operaciones leer_elemento(X) y escribir_elemento(X) en T.
    3. Una transacción T no emitirá una operación bloquear_elemento(X) si ya posee el bloqueo del elemento X.
    4. Una transacción T no emitirá una operación desbloquear_elemento(X) a menos que ya posea el bloqueo del elemento X.
    Referencia bibliograficas
    http://es.scribd.com/doc/414370/CONTROL-DE-CONCURRENCIA
    http://cnx.org/content/m18939/latest/
    http://html.rincondelvago.com/bases-de-datos_24.html 

      sábado, 25 de junio de 2011

      TÉCNICAS DE CONTROL DE CONCURRENCIA

                  Los sistemas que tratan el problema de control de concurrencia permiten que sus usuarios asuman que cada una de sus aplicaciones se ejecutan atómicamente, como si no existieran otras aplicaciones ejecutándose concurrentemente.

               Esta abstracción de una ejecución atómica y confiable de una aplicación se conoce como una transacción. Una transacción es una ejecución de un programa de usuario visto por el DBMS.


              Cuando varios usuarios intentan modificar datos al mismo tiempo, es necesario establecer controles para impedir que las modificaciones de un usuario influyan negativamente en las de otros. El acceso simultáneo puede dar como resultados información inconsistente o simplemente incorrecta, dependiendo de la mala o buena suerte que tengamos en la intercalación de las lecturas y escrituras simultáneas.


              Esta problemática ha llevado a diseñar e implementar diferentes estrategias de control de concurrencia, que se encargan de evitar todos esos problemas. El sistema mediante el cual se controla lo que sucede en esta situación se denomina control de concurrencia.


              Existen varias técnicas para controlar la concurrencia. Los bloqueos son los más conocidos, aunque también se utiliza el control multi-versión y otras técnicas como las marcas de tiempo.

      referencias
      http://cnx.org/content/m18939/latest/ 
      http://es.scribd.com/doc/51343259/IV-Control-De-Transacciones 

      CONTROL DE CONCURRENCIA EN LA BASES DE DATOS


              La concurrencia es la propiedad de los sistemas que permiten que múltiples procesos sean ejecutados al mismo tiempo, y que potencialmente puedan interactuar entre sí.

              La Concurrencia en las base de datos es de suprema importancia en los sistemas de información, ya que evita errores en el momento de ejecutar las diferentes transacciones

              El objetivo de los métodos de control de concurrencia es garantizar la no inferencia o la propiedad de aislamiento de transacciones que se ejecutan de manera concurrente. Los distintos objetivos atacan el problema garantizando que las transacciones se ejecuten en un plan que sea serializable, es decir, que el resultado sea equivalente a el resultante de ejecutar un plan en serie.