Awkward and Proud

Single-Use Tokens in Datomic

Single-use tokens have a variety of security applications. Whether it’s a password-reset token, or capturing a financial transaction, there are times when something should happen exactly once, atomically. Once a token is used, it is invalidated.

Doing things exactly once, atomically, is relatively straightforward in traditional ACID transactional databases: within a transaction, you find an entity (row) by the token, perform any updates to that entity, and finally invalidate the token (often by deleting or nullifying it). 1

But how can we accomplish some like this in Datomic?

The World’s Worst Singles Network

Welcome to WWSN! We’re so excited you’re here! On WWSN, you can sign up, sign in, and reset your password. It’s so simple!

Let’s say we have a really simple schema. A user has an email address and a bcrypted password:

[{:db/id #db/id [:db.part/db]
  :db/ident :user/email
  :db/valueType :db.type/string
  :db/unique :db.unique/identity
  :db/cardinality :db.cardinality/one
  :db.install/_attribute :db.part/db}
 {:db/id #db/id [:db.part/db]
  :db/ident :user/crypted-password
  :db/valueType :db.type/string
  :db/cardinality :db.cardinality/one
  :db.install/_attribute :db.part/db}
 {:db/id #db/id [:db.part/db]
  :db/ident :user/single-use-token
  :db/valueType :db.type/string
  :db/unique :db.unique/value
  :db/cardinality :db.cardinality/one
  :db.install/_attribute :db.part/db}]

Some initial data might be added like this:

(d/transact conn [{:db/id (d/tempid :db.part/user)
                   :user/email "jim@example.com"
                   :user/crypted-password (crypt "jello4stapler")}
                  {:db/id (d/tempid :db.part/user)
                   :user/email "pam@example.com"
                   :user/crypted-password (crypt "art4evah")}])

Later, one of the users wants to reset their password, so we generate a password reset token and persist it:

(d/transact conn [{:db/id (d/tempid :db.part/user)
                   :user/email "jim@example.com"
                   :user/single-use-token (generate-secure-random)}])

An initial approach

After receiving an email, they follow the link that includes the single-use token in the URL. When they submit their new password, we look up the user by that token and update them accordingly:

(let [db (d/db conn)
      token (:token params)
      e (d/q '[:find ?e .
               :in $ ?token
               :where [?e :user/single-use-token ?token]]
              db token)]
  (if e
    (d/transact conn [[:db/add e :user/crypted-password new-password]
                      [:db/retract e :user/single-use-token token]])))

But there’s a problem with this solution. Even though the new password is asserted in the same transaction that the token is invalidated, the opportunity for concurrency problems between threads and/or peers still exists.

Here’s why. In between the time that e is first found by its token and its new facts are transacted, somebody else could have already used (and deleted) the token. In other words, even though all writes are transactional, the reads are not. In practice this is rarely, if ever, a problem. (d/db conn) will return the most recent version of the database that the peer can get.

Croutons are just stale bread

Let’s illustrate this possibility of a stale database introducing a bug:

(def stale-db (d/db conn))

(let [{:keys [token new-password]} params
      e (d/q '[:find ?e .
               :in $ ?token
               :where [?e :user/single-use-token ?token]]
              stale-db token)]
  (if e
    (d/transact conn [[:db/add e :user/crypted-password new-password]
                      [:db/retract e :user/single-use-token token]])))

(let [token (:token params)
      ;; this token still exists because we're using and "old" db value
      e (d/q '[:find ?e .
               :in $ ?token
               :where [?e :user/single-use-token ?token]]
              stale-db token)]
  (if e
    (d/transact conn [[:db/add e :user/crypted-password "somethingelse"]
                      [:db/retract e :user/single-use-token token]])))

The user entity e is found both times because the database value is immutable. So, the transactions will both succeed.

The astute reader may have noticed something. I said all writes are transactional, but in the second block of code, we’re retracting a value that’s already been retracted. Something must be broken!

Nothing’s broken. This tripped me up at first, but it turns out that retractions work just like assertions with regard to redundancy elimination.

The Department of Redundancy Department

From the Datomic documentation on transactions:

Redundancy Elimination

A datom is redundant with the current value of the database if there is a matching datom that differs only by transaction id. If a transaction would produce redundant datoms, those datoms are filtered out, and do not appear a second time in either the indexes or the transaction log.

In other words, Datomic is eliminating the redundant retraction: we’ve already retracted the token, so the effective datoms of the transaction only include the [:db/add ...] of the new password. In this particular use case, retractions cannot be used to safeguard us from using a token more than once.

Transaction functions to the rescue

Datomic’s got us covered. I mentioned before that all writes are transactional, and reads are not. That’s actually only true on the peers. The transactor itself is guaranteed to always have access to the most recent database value at any time. Among other things, this is what enables built-in database functions like :db.fn/cas to work.

Within a transaction, a database function is used in place of a :db/add or :db/retract. When the transactor sees a transactor function, it invokes it and splices the result into the rest of the transaction. Also, a database function always receives the most recent db value as it’s first argument. Because you have access to the whole of the Datomic API, you can leverage this db value to do all sorts of things.

Let’s transact the following new schema info into our database:

[{:db/id #db/id [:db.part/db]
  :db/ident :db.fn/set-with-token
  :db/doc "Look up entity by token, set attr and value, and retract token"
  :db/fn #db/fn {:lang "clojure"
                 :params [db token-attr token-value attr value]
                 :code (let [e (datomic.api/q '[:find ?e .
                                                :in $ ?ta ?tv
                                                :where
                                                [?e ?ta ?tv]]
                                              db token-attr token-value)]
                         (if e
                           [[:db/add e attr value]
                            [:db/retract e token-attr token-value]]
                           (throw (ex-info "No entity with that token exists"
                                           {token-attr token-value}))))}}]

This function is more generic than our immediate use-case, but I prefer to parameterize attributes as well as values in database functions. It allows us to re-use the database function for other token fields, and won’t have to be updated in the schema if we ever change the name our token attribute.

Here’s how we use this shiny new function:

(let [{:keys [token new-password]} params]
  (d/transact conn [[:db.fn/set-with-token :user/single-use-token token
                                           :user/crypted-password new-password]]))

When we transact this data, the transactor invokes our function using the most recent database value. In other words, we are making the lookup portion serializable with the rest of the operations.

If we run this transaction a second time, we’ll get the error message.

In Summary

This kind of transaction atomicity is made possible by Datomic’s single-writer design. Other database systems (e.g. SQL) have to employ very complicated isolation patterns like MVVC to allow multiple writers while keeping data integrity guarantees. Datomic side-steps those problems by using a single writer, paired with immutable history.

The catch, as we have seen, is that read-dependent writes will require the use of database functions to maintain atomicity. Of course, database functions have uses outside of concurrency contexts. And, as a bonus, they can be loaded and invoked on the client as well.

For more information on database functions, see the docs, watch the video, or see the Day of Datomic examples. You can also view my scratch.clj file that I used to build up the code examples here.

1 However, even in SQL setups there are potential pitfalls. Because of the potential for multiple writers, care must be taken to satisfy the “exactly once” requirement. Where possible, a SQL client should use a single statement to find, update, and nullify a token. When a single statement isn’t possible, the use of row-level locks can be used. Or, better yet, wrap everything in a transaction with serializable isolation level.