Cache design

Cache design

OWFS Cache Design

  • Purpose

    • Persistent memory
    • Performance
    • Optional: OWFS can function in pure stateless design
    • The 1-wire architecture is inherently extensible and fluid.
  • Design

    • Binary search tree built into the C compiler <search.h>

      • In-memory
      • Key and (user allocated) data
      • The same data structure is also used for the device list
      • 1-wire unique device IDs provide part of the key
    • Three databases are used:

      • Persistent data

        • State information like cumulative counters for the LCD device
        • This will be the location of "Smart slave" configuration
      • New Cache data
      • Old Cache data
    • Roll-over design

      • New cached data is added to the "New" cache tree
      • After a given time or size is reached, the "New" tree is essentially frozen

        • "New" becomes "Old"
        • Another empty "New" is created
      • After the longest cached item has timed-out, the "Old" tree is deleted.

        • All the memory is freed.
        • The freezing of the current "New" is triggered
      • Data addition:

        • Add key to "New" if it doesn't exist
        • Update or add data and mark time
        • Similar key in "Old" will be masked
      • Data query

        • Look for key in "New". Check if still valid

        • Look for key on "Old" (only if not in "New") . Check if still valid

      • Data deletion

        • Should be rare
        • Timed-out data

          • No need to scan for it
          • No need to delete
          • Deleted when Roll-over occurs
        • Must delete from "New" and "Old" . Don't want to unmask "Old" data

      • Advantages of Roll-over design

        • No separate thread needed

          • All cache work triggered by user interaction
          • No need to scan for old data
        • Robust long run times

          • Old data automatically purged
          • Tolerates low memory states
          • No disk access
          • Zero baseline CPU utilization (demand driven)
        • Can limit resource utilization

          • Uncached data allowed
          • Can fix total cached items
        • Allows distributed computing

          • cache will be on both sides of a network link
    • CacheDataStructure


Previous page: Advanced
Next page: Cache objects