Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>With replication you could have: - one copy of your data structure (list w/ binary search, the interval tree mentioned, ..) (say, the "original" one) that is used only for the lookup (read-access). - A second copy, the "update" one, is created when the data is to be altered (write access). So the write is made to the update copy.</p> <p>Once writing completes, change some "current"-pointer from the "original" to the "update" version. Involving an access-counter to the "original" copy, this one can be destroyed when the counter decremented back to zero readers.</p> <p>In pseudo-code:</p> <pre><code>// read: data = get4Read(); ... do the lookup release4Read(data); // write data = get4Write(); ... alter the data release4Write(data); // implementation: // current is the datat structure + a 'readers' counter, initially set to '0' get4Read() { lock(current_lock) { // exclusive access to current current.readers++; // one more reader return current; } } release4Read(copy) { lock(current_lock) { // exclusive access to current if(0 == --copy.readers) { // last reader if(copy != current) { // it was the old, "original" one delete(copy); // destroy it } } } } get4Write() { aquire_writelock(update_lock); // blocks concurrent writers! var copy_from = get4Read(); var copy_to = deep_copy(copy_from); copy_to.readers = 0; return copy_to; } release4Write(data) { lock(current_lock) { // exclusive access to current var copy_from = current; current = data; } release4Read(copy_from); release_writelock(update_lock); // next write can come } </code></pre> <p>To complete the answer regarding the actual data structure to use: Given the fixed size of the data-entries (two integer tuple), also being quite small, i would use an array for storage and binary search for the lookup. (An alternative would be a balanced tree mentioned in the comment).</p> <p>Talking about performance: As i understand, the 'address' and 'size' define ranges. Thus, the lookup for a given address being within such a range would involve an addition operation of 'address' + 'size' (for comparison of the queried address with the ranges upper bound) over and over again. It may be more performant to store start- and end-adress explicitely, instead of start-adress and size - to avoid this repeated addition.</p>
    singulars
    1. This table or related slice is empty.
    1. PODesign of a high-performance sorted data structure read by many threads and written by few
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USfast
    1. USfast
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    1. COEven assuming atomic increment/decrement/assignment and proper memory barriers (utterly non-trivial task!) are placed, this (pseudo) code still contain a race - it's possible to access deleted data and/or delete data twice. Besides being incorrect, this approach is not scalable - `readers` is a shared location, written by *all* threads. Copying the entire structure is also dubious approach - compare the effort to copy a tree with a few thousand nodes on each update to the effort to perform a few tens (number of cores) of node insertions/deletions on each update.
      singulars
      1. PO
      1. USchill
    2. CO@chill: Where do you see the need to place any 'memory barriers'? - With propper use if the get..() and release..() functions, where do you see the problems to access deleted data or multiple deletion? Using an array w/ bin-search, for 100k entries there are just ~1.5MB of data - affordable for occasional copy, i think..
      singulars
      1. PO
      1. USfast
    3. COplease, check the answer below, the space here is too small to explain.
      singulars
      1. PO
      1. USchill
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload