How Datomic Uses Bit Engineering to Solve the Scattered I/O Problem

Slow reads are often symptoms of poor data locality in high-throughput systems. Datomic addresses this through: Implicit Partitions.

database should look more like a well organized library and less like a garage.

The Problem: The “Scattered I/O”. Imagine a global HR system where thousands of companies manage employees. If companies’ data is scattered randomly across storage, a simple query to list its employees requires multiple disk seeks. At scale, this ‘scattered I/O’ is one of related latency issue

Understanding Datomic's Datom to understand organization:

• E (Entity): The “Who” — the unique identifier (EID).
• A (Attribute): The “What” — the property (e.g., :employee/salary).
• V (Value): The “Value” — the actual data.
• T (Transaction): The “When” — the temporal record of the write.

The Solution: EID as an Address in Bits

The EID (Entity ID) is 64-bit long. Datomic doesn't generate this number randomly; Implicit Partitions utilize bit-shifting to embed the partition ID into the EID’s most significant bits, forcing related datoms to be stored close together.

(d/transact connection
  [{:db/id "company-1"
    :company/name "You"}

   {:db/id "employee-1"
    :employee/name "Joao Silva"}

   {:db/id "employee-2"
    :employee/name "Maria Souza"}

   {:db/force-partition {"company-1" (d/implicit-part 123)}
    :db/match-partition {"employee-1" "company-1"
                         "employee-2" "company-1"}}])

Bit Engineering backstage

When you create an entity within a partition (e.g., a Company), Datomic ensures the identifier reflects that origin. Imagine the 64-bit structure divided as follows:

;; binary
;; 0 0 10000000000001111011 000000000000000000000000000000000000000001
;; │ │ │└──── 123 ────────┘ └──────────── 1 (sequence) ─────────────┘
;; │ │ └ PType=1 (implicit partition)
;; │ └ -
;; └ Sign

(def eid 2306383968934559745)

(unsigned-bit-shift-right eid 63)            ;; => 0 (Positive)

(bit-and (bit-shift-right eid 42) 0x7FFFF)   ;; => 123 (The Implicit Partition Number)

(bit-and eid (dec (bit-shift-left 1 42)))     ;; => 1 (The unique sequence within that partition)

Outcome

By forcing the partition value into the high-order bits of the EID, Datomic ensures:

(d/q '[:find ?e ?name
       :where (or [?e :company/name ?name]
                  [?e :employee/name ?name])]
     db)
;; => #{[2306383968934559745 "You"]
;;      [2306383968934559746 "Joao Silva"]
;;      [2306383968934559747 "Maria Souza"]}

(defn eid->partition [eid]
  (bit-and (bit-shift-right eid 42) 0x7FFFF))

(map eid->partition [2306383968934559745
                     2306383968934559746
                     2306383968934559747])
;; => (123 123 123)

All three entities — the company and its two employees — live in the same partition (123).

• Data Locality: Entities that belong together are stored near — physically, not just logically.
• Scattered I/O Problem: What was once scattered across storage is now organized. Entities that share a partition are colocated in Datomic’s E-leading indexes (EAVT and AEVT), landing close together in the same index segments.
• Predictable Performance at Scale: Read latency stays flat as data grows, because the access pattern reads nearby data.