memory consumption

[henrus]

Dear g2p,

it interesting to see that I am the first to leave an issue. This is an excellent tool and I hope that this kind of feature makes it into btrfs one day. Many thanks for putting the effort in.

I am using bedup to de-duplicate large backups stored in a btrfs. For me the adavantages/features of this approach are:

• compression through btrfs
• offline file dedup through bedup
• acl/xattr stored natively
• no restore tool/user management necessary as backups are accessible as mount

My current problem is that bedup uses excessive amounts of memory (in my case more than 12GB) in dedup_tracked(sess, volset, tt). This is for an inode table with 1.6 million rows and happens when 'comm1.inodes' is executed.

Output:

41:02.0 Updated 1480885 items
00.00 Partial hash of same-size groups 0/109721

Note: Non of the common sets should be larger than 20 files.

I cannot see why this is necessary. Without SQL I would simply traverse the size-sorted inode list ...

Best Regards,

Henrik

[g2p]

Hello Henrik,
thanks for the feedback.
It seems you have a very large number of deduplication candidates, and forcing the comm1 query to be loaded in memory (to precompute the total for progress reports) is detrimental. The latest commit should fix that problem, please give it a try.

[g2p]

PS: I'll do the same for comm2 and comm3 if it proves necessary.

[henrus]

Dear g2p,

thanks for your quick reply.

yes, the set is large, but not excessive.

Sorry, that does not help because loading comm1 is NOT the problem.

The problem is in line 327

         space_gain1 += comm1.size * (len(comm1.inodes) - 1)

which evaluates to

SELECT
(
SELECT "Volume".fs_id
FROM "Volume"
WHERE "Volume".id = "Inode".vol_id
)
AS fs_id, "Inode".vol_id AS "Inode_vol_id", "Inode".ino AS "Inode_ino", "Inode".size AS "Inode_size", "Inode".mini_hash AS "Inode_mini_hash", "Inode".fiemap_hash AS "Inode_fiemap_hash", "Inode".has_updates AS "Inode_has_updates"
FROM "Inode",
(
SELECT
(
SELECT "Volume".fs_id
FROM "Volume"
WHERE "Volume".id = "Inode".vol_id
)
AS fs_id, "Inode".size AS size, count(*) AS inode_count, max("Inode".has_updates) AS has_updates
FROM "Inode"
WHERE "Inode".vol_id IN (?) GROUP BY
(
SELECT "Volume".fs_id
FROM "Volume"
WHERE "Volume".id = "Inode".vol_id
), "Inode".size
HAVING inode_count > ? AND has_updates > ?
)
AS anon_1
WHERE
(
SELECT "Volume".fs_id
FROM "Volume"
WHERE "Volume".id = "Inode".vol_id
) = anon_1.fs_id AND "Inode".vol_id IN (?) AND "Inode".size = ?

I suspect that this statement produces large temporary tables ... but I do not know SQLAlchemy enough to pinpoint the problem.

Henrik

[g2p]

One more question (before I go away for lunch): are many of your files clustering on a single size? (ie, is comm1.inodes large enough to fill 12G in one instance?)

[g2p]

Saw your edit, but just to be sure, please run:

sqlite3 ~/.local/share/bedup/db.sqlite 'select size, count(*) as cnt from Inode group by size order by cnt desc limit 10;'

[henrus]

Dear g2p,

Thanks for your help.

Well, yes and no. As I mentioned before, the resulting sets produced by comm1.inodes are relatively small, but SQLlite dies on the way to find it.

In order to answer your question more precisely I executed

SELECT size, COUNT() TotalCount
FROM Inode
GROUP BY size
HAVING COUNT() > 1
ORDER BY COUNT(*) DESC

This returns a maximum TotalCount of 4399, the rest is much smaller < 1000 - Okay, still a lot to de-dup, but that's the point.

I think the problem can be solved quite easily: Create a query sorting the inode table by size, then traverse this list one by one. Keep adding the items to list until the size steps up. Then process this list to update hash keys.

Your approach should also work, but I think SQLlite cannot handle the SQL statement efficiently - at least not in the form it is now.

Saw you edit ;-)

user@machine:~/bedup# sqlite3 ~/.local/share/bedup/db.sqlite 'select size, count(*) as cnt from Inode group by size order by cnt desc limit 10;'
17600|4399
5300|998
16997|909
17540|908
139576|904
494617|900
4096|622
7511|546
7524|512
118868|510

Henrik

[g2p]

I get the same SQL query, and I see it performing well with a comm1 cluster of 2460 inodes.
I'm reluctant towards the idea of reimplementing queries as Python loops.
What version of sqlite (and sqlalchemy, just in case the memory usage is on the Python heap) are you running?

