openldap-devel

openldap-devel@openldap.org

1420 discussions

LMDB app-level crash consistency
by Howard Chu 17 Oct '14

17 Oct '14

For posterity, this is the conversation we had with the University of Wisconsin researchers behind this Usenix OSDI paper: https://www.usenix.org/conference/osdi14/technical-sessions/presentation/pi… > On Thu, Jul 24, 2014 at 8:10 AM, Howard Chu <hyc(a)symas.com > <mailto:hyc@symas.com>> wrote: > > Hello Thanu, > I just saw your slides from > http://wisdom.cs.wisc.edu/__index.htm#news-2 > <http://wisdom.cs.wisc.edu/index.htm#news-2> and was wondering if you > could give more details on the crash vulnerabilities you found in LMDB. > Thanks. 25/07/14 09:42 Thanumalayan Sankaranarayana Pillai wrote: > > Hi Howard, > > > > Thanks for your interest in the slides. We appreciate you caring about the > > vulnerability. > > The single crash vulnerability that we discovered in LMDB concerns the > 106-byte update to the header while inserting a key-value pair (within the > mdb_txn_commit function). Specifically, if this overwrite is not done > atomically (i.e., if only a part of the 106 bytes goes to disk, and then a > crash happens), then LMDB reports an error if we try to further modify the > database after reboot. The error reported is "mdb_page_touch: Assertion > `mp->mp_p.p_pgno != pgno' failed". > > We also did some manual analysis by making the loss in atomicity correspond to > field boundaries within the information contained in those 106-bytes (such as > free list data and transaction ID), and found that LMDB loses the previous > transaction sometimes. For example, if the database contains Txn-1, Txn-2, and > Txn-3, and a crash happens while inserting Txn-4, the rebooted-database might > lose Txn-3. I have not included any such manual analysis results in the slides. > > I have attached a text file with a more detailed description of the > vulnerability. If you have any questions on the details, I have CC'ed Ram, who > actually tested LMDB for the vulnerabilities and might be able to help you > better than me. > > Thus, the vulnerability in LMDB relates to the atomicity of a file overwrite > that is within a 512-byte sector. With current (ext3/ext4/btrfs/xfs/zfs) file > systems running atop hard drives and SSDs, this is probably not a problem. > (The only place we have heard about that indicates atomicity might not be > maintained here is [1]). > > However, byte-accessible NVRAMs in the future will probably expose this > vulnerability. We are also not sure what happens with the multi-level storage > stacks many people use these days (Virtual machines atop Fusion-IO-card > connected via networks to a NAS?). In our understanding, even for these > situations, LMDB can solve this vulnerability easily, since it has two root > pointers. > > All said, since we are not particularly experts at using LMDB, there is a > slight chance we made a mistake in how we used LMDB while testing it. Please > let us know if you suspect this to be the case. Hope this helps! > > [1] http://lkml.iu.edu//hypermail/linux/kernel/0908.3/00155.html > > -- > Thanks, > Thanu 25/07/14 11:38 Howard: > Thanks much for your reply. The results you describe are not too surprising; > we assume atomic sector writes. This is an area we've spent quite a lot of > time researching ourselves. I summarized our findings here last year > http://www.openldap.org/its/index.cgi/Incoming?id=7668 > > Currently all hard drive/SSD manufacturers guarantee that 512 byte sector > writes are atomic. As such, failure to write the 106 byte header is not > something we account for in current LMDB releases. Also, failures of this type > should result in ECC errors in the disk sector - it should be impossible to > successfully read a sector that was written incorrectly in the ways you describe. > > Even in extreme cases, the probability of failure to write the leading 128 out > of 512 bytes of a sector is nearly nil - even on very old hard drives, before > 512-byte sector write guarantees. We would have to go back nearly 30 years to > find such a device, e.g. > > http://bitsavers.informatik.uni-stuttgart.de/pdf/quantum/Quantum_ProDrive_4… > > Page 23, Section 2.1 > "No damage or loss of data will occur if power is applied or removed during > drive operation, except that data may be lost in the sector being written at > the time of power loss." > > From the specs on page 15, the data transfer rate to/from the platters is > 1.25MB/sec, so the time to write one full sector is 0.4096ms; the time to > write the leading 128 bytes of the sector is thus 1/4 of that: 0.10ms. You > would have to be very very unlucky to have a power failure hit the drive > within this .1ms window of time. Fast-forward to present day and it's simply > not an issue. > > But as you say, byte-addressable storage is coming soon. The LMDB 1.x versions > will add a checksum to the two headers, and will fallback to using the > previous header if a checksum error is found. > > Thanks again for your work, looking forward to reading your full paper in the > future. 25/07/14 13:14 Thanu: > Hi Howard, > > Great to know that so much thought was already put into this issue. (We usually see people assume things about the storage stack that are simply false, and without any notion of when they will become false if they aren't already.) I am waiting for all the cool new things that will be on LMDB 1.0. > > Thanks, > Thanu 25/07/14 13:15 Howard: > Hi again, > looking over these vulnerabilities, they all seem unrealistic even given > the existence of byte-addressable storage devices. In particular, even if you > assume writes may be non-atomic, why do you assume that writes will be > non-sequential within a sector? > > For example, if we were talking about an HDD that did not guarantee atomic > sector writes, we still know that bytes are written sequentially from > beginning of sector to end of sector; this is one reason why the LMDB meta > page is laid out in the way that it is - the transaction ID is last because if > a partial write occurs and the txn ID doesn't make it to disk, this meta page > will be ignored and the previous one will be used automatically. > > In the tests you describe here, you have broken this sequential assumption, > but there are no storage devices in existence that can fail in the manners you > describe. And even in byte-addressable memories, DMA or memcpy routines will > always start at a low-numbered address and work sequentially higher. Do you > really believe it is important for software to protect against this type of > failure scenario? >> > Found using automatic analysis >> > ------------------------------ >> > >> > Write (106 bytes) at lib/mdb.c:3227[mdb_txn_commit]. Split into three, first part (first 36 bytes) alone does not go to disk. >> > >> > Error: lib/mdb.c:1921: mdb page touch: Assertion ‘mp->mp p.p pgno != pgno’ failed. >> > >> > Exact situations where the vulnerabilities arise, found using manual analysis >> > ----------------------------------------------------------------------------- >> > >> > 1. Only txn id gets into metapage and no other data: >> > >> > Previous transaction is lost. >> > >> > 2. Free list data, txn id and last page goes in but not main db details: >> > >> > Previous transaction is lost. Error: lib/mdb.c:1921: mdb page touch: Assertion ‘mp->mp p.p pgno != pgno’ failed. >> > >> > 3. only main db - 2 fields no free pointer: >> > >> > Error: lib/mdb.c:1921: mdb page touch: Assertion ‘mp->mp p.p pgno != pgno’ failed. >> > >> > 4. Everything gets in except database pointer - it is 48 bytes - but a crash happens such that second 24 bytes (which contains the root) is missed: >> > >> > Previous transaction is lost. Error: lib/mdb.c:1921: mdb page touch: Assertion ‘mp->mp p.p pgno != pgno’ failed. 25/07/14 14:03 Thanu: > Hi Howard, > > To be honest, we are not yet sure whether it is important for software to protect sequential-assumption-breaking under practical circumstances. While byte-addressable devices might only persist things sequentially, a byte-addressable file system itself might re-order bytes (what if the memcpy doesn't start from the lower address?); at this point however, I am probably being cynical and hypothesizing too much about the future. > > However there is currently no standard/guarantee that (file-system-level) writes should be sequential or atomic as far as we know. One of our goals in doing this project is to show the entire community how non-standardized the interaction between the application and the file system is. It is fully possible that, by the time NVMs become main-stream, standards arise and sector-size non-sequential (or even non-atomic) writes are disallowed. (It might also be possible that someone invents an NVM with high parallel bandwidth, and memcpy() explicitly parallelizes updates to contiguous bytes for higher throughput.) > > Personally, with software such as LMDB, I feel that we should simply add a CRC, just in case future storage stacks behave in "reasonably weird" ways. I do understand that it might be better to not do this for either readability or performance and simply keep an eye out for any new storage stacks. > > If it is not too much trouble, can you point me to any discussions about byte-addressable storage being sequential? I have heard this mentioned once before, but I cannot find any solid references to it. Any references to sequentiality within HDDs will be useful as well. > > Thanks, > Thanu On Fri, Jul 25, 2014 at 8:50 AM, Howard Chu <hyc(a)symas.com wrote: >>> Regarding sequentiality within HDDs, that's a natural consequence of the >>> physical construction/operation of HDDs. The platters rotate under the R/W >>> head, the R/W head spits out a stream of bits in sequential order. The >>> platter always rotates in one direction, at essentially constant speed, so >>> the R/W head cannot skip back and forth within 1 sector and write out of >>> order. It's physically impossible for HDDs to write non-sequentially >>> within a single sector. >>> >>> For your reference re: SSDs, here's an old Samsung NAND Flash data sheet. >>> http://pdf1.alldatasheet.com/__datasheet-pdf/view/84340/__SAMSUNG/K9F1G08U0… >>> <http://pdf1.alldatasheet.com/datasheet-pdf/view/84340/SAMSUNG/K9F1G08U0A.ht…> >>> >>> The relevant info is page 31 "Page Program" >>> "The device is programmed basically on a page basis, but it does allow >>> multiple partial page programing of a word or consecutive >>> bytes up to 2112, in a single page program cycle. The number of >>> consecutive partial page programming operation within the same >>> page without an intervening erase operation must not exceed 4 times for >>> main array(1time/512byte) and 4 times for spare >>> array(1time/16byte). The addressing should be done in sequential order in >>> a block." >>> >>> For byte-addressable storage I suppose no hard rules apply. If we're >>> talking about NVDIMMs, they are treated basically the same as DRAM. Still, >>> in Linux today you're most likely to see a block-device style layer >>> imposed above them. DMA controllers tend to be programmed for >>> auto-incrementing addresses. memcpy will tend to do the same, since CPU >>> prefetchers are also designed with at least cache-line sequentiality. >>> I.e., it may not be important to write to the destination in sequential >>> order, but there is a performance benefit to reading from the source in >>> sequential order, and there is no benefit to holding the read and >>> reordering it before pushing to the destination. >>> 25/07/14 15:46 Thanu: > Hi Howard, > > Thanks for the explanation and the pointers. They are really helpful. > > While you certainly have more working knowledge of byte-addressable > storage than me, I still believe there is an (extremely) small chance of non-sequential updates on Linux. Let us say that the cache block is 64 bytes in size, and the block-device layer modifies the mapped memory addresses corresponding to all user writes. For argument's sake, let us also say that writes are written back to the actual storage if there is a change in the (coherence) ownership of a cache block. If we consider two adjacent 64-byte blocks, and the second block is written twice by different cores, it is possible that the second block reaches the storage first. > > Of course, even if such non-sequential updates become possible in the future, it would require changes to the file-system journaling machinery itself, and is bound to be well-publicized. I am only justifying why we considered non-sequential updates in our study (to measure the impact of such scenarios on applications). We are hoping that if someone in the future (ever) debates about introducing non-atomic updates, they fully understand the application-level consequences by looking at our study. > > Thanks, > Thanu 25/07/14 16:46 Howard: > Fair enough. Certainly, if the question ever arose, I would be glad we have > your study to point to as a reference. -- -- Howard Chu CTO, Symas Corp. http://www.symas.com Director, Highland Sun http://highlandsun.com/hyc/ Chief Architect, OpenLDAP http://www.openldap.org/project/

