Re: reftable [v5]: new ref storage format

On Sun, Aug 6, 2017 at 4:37 PM, Ben Alex [off-list ref] wrote:

Just on the LmdbJava specific pieces:

On Mon, Aug 7, 2017 at 8:56 AM, Shawn Pearce [off-list ref] wrote:

quoted

Looks pretty complete. Its a Java wrapper around the C implementation
of LMDB, which may be sufficient for reference storage. Keys are
limited to 511 bytes, so insanely long reference names would have to
be rejected. Reftable allows reference names up to the file's
`page_size`, minus overhead (~15 bytes) and value (20 bytes).

For clarification LmdbJava code doesn't enforce a particular key size limit.
For puts the caller nominates the size in the buffer they present for
storage, and for get-style operations (cursors etc) the LMDB database stores
the key size and LmdbJava adjusts the Java-visible buffer accordingly.

A 511 byte key limit is specified at compile time for the native LMDB
library. For convenience the native library is compiled for 64-bit Windows,
Linux and Mac OS and included in the LmdbJava JAR, and this compilation is
performed using default values (including the 511 key limit) by the
https://github.com/lmdbjava/native project. Users can specify a different
native library to use (eg one packaged by their OS or separately compiled
using an LmdbJava Native-like automatic build) with a larger key size if
they wish.

As such if JGit wanted to use a longer key size, it is possible to implement
similar automatic builds and packaging into JGit.

I don't know if we need a larger key size. $DAY_JOB limits ref names
to ~200 bytes in a hook. I think GitHub does similar. But I'm worried
about the general masses who might be using our software and expect
ref names thus far to be as long as PATH_MAX on their system. Most
systems run PATH_MAX around 1024.

The limitation of needing native JARs, and having such a low compile
time constant, may be annoying to some.

quoted

A downside for JGit is getting these two open source projects cleared.
We would have to get approval from our sponsor (Eclipse Foundation) to
use both lmdbjava (Apache License) and LMDB (LMDB license).

I can't speak for the other contributors, but I'm happy to review LmdbJava's
license if this assisted. For example changing to the OpenLDAP License would
seem a reasonable variation given users of LmdbJava already need to accept
the OpenLDAP License to use it. Kristoffer, do you have thoughts on this?

Thanks for considering it, but please don't change your licensing just
because of JGit. Its unlikely we can use LMDB for a lot of technical
reasons.

quoted

Plus it
looks like lmdbjava still relies on local disk and isn't giving us a
way to patch in a virtual filesystem the way I need to at $DAY_JOB.

LMDB's mdb_env_open requires a const char* path, so we can pass through any
char array desired. But I think you'll find LMDB native can't map to a
virtual file system implemented by JVM code (the LMDB caveats section has
further local file system considerations).

Mostly at $DAY_JOB its because we can't virtualize the filesystem
calls the C library is doing.

In git-core, I'm worried about the caveats related to locking. Git
tries to work nicely on NFS, and it seems LMDB wouldn't. Git also runs
fine on a read-only filesystem, and LMDB gets a little weird about
that. Finally, Git doesn't have nearly the risks LMDB has about a
crashed reader or writer locking out future operations until the locks
have been resolved. This is especially true with shared user
repositories, where another user might setup and own the semaphore.

-----Original Message-----
From: Shawn Pearce [mailto:spearce@spearce.org]
In git-core, I'm worried about the caveats related to locking. Git tries to work
nicely on NFS, and it seems LMDB wouldn't. Git also runs fine on a read-only
filesystem, and LMDB gets a little weird about that. Finally, Git doesn't have
nearly the risks LMDB has about a crashed reader or writer locking out future
operations until the locks have been resolved. This is especially true with shared
user repositories, where another user might setup and own the semaphore.

FWIW, git has problems with stale lock file in the event of a crash (refs/foo.lock 
might still exist, and git does nothing to clean it up).

In my testing (which involved a *lot* of crashing), I never once had to clean up a
stale LMDB lock.  That said, I didn't test on a RO filesystem.

On Mon, Aug 07, 2017 at 07:41:43AM -0700, Shawn Pearce wrote:

quoted

As such if JGit wanted to use a longer key size, it is possible to implement
similar automatic builds and packaging into JGit.

I don't know if we need a larger key size. $DAY_JOB limits ref names
to ~200 bytes in a hook. I think GitHub does similar. But I'm worried
about the general masses who might be using our software and expect
ref names thus far to be as long as PATH_MAX on their system. Most
systems run PATH_MAX around 1024.

