This document describes techniques for rotating keys used to tokenize data stored in a streaming data store where data is stored for a maximum time [W]. In some embodiments, a data layer of such a data store can encrypt arriving original data values twice. The original data value is first encrypted with a first key, producing a first token. The original data value is encrypted with a second key, producing a second token. Each encrypted token can be stored separately in the data store. A field may be associated with two database columns, one holding the value encrypted with the first key and the second holding the value encrypted with the second key. Keys are rotated after time [K], which is at least equal to and preferably longer than [W]. Rotation can involve discarding the older key and generating a new key so that two keys are still used.