1 0

question about use of buffers in lmdb
by Luke Kenneth Casson Leighton 17 Oct '14

17 Oct '14

howard, et al, hi, i notice that LMDB stores data in an "append only" manner (from the Q&A). i was thinking of recommending that in python the buffers be handed around with *direct* and persistent pointers to the data within the LMDB shm/memory-map. the reason that i believe this will be successful is because the circumstances are rather unusual: once data is entered (added) it is *never* overwritten, updated, changed, or modified. there simply is no need [in this application]. so there will only ever be insertion (once and only once) or controlled and monitored deletion (by age of record). under these circumstances is it perfectly reasonable to pass around the pointers to the buffers returned from value look-ups *indefinitely*? if so that would be awesome. l.

2 2

Notice to move the Fortress source to Apache Directory project
by Shawn McKinney 08 Oct '14

08 Oct '14

Hello, This is a notice of intent to move the following sources to apache directory project: 1. fortress core 2. realm 3. emnasse 4. commander The goal is to expand user adoption and gain commiters by working alongside projects of a similar nature, i.e. syncope, shiro, studio, etc. Over the past three years I have enjoyed the benefits of these sources being housed within the openldap project and will continue to promote fortress using openldap directory server as before. Indeed there are projects in our pipeline (rbac accelerator overlay) that will (should) remain under the openldap umbrella so my participation with openldap project will continue for the forseeable future. Shawn McKinney -- 650-963-7681 smckinney(a)symas.com

