Existe una creciente demanda de sistemas online, especial-mente de aquellos que requieren procesamiento de informa-ción. Esta demanda sumada a las nuevas tecnologías de monitoreo (como por ejemplo las redes de sensores) impulsaron un nuevo tipo de aplicación que requiere bajas latencias y procesamiento continuo de grandes volúmenes de datos (los cuales arriban en forma de streams). El proce-samiento de streams constituye un paradigma de cómputo
relacionado con SIMD que permite que algunos tipos de apli-caciones puedan explotar una forma de procesamiento para-lelo y puede emplearse en diferentes dominios, como por e-jemplo para la implementación de sistemas financieros, moni-toreo basado en sensores, sistemas militares, monitoreo de red, etc. Si bien los sistemas de gestión de bases de datos (DBMS) pueden utilizarse para implementar este tipo de apli-caciones, las restricciones de bajas latencias de procesa-miento y grandes volúmenes de datos a procesar los vuelve inadecuados. Una mejor alternativa son los sistemas de ges-tión de streams de datos, usualmente sistemas distribuidos de gestión de streams de datos (DSMS por su sigla en inglés) de-bido a que estas aplicaciones son inherentemente distribuidas y por lo tanto las soluciones distribuidas son naturales y
proveen mejoras en cuanto a escalabilidad y performance.
Esta tesis se enfoca en dos aspectos desafiantes pertenecien-tes al campo de los sistemas distribuidos en general y al de los DSMS en particular: (1) tolerancia a fallas capaz de re-sistir fallas a nivel de nodos y de red y (2) gestión de carga en sistemas federados. Nuestro enfoque al problema de la to-lerancia a fallas se basa en replicación capaz de enmascarar tanto las fallas a nivel de los nodos como a nivel de las redes. Nuestroprotocolo, denominado Disponibilidad y Consistencia Ajustable a las Aplicaciones (DCAA) puede manejar adecua-damente la relación entre disponibilidad y consistencia, man-teniendo (si es posible) la disponibilidad especificada por el usuario o la aplicación, pero produciendo (eventualmente) los resultados correctos. Al mismo tiempo, DCAA también trata de producir el menor número de resultados incorrectos (impre-cisos) que luego deberían requerir corrección. La principal diferencia entre DCAA y enfoques previos sobre tolerancia a fallas en el campo de los DSMS es que DCAA soporta al mismo tiempo diferentes restricciones en las aplicaciones, esto
quiere decir que cada aplicación puede potencialmente tener distintas preferencias de disponibilidad y consistencia. Por otro lado presentaremos un nuevo protocolo de gestion de carga denominado Mecanismo de Precio Acotado (MPA), el cual permite que nodos autonomos (participantes colabora-tivos) compartan su carga sin la necesidad de contar con recursos suficientes para la operación durante picos de carga. MPA es un protocolo basado en contratos donde cada nodo practica una negociación offline y los participantes migran carga en tiempo de ejecución únicamente a nodos (pares) con los cuales mantienen un contrato (y pagan mutuamente de acuerdo al precio contratado). Este protocolo de gestión de carga ofrece incentivos que promueven la participación
de los nodos y produce una buena distribución de carga (a nivel global del sistema). Los aportes mas importantes de nuestro enfoque por sobre trabajos previos basados en economías de cómputo son su estabilidad, predecibilidad, baja carga de procesamiento, privacidad y promoción de relaciones entre participantes, posibilitando que los mismos pueden crear y explotar estas relaciones privilegiadas. El protocolo MPA es general y por lo tanto puede utilizarse para la gestión de carga
de cualquier entorno federado y no sólo bajo DSMS. Más aún, este nuevo protocolo de gestión de carga debe no sólo traba-jar en los típicos entornos colaborativos sino que también debe ser capaz de solucionar escenarios más reales, donde cada nodo (probablemente parte de diferentes organizaciones autónomas) juega bajo distintas reglas, tratando de maximi-zar su propia ganancia sin cooperar necesariamente con sus pares. Además de los modelos económicos existen varios tra-bjos basados en SLA (Service Level Agreements) para solucio-nar el problema de la gestión de carga cuando el entorno no es colaborativo. Mostraremos que los modelos SLA no proveen
una solucion completa y que los acuerdos entre pares usual-mente proveen mejores resultados. Si bien esta tesis parece tener dos focos en lugar de uno, es importante notar que ata-caremos especialmente el problema de la gestión de carga en sistemas distribuidos federados. La relación entre este enfo-que y la tolerancia a fallas radica en los contratos negocia-dos: además de precio y tareas (carga), los contratos pueden incluir disponibilidad, característica que vuelve especialmente importante la tolerancia a fallas. / There is an increased demand for online systems,especially those requiring information processing. This demand added to new monitoring technologies (like sensors networks) have motivated a new type of application that requires low latency and continuous processing of large volumes of data
(arriving as streams). Stream processing is a computer programming paradigm, related to SIMD, that allows some applications to more easily exploit a form of parallel pro-cessing and it can be employed in many different domains, such as financial systems, sensor based monitoring, milita-ry systems, network monitoring, etc. Even when traditional database management systems (DBMS) can be used to handle these applications, the low latency and high volume pro-cessing constrains make them not suitable. A much better alternative are the data stream management systems,
usually distributed data stream management systems (DSMS) because these are inherently distributed applications so distributed solutions are natural and providers of scalabi-lity and performance improvements. This thesis focuses on two challenges faced by distributed systems in general and
DSMS in particular: (1) fault tolerance able to resist node and network failures and (2) load management in fede-rated systems. The fault tolerance approach is based on re-plication and our protocol can resist most node and net-work failures. It is called Disponibilidad y Consistencia Ajustable a las Aplicaciones (DCAA) and addresses the availability/consistency relation by maintaining (if possi-ble), the availability specified by the user or the appli-cation but (eventually) producing correct results. At the same time, DCAA also attempts to produce the minimum number of incorrect (inaccurate) results that will need
correction. The main difference of DCAA over previous approaches for fault tolerance in DSMS is that DCAA supports at the same time different application constrains,
this means that each application can potentially choose a different preference of availability and consistency. Our load management protocol, called Mecanismo de Precio Acota-do (MPA) enable autonomous nodes (collaborative participa-nts) to share their load without having the required re-sources for peak load work. MPA is a contract based proto-col where nodes practice an offline negotiation and parti-cipants migrate load at execution time only to peers with whom they hold a contract (and pay each other according to the contracted price). This load management protocol offers incentives that promote participation and produces a good (system wide level) load distribution. The key differences of our approach over previous works based on computational economies are its stability, predictability, lightweight, privacy, and promotion of the relationships among participants, enabling them to create and exploit these privileged relationships. The MPA protocol is gene-ral, so it can be used to manage load in any federated en-vironment, and not only DSMS. Moreover, this new load ma-nagement protocol should not only work under the typical collaborative environment, but also should be able to address the more realistic scenery where each node (proba-bly part of different and autonomous organizations) plays under different rules trying to maximize their own gain, without necessarily cooperating with their partners. Besi-des economic models there are various works based on SLA (service level agreements) to solve the load management problem when the environment is not a collaborative one. We will show that SLA models do not provide a complete
solution and that peer agreements usually provide better results. Although this thesis seems to have two focuses instead of one, it is important to notice that we espe-cially address the load management problem under federated
distributed systems. The relation among this focus and fault tolerance is in the negotiated contracts: besides price and tasks (load), contracts can include availability,
which raises the importance of fault tolerance.
Identifer | oai:union.ndltd.org:uns.edu.ar/oai:repositorio.bc.uns.edu.ar:123456789/2228 |
Date | 00 December 2012 |
Creators | Echaiz, Javier |
Contributors | Simari, Guillermo R. |
Publisher | Universidad Nacional del Sur |
Source Sets | Universidad Nacional del Sur |
Language | Spanish |
Detected Language | Spanish |
Type | Electronic Thesis or Dissertation, Text |
Rights | 0 |
Page generated in 0.0031 seconds