openldap-devel October 2008

openldap-devel@openldap.org

20 participants
30 discussions

back-ndb design notes
by Howard Chu 19 Oct '08

19 Oct '08

While looking over the Admin Guide I was re-reading section 1.8 (LDAP vs RDBMS) and thought it would be worth describing the approach we took and tradeoffs we made. (Disclaimer: some of these decisions need to be changed.) (Also for more background: NDB is a cluster-based storage engine for MySQL. It runs as its own set of processes across the nodes of a cluster; all accesses to it are through remote procedure calls.) The basic approach starts with a rough adaptation of back-bdb to NDB. That is, we use one table to map DNs to numeric entryIDs, and use this numeric ID as the primary key to access the main entry data. But instead of using a monolithic id2entry table (and treating all the LDAP data as blobs) we start from the notion of a table per objectclass. For objectclasses that inherit from others, only the unique attributes of the subordinate class reside in that class's table. This is one of the underlying requirements - an LDAP attribute must only appear in one table. For attributes that appear in unrelated LDAP objectclasses, you must configure them into "attribute sets" (which are yet another set of tables) to ensure that their column definition is used uniformly by all the objectclasses. Note that this means to retrieve the complete information for a particular entry, we have to pull from many tables at once, and each requires a separate NDB operation. The NDB API allows many operations to be batched together and executed in parallel, so we can do all of these fetches in a single roundtrip. (Otherwise, performance for this approach would be pretty abominable.) The Admin Guide notes that this approach can be very poor because accessing many tables at once requires a lot of disk seeks. This consideration doesn't apply to NDB because each node of the cluster always caches everything completely in RAM. However, we first need to know which tables to fetch from, i.e., we need to consult a table to get a list of objectclasses, before we can spit out the batched request to all the relevant tables. To avoid having to visit so many different tables sequentially, we store the objectclass attribute in the dn2id table. (We obviously have to visit the dn2id table anyway. Just as with back-bdb, where accessing any entry by name requires first a dn2id lookup followed by an id2entry lookup, here we must do the dn2id lookup followed by the parallel lookups across all of the class/set tables.) For as much functionality as that covers, things are pretty straightforward. The dn2id table has some interesting issues as well. I think it's a poor design, but it was the best we could do under our initial constraints. Basically it has a 16 column primary key, where each rdn occupies a column. This approach makes it fairly easy to obtain base, subtree, and children scoping, but it suffers from the same problems as back-bdb and back-ldbm. (Bloated, no subtree rename... Plus, it imposes a hard limit on tree depth at 16 levels. It's probably an acceptable limit, but worth noting that none of our other backends have such a limit.) The entryID is just an integer column, and the objectclass attribute is a single column containing all of the classes concatenated as a space-delimited string. E.g., for an entry with objectClass: person objectClass: inetOrgPerson the column will contain " person inetOrgPerson " This format allows us to perform equality searches on objectclass using an SQL LIKE filter. (objectclass=foo) -> objectclass like "% foo %" (Filters aren't implemented using actual SQL, but the NDBapi filter mechanism obviously implements SQL filtering functionality.) As mentioned, the numeric entryID is used as the primary key of the main data tables. In fact, that was just our initial approach which only supported single-valued attributes. Now we support multivalued attributes by using a two-column primary key, <entryID,value#>. So there's a "value" column with values from 0 to N-1 for an attribute with N values, and each value occupies a separate row. The NDBapi allows us to do partially-specified primary key lookups, so we can do a lookup on just the entryID and automatically get all of the values/rows associated with that entryID in a single operation. Search indexing is currently a mess, and will need to be rewritten. We arrived at the current approach based on a couple main constraints: 1) this backend will do no local caching 2) we must always retrieve the desired data in only 2 API roundtrips #1 was based on the requirement that multiple slapds be able to operate concurrently on the database, along with multiple mysqlds. We didn't have time to design a distributed cache synchronization mechanism, therefore, no local caching. #2 was based on the simple fact that taking more than 2 roundtrips would destroy performance. The current solution uses the regular SQL table indexing features, but the indices are stored in the dn2id table, not in the main data tables. This means we can do an index lookup and obtain an entry's DN and objectclasses in a single roundtrip, then a single roundtrip for the main data, so it meets our #2 constraint. One problem with this is that a single table can only accommodate rows up to 8192 bytes wide, and we can easily max that out when multiple indices are needed. Another problem is that updating indexed attribute values requires writes to both the main data tables and the dn2id table. While back-ndb handles this itself, mysql daemons writing to the data tables won't know about this requirement. (We need to use a trigger/stored procedure to make sure the SQL side keeps the indices up to date.) The big problem here is that if you want to be able to match multiple columns in an indexed filter lookup, they must all belong to a single index. A 3 column index <a,b,c> is not the same as 3 individual indices <a>, <b>, and <c>... With the multi-column index, you can only match filters that use those columns in that specific order. E.g., (&(a=foo)(b=bar)(c=baz)) will work but not (&(c=baz)(b=bar)(a=foo)). You can omit the trailing columns (&(a=foo)(b=bar)) but you can't omit the leading columns (&(b=foo)(c=bar)). And, while the SQL indexers support equality and inequality indexing, they don't support substring indexing at all. Moving forward, I think the only feasible approach is to stop using multi-column indices. We'll use individual indices, and have to perform boolean evaluations within slapd, instead of letting the NDB engine evaluate them. This is unfortunate because it will use a lot more network bandwidth, but we don't have much choice. Likewise, we can't do anything about substring indexing, it's up to MySQL to provide a solution for that. Other big changes going forward include replacing the current dn2id scheme with a back-hdb style layout so that we don't waste so much space, and so we can support subtree rename. We'll also take a stab at local caching of the dn2id table. (That may be rather tricky; NDB has an event API that slapd can use to listen for add/delete/modify events, but it's totally asynchronous. If we can't work out a way to keep the cache transactionally consistent then this just isn't going to happen.) Mapping LDAP onto an RDBMS is still a hard problem. back-ndb implements some pretty good solutions to a lot of the problems, but there's still things that can be improved. The current backend works for a limited set of LDAP use cases, and operates well even with concurrent SQL access. With the changes I described, it will support a broader range of LDAP use cases... -- -- 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

