[ovs-dev] [PATCH v5 3/4] ovsdb-idl: idl compound indexes implementation

[Rodriguez Betancourt, Esteban]

Hello,
The UUID comparison was added to guarantee that always rows with the same keys are 
sorted in the same way (between executions of a command, for example). Before that we
 used the pointer comparison (which gives us some randomness in sorting) but we kept it
to be really really sure that we are deleting/inserting the correct row.

The row sync effectively was intended for finding the correct row to delete when there are duplicated "index keys" and there are
deletions/updates/inserts (note that the updates are really handled as a delete-and-reinsert).

We copied ovsdb_idl_index_read from ovsdb_idl_read because we were concerned of what would happen if somebody
access the indexes when a transaction is being made. If the index read the new values instead of the old one then
the rows could be lost/wrongly sorted, etc. It is the same story with ovsdb_idl_index_write_() and index_set: we 
wanted the indexes to behave correctly during a transaction with new changes.

ovsdb_idl_index_{find,forward_to} are used inside the autogenerated functions for iterating over the indexes.
We thought that it would be nice to be able to say things like:

OVSREC_EXAMPLE_FOR_EACH_RANGE(row, cursor, start, end) /* [start, end] */
OVSREC_EXAMPLE_FOR_EACH_RANGE(row, cursor, NULL, end) /* [0, end] */
OVSREC_EXAMPLE_FOR_EACH_RANGE(row, cursor, start, NULL) /* [start, "+infty"] */
OVSREC_EXAMPLE_FOR_EACH_RANGE(row, cursor, NULL, NULL) /* everything */

Regards,
Esteban

-----Original Message-----
From: Lance Richardson [mailto:lrichard at redhat.com] 
Sent: jueves, 13 de julio de 2017 14:29
To: Ben Pfaff <blp at ovn.org>
Cc: dev at openvswitch.org; Rodriguez Betancourt, Esteban <estebarb at hpe.com>; Albornoz, Javier <javier.albornoz at hpe.com>; jorge sauma <jorge.sauma at hpe.com>; Lutz, Arnoldo <arnoldo.lutz.guevara at hpe.com>
Subject: Re: [ovs-dev] [PATCH v5 3/4] ovsdb-idl: idl compound indexes implementation



----- Original Message -----
> From: "Ben Pfaff" <blp at ovn.org>
> To: "Lance Richardson" <lrichard at redhat.com>
> Cc: dev at openvswitch.org, estebarb at hpe.com, "javier albornoz" <javier.albornoz at hpe.com>, "jorge sauma"
> <jorge.sauma at hpe.com>, "arnoldo lutz guevara" 
> <arnoldo.lutz.guevara at hpe.com>
> Sent: Tuesday, 11 July, 2017 5:05:32 PM
> Subject: Re: [ovs-dev] [PATCH v5 3/4] ovsdb-idl: idl compound indexes 
> implementation
> 
> On Sat, Jun 24, 2017 at 05:01:51PM -0400, Lance Richardson wrote:
> > This patch adds support for the creation of multicolumn indexes in 
> > the C IDL to enable for efficient search and retrieval of database 
> > rows by key.
> > 
> > Signed-off-by: Esteban Rodriguez Betancourt <estebarb at hpe.com>
> > Co-authored-by: Lance Richardson <lrichard at redhat.com>
> > Signed-off-by: Lance Richardson <lrichard at redhat.com>
> > ---
> >   v5: - Coding style fixes (checkpatch.py)
> >       - Fixed memory leak (missing ovsdb_datum_destroy() in
> >         ovsdb_idl_index_destroy_row__()).
> >       - Some polishing of comment and log message text.
> 
> Thanks for reviving this series.
> 
> I don't understand ovsdb_idl_index_read().  It is almost the same as 
> ovsdb_idl_read().  It looks like ovsdb_idl_read() could be implemented 
> as a wrapper around it, but I'm also not sure why ovsdb_idl_read() 
> can't be used directly.  Also, I don't understand its comment about 
> "index_set functions", since there are no functions with index_set in their names.

Hi Ben,

I neglected to respond to the comment about "index_set functions" in my previous response, these are automatically generated for the IDL by the next patch. I had deleted that comment in v6 of this series (which is in the ml archive but not patchwork for some reason), it didn't seem useful to me.

> 
> ovsdb_idl_index_write_() is mostly copy-paste of a part of 
> ovsdb_idl_txn_write__(), so to avoid code duplication it would be best 
> to factor that code out of ovsdb_idl_txn_write__() and call it from 
> both places.
> 
> I don't understand the behavior of ovsdb_idl_index_find() and
> ovsdb_idl_index_forward_to() for a null 'value' argument.  Is there 
> some idiomatic usage where the null and nonnull behaviors work out nicely?
> 
> The row_sync behavior is confusing.  I remember it slightly from the 
> previous iteration but I don't remember being convinced it was the 
> best way to do things.
> 

The "row_sync" stuff seems to be a matter of using additional keys (row uuid values first, then memory addresses) when inserting or deleting a row in order to handle duplicate keys.

This still seems a bit strange, but after thinking about it a bit I believe it is a reasonable approach; these extra keys aren't used when searching, so we will always get the first entry in the list when there are multiple rows with the same key, and when inserting/deleting we still get O(log N) performance when there are many entries with identical keys by searching on the UUID value.

But "row_sync" isn't at all useful in figuring out the above, nor are any of the comments in this area.

I also wonder if the comparison on memory address is needed... is there any real possibility that two rows in a table will have the same UUID?

Do you think reworking the "row_sync" name and adding better comments would be an acceptable way forward here?

Thanks,

   Lance


> Thanks,
> 
> Ben.
>