diff --git a/common/changereplay.cpp b/common/changereplay.cpp
--- a/common/changereplay.cpp
+++ b/common/changereplay.cpp
@@ -116,16 +116,15 @@
                         } else {
                             // TODO: should not use internal representations
                             const auto key = Storage::Key(Storage::Identifier::fromDisplayByteArray(uid), revision);
-                            const auto internalKey = key.toInternalByteArray();
                             const auto displayKey = key.toDisplayByteArray();
                             QByteArray entityBuffer;
                             DataStore::mainDatabase(mMainStoreTransaction, type)
-                                .scan(internalKey,
-                                    [&entityBuffer](const QByteArray &key, const QByteArray &value) -> bool {
+                                .scan(revision,
+                                    [&entityBuffer](const size_t, const QByteArray &value) -> bool {
                                         entityBuffer = value;
                                         return false;
                                     },
-                                    [this, key](const DataStore::Error &) { SinkErrorCtx(mLogCtx) << "Failed to read the entity buffer " << key; });
+                                    [this, key](const DataStore::Error &e) { SinkErrorCtx(mLogCtx) << "Failed to read the entity buffer " << key << "error:" << e; });
 
                             if (entityBuffer.isEmpty()) {
                                 SinkErrorCtx(mLogCtx) << "Failed to replay change " << key;
diff --git a/common/domain/typeimplementations.cpp b/common/domain/typeimplementations.cpp
--- a/common/domain/typeimplementations.cpp
+++ b/common/domain/typeimplementations.cpp
@@ -80,16 +80,20 @@
         ValueIndex<Calendar::Name>
     > CalendarIndexConfig;
 
-
+template <typename EntityType, typename EntityIndexConfig>
+QMap<QByteArray, int> defaultTypeDatabases()
+{
+    return merge(QMap<QByteArray, int>{{QByteArray{EntityType::name} + ".main", Storage::IntegerKeys}}, EntityIndexConfig::databases());
+}
 
 void TypeImplementation<Mail>::configure(TypeIndex &index)
 {
     MailIndexConfig::configure(index);
 }
 
 QMap<QByteArray, int> TypeImplementation<Mail>::typeDatabases()
 {
-    return merge(QMap<QByteArray, int>{{QByteArray{Mail::name} + ".main", 0}}, MailIndexConfig::databases());
+    return defaultTypeDatabases<Mail, MailIndexConfig>();
 }
 
 void TypeImplementation<Mail>::configure(IndexPropertyMapper &indexPropertyMapper)
@@ -132,7 +136,7 @@
 
 QMap<QByteArray, int> TypeImplementation<Folder>::typeDatabases()
 {
-    return merge(QMap<QByteArray, int>{{QByteArray{Folder::name} + ".main", 0}}, FolderIndexConfig::databases());
+    return defaultTypeDatabases<Folder, FolderIndexConfig>();
 }
 
 void TypeImplementation<Folder>::configure(PropertyMapper &propertyMapper)
@@ -157,7 +161,7 @@
 
 QMap<QByteArray, int> TypeImplementation<Contact>::typeDatabases()
 {
-    return merge(QMap<QByteArray, int>{{QByteArray{Contact::name} + ".main", 0}}, ContactIndexConfig::databases());
+    return defaultTypeDatabases<Contact, ContactIndexConfig>();
 }
 
 void TypeImplementation<Contact>::configure(PropertyMapper &propertyMapper)
@@ -185,7 +189,7 @@
 
 QMap<QByteArray, int> TypeImplementation<Addressbook>::typeDatabases()
 {
-    return merge(QMap<QByteArray, int>{{QByteArray{Addressbook::name} + ".main", 0}}, AddressbookIndexConfig::databases());
+    return defaultTypeDatabases<Addressbook, AddressbookIndexConfig>();
 }
 
 void TypeImplementation<Addressbook>::configure(PropertyMapper &propertyMapper)
@@ -207,7 +211,7 @@
 
 QMap<QByteArray, int> TypeImplementation<Event>::typeDatabases()
 {
-    return merge(QMap<QByteArray, int>{{QByteArray{Event::name} + ".main", 0}}, EventIndexConfig::databases());
+    return defaultTypeDatabases<Event, EventIndexConfig>();
 }
 
 void TypeImplementation<Event>::configure(PropertyMapper &propertyMapper)
@@ -235,7 +239,7 @@
 
 QMap<QByteArray, int> TypeImplementation<Todo>::typeDatabases()
 {
-    return merge(QMap<QByteArray, int>{{QByteArray{Todo::name} + ".main", 0}}, TodoIndexConfig::databases());
+    return defaultTypeDatabases<Todo, TodoIndexConfig>();
 }
 
 void TypeImplementation<Todo>::configure(PropertyMapper &propertyMapper)
@@ -266,7 +270,7 @@
 
 QMap<QByteArray, int> TypeImplementation<Calendar>::typeDatabases()
 {
-    return merge(QMap<QByteArray, int>{{QByteArray{Calendar::name} + ".main", 0}}, CalendarIndexConfig::databases());
+    return defaultTypeDatabases<Calendar, CalendarIndexConfig>();
 }
 
 void TypeImplementation<Calendar>::configure(PropertyMapper &propertyMapper)
diff --git a/common/domain/typeimplementations_p.h b/common/domain/typeimplementations_p.h
--- a/common/domain/typeimplementations_p.h
+++ b/common/domain/typeimplementations_p.h
@@ -57,7 +57,7 @@
     template <typename EntityType>
     static QMap<QByteArray, int> databases()
     {
-        return {{QByteArray{EntityType::name} +".index." + Property::name, 1}};
+        return {{QByteArray{EntityType::name} +".index." + Property::name, Sink::Storage::AllowDuplicates}};
     }
 };
 
@@ -74,7 +74,7 @@
     template <typename EntityType>
     static QMap<QByteArray, int> databases()
     {
-        return {{QByteArray{EntityType::name} +".index." + Property::name + ".sort." + SortProperty::name, 1}};
+        return {{QByteArray{EntityType::name} +".index." + Property::name + ".sort." + SortProperty::name, Sink::Storage::AllowDuplicates}};
     }
 };
 
@@ -90,7 +90,7 @@
     template <typename EntityType>
     static QMap<QByteArray, int> databases()
     {
-        return {{QByteArray{EntityType::name} +".index." + SortProperty::name + ".sorted", 1}};
+        return {{QByteArray{EntityType::name} +".index." + SortProperty::name + ".sorted", Sink::Storage::AllowDuplicates}};
     }
 };
 
@@ -106,7 +106,7 @@
     template <typename EntityType>
     static QMap<QByteArray, int> databases()
     {
-        return {{QByteArray{EntityType::name} +".index." + Property::name + SecondaryProperty::name, 1}};
+        return {{QByteArray{EntityType::name} +".index." + Property::name + SecondaryProperty::name, Sink::Storage::AllowDuplicates}};
     }
 };
 
@@ -142,7 +142,7 @@
     template <typename EntityType>
     static QMap<QByteArray, int> databases()
     {
-        return {{QByteArray{EntityType::name} +".index." + RangeBeginProperty::name + ".range." + RangeEndProperty::name, 1}};
+        return {{QByteArray{EntityType::name} +".index." + RangeBeginProperty::name + ".range." + RangeEndProperty::name, Sink::Storage::AllowDuplicates}};
     }
 };
 
diff --git a/common/index.cpp b/common/index.cpp
--- a/common/index.cpp
+++ b/common/index.cpp
@@ -6,30 +6,30 @@
 
 Index::Index(const QString &storageRoot, const QString &dbName, const QString &indexName, Sink::Storage::DataStore::AccessMode mode)
     : mTransaction(Sink::Storage::DataStore(storageRoot, dbName, mode).createTransaction(mode)),
-      mDb(mTransaction.openDatabase(indexName.toLatin1(), std::function<void(const Sink::Storage::DataStore::Error &)>(), true)),
+      mDb(mTransaction.openDatabase(indexName.toLatin1(), std::function<void(const Sink::Storage::DataStore::Error &)>(), Sink::Storage::AllowDuplicates)),
       mName(indexName),
       mLogCtx("index." + indexName.toLatin1())
 {
 }
 
 Index::Index(const QString &storageRoot, const QString &name, Sink::Storage::DataStore::AccessMode mode)
     : mTransaction(Sink::Storage::DataStore(storageRoot, name, mode).createTransaction(mode)),
-      mDb(mTransaction.openDatabase(name.toLatin1(), std::function<void(const Sink::Storage::DataStore::Error &)>(), true)),
+      mDb(mTransaction.openDatabase(name.toLatin1(), std::function<void(const Sink::Storage::DataStore::Error &)>(), Sink::Storage::AllowDuplicates)),
       mName(name),
       mLogCtx("index." + name.toLatin1())
 {
 }
 
 Index::Index(const QString &storageRoot, const Sink::Storage::DbLayout &layout, Sink::Storage::DataStore::AccessMode mode)
     : mTransaction(Sink::Storage::DataStore(storageRoot, layout, mode).createTransaction(mode)),
-      mDb(mTransaction.openDatabase(layout.name, std::function<void(const Sink::Storage::DataStore::Error &)>(), true)),
+      mDb(mTransaction.openDatabase(layout.name, std::function<void(const Sink::Storage::DataStore::Error &)>(), Sink::Storage::AllowDuplicates)),
       mName(layout.name),
       mLogCtx("index." + layout.name)
 {
 }
 
 Index::Index(const QByteArray &name, Sink::Storage::DataStore::Transaction &transaction)
-    : mDb(transaction.openDatabase(name, std::function<void(const Sink::Storage::DataStore::Error &)>(), true)), mName(name),
+    : mDb(transaction.openDatabase(name, std::function<void(const Sink::Storage::DataStore::Error &)>(), Sink::Storage::AllowDuplicates)), mName(name),
       mLogCtx("index." + name)
 {
 }
diff --git a/common/mail/threadindexer.cpp b/common/mail/threadindexer.cpp
--- a/common/mail/threadindexer.cpp
+++ b/common/mail/threadindexer.cpp
@@ -118,7 +118,7 @@
 
 QMap<QByteArray, int> ThreadIndexer::databases()
 {
-    return {{"mail.index.messageIdthreadId", 1},
-            {"mail.index.threadIdmessageId", 1}};
+    return {{"mail.index.messageIdthreadId", Sink::Storage::AllowDuplicates},
+            {"mail.index.threadIdmessageId", Sink::Storage::AllowDuplicates}};
 }
 