Re: commit: ldap/servers/slapd schema_init.c
by Hallvard B Furuseth 18 Oct '08

18 Oct '08

ando(a)OpenLDAP.org writes: > schema_init.c 1.452 -> 1.453 > apply Luca Tamburo's patch for Attribute Certificate and X.509 PMI > support (with modifications, ITS#5695) Any reason to make these ber_int_t instead of ber_len_t? > + ber_int_t src, dst; > + (...) > + for ( src = 0, dst = 0; src < is->bv_len; src++, dst++ ) { I had just changed them to ber_len_t to kill a warning for the comparison with is->bv_len. -- Hallvard

2 3

Replication notes
by Howard Chu 17 Oct '08

17 Oct '08

Slurpd and syncrepl really took opposite approaches to replication. While syncrepl allows consumers to be configured without any special configuration of the provider, slurpd allowed slaves to be configured without any special knowledge. This feature allowed slurpd to be used to replicate to pretty much anything that understood some flavor of LDAP. With syncrepl, the consumer must minimally understand entryCSNs, entryUUIDs, and a contextCSN. This requirement would appear to limit our reach. But with delta-syncrepl, we actually need nothing more than a contextCSN to keep track of where we are in the changelog. And when using delta-syncrepl thru an LDAP proxy, there's actually no requirement that we store the contextCSN on the remote server. We could simply store the contextCSN as a DB-specific attribute of the proxy DB's entry under cn=config. Whether we do this by explicitly modifying the syncrepl code, or by using an overlay to accomplish the sleight-of-hand doesn't seem to matter much. (Though there may be more uses for a customizing/mapping overlay here; e.g. translating LDAPv3 schema to MS AD.) Just wanted to mention this here before I forgot it again. -- -- 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

Re: commit: ldap/servers/slapd/overlays collect.c
by Howard Chu 17 Oct '08

17 Oct '08

hallvard(a)OpenLDAP.org wrote: > Update of /repo/OpenLDAP/pkg/ldap/servers/slapd/overlays > > Modified Files: > collect.c 1.11 -> 1.12 > > Log Message: > ITS#5747: Only use C99 flexible array member when supported > > CVS Web URLs: > http://www.openldap.org/devel/cvsweb.cgi/servers/slapd/overlays/ > http://www.openldap.org/devel/cvsweb.cgi/servers/slapd/overlays/collect.c > > Changes are generally available on cvs.openldap.org (and CVSweb) > within 30 minutes of being committed. > Just set it to *ci_ad[1] and leave it at that. Ifdefing this situation is unnecessary. -- -- Howard Chu CTO, Symas Corp. http://www.symas.com Director, Highland Sun http://highlandsun.com/hyc/ Chief Architect, OpenLDAP http://www.openldap.org/project/

2 1

sorted values vs. compare errors
by Hallvard B Furuseth 17 Oct '08

17 Oct '08