1 0

On-demand page mapping in LMDB
by Howard Chu 01 Oct '14

01 Oct '14

The vl32 branch on gitorious has some tweaks for LMDB to mmap on individual page accesses, instead of mmap'ing the entire DB file all at once. This is primarily to support usage on 32 bit machines, where the address space is too small to accomodate multiple DBs mapped in competely, all at once. https://gitorious.org/mdb/mdb/source/69d7cb8d44e04f02d8d0c923ae71fbaaa9f42f…: There's a significant performance hit since almost every page reference results in an mmap system call. But it also has a much smaller memory footprint. While the code passes simple tests, it is also broken in one significant aspect: Currently, advancing a cursor to a new page causes the previous page to be unmapped. If there are two cursors open on the same DBI in the same transaction, it's possible that the other cursor will still be pointed to the old page, and the unmap will break it. There's currently no check to prevent this, and since read txns don't track all of their open cursors, there is no way to check (unless we add refcounts to this array, which would be clumsy). The solution I'm considering is to get rid of the per-txn array of mapped pages that I added here, and just operate on the cursor stacks directly. In that case, every cursor will have its own set of mapped read-only pages, and nothing that happens on one cursor will have any effect on any other cursor. (For read-only pages. For dirty pages, the usual cursor/page fixups apply as always.) -- -- Howard Chu CTO, Symas Corp. http://www.symas.com Director, Highland Sun http://highlandsun.com/hyc/ Chief Architect, OpenLDAP http://www.openldap.org/project/