[henrus]

All clear and fine - let's try and find out where the 'real' problem is.

user@machine:~/bedup# sqlite3 --version
3.7.13 2012-06-11 02:05:22 f5b5a13f7394dc143aa136f1d4faba6839eaa6dc

user@machine:~/bedup# uname -a
Linux diokletian 3.5.0-18-generic #29-Ubuntu SMP Fri Oct 19 10:26:51 UTC 2012 x86_64 x86_64 x86_64 GNU/Linux

I tried

user@machine:~/bedup# sqlite3 ~/.local/share/bedup/db.sqlite > out << EOF
SELECT (SELECT "Volume".fs_id
FROM "Volume"
WHERE "Volume".id = "Inode".vol_id) AS fs_id, "Inode".vol_id AS "Inode_vol_id", "Inode".ino AS "Inode_ino", "Inode".size AS
"Inode_size", "Inode".mini_hash AS "Inode_mini_hash", "Inode".fiemap_hash AS "Inode_fiemap_hash", "Inode".has_updates AS "
Inode_has_updates"
FROM "Inode", (SELECT (SELECT "Volume".fs_id
FROM "Volume"
WHERE "Volume".id = "Inode".vol_id) AS fs_id, "Inode".size AS size, count(*) AS inode_count, max("Inode".has_updates) AS has_updates
FROM "Inode"
WHERE "Inode".vol_id IN (1) GROUP BY (SELECT "Volume".fs_id
FROM "Volume"
WHERE "Volume".id = "Inode".vol_id), "Inode".size
HAVING inode_count > 0 AND has_updates > 0) AS anon_1
WHERE (SELECT "Volume".fs_id
FROM "Volume"
WHERE "Volume".id = "Inode".vol_id) = anon_1.fs_id AND "Inode".vol_id IN (1) AND "Inode".size = 4096;
EOF

user@machine:~/bedup# uniq -c out
232421 1|1|16629|4096|||1
232421 1|1|23476|4096|||1
232421 1|1|26849|4096|||1
232421 1|1|26850|4096|||1
232421 1|1|26851|4096|||1
232421 1|1|26852|4096|||1
232421 1|1|26853|4096|||1
232421 1|1|26854|4096|||1
232421 1|1|26862|4096|||1
232421 1|1|26864|4096|||1
232421 1|1|26866|4096|||1
232421 1|1|26883|4096|||1
232421 1|1|26886|4096|||1
232421 1|1|26889|4096|||1
232421 1|1|26906|4096|||1
232421 1|1|26910|4096|||1
232421 1|1|26923|4096|||1
232421 1|1|26925|4096|||1
232421 1|1|26937|4096|||1
232421 1|1|26944|4096|||1
232421 1|1|26953|4096|||1
232421 1|1|26970|4096|||1
232421 1|1|26974|4096|||1
232421 1|1|26976|4096|||1
232421 1|1|26982|4096|||1
232421 1|1|26984|4096|||1
232421 1|1|26990|4096|||1
232421 1|1|26998|4096|||1
232421 1|1|27014|4096|||1
232421 1|1|27017|4096|||1
232421 1|1|27018|4096|||1
232421 1|1|27019|4096|||1
232421 1|1|27020|4096|||1
232421 1|1|27021|4096|||1
232421 1|1|27022|4096|||1
232421 1|1|27023|4096|||1
232421 1|1|27024|4096|||1
232421 1|1|27025|4096|||1
232421 1|1|27026|4096|||1
232421 1|1|27027|4096|||1
115336 1|1|27028|4096|||1
1 1|1|27028|4096||

IMPORTANT NOTE: I am not sure that I put the right numbers

HAVING inode_count > HERE AND has_updates > HERE) AS anon_1

Obviously, this returns a huge table with many duplicates - I stopped it when it hit 5 million lines.

Maybe you can run something similar at your end to see whether you get the same. I suspect that the duplicates are trimmed automatically - possibly when the output is read into python data structures. That why we do not see the problem on smaller sets.

Henrik

[g2p]

The numbers are on the line after the query when you run with --verbose-sql.

[henrus]

Sorry struck with blindness - Got it

(1, 1, 0, 1, 4096)

Same result when I substitute this into the query.

Full run into file returns 50 million lines and counting ... 68246462.

Okay, I guess the problem is properly identified now.

[g2p]

SQLite version is fine (same as mine). I do notice some duplicate rows on my end as well, so I'll try to rectify that.

[g2p]

Can you try the latest commit?
I don't understand yet how the sql query gets bloated (adding * to the select clause, it seems like it picks up irrelevant inodes). The latest change might work around it by streaming the query.

[henrus]

Nope. I think you only moved the problem from line 329 to 331.