shithub: furgit

--- a/research/dynamic_packfiles.txt

+++ b/research/dynamic_packfiles.txt

@@ -43,3 +43,124 @@

 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

--

⑨