Cache transactions & fixing addAll

[jakearchibald]

What we need to solve

cache.put, cache.add and cache.allAll have transaction-like properties that aren't well explained by the spec. Eg, what happens in this case?

const pa = cache.put(request, response);
const pb = cache.put(request, anotherResponse);

Should the second cache abort the first? If so what happens to the pa promise? Should pb wait until pa settles? This is not currently defined.

cache.add and cache.addAll are atomic, but you cannot ensure responses are ok, making it a bit of a footgun. Developers are surprised to hear this, despite it being consistent with fetch(). We should change add and addAll to reject if any of the responses are !response.ok, or if ok-ness cannot be determined (opaque response) - maybe include an option to revert to current behaviour.

This change is safe, as there the number of opaque responses being added via add & addAll rounds to 0.00%.

Use-cases

Adding multiple resources to the cache atomically. Similar to:

caches.open('foo').then(cache => {
  return Promise.all(
    ['/hello', '/world'].map(url => {
      return fetch(url).then(response => {
        if (!response.ok) throw Error("Response not ok");
        return cache.put(`${url}-cached`, response);
      });
    })
  );
})

The above isn't atomic, "/hello" can succeed & be written to the cache, but "/world" can fail.

Say I wanted to look into the cache and decide whether to delete entries based on their response:

cache.open('foo').then(cache => {
  cache.keys().then(requests => {
    requests.forEach(request => {
      cache.match(request).then(response => {
        if (isTooOld(response)) {
          cache.delete(request);
        }
      });
    })
  });
});

The above is racy. The response we remove from the cache may not be response, as a cache.put(request, differentResponse) may have happened in a different thread.

Proposal: cache transactions

Aims:

• Allow the above usecases
• Avoid excessive locking that would hurt performance
• Explain existing cache-writing methods in terms of transactions

interface CacheStorage {
  # …
  [NewObject] Promise<CacheTransaction> transaction(DOMString cacheName, optional CacheTransactionOptions options);
}

dictionary CacheQueryOptions {
  sequence<RequestInfo> limitTo;
};

interface CacheTransaction {
  void waitUntil(Promise<any> f);

  # Same method signatures as Cache, except add & addAll
  [NewObject] Promise<Response> match(RequestInfo request, optional CacheQueryOptions options);
  [NewObject] Promise<sequence<Response>> matchAll(optional RequestInfo request, optional CacheQueryOptions options);
  [NewObject] Promise<void> put(RequestInfo request, Response response);
  [NewObject] Promise<boolean> delete(RequestInfo request, optional CacheQueryOptions options);
  [NewObject] Promise<sequence<Request>> keys(optional RequestInfo request, optional CacheQueryOptions options);
}

Examples

Multiple .puts atomically (from the usecases):

const urls = ['/hello', '/world'];