GitHub limits to 255 (for the fully-qualified name, so including
"refs/heads/"). I don't recall ever seeing any complaints about that,
though I suppose it's not out of the realm of possibility for somebody
with a multi-byte encoding to hit with a real name (it's configurable,
so I'm not sure if Enterprise customers in Asia might ever bump it).  I
do think something like 1024 would be well into "you're insane if you
really want to name your branch this" territory.

-Peff

On Mon, Aug 07, 2017 at 03:40:48PM +0000, David Turner wrote:

quoted

-----Original Message-----
From: Shawn Pearce [mailto:spearce@spearce.org]
In git-core, I'm worried about the caveats related to locking. Git tries to work
nicely on NFS, and it seems LMDB wouldn't. Git also runs fine on a read-only
filesystem, and LMDB gets a little weird about that. Finally, Git doesn't have
nearly the risks LMDB has about a crashed reader or writer locking out future
operations until the locks have been resolved. This is especially true with shared
user repositories, where another user might setup and own the semaphore.

FWIW, git has problems with stale lock file in the event of a crash (refs/foo.lock 
might still exist, and git does nothing to clean it up).

In my testing (which involved a *lot* of crashing), I never once had to clean up a
stale LMDB lock.  That said, I didn't test on a RO filesystem.

Yeah, I'd expect LMDB to do much better than Git in a crash, because it
relies on flock. So when the kernel goes away, so too does your lock
(ditto if a git process dies without remembering to remove the lock,
though I don't think we've ever had such a bug).

But that's also why it may not work well over NFS (though my impression
is that flock _does_ work on modern NFS; I've been lucky enough not to
ever use it). Lack of NFS support wouldn't be a show-stopper for most
people, but it would be for totally replacing the existing code, I'd
think. I'm just not clear on what the state of lmdb-on-nfs is.

Assuming it could work, the interesting tradeoffs to me are:

  - something like reftable is hyper-optimized for high-latency
    block-oriented access. It's not clear to me if lmdb would even be
    usable for the distributed storage case Shawn has.

  - reftable is more code for us to implement, but we'd "own" the whole
    stack down to the filesystem. That could be a big win for debugging
    and optimizing for our use case.

  - reftable is re-inventing a lot of the database wheel. lmdb really is
    a debugged, turn-key solution.

I'm not opposed to a world where lmdb becomes the standard solution and
Google does their own bespoke thing. But that's easy for me to say
because I'm not Google. I do care about keeping complexity and bugs to a
minimum for most users, and it's possible that lmdb could do that. But
if it can't become the baseline standard (due to NFS issues), then we'd
still want something to replace the current loose/packed storage. And if
reftable does that, then lmdb becomes a lot less interesting.

-Peff

On Tue, Aug 8, 2017 at 12:52 AM, Jeff King [off-list ref] wrote:

On Mon, Aug 07, 2017 at 03:40:48PM +0000, David Turner wrote:

quoted

quoted

-----Original Message-----
From: Shawn Pearce [mailto:spearce@spearce.org]
In git-core, I'm worried about the caveats related to locking. Git tries to work
nicely on NFS, and it seems LMDB wouldn't. Git also runs fine on a read-only
filesystem, and LMDB gets a little weird about that. Finally, Git doesn't have
nearly the risks LMDB has about a crashed reader or writer locking out future
operations until the locks have been resolved. This is especially true with shared
user repositories, where another user might setup and own the semaphore.

FWIW, git has problems with stale lock file in the event of a crash (refs/foo.lock
might still exist, and git does nothing to clean it up).

In my testing (which involved a *lot* of crashing), I never once had to clean up a
stale LMDB lock.  That said, I didn't test on a RO filesystem.

Yeah, I'd expect LMDB to do much better than Git in a crash, because it
relies on flock. So when the kernel goes away, so too does your lock
(ditto if a git process dies without remembering to remove the lock,
though I don't think we've ever had such a bug).

But that's also why it may not work well over NFS (though my impression
is that flock _does_ work on modern NFS; I've been lucky enough not to
ever use it). Lack of NFS support wouldn't be a show-stopper for most
people, but it would be for totally replacing the existing code, I'd
think. I'm just not clear on what the state of lmdb-on-nfs is.

Assuming it could work, the interesting tradeoffs to me are:

  - something like reftable is hyper-optimized for high-latency
    block-oriented access. It's not clear to me if lmdb would even be
    usable for the distributed storage case Shawn has.

  - reftable is more code for us to implement, but we'd "own" the whole
    stack down to the filesystem. That could be a big win for debugging
    and optimizing for our use case.

  - reftable is re-inventing a lot of the database wheel. lmdb really is
    a debugged, turn-key solution.