diff --git a/common/storage.h b/common/storage.h
--- a/common/storage.h
+++ b/common/storage.h
@@ -32,6 +32,11 @@
 namespace Sink {
 namespace Storage {
 
+extern int AllowDuplicates;
+extern int IntegerKeys;
+// Only useful with AllowDuplicates
+extern int IntegerValues;
+
 struct SINK_EXPORT DbLayout {
     typedef QMap<QByteArray, int> Databases;
     DbLayout();
@@ -80,15 +85,23 @@
          */
         bool write(const QByteArray &key, const QByteArray &value, const std::function<void(const DataStore::Error &error)> &errorHandler = std::function<void(const DataStore::Error &error)>());
 
+        // of QByteArray for keys
+        bool write(const size_t key, const QByteArray &value, const std::function<void(const DataStore::Error &error)> &errorHandler = std::function<void(const DataStore::Error &error)>());
+
         /**
          * Remove a key
          */
         void remove(const QByteArray &key, const std::function<void(const DataStore::Error &error)> &errorHandler = std::function<void(const DataStore::Error &error)>());
+
+        void remove(const size_t key, const std::function<void(const DataStore::Error &error)> &errorHandler = std::function<void(const DataStore::Error &error)>());
+
         /**
          * Remove a key-value pair
          */
         void remove(const QByteArray &key, const QByteArray &value, const std::function<void(const DataStore::Error &error)> &errorHandler = std::function<void(const DataStore::Error &error)>());
 
+        void remove(const size_t key, const QByteArray &value, const std::function<void(const DataStore::Error &error)> &errorHandler = std::function<void(const DataStore::Error &error)>());
+
         /**
         * Read values with a given key.
         *
@@ -101,6 +114,9 @@
         int scan(const QByteArray &key, const std::function<bool(const QByteArray &key, const QByteArray &value)> &resultHandler,
             const std::function<void(const DataStore::Error &error)> &errorHandler = std::function<void(const DataStore::Error &error)>(), bool findSubstringKeys = false, bool skipInternalKeys = true) const;
 
+        int scan(const size_t key, const std::function<bool(size_t key, const QByteArray &value)> &resultHandler,
+            const std::function<void(const DataStore::Error &error)> &errorHandler = std::function<void(const DataStore::Error &error)>(), bool skipInternalKeys = true) const;
+
         /**
          * Finds the last value in a series matched by prefix.
          *
@@ -110,6 +126,9 @@
         void findLatest(const QByteArray &uid, const std::function<void(const QByteArray &key, const QByteArray &value)> &resultHandler,
             const std::function<void(const DataStore::Error &error)> &errorHandler = std::function<void(const DataStore::Error &error)>()) const;
 
+        void findLatest(size_t key, const std::function<void(size_t key, const QByteArray &value)> &resultHandler,
+            const std::function<void(const DataStore::Error &error)> &errorHandler = std::function<void(const DataStore::Error &error)>()) const;
+
         /**
          * Finds all the keys and values whose keys are in a given range
          * (inclusive).
@@ -119,6 +138,10 @@
             const std::function<void(const DataStore::Error &error)> &errorHandler =
                 std::function<void(const DataStore::Error &error)>()) const;
 
+        int findAllInRange(const size_t lowerBound, const size_t upperBound,
+            const std::function<void(size_t key, const QByteArray &value)> &resultHandler,
+            const std::function<void(const DataStore::Error &error)> &errorHandler = {}) const;
+
         /**
          * Returns true if the database contains the substring key.
          */
@@ -163,8 +186,9 @@
 
         QList<QByteArray> getDatabaseNames() const;
 
-        NamedDatabase openDatabase(const QByteArray &name = {"default"},
-            const std::function<void(const DataStore::Error &error)> &errorHandler = {}, bool allowDuplicates = false) const;
+        NamedDatabase openDatabase(const QByteArray &name = { "default" },
+            const std::function<void(const DataStore::Error &error)> &errorHandler = {},
+            int flags = 0) const;
 
         Transaction(Transaction &&other);
         Transaction &operator=(Transaction &&other);
@@ -224,13 +248,17 @@
     static qint64 cleanedUpRevision(const Transaction &);
     static void setCleanedUpRevision(Transaction &, qint64 revision);
 
-    static QByteArray getUidFromRevision(const Transaction &, qint64 revision);
-    static QByteArray getTypeFromRevision(const Transaction &, qint64 revision);
-    static void recordRevision(Transaction &, qint64 revision, const QByteArray &uid, const QByteArray &type);
-    static void removeRevision(Transaction &, qint64 revision);
+    static QByteArray getUidFromRevision(const Transaction &, size_t revision);
+    static size_t getLatestRevisionFromUid(Transaction &, const QByteArray &uid);
+    static QList<size_t> getRevisionsUntilFromUid(DataStore::Transaction &, const QByteArray &uid, size_t lastRevision);
+    static QList<size_t> getRevisionsFromUid(DataStore::Transaction &, const QByteArray &uid);
+    static QByteArray getTypeFromRevision(const Transaction &, size_t revision);
+    static void recordRevision(Transaction &, size_t revision, const QByteArray &uid, const QByteArray &type);
+    static void removeRevision(Transaction &, size_t revision);
     static void recordUid(DataStore::Transaction &transaction, const QByteArray &uid, const QByteArray &type);
     static void removeUid(DataStore::Transaction &transaction, const QByteArray &uid, const QByteArray &type);
     static void getUids(const QByteArray &type, const Transaction &, const std::function<void(const QByteArray &uid)> &);
+    static bool hasUid(const QByteArray &type, const Transaction &, const QByteArray &uid);
 
     bool exists() const;
     static bool exists(const QString &storageRoot, const QString &name);
diff --git a/common/storage/entitystore.cpp b/common/storage/entitystore.cpp
--- a/common/storage/entitystore.cpp
+++ b/common/storage/entitystore.cpp
@@ -38,8 +38,9 @@
 
 static QMap<QByteArray, int> baseDbs()
 {
-    return {{"revisionType", 0},
-            {"revisions", 0},
+    return {{"revisionType", Storage::IntegerKeys},
+            {"revisions", Storage::IntegerKeys},
+            {"uidsToRevisions", Storage::AllowDuplicates | Storage::IntegerValues},
             {"uids", 0},
             {"default", 0},
             {"__flagtable", 0}};
@@ -242,12 +243,13 @@
     const auto key = Key(identifier, newRevision);
 
     DataStore::mainDatabase(d->transaction, type)
-        .write(key.toInternalByteArray(), BufferUtils::extractBuffer(fbb),
+        .write(newRevision, BufferUtils::extractBuffer(fbb),
             [&](const DataStore::Error &error) { SinkWarningCtx(d->logCtx) << "Failed to write entity" << entity.identifier() << newRevision; });
+
     DataStore::setMaxRevision(d->transaction, newRevision);
     DataStore::recordRevision(d->transaction, newRevision, entity.identifier(), type);
     DataStore::recordUid(d->transaction, entity.identifier(), type);
-    SinkTraceCtx(d->logCtx) << "Wrote entity: " << entity.identifier() << type << newRevision;
+    SinkTraceCtx(d->logCtx) << "Wrote entity: " << key << "of type:" << type;
     return true;
 }
 
@@ -319,8 +321,9 @@
     const auto key = Key(identifier, newRevision);
 
     DataStore::mainDatabase(d->transaction, type)
-        .write(key.toInternalByteArray(), BufferUtils::extractBuffer(fbb),
+        .write(newRevision, BufferUtils::extractBuffer(fbb),
             [&](const DataStore::Error &error) { SinkWarningCtx(d->logCtx) << "Failed to write entity" << newEntity.identifier() << newRevision; });
+
     DataStore::setMaxRevision(d->transaction, newRevision);
     DataStore::recordRevision(d->transaction, newRevision, newEntity.identifier(), type);
     SinkTraceCtx(d->logCtx) << "Wrote modified entity: " << newEntity.identifier() << type << newRevision;
@@ -356,8 +359,9 @@
     const auto key = Key(identifier, newRevision);
 
     DataStore::mainDatabase(d->transaction, type)
-        .write(key.toInternalByteArray(), BufferUtils::extractBuffer(fbb),
+        .write(newRevision, BufferUtils::extractBuffer(fbb),
             [&](const DataStore::Error &error) { SinkWarningCtx(d->logCtx) << "Failed to write entity" << uid << newRevision; });
+
     DataStore::setMaxRevision(d->transaction, newRevision);
     DataStore::recordRevision(d->transaction, newRevision, uid, type);
     DataStore::removeUid(d->transaction, uid, type);
@@ -375,30 +379,33 @@
     }
     SinkTraceCtx(d->logCtx) << "Cleaning up revision " << revision << uid << bufferType;
     const auto internalUid = Identifier::fromDisplayByteArray(uid).toInternalByteArray();
-    DataStore::mainDatabase(d->transaction, bufferType)
-        .scan(internalUid,
-            [&](const QByteArray &key, const QByteArray &data) -> bool {
-                EntityBuffer buffer(const_cast<const char *>(data.data()), data.size());
-                if (!buffer.isValid()) {
-                    SinkWarningCtx(d->logCtx) << "Read invalid buffer from disk";
-                } else {
-                    const auto metadata = flatbuffers::GetRoot<Metadata>(buffer.metadataBuffer());
-                    const qint64 rev = metadata->revision();
-                    const auto isRemoval = metadata->operation() == Operation_Removal;
-                    // Remove old revisions, and the current if the entity has already been removed
-                    if (rev < revision || isRemoval) {
-                        DataStore::removeRevision(d->transaction, rev);
-                        DataStore::mainDatabase(d->transaction, bufferType).remove(key);
-                    }
-                    //Don't cleanup more than specified
-                    if (rev >= revision) {
-                        return false;
-                    }
-                }
 
-                return true;
-            },
-            [&](const DataStore::Error &error) { SinkWarningCtx(d->logCtx) << "Error while reading: " << error.message; }, true);
+    // Remove old revisions
+    const auto revisionsToRemove = DataStore::getRevisionsUntilFromUid(d->transaction, uid, revision);
+
+    for (const auto &revisionToRemove : revisionsToRemove) {
+        DataStore::removeRevision(d->transaction, revisionToRemove);
+        DataStore::mainDatabase(d->transaction, bufferType).remove(revisionToRemove);
+    }
+
+    // And remove the specified revision only if marked for removal
+    DataStore::mainDatabase(d->transaction, bufferType).scan(revision, [&](size_t, const QByteArray &data) {
+        EntityBuffer buffer(const_cast<const char *>(data.data()), data.size());
+        if (!buffer.isValid()) {
+            SinkWarningCtx(d->logCtx) << "Read invalid buffer from disk";
+            return false;
+        }
+
+        const auto metadata = flatbuffers::GetRoot<Metadata>(buffer.metadataBuffer());
+        const qint64 rev = metadata->revision();
+        if (metadata->operation() == Operation_Removal) {
+            DataStore::removeRevision(d->transaction, revision);
+            DataStore::mainDatabase(d->transaction, bufferType).remove(revision);
+        }
+
+        return false;
+    });
+
     DataStore::setCleanedUpRevision(d->transaction, revision);
 }
 
@@ -433,20 +440,12 @@
         SinkTraceCtx(d->logCtx) << "Database is not existing: " << type;
         return {};
     }
-    //The scan can return duplicate results if we have multiple revisions, so we use a set to deduplicate.
+
     QSet<Identifier> keys;
-    DataStore::mainDatabase(d->getTransaction(), type)
-        .scan(QByteArray(),
-            [&](const QByteArray &key, const QByteArray &value) -> bool {
-                const auto uid = Sink::Storage::Key::fromInternalByteArray(key).identifier();
-                if (keys.contains(uid)) {
-                    //Not something that should persist if the replay works, so we keep a message for now.
-                    SinkTraceCtx(d->logCtx) << "Multiple revisions for uid: " << Sink::Storage::Key::fromInternalByteArray(key) << ". This is normal if changereplay has not completed yet.";
-                }
-                keys << uid;
-                return true;
-            },
-            [&](const DataStore::Error &error) { SinkWarningCtx(d->logCtx) << "Error during fullScan query: " << error.message; });
+
+    DataStore::getUids(type, d->getTransaction(), [&keys] (const QByteArray &uid) {
+        keys << Identifier::fromDisplayByteArray(uid);
+    });
 
     SinkTraceCtx(d->logCtx) << "Full scan retrieved " << keys.size() << " results.";
     return keys.toList().toVector();
@@ -492,12 +491,12 @@
 void EntityStore::readLatest(const QByteArray &type, const Identifier &id, const std::function<void(const QByteArray &uid, const EntityBuffer &entity)> callback)
 {
     Q_ASSERT(d);
-    const auto internalKey = id.toInternalByteArray();
+    const size_t revision = DataStore::getLatestRevisionFromUid(d->getTransaction(), id.toDisplayByteArray());
     auto db = DataStore::mainDatabase(d->getTransaction(), type);
-    db.findLatest(internalKey,
-        [=](const QByteArray &key, const QByteArray &value) {
-            const auto uid = Sink::Storage::Key::fromInternalByteArray(key).identifier().toDisplayByteArray();
-            callback(uid, Sink::EntityBuffer(value.data(), value.size()));
+    db.scan(revision,
+        [=](size_t, const QByteArray &value) {
+            callback(id.toDisplayByteArray(), Sink::EntityBuffer(value.data(), value.size()));
+            return false;
         },
         [&](const DataStore::Error &error) { SinkWarningCtx(d->logCtx) << "Error during readLatest query: " << error.message << id; });
 }
@@ -546,9 +545,9 @@
 {
     const auto key = Key::fromDisplayByteArray(displayKey);
     auto db = DataStore::mainDatabase(d->getTransaction(), type);
-    db.scan(key.toInternalByteArray(),
-        [=](const QByteArray &key, const QByteArray &value) -> bool {
-            const auto uid = Sink::Storage::Key::fromInternalByteArray(key).identifier().toDisplayByteArray();
+    db.scan(key.revision().toSizeT(),
+        [=](size_t rev, const QByteArray &value) -> bool {
+            const auto uid = DataStore::getUidFromRevision(d->transaction, rev);
             callback(uid, Sink::EntityBuffer(value.data(), value.size()));
             return false;
         },
@@ -604,18 +603,8 @@
 
 void EntityStore::readPrevious(const QByteArray &type, const Identifier &id, qint64 revision, const std::function<void(const QByteArray &uid, const EntityBuffer &entity)> callback)
 {
-    auto db = DataStore::mainDatabase(d->getTransaction(), type);
-    qint64 latestRevision = 0;
-    const auto internalUid = id.toInternalByteArray();
-    db.scan(internalUid,
-        [&latestRevision, revision](const QByteArray &key, const QByteArray &) -> bool {
-            const auto foundRevision = Key::fromInternalByteArray(key).revision().toQint64();
-            if (foundRevision < revision && foundRevision > latestRevision) {
-                latestRevision = foundRevision;
-            }
-            return true;
-        },
-        [&](const DataStore::Error &error) { SinkWarningCtx(d->logCtx) << "Failed to read current value from storage: " << error.message; }, true);
+    const auto previousRevisions = DataStore::getRevisionsUntilFromUid(d->getTransaction(), id.toDisplayByteArray(), revision);
+    const size_t latestRevision = previousRevisions[previousRevisions.size() - 1];
     const auto key = Key(id, latestRevision);
     readEntity(type, key.toDisplayByteArray(), callback);
 }
@@ -641,29 +630,29 @@
     DataStore::getUids(type, d->getTransaction(), callback);
 }
 
-bool EntityStore::contains(const QByteArray &type, const QByteArray &uid)
+bool EntityStore::contains(const QByteArray & /* type */, const QByteArray &uid)
 {
     Q_ASSERT(!uid.isEmpty());
-    const auto internalUid = Identifier::fromDisplayByteArray(uid).toInternalByteArray();
-    return DataStore::mainDatabase(d->getTransaction(), type).contains(internalUid);
+    return !DataStore::getRevisionsFromUid(d->getTransaction(), uid).isEmpty();
 }
 
 bool EntityStore::exists(const QByteArray &type, const QByteArray &uid)
 {
     bool found = false;
     bool alreadyRemoved = false;
-    const auto internalUid = Identifier::fromDisplayByteArray(uid).toInternalByteArray();
+    const size_t revision = DataStore::getLatestRevisionFromUid(d->getTransaction(), uid);
     DataStore::mainDatabase(d->transaction, type)
-        .findLatest(internalUid,
-            [&found, &alreadyRemoved](const QByteArray &key, const QByteArray &data) {
+        .scan(revision,
+            [&found, &alreadyRemoved](size_t, const QByteArray &data) {
                 auto entity = GetEntity(data.data());
                 if (entity && entity->metadata()) {
                     auto metadata = GetMetadata(entity->metadata()->Data());
                     found = true;
                     if (metadata->operation() == Operation_Removal) {
                         alreadyRemoved = true;
                     }
                 }
+                return true;
             },
             [&](const DataStore::Error &error) { SinkWarningCtx(d->logCtx) << "Failed to read old revision from storage: " << error.message; });
     if (!found) {
@@ -677,23 +666,32 @@
     return true;
 }
 
-void EntityStore::readRevisions(const QByteArray &type, const QByteArray &uid, qint64 startingRevision, const std::function<void(const QByteArray &uid, qint64 revision, const EntityBuffer &entity)> callback)
+void EntityStore::readRevisions(const QByteArray &type, const QByteArray &uid, qint64 startingRevision,
+    const std::function<void(const QByteArray &uid, qint64 revision, const EntityBuffer &entity)> callback)
 {
     Q_ASSERT(d);
     Q_ASSERT(!uid.isEmpty());
-    const auto internalUid = Identifier::fromDisplayByteArray(uid).toInternalByteArray();
-    DataStore::mainDatabase(d->transaction, type)
-        .scan(internalUid,
-            [&](const QByteArray &key, const QByteArray &value) -> bool {
-                const auto parsedKey = Key::fromInternalByteArray(key);
-                const auto revision = parsedKey.revision().toQint64();
-                if (revision >= startingRevision) {
-                    callback(parsedKey.identifier().toDisplayByteArray(), revision, Sink::EntityBuffer(value.data(), value.size()));
-                }
-                return true;
-            },
-            [&](const DataStore::Error &error) { SinkWarningCtx(d->logCtx) << "Error while reading: " << error.message; }, true);
 
+    const auto revisions = DataStore::getRevisionsFromUid(d->transaction, uid);
+
+    const auto db = DataStore::mainDatabase(d->transaction, type);
+
+    for (const auto revision : revisions) {
+        if (revision < startingRevision) {
+            continue;
+        }
+
+        db.scan(revision,
+            [&](size_t rev, const QByteArray &value) {
+                Q_ASSERT(rev == revision);
+                callback(uid, revision, Sink::EntityBuffer(value.data(), value.size()));
+                return false;
+            },
+            [&](const DataStore::Error &error) {
+                SinkWarningCtx(d->logCtx) << "Error while reading: " << error.message;
+            },
+            true);
+    }
 }
 
 qint64 EntityStore::maxRevision()
diff --git a/common/storage/key.h b/common/storage/key.h
--- a/common/storage/key.h
+++ b/common/storage/key.h
@@ -67,14 +67,15 @@
     static const constexpr size_t INTERNAL_REPR_SIZE = 19;
     static const constexpr size_t DISPLAY_REPR_SIZE = 19;
 
-    Revision(qint64 rev) : rev(rev) {}
+    Revision(size_t rev) : rev(rev) {}
 
     QByteArray toInternalByteArray() const;
     static Revision fromInternalByteArray(const QByteArray &bytes);
     QString toDisplayString() const;
     QByteArray toDisplayByteArray() const;
     static Revision fromDisplayByteArray(const QByteArray &bytes);
     qint64 toQint64() const;
+    size_t toSizeT() const;
 
     static bool isValidInternal(const QByteArray &);
     static bool isValidDisplay(const QByteArray &);
@@ -84,7 +85,7 @@
     bool operator!=(const Revision &other) const;
 
 private:
-    qint64 rev;
+    size_t rev;
 };
 
 class Key
diff --git a/common/storage/key.cpp b/common/storage/key.cpp
--- a/common/storage/key.cpp
+++ b/common/storage/key.cpp
@@ -155,6 +155,11 @@
     return rev;
 }
 
+size_t Revision::toSizeT() const
+{
+    return rev;
+}
+
 bool Revision::isValidInternal(const QByteArray &bytes)
 {
     if (bytes.size() != Revision::INTERNAL_REPR_SIZE) {
diff --git a/common/storage_common.cpp b/common/storage_common.cpp
--- a/common/storage_common.cpp
+++ b/common/storage_common.cpp
@@ -117,45 +117,102 @@
     return r;
 }
 
-QByteArray DataStore::getUidFromRevision(const DataStore::Transaction &transaction, qint64 revision)
+QByteArray DataStore::getUidFromRevision(const DataStore::Transaction &transaction, size_t revision)
 {
     QByteArray uid;
-    transaction.openDatabase("revisions")
-        .scan(QByteArray::number(revision),
-            [&](const QByteArray &, const QByteArray &value) -> bool {
-                uid = QByteArray{value.constData(), value.size()};
+    transaction
+        .openDatabase("revisions", /* errorHandler = */ {}, IntegerKeys)
+        .scan(revision,
+            [&](const size_t, const QByteArray &value) -> bool {
+                uid = QByteArray{ value.constData(), value.size() };
                 return false;
             },
-            [revision](const Error &error) { SinkWarning() << "Couldn't find uid for revision: " << revision << error.message; });
+            [revision](const Error &error) {
+                SinkWarning() << "Couldn't find uid for revision: " << revision << error.message;
+            });
     Q_ASSERT(!uid.isEmpty());
     return uid;
 }
 
-QByteArray DataStore::getTypeFromRevision(const DataStore::Transaction &transaction, qint64 revision)
+size_t DataStore::getLatestRevisionFromUid(DataStore::Transaction &t, const QByteArray &uid)
+{
+    size_t revision;
+    t.openDatabase("uidsToRevisions", {}, AllowDuplicates | IntegerValues)
+        .findLatest(uid, [&revision](const QByteArray &key, const QByteArray &value) {
+            revision = byteArrayToSizeT(value);
+        });
+
+    return revision;
+}
+
+QList<size_t> DataStore::getRevisionsUntilFromUid(DataStore::Transaction &t, const QByteArray &uid, size_t lastRevision)
+{
+    QList<size_t> queriedRevisions;
+    t.openDatabase("uidsToRevisions", {}, AllowDuplicates | IntegerValues)
+        .scan(uid, [&queriedRevisions, lastRevision](const QByteArray &, const QByteArray &value) {
+            size_t currentRevision = byteArrayToSizeT(value);
+            if (currentRevision < lastRevision) {
+                queriedRevisions << currentRevision;
+                return true;
+            }
+
+            return false;
+        });
+
+    return queriedRevisions;
+}
+
+QList<size_t> DataStore::getRevisionsFromUid(DataStore::Transaction &t, const QByteArray &uid)
+{
+    QList<size_t> queriedRevisions;
+    t.openDatabase("uidsToRevisions", {}, AllowDuplicates | IntegerValues)
+        .scan(uid, [&queriedRevisions](const QByteArray &, const QByteArray &value) {
+            queriedRevisions << byteArrayToSizeT(value);
+            return true;
+        });
+
+    return queriedRevisions;
+}
+
+QByteArray DataStore::getTypeFromRevision(const DataStore::Transaction &transaction, size_t revision)
 {
     QByteArray type;
-    transaction.openDatabase("revisionType")
-        .scan(QByteArray::number(revision),
-            [&](const QByteArray &, const QByteArray &value) -> bool {
+    transaction.openDatabase("revisionType", /* errorHandler = */ {}, IntegerKeys)
+        .scan(revision,
+            [&](const size_t, const QByteArray &value) -> bool {
                 type = QByteArray{value.constData(), value.size()};
                 return false;
             },
             [revision](const Error &error) { SinkWarning() << "Couldn't find type for revision " << revision; });
     Q_ASSERT(!type.isEmpty());
     return type;
 }
 
-void DataStore::recordRevision(DataStore::Transaction &transaction, qint64 revision, const QByteArray &uid, const QByteArray &type)
+void DataStore::recordRevision(DataStore::Transaction &transaction, size_t revision,
+    const QByteArray &uid, const QByteArray &type)
 {
-    // TODO use integerkeys
-    transaction.openDatabase("revisions").write(QByteArray::number(revision), uid);
-    transaction.openDatabase("revisionType").write(QByteArray::number(revision), type);
+    transaction
+        .openDatabase("revisions", /* errorHandler = */ {}, IntegerKeys)
+        .write(revision, uid);
+    transaction.openDatabase("uidsToRevisions", /* errorHandler = */ {}, AllowDuplicates | IntegerValues)
+        .write(uid, sizeTToByteArray(revision));
+    transaction
+        .openDatabase("revisionType", /* errorHandler = */ {}, IntegerKeys)
+        .write(revision, type);
 }
 
-void DataStore::removeRevision(DataStore::Transaction &transaction, qint64 revision)
+void DataStore::removeRevision(DataStore::Transaction &transaction, size_t revision)
 {
-    transaction.openDatabase("revisions").remove(QByteArray::number(revision));
-    transaction.openDatabase("revisionType").remove(QByteArray::number(revision));
+    const QByteArray uid = getUidFromRevision(transaction, revision);
+
+    transaction
+        .openDatabase("revisions", /* errorHandler = */ {}, IntegerKeys)
+        .remove(revision);
+    transaction.openDatabase("uidsToRevisions", /* errorHandler = */ {}, AllowDuplicates | IntegerValues)
+        .remove(uid, sizeTToByteArray(revision));
+    transaction
+        .openDatabase("revisionType", /* errorHandler = */ {}, IntegerKeys)
+        .remove(revision);
 }
 
 void DataStore::recordUid(DataStore::Transaction &transaction, const QByteArray &uid, const QByteArray &type)
@@ -176,6 +233,18 @@
     });
 }
 
+bool DataStore::hasUid(const QByteArray &type, const Transaction &transaction, const QByteArray &uid)
+{
+    bool hasTheUid = false;
+    transaction.openDatabase(type + "uids").scan(uid, [&](const QByteArray &key, const QByteArray &) {
+        Q_ASSERT(uid == key);
+        hasTheUid = true;
+        return false;
+    });
+
+    return hasTheUid;
+}
+
 bool DataStore::isInternalKey(const char *key)
 {
     return key && strncmp(key, s_internalPrefix, s_internalPrefixSize) == 0;
@@ -207,7 +276,7 @@
         Q_ASSERT(false);
         return {};
     }
-    return t.openDatabase(type + ".main");
+    return t.openDatabase(type + ".main", /* errorHandler= */ {}, IntegerKeys);
 }
 
 bool DataStore::NamedDatabase::contains(const QByteArray &uid)
diff --git a/common/storage_lmdb.cpp b/common/storage_lmdb.cpp
--- a/common/storage_lmdb.cpp
+++ b/common/storage_lmdb.cpp
@@ -48,6 +48,10 @@
 static QHash<QString, MDB_env *> sEnvironments;
 static QHash<QString, MDB_dbi> sDbis;
 
+int AllowDuplicates = MDB_DUPSORT;
+int IntegerKeys = MDB_INTEGERKEY;
+int IntegerValues = MDB_INTEGERDUP;
+
 int getErrorCode(int e)
 {
     switch (e) {
@@ -101,14 +105,8 @@
  * and we always need to commit the transaction ASAP
  * We can only ever enter from one point per process.
  */
-static bool createDbi(MDB_txn *transaction, const QByteArray &db, bool readOnly, bool allowDuplicates, MDB_dbi &dbi)
+static bool createDbi(MDB_txn *transaction, const QByteArray &db, bool readOnly, int flags, MDB_dbi &dbi)
 {
-
-    unsigned int flags = 0;
-    if (allowDuplicates) {
-        flags |= MDB_DUPSORT;
-    }
-
     MDB_dbi flagtableDbi;
     if (const int rc = mdb_dbi_open(transaction, "__flagtable", readOnly ? 0 : MDB_CREATE, &flagtableDbi)) {
         if (!readOnly) {
@@ -130,6 +128,10 @@
         }
     }
 
+    if (flags & IntegerValues && !(flags & AllowDuplicates)) {
+        SinkWarning() << "Opening a database with integer values, but not duplicate keys";
+    }
+
     if (const int rc = mdb_dbi_open(transaction, db.constData(), flags, &dbi)) {
         //Create the db if it is not existing already
         if (rc == MDB_NOTFOUND && !readOnly) {
@@ -165,7 +167,7 @@
             //Store the flags without the create option
             const auto ba = QByteArray::number(flags);
             value.mv_data = const_cast<void*>(static_cast<const void*>(ba.constData()));
-            value.mv_size = db.size();
+            value.mv_size = ba.size();
             if (const int rc = mdb_put(transaction, flagtableDbi, &key, &value, MDB_NOOVERWRITE)) {
                 //We expect this to fail if we're only creating the dbi but not the db
                 if (rc != MDB_KEYEXIST) {
@@ -175,7 +177,7 @@
         } else {
             //It's not an error if we only want to read
             if (!readOnly) {
-                SinkWarning() << "Failed to open db " << QByteArray(mdb_strerror(rc));
+                SinkWarning() << "Failed to open db " << db << "error:" << QByteArray(mdb_strerror(rc));
                 return true;
             }
             return false;
@@ -187,8 +189,14 @@
 class DataStore::NamedDatabase::Private
 {
 public:
-    Private(const QByteArray &_db, bool _allowDuplicates, const std::function<void(const DataStore::Error &error)> &_defaultErrorHandler, const QString &_name, MDB_txn *_txn)
-        : db(_db), transaction(_txn), allowDuplicates(_allowDuplicates), defaultErrorHandler(_defaultErrorHandler), name(_name)
+    Private(const QByteArray &_db, int _flags,
+        const std::function<void(const DataStore::Error &error)> &_defaultErrorHandler,
+        const QString &_name, MDB_txn *_txn)
+        : db(_db),
+          transaction(_txn),
+          flags(_flags),
+          defaultErrorHandler(_defaultErrorHandler),
+          name(_name)
     {
     }
 
@@ -199,7 +207,7 @@
     QByteArray db;
     MDB_txn *transaction;
     MDB_dbi dbi;
-    bool allowDuplicates;
+    int flags;
     std::function<void(const DataStore::Error &error)> defaultErrorHandler;
     QString name;
     bool createdNewDbi = false;
@@ -313,7 +321,7 @@
         } else {
             dbiTransaction = transaction;
         }
-        if (createDbi(dbiTransaction, db, readOnly, allowDuplicates, dbi)) {
+        if (createDbi(dbiTransaction, db, readOnly, flags, dbi)) {
             if (readOnly) {
                 mdb_txn_commit(dbiTransaction);
                 Q_ASSERT(!sDbis.contains(dbiName));
@@ -371,6 +379,12 @@
     delete d;
 }
 
+bool DataStore::NamedDatabase::write(const size_t key, const QByteArray &value,
+    const std::function<void(const DataStore::Error &error)> &errorHandler)
+{
+    return write(sizeTToByteArray(key), value, errorHandler);
+}
+
 bool DataStore::NamedDatabase::write(const QByteArray &sKey, const QByteArray &sValue, const std::function<void(const DataStore::Error &error)> &errorHandler)
 {
     if (!d || !d->transaction) {
@@ -407,11 +421,23 @@
     return !rc;
 }
 
+void DataStore::NamedDatabase::remove(
+    const size_t key, const std::function<void(const DataStore::Error &error)> &errorHandler)
+{
+    return remove(sizeTToByteArray(key), errorHandler);
+}
+
 void DataStore::NamedDatabase::remove(const QByteArray &k, const std::function<void(const DataStore::Error &error)> &errorHandler)
 {
     remove(k, QByteArray(), errorHandler);
 }
 
+void DataStore::NamedDatabase::remove(const size_t key, const QByteArray &value,
+    const std::function<void(const DataStore::Error &error)> &errorHandler)
+{
+    return remove(sizeTToByteArray(key), value, errorHandler);
+}
+
 void DataStore::NamedDatabase::remove(const QByteArray &k, const QByteArray &value, const std::function<void(const DataStore::Error &error)> &errorHandler)
 {
     if (!d || !d->transaction) {
@@ -445,6 +471,17 @@
     }
 }
 
+int DataStore::NamedDatabase::scan(const size_t key,
+    const std::function<bool(size_t key, const QByteArray &value)> &resultHandler,
+    const std::function<void(const DataStore::Error &error)> &errorHandler, bool skipInternalKeys) const
+{
+    return scan(sizeTToByteArray(key),
+        [&resultHandler](const QByteArray &key, const QByteArray &value) {
+            return resultHandler(byteArrayToSizeT(key), value);
+        },
+        errorHandler, /* findSubstringKeys = */ false, skipInternalKeys);
+}
+
 int DataStore::NamedDatabase::scan(const QByteArray &k, const std::function<bool(const QByteArray &key, const QByteArray &value)> &resultHandler,
     const std::function<void(const DataStore::Error &error)> &errorHandler, bool findSubstringKeys, bool skipInternalKeys) const
 {
@@ -471,8 +508,10 @@
 
     int numberOfRetrievedValues = 0;
 
-    if (k.isEmpty() || d->allowDuplicates || findSubstringKeys) {
-        MDB_cursor_op op = d->allowDuplicates ? MDB_SET : MDB_FIRST;
+    bool allowDuplicates = d->flags & AllowDuplicates;
+
+    if (k.isEmpty() || allowDuplicates || findSubstringKeys) {
+        MDB_cursor_op op = allowDuplicates ? MDB_SET : MDB_FIRST;
         if (findSubstringKeys) {
             op = MDB_SET_RANGE;
         }
@@ -490,7 +529,7 @@
                         key.mv_data = (void *)k.constData();
                         key.mv_size = k.size();
                     }
-                    MDB_cursor_op nextOp = (d->allowDuplicates && !findSubstringKeys) ? MDB_NEXT_DUP : MDB_NEXT;
+                    MDB_cursor_op nextOp = (allowDuplicates && !findSubstringKeys) ? MDB_NEXT_DUP : MDB_NEXT;
                     while ((rc = mdb_cursor_get(cursor, &key, &data, nextOp)) == 0) {
                         const auto current = QByteArray::fromRawData((char *)key.mv_data, key.mv_size);
                         // Every consequitive lookup simply iterates through the list
@@ -529,6 +568,18 @@
     return numberOfRetrievedValues;
 }
 
+
+void DataStore::NamedDatabase::findLatest(size_t key,
+    const std::function<void(size_t key, const QByteArray &value)> &resultHandler,
+    const std::function<void(const DataStore::Error &error)> &errorHandler) const
+{
+    return findLatest(sizeTToByteArray(key),
+        [&resultHandler](const QByteArray &key, const QByteArray &value) {
+            resultHandler(byteArrayToSizeT(value), value);
+        },
+        errorHandler);
+}
+
 void DataStore::NamedDatabase::findLatest(const QByteArray &k, const std::function<void(const QByteArray &key, const QByteArray &value)> &resultHandler,
     const std::function<void(const DataStore::Error &error)> &errorHandler) const
 {
@@ -602,6 +653,17 @@
     return;
 }
 
+int DataStore::NamedDatabase::findAllInRange(const size_t lowerBound, const size_t upperBound,
+    const std::function<void(size_t key, const QByteArray &value)> &resultHandler,
+    const std::function<void(const DataStore::Error &error)> &errorHandler) const
+{
+    return findAllInRange(sizeTToByteArray(lowerBound), sizeTToByteArray(upperBound),
+        [&resultHandler](const QByteArray &key, const QByteArray &value) {
+            resultHandler(byteArrayToSizeT(value), value);
+        },
+        errorHandler);
+}
+
 int DataStore::NamedDatabase::findAllInRange(const QByteArray &lowerBound, const QByteArray &upperBound,
     const std::function<void(const QByteArray &key, const QByteArray &value)> &resultHandler,
     const std::function<void(const DataStore::Error &error)> &errorHandler) const
@@ -839,39 +901,18 @@
     d->transaction = nullptr;
 }
 
-//Ensure that we opened the correct database by comparing the expected identifier with the one
-//we write to the database on first open.
-static bool ensureCorrectDb(DataStore::NamedDatabase &database, const QByteArray &db, bool readOnly)
-{
-    bool openedTheWrongDatabase = false;
-    auto count = database.scan("__internal_dbname", [db, &openedTheWrongDatabase](const QByteArray &key, const QByteArray &value) ->bool {
-        if (value != db) {
-            SinkWarning() << "Opened the wrong database, got " << value << " instead of " << db;
-            openedTheWrongDatabase = true;
-        }
-        return false;
-    },
-    [&](const DataStore::Error &) {
-    }, false);
-    //This is the first time we open this database in a write transaction, write the db name
-    if (!count) {
-        if (!readOnly) {
-            database.write("__internal_dbname", db);
-        }
-    }
-    return !openedTheWrongDatabase;
-}
-
-DataStore::NamedDatabase DataStore::Transaction::openDatabase(const QByteArray &db, const std::function<void(const DataStore::Error &error)> &errorHandler, bool allowDuplicates) const
+DataStore::NamedDatabase DataStore::Transaction::openDatabase(const QByteArray &db,
+    const std::function<void(const DataStore::Error &error)> &errorHandler, int flags) const
 {
     if (!d) {
         SinkError() << "Tried to open database on invalid transaction: " << db;
         return DataStore::NamedDatabase();
     }
     Q_ASSERT(d->transaction);
     // We don't now if anything changed
     d->implicitCommit = true;
-    auto p = new DataStore::NamedDatabase::Private(db, allowDuplicates, d->defaultErrorHandler, d->name, d->transaction);
+    auto p = new DataStore::NamedDatabase::Private(
+        db, flags, d->defaultErrorHandler, d->name, d->transaction);
     auto ret = p->openDatabase(d->requestedRead, errorHandler);
     if (!ret) {
         delete p;
@@ -883,11 +924,6 @@
     }
 
     auto database = DataStore::NamedDatabase(p);
-    if (!ensureCorrectDb(database, db, d->requestedRead)) {
-        SinkWarning() << "Failed to open the database correctly" << db;
-        Q_ASSERT(false);
-        return DataStore::NamedDatabase();
-    }
     return database;
 }
 
@@ -1049,11 +1085,11 @@
 
                             //Create dbis from the given layout.
                             for (auto it = layout.tables.constBegin(); it != layout.tables.constEnd(); it++) {
-                                const bool allowDuplicates = it.value();
+                                const int flags = it.value();
                                 MDB_dbi dbi = 0;
                                 const auto db = it.key();
                                 const auto dbiName = name + db;
-                                if (createDbi(transaction, db, readOnly, allowDuplicates, dbi)) {
+                                if (createDbi(transaction, db, readOnly, flags, dbi)) {
                                     sDbis.insert(dbiName, dbi);
                                 }
                             }
@@ -1063,8 +1099,8 @@
                                 MDB_dbi dbi = 0;
                                 const auto dbiName = name + db;
                                 //We're going to load the flags anyways.
-                                bool allowDuplicates = false;
-                                if (createDbi(transaction, db, readOnly, allowDuplicates, dbi)) {
+                                const int flags = 0;
+                                if (createDbi(transaction, db, readOnly, flags, dbi)) {
                                     sDbis.insert(dbiName, dbi);
                                 }
                             }
diff --git a/common/utils.h b/common/utils.h
--- a/common/utils.h
+++ b/common/utils.h
@@ -26,6 +26,20 @@
 
 QByteArray createUuid();
 
+// No copy is done on this functions. Therefore, the caller must not use the
+// returned QByteArray after the size_t has been destroyed.
+const QByteArray sizeTToByteArray(const size_t &);
+size_t byteArrayToSizeT(const QByteArray &);
+
+template <typename T>
+static QByteArray padNumber(T number);
+
+template <>
+QByteArray padNumber<size_t>(size_t number)
+{
+    return padNumber<qint64>(number);
+}
+
 template <typename T>
 static QByteArray padNumber(T number)
 {
diff --git a/common/utils.cpp b/common/utils.cpp
--- a/common/utils.cpp
+++ b/common/utils.cpp
@@ -23,3 +23,13 @@
 {
     return QUuid::createUuid().toByteArray();
 }
+
+const QByteArray Sink::sizeTToByteArray(const size_t &value)
+{
+    return QByteArray::fromRawData(reinterpret_cast<const char *>(&value), sizeof(size_t));
+}
+
+size_t Sink::byteArrayToSizeT(const QByteArray &value)
+{
+    return *reinterpret_cast<const size_t *>(value.constData());
+}
diff --git a/sinksh/syntax_modules/sink_inspect.cpp b/sinksh/syntax_modules/sink_inspect.cpp
--- a/sinksh/syntax_modules/sink_inspect.cpp
+++ b/sinksh/syntax_modules/sink_inspect.cpp
@@ -87,13 +87,13 @@
                 [&] (const Sink::Storage::DataStore::Error &e) {
                     Q_ASSERT(false);
                     state.printError(e.message);
-                }, false);
+                }, Sink::Storage::IntegerKeys);
 
         auto ridMap = syncTransaction.openDatabase("localid.mapping." + type,
                 [&] (const Sink::Storage::DataStore::Error &e) {
                     Q_ASSERT(false);
                     state.printError(e.message);
-                }, false);
+                });
 
         QHash<QByteArray, QByteArray> hash;
 
@@ -108,7 +108,8 @@
 
         QSet<QByteArray> uids;
         db.scan("", [&] (const QByteArray &key, const QByteArray &data) {
-                    uids.insert(Key::fromInternalByteArray(key).identifier().toDisplayByteArray());
+                    size_t revision = Sink::byteArrayToSizeT(key);
+                    uids.insert(Sink::Storage::DataStore::getUidFromRevision(transaction, revision));
                     return true;
                 },
                 [&](const Sink::Storage::DataStore::Error &e) {
@@ -180,7 +181,7 @@
             [&] (const Sink::Storage::DataStore::Error &e) {
                 Q_ASSERT(false);
                 state.printError(e.message);
-            }, false);
+            });
 
     if (showInternal) {
         //Print internal keys
diff --git a/tests/dbwriter.cpp b/tests/dbwriter.cpp
--- a/tests/dbwriter.cpp
+++ b/tests/dbwriter.cpp
@@ -29,14 +29,14 @@
             qWarning() << "No valid transaction";
             return -1;
         }
-        transaction.openDatabase("a", nullptr, false).write(QByteArray::number(i), "a");
-        transaction.openDatabase("b", nullptr, false).write(QByteArray::number(i), "b");
-        transaction.openDatabase("c", nullptr, false).write(QByteArray::number(i), "c");
-        transaction.openDatabase("p", nullptr, false).write(QByteArray::number(i), "c");
-        transaction.openDatabase("q", nullptr, false).write(QByteArray::number(i), "c");
+        transaction.openDatabase("a", nullptr, 0).write(QByteArray::number(i), "a");
+        transaction.openDatabase("b", nullptr, 0).write(QByteArray::number(i), "b");
+        transaction.openDatabase("c", nullptr, 0).write(QByteArray::number(i), "c");
+        transaction.openDatabase("p", nullptr, 0).write(QByteArray::number(i), "c");
+        transaction.openDatabase("q", nullptr, 0).write(QByteArray::number(i), "c");
         if (i > (count/2)) {
             for (int d = 0; d < 40; d++) {
-                transaction.openDatabase("db" + QByteArray::number(d), nullptr, false).write(QByteArray::number(i), "a");
+                transaction.openDatabase("db" + QByteArray::number(d), nullptr, 0).write(QByteArray::number(i), "a");
             }
         }
         if ((i % 1000) == 0) {
diff --git a/tests/entitystoretest.cpp b/tests/entitystoretest.cpp
--- a/tests/entitystoretest.cpp
+++ b/tests/entitystoretest.cpp
@@ -18,6 +18,7 @@
     void initTestCase()
     {
         Sink::AdaptorFactoryRegistry::instance().registerFactory<Sink::ApplicationDomain::Mail, TestMailAdaptorFactory>("test");
+        Sink::AdaptorFactoryRegistry::instance().registerFactory<Sink::ApplicationDomain::Event, TestEventAdaptorFactory>("test");
     }
 
     void cleanup()
@@ -29,6 +30,100 @@
     {
     }
 
+    void testFullScan()
+    {
+        using namespace Sink;
+        ResourceContext resourceContext{resourceInstanceIdentifier.toUtf8(), "dummy", AdaptorFactoryRegistry::instance().getFactories("test")};
+        Storage::EntityStore store(resourceContext, {});
+
+        auto mail = ApplicationDomain::ApplicationDomainType::createEntity<ApplicationDomain::Mail>("res1");
+        mail.setExtractedMessageId("messageid");
+        mail.setExtractedSubject("boo");
+
+        auto mail2 = ApplicationDomain::ApplicationDomainType::createEntity<ApplicationDomain::Mail>("res1");
+        mail2.setExtractedMessageId("messageid2");
+        mail2.setExtractedSubject("foo");
+
+        auto mail3 = ApplicationDomain::ApplicationDomainType::createEntity<ApplicationDomain::Mail>("res1");
+        mail3.setExtractedMessageId("messageid2");
+        mail3.setExtractedSubject("foo");
+
+        store.startTransaction(Storage::DataStore::ReadWrite);
+        store.add("mail", mail, false);
+        store.add("mail", mail2, false);
+        store.add("mail", mail3, false);
+
+        mail.setExtractedSubject("foo");
+
+        store.modify("mail", mail, QByteArrayList{}, false);
+
+        {
+            const auto ids = store.fullScan("mail");
+
+            QCOMPARE(ids.size(), 3);
+            QVERIFY(ids.contains(Sink::Storage::Identifier::fromDisplayByteArray(mail.identifier())));
+            QVERIFY(ids.contains(Sink::Storage::Identifier::fromDisplayByteArray(mail2.identifier())));
+            QVERIFY(ids.contains(Sink::Storage::Identifier::fromDisplayByteArray(mail3.identifier())));
+        }
+
+        store.remove("mail", mail3, false);
+        store.commitTransaction();
+
+        {
+            const auto ids = store.fullScan("mail");
+
+            QCOMPARE(ids.size(), 2);
+            QVERIFY(ids.contains(Sink::Storage::Identifier::fromDisplayByteArray(mail.identifier())));
+            QVERIFY(ids.contains(Sink::Storage::Identifier::fromDisplayByteArray(mail2.identifier())));
+        }
+    }
+
+    void testExistsAndContains()
+    {
+
+        using namespace Sink;
+        ResourceContext resourceContext{resourceInstanceIdentifier.toUtf8(), "dummy", AdaptorFactoryRegistry::instance().getFactories("test")};
+        Storage::EntityStore store(resourceContext, {});
+
+        auto mail = ApplicationDomain::ApplicationDomainType::createEntity<ApplicationDomain::Mail>("res1");
+        mail.setExtractedMessageId("messageid");
+        mail.setExtractedSubject("boo");
+
+        auto mail2 = ApplicationDomain::ApplicationDomainType::createEntity<ApplicationDomain::Mail>("res1");
+        mail2.setExtractedMessageId("messageid2");
+        mail2.setExtractedSubject("foo");
+
+        auto mail3 = ApplicationDomain::ApplicationDomainType::createEntity<ApplicationDomain::Mail>("res1");
+        mail3.setExtractedMessageId("messageid2");
+        mail3.setExtractedSubject("foo");
+
+        auto event = ApplicationDomain::ApplicationDomainType::createEntity<ApplicationDomain::Event>("res1");
+        event.setExtractedUid("messageid2");
+        event.setExtractedSummary("foo");
+
+        store.startTransaction(Storage::DataStore::ReadWrite);
+        store.add("mail", mail, false);
+        store.add("mail", mail2, false);
+        store.add("mail", mail3, false);
+        store.add("event", event, false);
+
+        mail.setExtractedSubject("foo");
+
+        store.modify("mail", mail, QByteArrayList{}, false);
+        store.remove("mail", mail3, false);
+        store.commitTransaction();
+
+        QVERIFY(store.contains("mail", mail.identifier()));
+        QVERIFY(store.contains("mail", mail2.identifier()));
+        QVERIFY(store.contains("mail", mail3.identifier()));
+        QVERIFY(store.contains("event", event.identifier()));
+
+        QVERIFY(store.exists("mail", mail.identifier()));
+        QVERIFY(store.exists("mail", mail2.identifier()));
+        QVERIFY(!store.exists("mail", mail3.identifier()));
+        QVERIFY(store.exists("event", event.identifier()));
+    }
+
     void readAll()
     {
         using namespace Sink;
diff --git a/tests/pipelinetest.cpp b/tests/pipelinetest.cpp
--- a/tests/pipelinetest.cpp
+++ b/tests/pipelinetest.cpp
@@ -28,26 +28,29 @@
     store.removeFromDisk();
 }
 
-static QList<QByteArray> getKeys(const QByteArray &dbEnv, const QByteArray &name)
+static QList<Sink::Storage::Key> getKeys(const QByteArray &dbEnv, const QByteArray &name)
 {
     Sink::Storage::DataStore store(Sink::storageLocation(), dbEnv, Sink::Storage::DataStore::ReadOnly);
     auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadOnly);
-    auto db = transaction.openDatabase(name, nullptr, false);
-    QList<QByteArray> result;
+    auto db = transaction.openDatabase(name, nullptr, Sink::Storage::IntegerKeys);
+    QList<Sink::Storage::Key> result;
     db.scan("", [&](const QByteArray &key, const QByteArray &value) {
-        result << key;
+        size_t revision = Sink::byteArrayToSizeT(key);
+        result << Sink::Storage::Key(Sink::Storage::Identifier::fromDisplayByteArray(
+                                         Sink::Storage::DataStore::getUidFromRevision(transaction, revision)),
+            revision);
         return true;
     });
     return result;
 }
 
-static QByteArray getEntity(const QByteArray &dbEnv, const QByteArray &name, const QByteArray &uid)
+static QByteArray getEntity(const QByteArray &dbEnv, const QByteArray &name, const Sink::Storage::Key &key)
 {
     Sink::Storage::DataStore store(Sink::storageLocation(), dbEnv, Sink::Storage::DataStore::ReadOnly);
     auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadOnly);
-    auto db = transaction.openDatabase(name, nullptr, false);
+    auto db = transaction.openDatabase(name, nullptr, Sink::Storage::IntegerKeys);
     QByteArray result;
-    db.scan(uid, [&](const QByteArray &key, const QByteArray &value) {
+    db.scan(key.revision().toSizeT(), [&](size_t rev, const QByteArray &value) {
         result = value;
         return true;
     });
@@ -251,7 +254,7 @@
         // Get uid of written entity
         auto keys = getKeys(instanceIdentifier(), "event.main");
         QCOMPARE(keys.size(), 1);
-        auto key = Sink::Storage::Key::fromInternalByteArray(keys.first());
+        auto key = keys.first();
         const auto uid = key.identifier().toDisplayByteArray();
 
         // Execute the modification
@@ -264,7 +267,7 @@
         key.setRevision(2);
 
         // Ensure we've got the new revision with the modification
-        auto buffer = getEntity(instanceIdentifier(), "event.main", key.toInternalByteArray());
+        auto buffer = getEntity(instanceIdentifier(), "event.main", key);
         QVERIFY(!buffer.isEmpty());
         Sink::EntityBuffer entityBuffer(buffer.data(), buffer.size());
         auto adaptor = adaptorFactory->createAdaptor(entityBuffer.entity());
@@ -299,7 +302,7 @@
         // Get uid of written entity
         auto keys = getKeys(instanceIdentifier(), "event.main");
         QCOMPARE(keys.size(), 1);
-        auto key = Sink::Storage::Key::fromInternalByteArray(keys.first());
+        auto key = keys.first();
         const auto uid = key.identifier().toDisplayByteArray();
 
 
@@ -322,7 +325,7 @@
         key.setRevision(3);
 
         // Ensure we've got the new revision with the modification
-        auto buffer = getEntity(instanceIdentifier(), "event.main", key.toInternalByteArray());
+        auto buffer = getEntity(instanceIdentifier(), "event.main", key);
         QVERIFY(!buffer.isEmpty());
         Sink::EntityBuffer entityBuffer(buffer.data(), buffer.size());
         auto adaptor = adaptorFactory->createAdaptor(entityBuffer.entity());
@@ -343,7 +346,7 @@
         auto result = getKeys(instanceIdentifier(), "event.main");
         QCOMPARE(result.size(), 1);
 
-        const auto uid = Sink::Storage::Key::fromInternalByteArray(result.first()).identifier().toDisplayByteArray();
+        const auto uid = result.first().identifier().toDisplayByteArray();
 
         // Delete entity
         auto deleteCommand = deleteEntityCommand(uid, 1);
@@ -386,7 +389,7 @@
         pipeline.startTransaction();
         auto keys = getKeys(instanceIdentifier(), "event.main");
         QCOMPARE(keys.size(), 1);
-        const auto uid = Sink::Storage::Key::fromInternalByteArray(keys.first()).identifier().toDisplayByteArray();
+        const auto uid = keys.first().identifier().toDisplayByteArray();
         {
             auto modifyCommand = modifyEntityCommand(createEvent(entityFbb, "summary2"), uid, 1);
             pipeline.modifiedEntity(modifyCommand.constData(), modifyCommand.size());
@@ -427,7 +430,7 @@
         // Get uid of written entity
         auto keys = getKeys(instanceIdentifier(), "event.main");
         QCOMPARE(keys.size(), 1);
-        auto key = Sink::Storage::Key::fromInternalByteArray(keys.first());
+        auto key = keys.first();
         const auto uid = key.identifier().toDisplayByteArray();
 
         //Simulate local modification
@@ -453,7 +456,7 @@
         key.setRevision(3);
 
         // Ensure we've got the new revision with the modification
-        auto buffer = getEntity(instanceIdentifier(), "event.main", key.toInternalByteArray());
+        auto buffer = getEntity(instanceIdentifier(), "event.main", key);
         QVERIFY(!buffer.isEmpty());
         Sink::EntityBuffer entityBuffer(buffer.data(), buffer.size());
         auto adaptor = adaptorFactory->createAdaptor(entityBuffer.entity());
diff --git a/tests/storagetest.cpp b/tests/storagetest.cpp
--- a/tests/storagetest.cpp
+++ b/tests/storagetest.cpp
@@ -227,7 +227,7 @@
         bool gotError = false;
         Sink::Storage::DataStore store(testDataPath, {dbName, {{"default", 0}}}, Sink::Storage::DataStore::ReadWrite);
         auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
-        auto db = transaction.openDatabase("default", nullptr, false);
+        auto db = transaction.openDatabase("default");
         db.write("key", "value");
         db.write("key", "value");
 
@@ -250,9 +250,10 @@
     {
         bool gotResult = false;
         bool gotError = false;
-        Sink::Storage::DataStore store(testDataPath, {dbName, {{"default", 0x04}}}, Sink::Storage::DataStore::ReadWrite);
+        const int flags = Sink::Storage::AllowDuplicates;
+        Sink::Storage::DataStore store(testDataPath, {dbName, {{"default", flags}}}, Sink::Storage::DataStore::ReadWrite);
         auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
-        auto db = transaction.openDatabase("default", nullptr, true);
+        auto db = transaction.openDatabase("default", nullptr, flags);
         db.write("key", "value1");
         db.write("key", "value2");
         int numValues = db.scan("key",
@@ -357,7 +358,7 @@
 
         Sink::Storage::DataStore store(testDataPath, {dbName, {{"test", 0}}}, Sink::Storage::DataStore::ReadWrite);
         store.createTransaction(Sink::Storage::DataStore::ReadWrite)
-            .openDatabase("test", nullptr, true)
+            .openDatabase("test", nullptr, Sink::Storage::AllowDuplicates)
             .write("key1", "value1", [&](const Sink::Storage::DataStore::Error &error) {
                 qDebug() << error.message;
                 gotError = true;
@@ -368,9 +369,10 @@
     // By default we want only exact matches
     void testSubstringKeys()
     {
-        Sink::Storage::DataStore store(testDataPath, {dbName, {{"test", 0x04}}}, Sink::Storage::DataStore::ReadWrite);
+        const int flags = Sink::Storage::AllowDuplicates;
+        Sink::Storage::DataStore store(testDataPath, {dbName, {{"test", flags}}}, Sink::Storage::DataStore::ReadWrite);
         auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
-        auto db = transaction.openDatabase("test", nullptr, true);
+        auto db = transaction.openDatabase("test", nullptr, flags);
         db.write("sub", "value1");
         db.write("subsub", "value2");
         int numValues = db.scan("sub", [&](const QByteArray &key, const QByteArray &value) -> bool { return true; });
@@ -382,7 +384,7 @@
     {
         Sink::Storage::DataStore store(testDataPath, {dbName, {{"test", 0}}}, Sink::Storage::DataStore::ReadWrite);
         auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
-        auto db = transaction.openDatabase("test", nullptr, false);
+        auto db = transaction.openDatabase("test");
         db.write("sub", "value1");
         db.write("subsub", "value2");
         db.write("wubsub", "value3");
@@ -395,7 +397,7 @@
     {
         Sink::Storage::DataStore store(testDataPath, {dbName, {{"test", 0}}}, Sink::Storage::DataStore::ReadWrite);
         auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
-        auto db = transaction.openDatabase("test", nullptr, true);
+        auto db = transaction.openDatabase("test", nullptr, Sink::Storage::AllowDuplicates);
         db.write("sub", "value1");
         db.write("subsub", "value2");
         db.write("wubsub", "value3");
@@ -408,7 +410,7 @@
     {
         Sink::Storage::DataStore store(testDataPath, {dbName, {{"test", 0}}}, Sink::Storage::DataStore::ReadWrite);
         auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
-        auto db = transaction.openDatabase("test", nullptr, false);
+        auto db = transaction.openDatabase("test");
         db.write("sub_2", "value2");
         db.write("sub_1", "value1");
         db.write("sub_3", "value3");
@@ -429,7 +431,7 @@
     {
         Sink::Storage::DataStore store(testDataPath, {dbName, {{"test", 0}}}, Sink::Storage::DataStore::ReadWrite);
         auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
-        auto db = transaction.openDatabase("test", nullptr, true);
+        auto db = transaction.openDatabase("test", nullptr, Sink::Storage::AllowDuplicates);
         db.write("sub1", "value1");
         int numValues = db.scan("sub", [&](const QByteArray &key, const QByteArray &value) -> bool { return true; });
 
@@ -440,7 +442,7 @@
     {
         Sink::Storage::DataStore store(testDataPath, {dbName, {{"test", 0}}}, Sink::Storage::DataStore::ReadWrite);
         auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
-        auto db = transaction.openDatabase("test", nullptr, false);
+        auto db = transaction.openDatabase("test");
         db.write("sub1", "value1");
         db.write("sub2", "value2");
         db.write("wub3", "value3");
@@ -455,7 +457,7 @@
     {
         Sink::Storage::DataStore store(testDataPath, {dbName, {{"test", 0}}}, Sink::Storage::DataStore::ReadWrite);
         auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
-        auto db = transaction.openDatabase("test", nullptr, false);
+        auto db = transaction.openDatabase("test");
         db.write("sub2", "value2");
         QByteArray result;
         db.findLatest("sub", [&](const QByteArray &key, const QByteArray &value) { result = value; });
@@ -467,7 +469,7 @@
     {
         Sink::Storage::DataStore store(testDataPath, {dbName, {{"test", 0}}}, Sink::Storage::DataStore::ReadWrite);
         auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
-        auto db = transaction.openDatabase("test", nullptr, false);
+        auto db = transaction.openDatabase("test");
         db.write("sub2", "value2");
         db.write("wub3", "value3");
         QByteArray result;
@@ -478,8 +480,8 @@
 
     static QMap<QByteArray, int> baseDbs()
     {
-        return {{"revisionType", 0},
-                {"revisions", 0},
+        return {{"revisionType", Sink::Storage::IntegerKeys},
+                {"revisions", Sink::Storage::IntegerKeys},
                 {"uids", 0},
                 {"default", 0},
                 {"__flagtable", 0}};
@@ -499,7 +501,7 @@
         Sink::Storage::DataStore store(testDataPath, {dbName, {{"test", 0}}}, Sink::Storage::DataStore::ReadWrite);
         auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
         QByteArray result;
-        auto db = transaction.openDatabase("test", nullptr, false);
+        auto db = transaction.openDatabase("test");
         const auto uid = "{c5d06a9f-1534-4c52-b8ea-415db68bdadf}";
         //Ensure we can sort 1 and 10 properly (by default string comparison 10 comes before 6)
         const auto id = Sink::Storage::Identifier::fromDisplayByteArray(uid);
@@ -523,7 +525,7 @@
     {
         Sink::Storage::DataStore store(testDataPath, dbName, Sink::Storage::DataStore::ReadWrite);
         auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
-        auto db = transaction.openDatabase("test", nullptr, false);
+        auto db = transaction.openDatabase("test");
         setupTestFindRange(db);
         QByteArrayList results;
         db.findAllInRange("0002", "0004", [&](const QByteArray &key, const QByteArray &value) { results << value; });
@@ -535,7 +537,7 @@
     {
         Sink::Storage::DataStore store(testDataPath, dbName, Sink::Storage::DataStore::ReadWrite);
         auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
-        auto db = transaction.openDatabase("test", nullptr, false);
+        auto db = transaction.openDatabase("test");
         setupTestFindRange(db);
 
         QByteArrayList results1;
@@ -559,7 +561,7 @@
     {
         Sink::Storage::DataStore store(testDataPath, dbName, Sink::Storage::DataStore::ReadWrite);
         auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
-        auto db = transaction.openDatabase("test", nullptr, false);
+        auto db = transaction.openDatabase("test");
         setupTestFindRange(db);
 
         QByteArrayList results1;
@@ -571,7 +573,7 @@
     {
         Sink::Storage::DataStore store(testDataPath, dbName, Sink::Storage::DataStore::ReadWrite);
         auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
-        auto db = transaction.openDatabase("test", nullptr, false);
+        auto db = transaction.openDatabase("test");
         setupTestFindRange(db);
 
         QByteArrayList results1;
@@ -601,21 +603,21 @@
             Sink::Storage::DataStore store(testDataPath, {dbName, {{"testTransactionVisibility", 0}}}, Sink::Storage::DataStore::ReadWrite);
             auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
 
-            auto db = transaction.openDatabase("testTransactionVisibility", nullptr, false);
+            auto db = transaction.openDatabase("testTransactionVisibility");
             db.write("key1", "foo");
             QCOMPARE(readValue(db, "key1"), QByteArray("foo"));
 
             {
                 auto transaction2 = store.createTransaction(Sink::Storage::DataStore::ReadOnly);
                 auto db2 = transaction2
-                    .openDatabase("testTransactionVisibility", nullptr, false);
+                    .openDatabase("testTransactionVisibility");
                 QCOMPARE(readValue(db2, "key1"), QByteArray());
             }
             transaction.commit();
             {
                 auto transaction2 = store.createTransaction(Sink::Storage::DataStore::ReadOnly);
                 auto db2 = transaction2
-                    .openDatabase("testTransactionVisibility", nullptr, false);
+                    .openDatabase("testTransactionVisibility");
                 QCOMPARE(readValue(db2, "key1"), QByteArray("foo"));
             }
 
@@ -627,16 +629,16 @@
         Sink::Storage::DataStore store(testDataPath, {dbName, {{"a", 0}, {"b", 0}, {"c", 0}}}, Sink::Storage::DataStore::ReadWrite);
         {
             auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
-            transaction.openDatabase("a", nullptr, false);
-            transaction.openDatabase("b", nullptr, false);
-            transaction.openDatabase("c", nullptr, false);
+            transaction.openDatabase("a");
+            transaction.openDatabase("b");
+            transaction.openDatabase("c");
             transaction.commit();
         }
         auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadOnly);
         for (int i = 0; i < 1000; i++) {
-            transaction.openDatabase("a", nullptr, false);
-            transaction.openDatabase("b", nullptr, false);
-            transaction.openDatabase("c", nullptr, false);
+            transaction.openDatabase("a");
+            transaction.openDatabase("b");
+            transaction.openDatabase("c");
             transaction = store.createTransaction(Sink::Storage::DataStore::ReadOnly);
         }
     }
@@ -662,11 +664,11 @@
     //            Sink::Storage::DataStore store(testDataPath, dbName, Sink::Storage::DataStore::ReadOnly);
     //            auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadOnly);
     //            for (int i = 0; i < 100000; i++) {
-    //                transaction.openDatabase("a", nullptr, false);
-    //                transaction.openDatabase("b", nullptr, false);
-    //                transaction.openDatabase("c", nullptr, false);
-    //                transaction.openDatabase("p", nullptr, false);
-    //                transaction.openDatabase("q", nullptr, false);
+    //                transaction.openDatabase("a");
+    //                transaction.openDatabase("b");
+    //                transaction.openDatabase("c");
+    //                transaction.openDatabase("p");
+    //                transaction.openDatabase("q");
     //            }
     //        });
     //    }
@@ -733,7 +735,7 @@
             Sink::Storage::DataStore store(testDataPath, {dbName, {{"testTransactionVisibility", 0}}}, Sink::Storage::DataStore::ReadWrite);
             auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
 
-            auto db = transaction.openDatabase("testTransactionVisibility", nullptr, false);
+            auto db = transaction.openDatabase("testTransactionVisibility");
             db.write("key1", "foo");
             QCOMPARE(readValue(db, "key1"), QByteArray("foo"));
             transaction.commit();
@@ -748,12 +750,12 @@
 
             //This transaction should open the dbi
             auto transaction2 = store.createTransaction(Sink::Storage::DataStore::ReadOnly);
-            auto db2 = transaction2.openDatabase("testTransactionVisibility", nullptr, false);
+            auto db2 = transaction2.openDatabase("testTransactionVisibility");
             QCOMPARE(readValue(db2, "key1"), QByteArray("foo"));
 
             //This transaction should have the dbi available
             auto transaction3 = store.createTransaction(Sink::Storage::DataStore::ReadOnly);
-            auto db3 = transaction3.openDatabase("testTransactionVisibility", nullptr, false);
+            auto db3 = transaction3.openDatabase("testTransactionVisibility");
             QCOMPARE(readValue(db3, "key1"), QByteArray("foo"));
         }
 
@@ -766,20 +768,198 @@
 
             //This transaction should open the dbi
             auto transaction2 = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
-            auto db2 = transaction2.openDatabase("testTransactionVisibility", nullptr, false);
+            auto db2 = transaction2.openDatabase("testTransactionVisibility");
             QCOMPARE(readValue(db2, "key1"), QByteArray("foo"));
 
             //This transaction should have the dbi available (creating two write transactions obviously doesn't work)
             //NOTE: we don't support this scenario. A write transaction must commit or abort before a read transaction opens the same database.
             // auto transaction3 = store.createTransaction(Sink::Storage::DataStore::ReadOnly);
-            // auto db3 = transaction3.openDatabase("testTransactionVisibility", nullptr, false);
+            // auto db3 = transaction3.openDatabase("testTransactionVisibility");
             // QCOMPARE(readValue(db3, "key1"), QByteArray("foo"));
 
             //Ensure we can still open further dbis in the write transaction
-            auto db4 = transaction2.openDatabase("anotherDb", nullptr, false);
+            auto db4 = transaction2.openDatabase("anotherDb");
         }
 
     }
+
+    void testIntegerKeys()
+    {
+        const int flags = Sink::Storage::IntegerKeys;
+        Sink::Storage::DataStore store(testDataPath,
+            { dbName, { { "test", flags } } }, Sink::Storage::DataStore::ReadWrite);
+        auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
+        auto db = transaction.openDatabase("testIntegerKeys", {}, flags);
+        db.write(0, "value1");
+        db.write(1, "value2");
+
+        size_t resultKey;
+        QByteArray result;
+        int numValues = db.scan(0, [&](size_t key, const QByteArray &value) -> bool {
+            resultKey = key;
+            result = value;
+            return true;
+        });
+
+        QCOMPARE(numValues, 1);
+        QCOMPARE(resultKey, 0);
+        QCOMPARE(result, "value1");
+
+        int numValues2 = db.scan(1, [&](size_t key, const QByteArray &value) -> bool {
+            resultKey = key;
+            result = value;
+            return true;
+        });
+
+        QCOMPARE(numValues2, 1);
+        QCOMPARE(resultKey, 1);
+        QCOMPARE(result, "value2");
+    }
+
+    void testDuplicateIntegerKeys()
+    {
+        const int flags = Sink::Storage::IntegerKeys | Sink::Storage::AllowDuplicates;
+        Sink::Storage::DataStore store(testDataPath,
+            { dbName, { { "testDuplicateIntegerKeys", flags} } },
+            Sink::Storage::DataStore::ReadWrite);
+        auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
+        auto db = transaction.openDatabase("testDuplicateIntegerKeys", {}, flags);
+        db.write(0, "value1");
+        db.write(1, "value2");
+        db.write(1, "value3");
+        QSet<QByteArray> results;
+        int numValues = db.scan(1, [&](size_t, const QByteArray &value) -> bool {
+            results << value;
+            return true;
+        });
+
+        QCOMPARE(numValues, 2);
+        QCOMPARE(results.size(), 2);
+        QVERIFY(results.contains("value2"));
+        QVERIFY(results.contains("value3"));
+    }
+
+    void testDuplicateWithIntegerValues()
+    {
+        const int flags = Sink::Storage::AllowDuplicates | Sink::Storage::IntegerValues;
+        Sink::Storage::DataStore store(testDataPath,
+            { dbName, { { "testDuplicateWithIntegerValues", flags} } },
+            Sink::Storage::DataStore::ReadWrite);
+
+        auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
+        auto db = transaction.openDatabase("testDuplicateWithIntegerValues", {}, flags);
+
+        const size_t number1 = 1;
+        const size_t number2 = 2;
+
+        const QByteArray number1BA = Sink::sizeTToByteArray(number1);
+        const QByteArray number2BA = Sink::sizeTToByteArray(number2);
+
+        db.write(0, number1BA);
+        db.write(1, number2BA);
+        db.write(1, number1BA);
+
+        QList<QByteArray> results;
+        int numValues = db.scan(1, [&](size_t, const QByteArray &value) -> bool {
+            results << value;
+            return true;
+        });
+
+        QCOMPARE(numValues, 2);
+        QCOMPARE(results.size(), 2);
+        QCOMPARE(results[0], number1BA);
+        QCOMPARE(results[1], number2BA);
+    }
+
+    void testIntegerKeyMultipleOf256()
+    {
+        const int flags = Sink::Storage::IntegerKeys;
+        Sink::Storage::DataStore store(testDataPath,
+                { dbName, { {"testIntegerKeyMultipleOf256", flags} } },
+                Sink::Storage::DataStore::ReadWrite);
+
+        {
+            auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
+            auto db = transaction.openDatabase("testIntegerKeyMultipleOf256", {}, flags);
+
+            db.write(0x100, "hello");
+            db.write(0x200, "hello2");
+            db.write(0x42, "hello3");
+
+            transaction.commit();
+        }
+
+        {
+            auto transaction2 = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
+            auto db = transaction2.openDatabase("testIntegerKeyMultipleOf256", {}, flags);
+
+            size_t resultKey;
+            QByteArray resultValue;
+            db.scan(0x100, [&] (size_t key, const QByteArray &value) {
+                resultKey = key;
+                resultValue = value;
+                return false;
+            });
+
+            QCOMPARE(resultKey, 0x100);
+            QCOMPARE(resultValue, "hello");
+        }
+    }
+
+    void testIntegerProperlySorted()
+    {
+        const int flags = Sink::Storage::IntegerKeys;
+        Sink::Storage::DataStore store(testDataPath,
+                { dbName, { {"testIntegerProperlySorted", flags} } },
+                Sink::Storage::DataStore::ReadWrite);
+
+        {
+            auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
+            auto db = transaction.openDatabase("testIntegerProperlySorted", {}, flags);
+
+            for (size_t i = 0; i < 0x100; ++i) {
+                db.write(i, "hello");
+            }
+
+            size_t previous = 0;
+            bool success = true;
+            db.scan("", [&] (const QByteArray &key, const QByteArray &value) {
+                size_t current = Sink::byteArrayToSizeT(key);
+                if (current < previous) {
+                    success = false;
+                    return false;
+                }
+
+                previous = current;
+                return true;
+            });
+
+            QVERIFY2(success, "Integer are not properly sorted before commit");
+
+            transaction.commit();
+        }
+
+        {
+            auto transaction = store.createTransaction(Sink::Storage::DataStore::ReadWrite);
+            auto db = transaction.openDatabase("testIntegerProperlySorted", {}, flags);
+
+            size_t previous = 0;
+            bool success = true;
+            db.scan("", [&] (const QByteArray &key, const QByteArray &value) {
+                size_t current = Sink::byteArrayToSizeT(key);
+                if (current < previous) {
+                    success = false;
+                    return false;
+                }
+
+                previous = current;
+                return true;
+            });
+
+            QVERIFY2(success, "Integer are not properly sorted after commit");
+        }
+    }
+
 };
 
 QTEST_MAIN(StorageTest)