1 0

Incremental backup in LMDB
by Howard Chu 01 Oct '14

01 Oct '14

A preliminary branch has been available on gitorious for a few months. It has some issues though, which still need to be resolved. https://gitorious.org/mdb/mdb/source/a7fc32c0b39c29f9afd2172338060b079d549c…: The biggest problem is that scanning every page of the DB is unsafe - if a page was an overflow page, and was freed and partially reused, then a scan may walk into intermediate chunks of data (which won't have valid page headers, although the data might coincidentally appear to have them). Two approaches to solving this are to perform the scan, but ignore pages that are currently listed in the freeDB, or to do a regular tree walk instead. At the moment I'm leaning toward just walking the trees. If the freeDB is large then comparing every scanned page to the freeDB could be expensive. Also, newer pages of the freeDB itself must be copied as well, and this would mean freeDB pages get read twice. Just thinking out loud here to document what we discussed before in IRC, so it doesn't get lost in the meantime. -- -- Howard Chu CTO, Symas Corp. http://www.symas.com Director, Highland Sun http://highlandsun.com/hyc/ Chief Architect, OpenLDAP http://www.openldap.org/project/

1 0

unique incrementing value with lmdb?
by CJ Ess 23 Sep '14

23 Sep '14

What is the best way to implement a unique incrementing value (for use as a key or value) with lmdb? Is there a property if the transaction mechanism I could piggy-back off of to atomically generate my number? Or should I block writers above mdb_cursor_put, do my lmdb transaction, and unblock?

