/
Block Structure Cache Invalidation Proposal

Block Structure Cache Invalidation Proposal

Owned by Nimisha Asthagiri (Deactivated)
Last updated: Feb 22, 2017

Block Structure is the terminology we currently use for the framework that manages and caches data collected and transformed by Block Transformers.  This document proposes a solution to address the issues with the current design for updating and invalidating Block Structure data.

The proposal (below) is provided after a summary of the current strategy and issues.

Current Strategy

  • Memcached as the L1 cache. The data collected by Block Transformers during the collect phase (a.k.a., Collected Block Structure = CBS) is currently stored in memcached.
  • Course Publishes on Course Edits. Whenever a new version of a course is published in Studio, 
    • The CBS for that course is immediately (synchronously) deleted in memcached by the Studio process.
    • An (asynchronous) background task is enqueued on an LMS celery worker to update the CBS cache entry for that course.
      • This task collects data for all registered Block Transformers and updates memcached with the updated CBS for the course.
      • This can be a very slow operation (taking multiple seconds) for large courses with many blocks - as each xblock is instantiated and read from the modulestore.
  • Correctness over Performance. In the meantime, if a web server process receives a request that requires access to the course's CBS, and finds that the CBS is unavailable in the cache, that process goes ahead and does the same work that the background task was expected to perform.
    • Although this strategy can potentially cause spikes in client-facing response times (especially for large courses), it intends to provide accurate responses back to the client.
    • Currently, the following LMS features require access to Block Structures:
      • Progress page
      • Course Blocks API (used by mobile apps)
      • Grades calculation
  • Versioning Transformers on Schema changes. Whenever a Block Transformer's code changes such that it needs to collect additional or different data, it's version number needs to be incremented.  This allows the Block Structure framework to realize that previously collected data for the Transformer is unusable and needs to be re-collected.
    • Currently, the primary index on CBS is by Block-Ids and not by Transformers.  Hence, the entire CBS needs to be re-collected and updated in this case, rather than just the Transformer's specific collected data.  

Current issues

  • Data-contention during active editing of a course. 
    When a course team is actively editing a course, the CBS for that course is repeatedly invalidated.  All (web and background) workers that require access to that course's CBS are slowed down since each recomputes the CBS on their own.
     

  • Block Transformer Version updates.
    Whenever there's a new production deployment requiring a Block Transformer version change, all previously memcached data instantly become invalid - causing all CBS-requiring workers to slow down as they each recompute the CBS on their own.  This can happen when:

    • a new Transformer is registered in the platform, or
    • a Transformer's collected-data schema changes.

Proposed Solution

The proposal is to err on the side of performance and scalability rather than on immediate correctness.  Production monitoring and load testing will allow us to determine a reasonable SLA on the latency of correctness - that is, how long a delay is reasonable before updating LMS's BS when Studio publishes a course?

The crux of the proposal is 3-fold: (1) embedding version information in the identifier of the CBS, (2) using a multi-level cache, and (3) carefully managing the background tasks for CBS updates.

Collected Block Structure Identifier includes Version

The "full versioning identifier" of a collected block structure will contain additional version-meta-data, as follows: 

  • root_usage_key: UsageKey of the root block in the course (used in the identifier today)
  • BS_version: Version number of the BlockStructure python class that affects the pickled output of the CBS (used in the identifier today)
  • course_version: Version number of the course, as exposed by the DraftVersioningModulestore (Split).
  • course_edit_timestamp: Timestamp of the last edit to the course, as exposed by both DraftVersioningModulestore (Split) and DraftModulestore (Old Mongo).  (Needed to make this work with Old Mongo courses.)
  • transformers_version: Hash of the version numbers of all registered transformers in the platform.

Multi-Level Cache

