owfs Development Site

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