2 1

Re: Problem: LDAP installation without internet
by Aaron Richton 23 Sep '14

23 Sep '14

On Fri, 22 Aug 2014, Patrick Pat wrote: > Hi, > I would like all LDAP installation procedure without internet in linux > (ubuntu (9.10 or other), Debian, ...), but by its compressed file > > namely: > openldap-2.4.8.tgz or openldap-2.4.7.tgz or openldap-2.4.9.tgz or > openldap-2.0-beta.tgz ... > And any configuration environment variables. So inside that .tgz, there's a file called "INSTALL"; you might want to take a look. None of the procedures mentioned in "INSTALL" require anything other than a vaguely sane POSIX-esque (or Windows, but let's not go there) system. This includes any particular network connectivity, Internet or otherwise. > best regards ! > >

1 0

writing about lmdb semantics, need some help
by bert hubert 23 Sep '14

23 Sep '14

Hi everybody, First, thank you for developing openldap & lmdb, both are appreciated. I ran openldap 'way back in the day' to power one of the first cable internet providers in The Netherlands, and once we shook out the bugs, it was great! Within PowerDNS, we have an LMDB backend for the highest performance, and we also want to use it for Metronome (https://github.com/ahupowerdns/metronome , a sort of mini-graphite). In order to do so, I'm documenting LMDB semantics. The LMDB documentation has most of this, but I'd like to get the semantics in one place. ( https://github.com/ahupowerdns/ahutils/blob/master/lmdb-semantics.md - with some great help from Howard already) A few questions: * - Do not have open an MDB database twice in the same process at * the same time. Not even from a plain open() call - close()ing it * breaks flock() advisory locking. I see this note, but I also see a lot about TLS locking. Is this remark still true? It is quite difficult for many applications to effectively serialize LMDB access this way, which would be required because: * - A thread can only use one transaction at a time, plus any child * transactions. Each transaction belongs to one thread. See below. * The #MDB_NOTLS flag changes this for read-only transactions. I note that the source does not actually use flock() but fcntl()-based locking, which does have the problem described above. So my question, if there is one process with many threads that need to read and update an lmdb, what is the recommended way to do that, short of single threading the access to lmdb? Bert

2 1

TXN in master
by Michael Ströder 22 Sep '14

22 Sep '14

HI! It seems TXN support has landed in git master. Is it ready for interop testing? Ciao, Michael.

2 3

writing about lmdb semantics, need some help
by bert hubert 21 Sep '14

21 Sep '14

(third attempt to get this posted) Hi everybody, First, thank you for developing openldap & lmdb, both are appreciated. I ran openldap 'way back in the day' to power one of the first cable internet providers in The Netherlands, and once we shook out the bugs, it was great! Within PowerDNS, we have an LMDB backend for the highest performance, and we also want to use it for Metronome (https://github.com/ahupowerdns/metronome , a sort of mini-graphite). In order to do so, I'm documenting LMDB semantics. The LMDB documentation has most of this, but I'd like to get the semantics in one place. ( https://github.com/ahupowerdns/ahutils/blob/master/lmdb-semantics.md - with some great help from Howard already) A few questions: * - Do not have open an MDB database twice in the same process at * the same time. Not even from a plain open() call - close()ing it * breaks flock() advisory locking. I see this note, but I also see a lot about TLS locking. Is this remark still true? It is quite difficult for many applications to effectively serialize LMDB access this way, which would be required because: * - A thread can only use one transaction at a time, plus any child * transactions. Each transaction belongs to one thread. See below. * The #MDB_NOTLS flag changes this for read-only transactions. I note that the source does not actually use flock() but fcntl()-based locking, which does have the problem described above. So my question, if there is one process with many threads that need to read and update an lmdb, what is the recommended way to do that, short of single threading the access to lmdb? Bert

1 0

Jump to page:

2025

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

openldap-devel