Whenever a worker requests a CBS for a course, the following storage layers are queried, in order:

  1. SQL (Discovery) - (New) table to retrieve elements of the latest version information ("full versioning identifier") for the requested course.  The table would include (at least) the following columns:
    1. timestamps: created, modified
    2. CBS "full versioning identifier": root_usage_key, BS_version, course_version, course_edit_timestamp, transformers_version
    3. URL to the S3 location of the CBS
  2. Memcached (L1 cache) - Using LRU, keyed by "full versioning identifier"
  3. S3 (L2 cache) - Automatically retrieved via django's FileField model type, per 1d above.
  4. Modulestore (Storage) - If the requesting worker requires on-demand recomputation, then only.  Otherwise, return a Not Found exception.  

CBS Update Task Management

Manage CBS Update tasks, as follows:

  • Multiple versions in memcached. No longer delete the memcached entry as soon as a new version of the course published. With version identifiers, there may now be multiple entries per course at any given time.   TNL-6323 - Getting issue details... STATUS
  • Separate Queue. Have a separate celery queue for CBS updates, so they can be monitored and horizontally scaled in isolation. Decided against this.  See  TNL-6324 - Getting issue details... STATUS .
  • The CBS Update task should:
    • Not recompute the CBS if there is already a cached entry for the latest version.
    • Store the CBS in S3 and update the pointer in SQL.
    • Store the CBS in Memcached and let the LRU cache be maintained based on Reader access.

Transformer Version Updates

Two-phase Deployment

When deploying a Transformer with a new version:

  • Release Phase 1. Release the code with the new Transformer schema in a prior release of the code that actually requires using it.  The schema change should be backward compatible so that older Transformer code doesn't break.
  • Run Update Tasks. Run a management command to enqueue CBS updates for all courses in the system.  TNL-6325 - Getting issue details... STATUS
  • Release Phase 2. Release the new Transformer code that requires the new schema after 24-hours (need to monitor to get a better estimate) from running the management command.

Versioning Scheme: read-version versus write-version

Right now, Transformers only have a single version number. But with a multi-phase version upgrade, we'll need to distinguish which version is used for writing versus which version is used for reading.

The only way a single version would work is if the management command runs on an isolated machine with the updated code (writing data with the new version), while remaining workers execute old code (expecting the previous version or higher).  However, in a world of continuous deployment we don't want to halt version releases and wait for a single machine to complete its work before upgrading other workers.

So, the version increment process would be:

  • In Release Phase 1, increment the write-version.  
    • Updates store this new write-version as the schema version of the Transformer's data.  
    • Reads continue to compare the old read-version (being less than or equal) to the version of the Transformer's data.
  • In Release Phase 2, increment the read-version. 
    • Both versions are now equal.
    • Reads now compare the new read-version to the version of the Transformer's data.

Archive: Considered Solutions (from Brainstorms)

  1. Have long-running tasks (such as grade reports) use the same CBS throughout the task instead of re-fetching/re-computing during the long-running task.  (e.g.,  TNL-6275 - Getting issue details... STATUS )
  2. Have workers use stale data until the background task is completed rather than having each worker actively update the CBS itself.   TNL-6302 - Getting issue details... STATUS
  3. Batch process course publishes.
  4. Smarter Task contention handling by prioritizing/stalling workers based on existence of other pending and active tasks. (Not ideal since it requires coupling between tasks.)
  5. Multi-level data caching with a persistent backend: S3 as primary backend storage, then memcached with short TTL, then (optionally) local process.   TNL-5889 - Getting issue details... STATUS
  6. Update deployment process to run the generate_blocks management command prior to enabling the new workers.
  7. Add the collective transformer version number (i.e., hash of all T-version numbers) within the cache key so old workers can continue to use older collected data.  And a canary new worker can start creating new cache entries.
  8. Change the primary index on CBS to be by Transformers rather than by Block-Ids, so only the version-changing Transformer's data needs to be re-collected and not for the entire CBS.   PERF-383 - Getting issue details... STATUS

Related content