Promise.all(
  urls.map(u => fetch(u))
).then(responses => {
  if (responses.some(r => !r.ok)) throw Error("Response not ok");
  const cacheURLs = urls.map(u => `${u}-cached`;

  return caches.transaction('foo', {
    // keep a minimal lock
    limitTo: cacheURLs
  }).then(tx => {
    cacheURLs.forEach((url, i) => {
      tx.put(url, responses[i]);
    });
    return tx.complete;
  });
});

Look into the cache and decide whether to delete entries based on their response (from usecases):

caches.transaction('foo').then(tx => {
  tx.waitUntil(
    tx.keys().then(requests => {
      return Promise.all(
        requests.map(request => {
          return tx.match(request).then(response => {
            if (isTooOld(response)) {
              return tx.delete(request);
            }
          });
        })
      );
    });
  );

  return tx.complete;
});

cache.put and cache.delete become shortcuts to creating transactions, eg:

Cache.prototype.put = function(request, response) {
  return caches.transaction(this._cacheName, {
    limitTo: [request]
  }).then(tx => {
    tx.put(request, response);
    return tx.complete;
  });
};

Cache.prototype.delete = function(request) {
  return caches.transaction(this._cacheName, {
    limitTo: [request]
  }).then(tx => {
    tx.delete(request);
    return tx.complete;
  });
};

And our modified addAll can be defined (roughly):

Cache.prototype.addAll = function(requests) {
  return Promise.all(
    requests.map(r => fetch(r))
  ).then(responses => {
    if (responses.some(r => !r.ok)) throw TypeError('Nooope');
    return caches.transaction(this._cacheName, {
      limitTo: requests
    }).then(tx => {
      requests.forEach((request, i) => {
        tx.put(request, responses[i]);
      });
      return tx.complete;
    });
  });
}

Detail

Some of this is a little rough. Apologies for lack of strictness, hopefully it gets the idea across.

• A cache transaction has an associated locked requests, a list of Requests, initially null
• A cache transaction has an associated closed flag
• A cache transaction has an associated settled flag
• A cache transaction has an associated aborted flag
• A cache transaction has an associated operations array of CacheBatchOperation dictionary objects
• A cache transaction has associated extend lifetime promises
• A request to response map as an associated pending transactions, a list of cache transactions

caches.transaction(cacheName, options):

1. If the result of running is settings object a secure context with the incumbent settings object is "Not Secure", return a new promise rejected with a SecurityError exception.
2. Let p be a new promise.
   1. TODO: type check, turn options.limitTo into requests
   2. TODO: Same as caches.open, aside from creating a Cache. Then once we have a request to response map…
   3. Let pendingTransaction be the result of running the Request transaction algorithm, passing in the request to response map and options.limitTo
   4. Let cacheTransaction be a
   5. Resolve p with a new CacheTransaction associated with the cache transaction
   6. Queue a microtask:
      1. If the cache transaction's extend lifetime promises is not null
         1. Let waitFor be waiting for all of cache transaction's extend lifetime promises
      2. Else
         1. Set pendingTransaction's closed flag
         2. Let waitFor be a promise resolved with no value
      3. Wait for waitFor to settle
      4. Set pendingTransaction's closed flag
      5. If rejected:
         1. Set pendingTransaction's aborted flag
      6. If pendingTransaction's aborted flag set
         1. Remove pendingTransaction from request to response map's pending transactions
         2. Set pendingTransaction's settled flag
         3. Reject p with TypeError
      7. Resolve p with the result of running Batch Cache Operations passing the pendingTransaction's operations as the argument
3. Return p.

cacheTransaction.match & cacheTransaction.matchAll behave as they currently do, except:

1. If closed throw TypeError
2. If locked requests is not null, and request url is not equal to one of those in locked requests, throw TypeError (TODO: or do we allow it, but developer should be aware it's racy?)
3. TODO: …consider pending writes in operations?

cacheTransaction.keys behaves as it currently does, except:

1. If closed throw TypeError
2. If locked requests is not null, throw TypeError (TODO: or… same question as above)
3. TODO: …consider pending writes in operations?

cacheTransaction.put(request, response)

1. If closed throw TypeError
2. If locked requests is not null, and request url is not equal to one of those in locked requests, throw TypeError
3. As current .put steps 1-11, but also abort transaction before rejecting
4. Append o to operations
5. Return promise resolved with undefined

cacheTransaction.delete(request)

1. If closed throw TypeError
2. If locked requests is not null, and request url is not equal to one of those in locked requests, throw TypeError
3. As current .delete steps 1-9
4. Append o to operations
5. (hand waving) Return true/false if this operation would result in deletion

Request transaction:

Input

• requestResponseMap, a request to response map
• lockedRequests, a sequence of requests

Outputs pendingTransaction, a pending transaction

1. Let currentPendingTransactions be a copy of the pending transactions associated with requestResponseMap
2. Let pendingTransaction be a cache transaction
3. Set pendingTransactions locked request to lockedRequests
4. Add a new pendingTransaction to requestResponseMap's pending transactions
5. For each pendingTransaction in currentPendingTransactions:
   1. If lockedRequests is undefined, or if any of lockedRequests have the same url as one or more of the requests in pendingTransaction's locked requests
      1. Wait for pendingTransaction's settled flag to become set
6. Return pendingTransaction

Abort transaction:

• cacheTransaction, a cache transaction

Outputs none

1. Set cacheTransaction's aborted flag
2. Reject cacheTransaction's extend lifetime promises

Batch Cache Operations

Similar to as it is now, except:

• Performs squashing to remove redundant operations
• Resolves once data fully written into cache, and reverts if writing fails (similar to what the current .put is doing in step 14)
• Deletes should be reverted if puts fail - I think we should be able to perform the deletes after all the puts once correctly squashed

Questions

Creating a transaction:

caches.transaction(cacheName, options).then(tx => {
  tx.waitUntil(promise);
  return tx.complete;
}).then(() => console.log("Transaction complete!"));

// or…

caches.transaction(cacheName, tx => {
  return promise;
}, options).then(() => console.log("Transaction complete!"));
// No need for waitUntil or tx.complete
// Easier to reason about transaction lifetime? (less like IDB)
// Can detect throws in callback execution
// Using a callback feels like an antipattern

// or even…

cache.open(cacheName).then(cache => {
  cache.transaction(tx => {
    return promise;
  }, options).then(() => console.log("Transaction complete!"));
});
// One method of opening a cache
// Really easy to deadlock by returning `cache.put(…)` in the transaction callback

cacheTransaction.put could return synchronously, is it better to return a promise for consistency?

Should read operations like cacheTransaction.match consider pending tasks (operations) in their return values?

I guess cacheTransaction.abort() is worth adding (and easy).

Apologies for both the length and hand-waving in this proposal, but I'd rather not spend any more time on it if we think it's a no-go.

[jakearchibald]

@wanderview threw this together on a flight, let me know if it's unreadable and I'll see if I can repair it

[wanderview]

Can you share some real world use cases where this extra complexity was needed? Cache's simple API is an advantage over IDB, IMO.

[jakearchibald]

Looking through the cache and deleting old items isn't a good enough example?

We also need to explain what happens if two puts (or addAlls) happen at the same time.

[jakearchibald]

In terms of simplicity, this doesn't replace regular cache.put etc, you'd only use transactions if you needed them. But transactions explain how multiple-puts-at-once works.

[wanderview]

I guess I'm more asking if this is something devs have asked for due to encountering the problem? Or is it all theory?

[wanderview]

"Squashing" would need to be defined. Also, we reject addAll() in squashable cases today. Why change to support it?

[jakearchibald]

People have asked for a way to look at the cache and decide what to delete. We don't support that safely right now.

[wanderview]

I guess my first take is this is close to a rewrite for our cache impl to support this. I don't want to do that unless it's a real problem for devs.

[jakearchibald]

Yeah, I hand-waved through squashing, and of course it would need to be defined. I'd be happy to reject if there are competing puts within a single transaction, but delete(request) put(request, response) should safely squash to just the put.

I hand-waved through that as I didn't think it was make or break for the general idea. I can flesh that bit out if it is.

[jakearchibald]

Can we explain what happens with multiple overlapping addAlls & puts in a simpler way? What does gecko currently do?

[wanderview]

People have asked for a way to look at the cache and decide what to delete. We don't support that safely right now.

Can you explain the safety issue with this? For example, this seems somewhat safe today to me:

caches.open('foo').then(cache => {
  // Find all responses that are too big
  cache.keys().then(requests => {
    return requests.map(request => {
      cache.match(request).then(response => {
        return isTooOld(response) ? request : null;
      });
    });

  // Now delete them all
  }).then(requestsToDelete => {
    return Promise.all(requestsToDelete.map(request => {
      if (!request) {
        return;
      }
      return cache.delete(request);
    }));
  });
});

I agree this could have issues with many threads reading and writing, but right now we mainly have one thread; the service worker.

[wanderview]

Can we explain what happens with multiple overlapping addAlls & puts in a simpler way? What does gecko currently do?

What gecko does is very simple:

• Every put() writes the corresponding body to a disk temp file. When the file is complete its committed into the backing sqlite database. Any old, overwritten records are removed at this point. Multiple overlapping put()s will result in the last put() winning.
• For addAll() we write the bodies for all responses to disk temp files. When all of the temp files are complete its committed into the backing sqlite database. Again, last to complete wins.
• Any match() calls between the start of a put() and the put() being committed do not take into account the new record.

[jakearchibald]

By the time you get to the .delete(request), the response that gets deleted may not be the response you decided was too old. Another may have add in the meantime time.

[wanderview]

By the time you get to the .delete(request), the response that gets deleted may not be the response you decided was too old. Another may have add in the meantime time.

So we have responses of wildly varying size being stored under the same request? What kind of html resources have this characteristic? I'm probably wrong, but it seems to me resources are mostly stable in size over the short term.

Also, they could use a vary header to avoid this situation, no?

[jakearchibald]

Multiple overlapping put()s will result in the last put() winning.

Does this mean:

cache.put(request, response1);
cache.put(request, response2);

…response1 may overwrite response2 even though it was .put afterwards?

[wanderview]

…response1 may overwrite response2 even though it was .put afterwards?

Yes, if response1 has a larger or slower body stream.

[wanderview]

Does your proposal allow multiple overlapping transactions? I don't see anything that would block that.

Edit: Can you equate what you are asking for into the kind of transactions locking mechanisms supported in sqlite? https://www.sqlite.org/lang_transaction.html#immediate

[wanderview]

Oh, I see Request Transactions now. Does each transaction wait for any previous transactions affecting the given request(s) to complete before starting?

[jakearchibald]

So we have responses of wildly varying size being stored under the same request? What kind of html resources have this characteristic? I'm probably wrong, but it seems to me resources are mostly stable in size over the short term.

Also, they could use a vary header to avoid this situation, no?

I'm not following this, but I'm pretty jetlagged right now (hence all the spelling and grammar mistakes - more than usual). Taking your example, but making it about age, not size:

caches.open('foo').then(cache => {
  cache.keys().then(requests => {
    return requests.map(request => {
      cache.match(request).then(response => {
        return isTooOld(response) ? request : null;
      });
    });
  }).then(requestsToDelete => {
    return Promise.all(requestsToDelete.map(request => {
      if (!request) return;
      return cache.delete(request);
    }));
  });
});

When we cache.match(requests[0]), many writes may have happened by the time we get to cache.delete(requests[0]), so I may be deleting a response other than the one that isTooOld(response).

[wanderview]

When we cache.match(requests[0]), many writes may have happened by the time we get to cache.delete(requests[0]), so I may be deleting a response other than the one that isTooOld(response).

I guess that makes sense.

If transaction wait for one another, and body streams can be js controlled in the future, do you worry about deadlocks?

[jakearchibald]

Does each transaction wait for any previous transactions affecting the given request(s) to complete before starting?

Yeah, that's 5.i.a of Request transaction. The "wait" is a bit hand-wavey, but the intent is that .transaction doesn't resolve until other transactions that operate on one or more of the same requests settle.

[wanderview]

If a transaction fails, are all operations rolled back to the previous state? Maybe I was assuming that as I can't find it in your proposal now. But I'm obviously having trouble reading tonight.

[jakearchibald]

If transaction wait for one another, and body streams can be js controlled in the future, do you worry about deadlocks?

What would you do to cause a deadlock this way? Deadlocking shouldn't be easy.

There's also:

caches.open('foo', cache => {
  return caches.transaction('foo').then(tx => {
    tx.waitUntil(cache.put(request, response));
  });
});

…which would deadlock. That's one of the reasons I put .transaction on caches rather than cache, to make look odd to use a cache in a cacheTransaction's waitUntil.

[wanderview]

What would you do to cause a deadlock this way? Deadlocking shouldn't be easy.

Start a put(), then lazy .match() a response to fill in the body for the response being putted. So a cache copy essentially.

[jakearchibald]

If a transaction fails, are all operations rolled back to the previous state?

Hand-waved in Batch Cache Operations. Sorry, my laptop battery was running out when I got to this bit so it's a bit brief. We already handle put reverting, but yeah would need to handle delete too.

[wanderview]

Hand-waved in Batch Cache Operations. Sorry, my laptop battery was running out when I got to this bit so it's a bit brief. We already handle put reverting, but yeah would need to handle delete too.

This is a bit harder, but doable I guess.

I will look more at the proposal before our meeting on Tuesday. I have to run now.

[jakearchibald]

I'm hoping squashing can always turn interleaved puts and deletes into a series of puts, then deletes. If all the puts succeed, then you're just left with the deletes… what could cause a delete to fail?

[wanderview]

I'm hoping squashing can always turn interleaved puts and deletes into a series of puts, then deletes. If all the puts succeed, then you're just left with the deletes… what could cause a delete to fail?

I think this depends on if we allow put(), match(), delete() within a transaction. If you can interleave reads and writes, then you cannot safely reorder writes.

Also keep in mind we have the rules about match()+delete() leaving the Response returned from the match() as a functioning object. Any body file storage needs to exist until the Response is gc'd. How does this work with a match() within a transaction? Are Response and Request objects normally kept alive past the end of the transaction? What about a Response from a rejected/rolled-back transaction?

I think I can accommodate keeping those Response objects alive in the gecko impl because I keep the body in a separate file from the sqlite database. I just need to track when the last use of any particulr body file goes away and reap the file at that point. That may not be the case for all implementations, though.

[jakearchibald]

F2F: change addAll and add now, while it's safe. For v1.

We should work towards under-the-hood transactions to prevent races on writes.

Transaction API v2. Talk to Josh.

[NekR]

Blink change landed; will appear in M50 (April-ish release) unless disaster occurs.
Gecko change landed. I uplifted it to FF46 so that we will also release the change in April.

Maybe it should be fixed here https://github.com/coonsta/cache-polyfill too (for older versions, i.e. before Chrome 50 and Firefox 46)?

[jakearchibald]

@NekR happy to merge a PR for it

[NekR]

PR is here: dominiccooney/cache-polyfill#19

Everyone is welcome to review :-)

[asutherland]

I retract the deleteResponse suggestion. I still think transactions combined with waitUntil support are super-powerful and may be used as a primitive for cool things that are unrelated to the intent of Cache, but transactions do seem like the best option for user code and implementer code. (And waitUntil is the only sane way to allow a transaction to do data-dependent things while holding the transaction open since body reads are async and don't happen directly from the Cache API, making IDB self-closing transaction semantics infeasible or just jerky.) Hooray for transactions!

[jakearchibald]

Use-case from #867 (comment):

Allow a transactional form of caches.open(name).then(c => c.addAll(urls)) where the cache named name wouldn't be created if addAll fails, unless that cache existed prior to the transaction.

[jakearchibald]

F2F: need to make sure you can make a transaction across multiple caches

Need to make sure .waitUntil can compose between multiple transaction systems.

[jakearchibald]

F2F: we can do timeouts via setTimeout and abort, let's not overcomplicate it.

[jakearchibald]

F2F: be explicit that cache.match isn't in its own transaction because it isn't locking

[NekR]

Just got into this case where I may need transaction:

I have 2 hash maps: 1) stored on device from previous SW; 2) is in memory which came with new SW.

