Trading Consistency for Synchronization Cost Reduction in Real-time On-Line Analytical Processing (OLAP) Systems

  • Author / Creator
    Li, You
  • A real-time OLAP system caches previous queries' results to accelerate the processing of future queries. On such a system, whenever an update happens, affected cached values must be invalidated, or re-calculated, to maintain their consistency. Several different invalidation policies are used in real-time OLAP system. For all these policies, during the invalidation, the system must perform synchronization to ensure the consistency of cached values. Such synchronization can lead to poor scalability and may, therefore, dramatically degrades the throughput of the OLAP system. A synchronization-free invalidation policy was introduced in previous work to improve scalability. Such a policy results in stale cached values that can lead to incorrect query answers. To reduce the level of inconsistency in the system, this policy relies on independent threads, called {\it fresheners}, to recompute stale values. This thesis evaluates this policy with a manufacturer data set. It introduces new metrics to measure the level of inconsistency in the system. Based on these metrics, it measures the throughput improvement and number of incorrect results generated with this policy. Invalidation incurs high overhead even when the system is not performing synchronization. An alternative is to skip invalidation and to rely solely on fresheners to update incorrect results. This thesis introduces such a policy. This policy requires a more sophisticated strategy to keep the number of stale cached values to an acceptable level. This thesis also develops a framework to monitor the current status of the OLAP system and adjusts the number of fresheners. The goal of this framework is to deliver a stable, and acceptable, probability of incorrect results, due to stale cached values, under various workload.

  • Subjects / Keywords
  • Graduation date
  • Type of Item
  • Degree
    Master of Science
  • DOI
  • License
    This thesis is made available by the University of Alberta Libraries with permission of the copyright owner solely for non-commercial purposes. This thesis, or any portion thereof, may not otherwise be copied or reproduced without the written consent of the copyright owner, except to the extent permitted by Canadian copyright law.
  • Language
  • Institution
    University of Alberta
  • Degree level
  • Department
    • Department of Computing Science
  • Supervisor / co-supervisor and their department(s)
    • Amaral, Jose(Computing Science)
  • Examining committee members and their departments
    • Zaïane, Osmar(Computing Science)
    • Lu, Paul(Computing Science)