How to serialize a big dict to a disk file, such that small modifications don't require a full rewrite, but only a few bytes?

user_1422096 0
Viewed 89

Let's work with a big dictionary (110 MB) and save it to disk:

import pickle, os
d = {i: os.urandom(100) for i in range(1_000_000)}  
with open('mydict', 'wb') as f:  
    pickle.dump(d, f)           # 110 MB file

Now let's do small modifications (only 2 key/values changed among 1 million):

d[17] = "hello"  # addition
del d[1234]      # deletion
with open('mydict', 'wb') as f:
    pickle.dump(d, f)           # we're rewriting 110 MB to disk again! unefficient!

How to avoid to rewrite the whole dict?

Which serialization techniques to use that such small modifications on d only requires a few bytes to write on disk?

Of course, a database (e.g. Sqlite) could be a solution, but I wanted to see first if there are even easier techniques.

Something like this (pseudo-code):

before_modification_state = d.getstate()
d[17] = "hello"  # addition
del d[1234]      # deletion
diff = d.getdiff(from=before_modification_state)   # only a few bytes

patch('mydict', diff)   # this only writes a few bytes to the disk file "mydict"

# or

with open('mydict', 'r+') as f:  # read-write
    for pos, newbytes in diff:
        f.seek(pos)         # move to position pos
        f.write(newbytes)   # write the new bytes
# with this solution d.getdiff() would return something like 
# [[6576, b"fsq678"], [16537, b"!/=13IH"]]
# i.e. position to seek in file, and new bytes to write

Or is there another data structure more adapted for this?

Edit: As suggested in a comment, I tried with shelve:

import shelve
d = shelve.open("dict2")
for i in range(1_000_000):
    d[str(i)] = os.urandom(100)

but this takes 300 seconds and 514 MB! (and with writeback=True it's the same).

As a comparison, with the first code above (modified to have str(i) instead of i as keys to have a fair comparison - shelve doesn't support integer keys), it takes 4 seconds and 120 MB only.

So it seems shelve is not well adapted here.

Also, shelve is basically just dbm with pickle for the the dict values. So it's worth looking at dbm directly. Unfortunately on Windows, only dbm.dumb is available, and it's a bit weak: https://github.com/python/cpython/blob/3.9/Lib/dbm/dumb.py#L11, "Currently, space once occupied by deleted or expanded items is never reused".

diff serialization dictionary sqlite python
1 Answers

If what you want is a very fast write, you could just append it to a YAML file, at the end, using regular text mode. Last key value "wins".

So your write speed is basically as per appending one line each time. Read speed would be slow because of YAML, but you could always read/write in YAML mode to strip out duplicate data.

Note: YAML, not JSON, because JSON requires ending the file with a '}or]`, which complicates things.

test.py

from yaml import safe_load as yload, safe_dump as ydump
import sys
from pathlib import Path

pa_yaml = Path(__file__).with_suffix(".yaml")
value = sys.argv[1]

if pa_yaml.exists():
    existed = True
    with pa_yaml.open("a") as fo:
        fo.write(f"value: {value}\n")
else:
    existed = False
    data = dict(dummy="dummy", value=value)
    print("seeding test.yaml with {data=}")
    with pa_yaml.open("w") as fo:
        fo.write(ydump(data))

print(f"\n{pa_yaml} contents after write:\n{pa_yaml.read_text()}")
with pa_yaml.open() as fi:
    data = yload(fi)
    print(f"after write {data=}")

output:

(venv38) me@test_206_yaml$ python test.py value1
seeding test.yaml with {data=}

test.yaml contents after write:
dummy: dummy
value: value1

after write data={'dummy': 'dummy', 'value': 'value1'}
(venv38) me@test_206_yaml$ python test.py value2

test.yaml contents after write:
dummy: dummy
value: value1
value: value2

after write data={'dummy': 'dummy', 'value': 'value2'}
(venv38) me@test_206_yaml$ python test.py value3

test.yaml contents after write:
dummy: dummy
value: value1
value: value2
value: value3

after write data={'dummy': 'dummy', 'value': 'value3'}

integer keys worked fine. I tested by adding {4:4} to the seed value.

user_13943530
Related