I'm not opposed to a world where lmdb becomes the standard solution and
Google does their own bespoke thing. But that's easy for me to say
because I'm not Google. I do care about keeping complexity and bugs to a
minimum for most users, and it's possible that lmdb could do that. But
if it can't become the baseline standard (due to NFS issues), then we'd
still want something to replace the current loose/packed storage. And if
reftable does that, then lmdb becomes a lot less interesting.

Peff, thank you for this summary. It echos my opinions as well.

On the one hand, I love the idea of offloading the database stuff to
lmdb. But its got two technical blockers for me: behavior on NFS, and
virtualizing onto a different filesystem in userspace.

I really need a specialized reference store on a virtualized
distributed storage. The JGit reftable implementation fits that need
today. So we're probably going to go ahead and deploy that in our
environment.

I'd like to start writing a prototype reftable in C for git-core soon,
but I've been distracted by the JGit version first. It would be good
to have something to compare against the lmdb approach for git-core
before we make any decisions about what git-core wants to promote as
the new standard for ref storage.

Shawn Pearce wrote:

On Sun, Aug 6, 2017 at 4:37 PM, Ben Alex [off-list ref] wrote:

quoted

quoted

Just on the LmdbJava specific pieces:

On Mon, Aug 7, 2017 at 8:56 AM, Shawn Pearce [off-list ref] wrote:

I don't know if we need a larger key size. $DAY_JOB limits ref names
to ~200 bytes in a hook. I think GitHub does similar. But I'm worried
about the general masses who might be using our software and expect
ref names thus far to be as long as PATH_MAX on their system. Most
systems run PATH_MAX around 1024.

The key size limit in LMDB can be safely raised to around 2KB or so without 
any issues. There's also work underway in LMDB 1.0 to raise the limit to 2GB, 
but in general it would be silly to use such large keys.

Mostly at $DAY_JOB its because we can't virtualize the filesystem
calls the C library is doing.

In git-core, I'm worried about the caveats related to locking. Git
tries to work nicely on NFS,

That may be a problem in current LMDB 0.9, but needs further clarification.

and it seems LMDB wouldn't. Git also runs
fine on a read-only filesystem, and LMDB gets a little weird about
that.

Not sure what you're talking about. LMDB works perfectly fine on read-only 
filesystems, it just enforces that it is used in read-only mode.

Finally, Git doesn't have nearly the risks LMDB has about a
crashed reader or writer locking out future operations until the locks
have been resolved. This is especially true with shared user
repositories, where another user might setup and own the semaphore.

All locks disappear when the last process using the DB environment exits.
If only a single process is using the DB environment, there's no issue. If 
multiple processes are sharing the DB environment concurrently, the write lock 
cleans up automatically when the writer terminates; stale reader locks would 
require a call to mdb_reader_check() to clean them up.

The primary issue with using LMDB over NFS is with performance. All reads are 
performed thru accesses of mapped memory, and in general, NFS implementations 
don't cache mmap'd pages. I believe this is a consequence of the fact that 
they also can't guarantee cache coherence, so the only way for an NFS client 
to see a write from another NFS client is by always refetching pages whenever 
they're accessed.

This is also why LMDB doesn't provide user-level VFS hooks - it's generally 
impractical to emulate mmap from application level. You could always write a 
FUSE driver if that's really what you need to do, but again, the performance 
of such a solution is pretty horrible.

LMDB's read lock management also wouldn't perform well over NFS; it also uses 
an mmap'd file. On a local filesystem LMDB read locks are zero cost since they 
just atomically update a word in the mmap. Over NFS, each update to the mmap 
would also require an msync() to propagate the change back to the server. This 
would seriously limit the speed with which read transactions may be opened and 
closed. (Ordinarily opening and closing a read txn can be done with zero 
system calls.)

-- 
   -- Howard Chu
   CTO, Symas Corp.           http://www.symas.com
   Director, Highland Sun     http://highlandsun.com/hyc/
   Chief Architect, OpenLDAP  http://www.openldap.org/project/

Howard Chu wrote:

The primary issue with using LMDB over NFS is with performance. All reads are 
performed thru accesses of mapped memory, and in general, NFS implementations 
don't cache mmap'd pages. I believe this is a consequence of the fact that 
they also can't guarantee cache coherence, so the only way for an NFS client 
to see a write from another NFS client is by always refetching pages whenever 
they're accessed.

LMDB's read lock management also wouldn't perform well over NFS; it also uses an mmap'd file. On a local filesystem LMDB read locks are zero cost since they just atomically update a word in the mmap. Over NFS, each update to the mmap would also require an msync() to propagate the change back to the server. This would seriously limit the speed with which read transactions may be opened and closed. (Ordinarily opening and closing a read txn can be done with zero system calls.) 