On install:

1. I compute their difference;
2. download new files and then put them into tmp-cache.

On activate:

1. again difference is computed;
2. old files deleted from original-cache;
3. moved files (e.g. renames) are moved inside original-cache, original copied are removed (copied with previous URL);
4. new files (from install event) are merged from tmp-cache to original-cache;
   5)tmp-cache deleted.

Obvious problem here is that I shouldn't do operations direction on original-cache because everything could be stopped at middle of operation (e.g. computer hard power off).
But thing is--I really want do that, because files are not added/changed so often and merging new files into original-cache is much less expensive than moving files from original-cache to tmp-cache, and then using tmp-cache as new original-cache.

I can be wrong in everything, so please correct me.

[NekR]

Just to clarify:

Imagine 100 small files in SW cache (http2). On each project release 2-3 files are changed.
So on each release I want to move 2-3 files from tmp-cache to original-cache and be sure that all files in original-cache always are up-to-date (no collisions).
Moving 97-98 files from original-cache to tmp-cache and then swapping pointer to tmp-cache could help here, but.. it's movement of 97-98 files.

[wanderview]

Note, I believe chrome is also non-deterministic when it comes to cache.put() commit order. For example, visit:

https://cache-api-perf.glitch.me/order.html

This puts slow,fast into the cache, and checks the resulting order with keys. Chrome 67 gives me fast,slow (the reverse of call order). Firefox and Safari TP also give fast,slow.

The difference between firefox and chrome is where the body is accumulated. In chrome its accumulated in the renderer in memory and then added to the operation queue. In firefox the body is accumulated on the disk and then added to the operation queue.

So if the body of one resource is slow to come over the network then both firefox and chrome can result in non-deterministic commit order. If the body is very large and slow to write to disk, then firefox may also have non-deterministic commit order.

Given that at three browsers are non-deterministic, I wonder if we really need to add that kind of determinism to the spec. Particularly if other primitives like WebLocks are coming along which might allow the site to enforce ordering if it needs it.

Edit: It seems only edge results in slow,fast on the order.html link above.

[jakearchibald]

I can't say I've heard of any complaints about ordering here. As you say, weblocks etc can provide it if needed. I'm happy to shelve the whole transactions thing.