Cache

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