All that aside, we could simply add an EXCLUSIVE open-flag to LMDB, and 
prevent multiple processes from using the DB concurrently. In that case, 
maintaining coherence with other NFS clients is a non-issue. It strikes me 
that git doesn't require concurrent multi-process access anyway, and any 
particular process would only use the DB for a short time before closing it 
and going away.

-- 
   -- Howard Chu
   CTO, Symas Corp.           http://www.symas.com
   Director, Highland Sun     http://highlandsun.com/hyc/
   Chief Architect, OpenLDAP  http://www.openldap.org/project/

-----Original Message-----
From: Howard Chu [mailto:hyc@symas.com]
Sent: Monday, August 14, 2017 8:31 AM
To: spearce@spearce.org
Cc: David Turner <redacted>; avarab@gmail.com;
ben.alex@acegi.com.au; dborowitz@google.com; git@vger.kernel.org;
gitster@pobox.com; mhagger@alum.mit.edu; peff@peff.net;
sbeller@google.com; stoffe@gmail.com
Subject: Re: reftable [v5]: new ref storage format

Howard Chu wrote:

quoted

The primary issue with using LMDB over NFS is with performance. All
reads are performed thru accesses of mapped memory, and in general,
NFS implementations don't cache mmap'd pages. I believe this is a
consequence of the fact that they also can't guarantee cache
coherence, so the only way for an NFS client to see a write from
another NFS client is by always refetching pages whenever they're accessed.

quoted

LMDB's read lock management also wouldn't perform well over NFS; it
also uses an mmap'd file. On a local filesystem LMDB read locks are
zero cost since they just atomically update a word in the mmap. Over
NFS, each update to the mmap would also require an msync() to
propagate the change back to the server. This would seriously limit
the speed with which read transactions may be opened and closed.
(Ordinarily opening and closing a read txn can be done with zero
system calls.)

All that aside, we could simply add an EXCLUSIVE open-flag to LMDB, and
prevent multiple processes from using the DB concurrently. In that case,
maintaining coherence with other NFS clients is a non-issue. It strikes me that git
doesn't require concurrent multi-process access anyway, and any particular
process would only use the DB for a short time before closing it and going away.

Git, in general, does require concurrent multi-process access, depending on what 
that means.

For example, a post-receive hook might call some git command which opens the 
ref database.  This means that git receive-pack would have to close and 
re-open the ref database.  More generally, a fair number of git commands are
implemented in terms of other git commands, and might need the same treatment.
We could, in general, close and re-open the database around fork/exec, but I am
not sure that this solves the general problem -- by mere happenstance, one might
be e.g. pushing in one terminal while running git checkout in another.  This is 
especially true with git worktrees, which share one ref database across multiple
working directories.

On Mon, Aug 14, 2017 at 04:05:05PM +0000, David Turner wrote:

quoted

All that aside, we could simply add an EXCLUSIVE open-flag to LMDB, and
prevent multiple processes from using the DB concurrently. In that case,
maintaining coherence with other NFS clients is a non-issue. It strikes me that git
doesn't require concurrent multi-process access anyway, and any particular
process would only use the DB for a short time before closing it and going away.

Git, in general, does require concurrent multi-process access, depending on what 
that means.

For example, a post-receive hook might call some git command which opens the 
ref database.  This means that git receive-pack would have to close and 
re-open the ref database.  More generally, a fair number of git commands are
implemented in terms of other git commands, and might need the same treatment.
We could, in general, close and re-open the database around fork/exec, but I am
not sure that this solves the general problem -- by mere happenstance, one might
be e.g. pushing in one terminal while running git checkout in another.  This is 
especially true with git worktrees, which share one ref database across multiple
working directories.

Yeah, I'd agree that git's multi-process way of working would probably
cause some headaches if there were a broad lock.

I had the impression that Howard meant we would lock for _read_
operations, too. If so, I think that's probably going to cause a
noticeable performance problem for servers.  A repository which is
serving fetches to a lot of clients (even if some of those are noops)
has to send the current ref state out to each client. I don't think we'd
want to add a serial bottleneck to that portion of each process, which
can otherwise happen totally in parallel.

Serializing writes is probably not so big a deal as long as it is kept
to the portion where the process is actively writing out values. And as
long as there's a reasonable backoff/retry protocol; right now we don't
generally bother retrying ref locks because they're taken individually,
so racing on a lock almost certainly[1] means that you've lost the
sha1-lease and need to restart the larger operation.

-Peff

[1] Actually, we've found this isn't always true. Things like ref
    packing require taking locks for correctness, which means they can
    interfere with actual ref updates. That's yet another thing it would
    be nice to get rid of when moving away from the loose/packed
    storage.