[Date Prev][Date Next]
Re: back-bdb IDL limitations
Jonghyuk Choi wrote:
The proposed scheme can increase the size of IDLs for attribute
indices (esp. substring indices). If neighboring indices in an IDL are
spaced with large intervals, the proposed scheme can either 1) double
the storage required to represent an ID in the IDL (because lo/hi are
needed instead of a single ID), or 2) cause IDs of many irrelevant
entries to be included in the IDL.
Rather coincidentally, I've also prepared patches to optimize indexing
The first one is targeting to accelerate slapadd based on the
observation that IDs are added in a monotonically ascending order
during slapadd. Instead of writing to the index database upon addition
of every single ID, slapadd can be made to buffer multiple IDs to make
an ID cluster and writes the cluster as a single unit.
An IDL for an index hash will look like the following:
Header consisting of NOID and # of IDs in the IDL
ID cluster 1
ID cluster 2
ID cluster 3
ID cluster N
The header and ID clusters are keyed with the same hash value and they
are sorted in an ascending order (NOID is treated as the smallest in
the dup function). As a result, the number of writes to the index
databases can be reduced by the factor of the cluster size. For
example, if the cluster size is 1024, the number of writes to the
index database can be reduced by up to 1024 and this significantly
improves the performance of slapadd.
That sounds pretty good. Also sounds somewhat like extending the
IDLcache to have writeback behavior instead of its current writethru mode.
If the IDs in an IDL are rather contiguous, the range optimization you
suggested can help. Otherwise, it won't be able to buy us much. I
suspect this be the case for the subtree indices for general ldifs (by
the term general, I mean not specially sorted for a naming attribute,
for example, ou) and substring indices.
For non-tool mode addition (ldapadd), if the currently added ID is the
greatest of all IDs in the IDL, it is added as a single ID stored as
the end data for the index key. If the currently added ID is not the
greatest, then it is added into the ID cluster it belongs (where lo <=
ID <= hi holds). If the size of the cluster becomes larger than the
max cluster size, it is split into half. To delete an ID from an IDL,
the corresponding ID cluster need be located. The cluster will be
read, modified, and written in order to remove the ID from the cluster.
This begins to sound like back-ldbm IDblocks. Shuffling IDs from one
chunk to another was definitely error-prone there. Certainly it can be
done right, just need to be careful about it.
The second one is targeting to accelerate the overall index database
performance by using a bit-map to represent IDLs. The compaction
achieved by using a bit map instead of using a pointer ID can result
in the reduced number of data items for an index key in the index
database. This in turn leads to the improved btree search performance.
A bit map structure called the segment bit-map can be used for this
purpose. A segment bit-map consists of a pointer and a bit map. For
example, let's assume that a segment bit-map is 32 bits long of which
24 bits are assigned to the pointer and 8 bits are to the bit map.
The pointer represents the 8-bit aligned position of the bit map in
the entire ID space while the bit map represents the indexing status
for 8 contiguous indices whose position is determined by the pointer.
In this example, the segment bit-map can cover indices for (2**24) * 8
entries (128M entries). As a concrete example, a segment bit-map
having its pointer field of 2 and its bit map field of 0xA5 tells that
the IDs 16, 18, 21, 23 are the indexed entries. We can have multiple
of them to represent an entire IDL in the same way we had multiple IDs
to represent an IDL. If we use 64 bit long segment bit-maps, then we
can increase the coverage that a single segment bit-map can provide
and can increase the number of indexed entries. For example if we
assign 32 bits to the pointer field and 32 bits to the bit map field,
a 64 bit segment bit-map can store indexing values for 32 contiguous
entries and it can support up to 128G entries.
This is definitely an improvement over the current scheme, but it still
suffers from a hard size limit in a given IDL size. For our current
default of 64K words per IDL, using 32 bit maps restricts us to a total
of 512K entries in one IDL. Using 64 bit maps only extends that to 1M
entries. To be able to approach the limits you describe will still
require much larger IDLs than we currently use. Otherwise we're still
stuck falling back to ranges when the IDL gets full.
I think this bit-mapped approach provides more workable solution than
the range ID solution for the case where IDs in an IDL are rather
contiguous. A 32 bit segment bit map covers 8 entries having
contiguous IDs without increasing storage requirement and with the
ability of pinpointing the exact indexing status of the 8 entries in
the contigous range. On the other hand, the range ID consumes double
the storage, but it cannot pinpoint the indexing status of the
indiviual entries in the range once it is scaled. A 64 bit segment bit
map covers 32 entries having contigous IDs with the same amount of
storage as in the range ID scheme, but it can provide exact indexing
for those 32 entries unlike the range ID approach with scaling.
The bitmap scheme definitely has great appeal. But it only provides a
factor-of-8 increase in range over the current scheme, and that just
isn't enough. Nor do I think that increasing the size definitions of the
IDLs is viable. Whatever size you pick, it will be a hard limit beyond
which performance will be radically degraded (because the IDL is
necessarily converted to a range anyway at that point). Using scaled
ranges as I describe does lose some exactness but it is a much more
graceful degradation, and continues to offer some value no matter how
large the database gets.
Your point about sparseness of e.g. substring indexes is certainly
important. But I believe it's an acceptable tradeoff. In the current
scheme, after a slot gets full (at 64K entries), adding another element
to it converts the whole thing to a range and then all detail is lost.
In the scheme I propose, a slot gets full two times sooner (at 32K
ranges, 32K entries worst case) but rescaling only loses a small amount
of detail. Also it's possible that the IDL will operate at its 32K limit
for a long time without any loss of detail, if the individual ranges
naturally grow to overlap and coalesce.
-- Howard Chu
Chief Architect, Symas Corp. Director, Highland Sun
Symas: Premier OpenSource Development and Support