<html>
<head>
</head>
<body>
Scott, <br>
<br>
Here is a small explanation<br>
<br>
A simple LDIF entry:<br>
<br>
dn: uid=yoel, ou=people, o=xyz.com<br>
objectclass: top<br>
objectclass: person<br>
objectclass: organziationalPerson<br>
objectclass: inetOrgPerson<br>
uid: yoel<br>
cn: yoel<br>
sn: jacobsen<br>
mail: <a class="moz-txt-link-abbreviated" href="mailto:yoel@emet.co.il">yoel@emet.co.il</a><br>
<br>
This is one complete entry. Each entry is composed from multiple key-value
pairs (called the entry's attributes).The name dn stands for 'distinguished
name' and it is actually the key of the entire entry in the LDAP directory.
It is actually the path of the enrtry in the LDAP hierarchy meaning that
uid=yoel (this entry) is placed under a branch point named ou=people placed
under a root entry named o=xyz.com.<br>
<br>
In real life, entries are much more complicated. In my case, each entry
is composed of about 40 such key-value pairs and such big entries should
be compared. <br>
<br>
My python program (and future squeak program!) compares complete entries.
It finds if the path changed, if an attribute name or value changed or if
the entry does not exists at all. Since I need to find the match entry in
the destination database for each entry of the source database, I need to
place these database somewhere. I don't want to search the destination database
linearly for every source entry. This will not use a lot of memory but will
take forever. This is why I wanted to build a memory or disk based database
which maps each dn to the complete pre parsed entry<br>
<br>
Please complete your educated analysis from here.<br>
<br>
Scott A Crosby wrote:<br>
<blockquote type="cite" cite="mid:Pine.LNX.4.33.0201291250150.12007-100000@qwe3.math.cmu.edu">
<pre wrap="">On Tue, 29 Jan 2002, Yoel Jacobsen wrote:<br><br></pre>
<blockquote type="cite">
<pre wrap="">We suspected that the migration process had mistakes (in the analysis<br>and implementation). We wanted to compare the current and old LDAP<br>directories.<br><br></pre>
</blockquote>
<pre wrap=""><!----><br>There seem to be at least a few algorithms-related errors made.<br><br></pre>
<blockquote type="cite">
<pre wrap="">What I did with Python<br>================<br>After I realized that analyzing it in memory is impractical (I had a<br>machine with 4GB of RAM for this and it was not enough for holding the<br>two databases 'in the air'), I was using Berkeley DB for storing databases.<br><br></pre>
</blockquote>
<pre wrap=""><!----><br>What is the average size (in bytes) of an entry. What is the average<br>size(in bytes) of the value (non-key) part of an entry?<br><br>If you can fit it in $100 of RAM, you're probably in better shape spending<br>the $100 then fooling with it for a day or two. FOr something like this,<br>you should be able to store it in less RAM than a textfile representation<br>itself would need. One trick: Make sure duplicate keys are only held<br>once in RAM. If both keys and values are duplicated a lot, you can save a<br>lot more. (I'd need a realistic data sample to judge.)<br><br>So, make sure that that *isn't* possible.<br><br></pre>
<blockquote type="cite">
<pre wrap="">The algorithm in general:<br> 1. Make a database from the two 18M lines LDIF files (resulting in<br>about 800MB database files). What I did here is to create an<br>LDAPObject instance (see attached squeak file) and store it serialized<br>with it's DN as the key.<br></pre>
</blockquote>
<pre wrap=""><!----><br>Make sure the DN's are not random attributs and not uncorrelated between<br>the datasets. When serializing data like this, serialize it based on some<br>semi-unique key within the data. Say, by 'name' or 'email'.<br><br>Do this for both datasets, then, they'll be in roughly the same order.<br><br>Then you can stream data from both files, cache any entry that you haven't<br>used in RAM, and as soon as you find a match, 'forget' about both entries.<br>(and write a log-line indicating the match). Now you're basically doing<br>optimized LCS-style matching. Squeak never needs to remember anything<br>except the additions/differences between both datasets.<br><br></pre>
<blockquote type="cite">
<pre wrap=""> 2. For each entry in the source, find the entry in the destination.<br>If not exists - report and try with the next entry<br></pre>
</blockquote>
<pre wrap=""><!----><br>Object persistence doesn't help you one whit. If you actually are going to<br>run out of memory, and your cache hit rate is low. You're going to take a<br>20ms disk-hit doing a lookup on each entry, which comes out at 3 hours<br>worth of disk latency. (20ms * 500k)<br><br>Nothing is going to stop that.<br><br>You might as well load em into memory and let the OS swapping daemon do<br>that for you.<br><br>Which is why you should not be focussing on persistence, which won't help.<br>Instead try to work on how to avoid that. Either with more RAM or better<br>algorithms.<br><br></pre>
<blockquote type="cite">
<pre wrap="">My Squeak tests<br>============<br><br>Parsing 10K lines took me about 12 minutes in which the image was<br>working on this as a single task. Profiling shoes the time is mostly<br>spent on adding to collections.<br><br></pre>
</blockquote>
<pre wrap=""><!----><br>Which part of collection? :)<br><br>Care to offer a bet that it was spending 90% of its time doing<br>String>>hash or String>>=? :)<br><br>With an extra 16 bytes/string, that can be dropped by about 80-98%, and<br>allow sharing.<br><br>Ah, when building the data, String>>, is very expensive when doing<br>multiple concatenations, try String>>streamContents:<br>for building. That may be where you got the 120 seconds from.<br><br><br></pre>
<blockquote type="cite">
<pre wrap="">Questions<br>=========<br>0. Any good idea about how to make it practical for 450K entries (18M<br>lines)? What should I use for persistence?<br></pre>
</blockquote>
<pre wrap=""><!----><br>Avoid disk-based persistence when it won't help. There's nothing magical<br>about it making random key lookups any faster.<br><br>Scott<br><br><br><br><br></pre>
</blockquote>
<br>
</body>
</html>