On Tue, Jul 02, 2002 at 11:26:49AM +0200, Ralf Hildebrandt wrote:

| On Tue, Jul 02, 2002 at 04:15:48AM -0500, Phil Howard wrote:
|
| > Accessing one large map is faster than accessing one smaller map? If
| > that's true, then I'll add a million dummy entries to make it faster.
|
| I was not talking about adding garbage to the map.
|
| > Actually, the performance of accessing the map isn't the reason I want
| > to split by domain. It's a maintenance issue. Suppose there are 1000
| > domains with an average of 500 users each. The program that generates
| > the maps when there is a change would be exposed to 1000 times more
| > updates, and have 1000 times more work to do, each time a change is
| > made. That's O(N^2) for N = number of domains. Then there is the
| > issue of maintenance permission per domain. I need to leave open the
| > possibility that different domains will be managed by different user
| > access permissions. That might become part of the design.
|
| Valid point. But why not use a map instead that does NOT require
| rebuilding (like LDAP!)

I don't want to add the administrative complexity of having yet another
server with all of its permissions and access schemes to make sure that
different administrators can only administer the subset of data they are
allowed to. While I am certain LDAP implementations can do that, it is
my experience that these things add a new complex layer of management
control to achieve it. I'm trying to keep it simple.

| Looking up something in one btree:
| O(n) = ln(n) (well, sort of)
|
| Looking up something in x btrees of size (n/x):
|
| O(n) = x*ln(n/x)
| which is bigger than ln(n)

What is x? I think you are making the same mistake Victor did and are
trying to sequentially search each map separately. Such a search can't
even work since a map per-domain should have only the user part as the
key. So looking for fooexample.com by searching for foo in example.com
would be right, but what would you search for when searching the map for
example.org? foo? You might find foo in example.org, but it's the wrong
foo. And what if you are searching for fooexample.org but found it first
in the map for example.com?

Just search ONE map, the one for the appropriate domain. Then we're
doing 1*ln(n/x) ... times whatever it takes for the filesystem to
find that map ... which makes it ln(n/x)+ln(x) ... or ln(max(n/x,x))
as far as big-O is concerned.

Then you can also symlink one domain to another at the maps. With the
user part by itself as the key, this would work.

-- 
-----------------------------------------------------------------
| Phil Howard - KA9WGN |   Dallas   | http://linuxhomepage.com/ |
| phil-nospamipal.net | Texas, USA | http://phil.ipal.org/     |
-----------------------------------------------------------------
-
To unsubscribe, send mail to majordomopostfix.org with content
(not subject): unsubscribe postfix-users

• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]