ref: df1f2fb3daa1acd25c88510f259d5535fb482126
dir: /research/dynamic_packfiles.txt/
dynamic packfiles to append objects gc/refcount process punches page-sized holes in them for pages fully within the space of unwanted objects, after setting a tombstone mark holes are recorded in an index and re-used then, if desired, the repack process removes all the punched holes and anything surrounding from unwanted objects that are slightly out of the page boundary repack is not really git's repack algorithm, it's bascially just defragmentation. genreational bloom filters idx design ========== so, let's first get our invariants and patterns clear. * fixed-length cryptographic object IDs * essentially uniform key distribution * exact lookup only, no range scans, no ordered iteration requirements * reads are extremely important * writes are mostly append-like * deletes/tombstones may happen later but are secondary 1st design ---------- * mutable front index * immutable base index * period merge/compaction into a new base generation upload-pack/send-pack/defrag ============================ take current pack, remove dead objects/holes, filter objects out, record offsets and adjust ofs_deltas since they always go backwards, write the pack back; then stream written pack to client. two-step necessary because pack header includes object count; could have a custom new protocol that doesn't do so. random chat log dump ==================== <~runxiyu> ori: actually. i think my hashtable-ish .idx scheme doesn't work really well with e.g. "user provided us a small part of the hash" <~runxiyu> and when using the Git CLI, abbreviated hashes are extremely common.... <~runxiyu> not lik ei'd need them in a *forge* <~runxiyu> but ugh <~runxiyu> i guess i'm going with some sort of b-tree :(( <~runxiyu> ~~maybe i should just port gefs to git~~ <&ori> runxiyu: why not? you should be able to pick the pages based on the prefix and then scan, no? <~rx> ori: i need to somehow munge the has to prevent page directory explosions <~rx> the hash* <~rx> e.g. siphash(objectid, secret) <~rx> otherwise an attacker could give you 10M objects that start with 00000 and whatnot <&ori> what's the worst case that would happen there, and is it exponentially worse than giving you 10M objects that start with anything? <&ori> I'm thinking that you can't generate a case worse than 256/nobject extra table lookups, assuming one bit per fanout.. <~runxiyu> ori: for extendible hashing, yes, definitely worse <~runxiyu> the directory will expand a lot for no good reason <&ori> yes, but you have 256 bits of hash <&ori> how much is a lot worse? <&ori> what's the worst an attacker can do, and how is the impact worse than uploading 10M giant objects? <&ori> also, spotted a bag of kuai kuai keeping the cash register working today at a tea shop <~runxiyu> waitt <~runxiyu> hmmm * runxiyu looks agagin if it's O(N) or O(2^N) <~runxiyu> well <~runxiyu> i think it should be a O(2^n) directory size when the attacker can control n bits prefix <&ori> what's the 'n' here? <~runxiyu> > can control n bits prefix <&ori> yeah, you run out of prefix pretty quickly, though <&ori> I'm not seeing how you could get an exponential blowup if you share pages <&ori> may be missing something, though <~runxiyu> hm <&ori> oh, wait, I see <&ori> no, wait <~runxiyu> i think im confusing myself too to some extent but something doesn't feel right <~runxiyu> urgh <~runxiyu> okay, rethinking this <~runxiyu> d is the global depth <~runxiyu> diretory size is 2^d <~runxiyu> B records per bucket <~runxiyu> whatever happens inside the bucket idc, let's say it's a linked list <~runxiyu> whatever happens inside the bucket idc, let's say it's an array* (linked lists suck) <~runxiyu> l <= d <~runxiyu> (l being the local depth of a bucket) <~runxiyu> normal: d = log^2(N/B) <&ori> ahh, I see. <~runxiyu> N is the object count <&ori> yes, so what if you binary searched the page directory, or made it multi-level <~runxiyu> an attacker could grab a giant repo and find commonly-prefixed objects, they don't need to brute force their own <~runxiyu> ori: remember we're trying to do something easy to add new objects into <~runxiyu> how'd you do that with a binary search? <~runxiyu> not sure what you mean by multi-level yet here <~runxiyu> well, it could just turn into a b+tree... <~runxiyu> hm <&ori> multilevel -- you have pd[0] using bits 0..n <~runxiyu> maybe an lmdb object store isn't too bad after all <&ori> pd[0][1] using bits n...m <&ori> etc <&ori> and the reason I was a bit confused was that I had thought the directory was a trie <&ori> rather than just an expanding top level directory <~runxiyu> ah <&ori> so, yeah, I was thinking you could make the page directory an actual trie <~runxiyu> sigh <~runxiyu> i guess abbreviated object IDs is something i can't really skip. <~runxiyu> ori: ill look into radix trees and LSM trees too <~runxiyu> well, you're basically suggesting a radix tree i guess <~runxiyu> well actually <~runxiyu> radix might not necessarily be the best trie here <~runxiyu> idk <~runxiyu> hm <~runxiyu> firstly im really heavy on reads <~runxiyu> and random keys with no sequential access <~runxiyu> ok LSM makes no sense <&hax[xor]> > O(2^N) <~runxiyu> ori: thoughts on how to make tries reasonable to use on disks? <&hax[xor]> that sounds like something is already very broken <~runxiyu> hax[xor]: wdym <&hax[xor]> directory size should absolutely not scale like that <~runxiyu> hax[xor]: maybe read up on how extendible hsahing works again? <&hax[xor]> probably but if that's how it scales it still sounds verybroken <~runxiyu> n is not the amount of objects <~runxiyu> it's a pathlogic condition caused by chosne-prefix keys <~runxiyu> (your keys are usually supposed to be hashed into something the attacker can't predict) <&hax[xor]> if you mean the directory size scales linearly with the number of objects the attacker puts in it... that sounds perfectly normal? <&ori> runxiyu: same as extendible hashing, just after you extend to, say, 8 bits, you stop splitting the page directory, and have subdirectories <~runxiyu> ori: that could make senes <~runxiyu> haven't thought it through <~runxiyu> directory size is 2^d, d being the global depth <~runxiyu> urgh i need to review for exams <~runxiyu> okay <~runxiyu> write amplification issue <~runxiyu> im not sure how significant this is for realistic git workloads <~runxiyu> i haven't counted, but there should be many, many, many more reads than writes <~runxiyu> if write amplification is really an issue <&ori> I may go wander around a bit. <~runxiyu> then ill just port gefs <~runxiyu> ori: do you mean IRL, or over dynamic pack data structures- <&ori> irl. <~runxiyu> alright that makes more sense :P <&ori> tomorrow I think I check out Jiufen <~runxiyu> frick i want to be able to type epsilon with compose <&ori> is that not possible? <~runxiyu> i don't seem to be able to <~runxiyu> but idk the compose tables on my system <~runxiyu> ε <~runxiyu> well <~runxiyu> unicode hex input always works :/ <~runxiyu> OKAY FUCK <~runxiyu> I keep getting distracted by interesting things <~runxiyu> I need to review for my fucking exams -- Mode #chat [-q runxiyu] by runxiyu -- Mode #chat [-a runxiyu] by runxiyu -- #chat: You must be a channel halfop or higher to set channel mode b (ban). -- Mode #chat [+b mute:account:runxiyu] by runxiyu -- #chat: You cannot send messages to this channel whilst a m: (mute) extban is set matching you. -- #chat: You cannot send messages to this channel whilst a m: (mute) extban is set matching you. <&f_> does that even work? <&ori> for 9front, <alt>*e gives ε <&ori> but, don't remember the compose map <&ori> thought that there was a similar thing for all greek letters See also: https://github.com/inkandswitch/darn https://www.youtube.com/watch?v=nk4nefmguZk https://crates.io/crates/iroh-blobs https://crates.io/crates/bao-tree