Formula Evaluation

Formula evaluation in DataSpread is triggered by updates to cells from the user interface. In brief, mappings between cells and dependent cells are maintained in a dependency graph; when users add a formula, the dependent cells are fetched from the LRU cell cache in a read-through manner, with the result being written in a write-through manner. When users update cells, computation of the cells dependent on it via formulae are triggered, with prioritization given to the cells visible to the user. When a formula is entered into a cell, the parser interprets it and identifies the cells required for its computation. The cell containing the formula is then said to be dependent on the cells required for its computation. The parser captures this dependency, \ie the mapping between a cell and its dependent cells, in a so-called dependency graph. The evaluator fetches the cells required for computing the formula from the LRU cell cache in a read-through manner, \ie the cache fetches the cells that are not present on demand from the underlying layer, and then computes the result of the formula. Finally, it persists the computed result by passing it back to the LRU cell cache in a write-through manner, \ie the cache pushes its updates to the database via the hybrid translator.
Whenever a user updates a cell, the evaluator uses the dependency graph to identify the cells that are dependent on the updated cell and triggers their computations. The triggered computations are performed by the evaluator and resultant values are persisted in the database by passing them to the LRU cell cache. If the resultant values are different from the old ones, then the evaluator triggers computation of the cells dependent on them, if any. There are a number of challenges in efficient formula evaluation, including compact representation of dependencies, batched evaluation of formulae, and optimizing further for user attention---these are important, but beyond the scope of the present paper on the storage engine.

Asynchonous Evaluation

Motivation

Design

• Formula evaluation on update is divided into 4 tasks: masking affected area, scheduling calculation tasks, performing calculation and pushing updated value.
• Only masking is performed within servlet thread and blocking user access. Instances of tasks can be performed concurrently at background.
• Constant blocking time on any update.