I don't know if this is a false alarm or not, but anyway: Sorted values, as with SLAP_ATTR_SORTED_VALS in attr_valfind(), needs an unambiguous ordering. However value_match() can return error, and does not say which of the compared values caused the error. Are there sorted value examples where it can return error both because of the stored value and because of the assertion value? Or overlays like rwm which can cause this? If so the sort order of (normal value, value causing error) will depend on the order of arguments to the compare function. Then if we manage to insert an "ambiguously-sorted" attribute value into the sorted list of values, then a binary search for an existing normal value can fail if it hits the naughty value as a pivot entry. Or it can cause a new value to be inserted at the wrong place. Possibly there are also some other strange matching rules where the ordering is ambiguous, I don't know. In any case, I think this whould mean that: - value_match() and ordering-compare functions should try to define unambiguous orderings of (normal value, truble value). I think sorting of (trouble value 1, truble value 2) does not matter. - maybe Sorted values should only be supported for attributes whose compare functions do define such an ordering. However there are also inequality filters vs. sorted attribute values. This code in slapd/filterentry.c:test_ava_filter() is similarly broken if there is an error-generating value at either end of the array of values: if (( a->a_flags & SLAP_ATTR_SORTED_VALS ) && type != LDAP_FILTER_APPROX ) { unsigned slot; int ret; /* For Ordering matches, we just need to do one comparison with * either the first (least) or last (greatest) value. */ if ( use == SLAP_MR_ORDERING ) { const char *text; int match, which; which = (type == LDAP_FILTER_LE) ? 0 : a->a_numvals-1; ret = value_match( &match, a->a_desc, mr, use, &a->a_nvals[which], &ava->aa_value, &text ); if ( ret != LDAP_SUCCESS ) return ret; For such a value, and with a normal assertion value, the function ought to search for the nearest non-error-generating value and compare with that. -- Hallvard

1 0

Re: commit: ldap/doc/man/man5 slapd.conf.5
by Hallvard B Furuseth 17 Oct '08

17 Oct '08

ando(a)OpenLDAP.org writes: > slapd.conf.5 1.291 -> 1.292 > minor clarifications Remember slapd-config.5. -- Hallvard

1 0

Trivial build fixes for addpartial
by Buchan Milne 16 Oct '08

16 Oct '08

I should have reported this when I first enabled addpartial (but it was most likely near distribution release time ...), but I had patched the Makefile to build more sanely: http://svn.mandriva.com/cgi- bin/viewvc.cgi/packages/cooker/openldap/current/SOURCES/openldap-2.4.8- addpartial-makefile.patch?revision=189682&view=markup Since some things have now been fixed (but others not), I had to re-diff to address the outstanding items: 1)-fPIC is required in LDFLAGS to build on x86_64 (I didn't check to see if there's a more portable way) 2)I don't see a reason to call the overlay addpartial-overlay, we all know it is an overlay. http://svn.mandriva.com/cgi- bin/viewvc.cgi/packages/cooker/openldap/current/SOURCES/openldap-2.4.8- addpartial-makefile.patch?revision=293664&view=markup Regards, Buchan

3 2

Re: commit: ldap/doc/man/man5 slapd-bdb.5
by Hallvard B Furuseth 15 Oct '08

15 Oct '08

hyc(a)OpenLDAP.org writes: > slapd-bdb.5 1.40 -> 1.41 > Add dbpagesize keyword for configuring DB file page sizes If I understand the DB doc correctly, a pagesize parameter which means "use the file system's block size" could also be useful, at least for data integrity. Unless that's already the default. -- Hallvard

2 8

Re: commit: ldap/libraries/libldap gssapi.c
by Hallvard B Furuseth 13 Oct '08

13 Oct '08

hyc writes: > gssapi.c NONE -> 1.1 > > ITS#5369 SASL/GSSAPi refactoring from Stefan Metzmacher <metze(a)samba.org> > and Rafal Szczeniak <mimir(a)samba.org>, with minor cleanups This is buggy: pkt_len is used uninitialized in sb_sasl_gssapi_decode(). guess_service_principal() is broken: It uses 'ret' uninitialized, as if a return value from malloc. It passes (buffer length - 1) instead of buffer length to snprintf, which I think fails for the (allow_remote && givenstr) case. snprintf() unnecessary anyway since the function can malloc the exact needed size. Also it's preferable to only use a string literal as format argument, so gcc can verify the printf (instead of warning that it can't). Format errors: OM_uint32 printed as %u, size_t/ber_len_t as %lu. Here is a draft patch. Untested. Note I've not looked at how this actually works, just how to get rid of warnings. http://folk.uio.no/hbf/OpenLDAP/gssapi.txt Finally, some header files should declare these functions: ldap_gssapi_bind_s(), ldap_int_gssapi_close(), ldap_int_gssapi_config(), ldap_int_gssapi_get_option(), ldap_int_gssapi_set_option(), ldap_pvt_sasl_generic_install(), ldap_pvt_sasl_generic_remove(), and be #included by bind.c, cyrus.c, gssapi.c, init.c, options.c, request.c. -- Regards, Hallvard

3 3

ldap_sasl_interactive_bind support
by Howard Chu 09 Oct '08

09 Oct '08

I think we need to move the lutil_sasl_interact stuff into libldap. Clients ought to be able to use libldap's SASL support without having to #include Cyrus's <sasl.h> themselves. Right now they're forced to write their own interact handlers and the handlers must know about the SASL_CB constants etc. This is ugly; callers shouldn't need to know anything about what the underlying SASL implementation is doing. Actually the lutil_sasl_ code should be cleaned up a bit, not used in libldap as-is. In particular, we should define a callback whose only purpose is to display a provided prompt string and retrieve user input. This callback's interface must have zero dependencies on <sasl.h>. We can provide a generic callback that writes to stderr and uses getpassphrase, but callers should be able to replace this with GUI dialog callbacks etc. -- -- Howard Chu CTO, Symas Corp. http://www.symas.com Director, Highland Sun http://highlandsun.com/hyc/ Chief Architect, OpenLDAP http://www.openldap.org/project/

2 1

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

openldap-devel October 2008