Refactored and enhanced the consolidation algorithm by stavrospapadopoulos · Pull Request #1101 · TileDB-Inc/TileDB

stavrospapadopoulos · 2018-12-26T16:44:00Z

Closes #52

jakebolewski · 2018-12-27T14:39:27Z

+``[1,2], [1,4]``. Observe that, if those four fragments were to
+be consolidated, the cells of the second and third fragment
+would be completely overwritten from the cells of the
+fourth fragment. Therefore, the existence of those two fragments


Two therefores in a row in copy

jakebolewski · 2018-12-27T14:43:32Z

+  be considered for consolidation.
+
+- The third criterion is the fragment *amplification factor*, applicable to
+  the case where the fragment subset fo be consolidated contains at least


"fo" -> "to"

jakebolewski · 2018-12-27T14:52:23Z

+                                                                      during consolidation.
+    ``"sm.consolidation.step_max_frags"``     ``"4294967295"``        The maximum number of fragments to consolidate in
+                                                                      a single step.
+    ``"sm.consolidation.step_min_frags"``     ``"4294967295"``        The minimum number of fragments to consolidate in


shouldn't the default be 2?

This is up for discussion. There are no defaults that can simulate the current consolidation algorithm (i.e., force-consolidate all), as there may be scenarios that fragments are not "consolidatable". In that case, a default of 2 will attempt to consolidate at least 2 fragments. Is that desirable?

jakebolewski · 2018-12-27T14:53:24Z

+                                                                      a single step.
+    ``"sm.consolidation.step_min_frags"``     ``"4294967295"``        The minimum number of fragments to consolidate in
+                                                                      a single step.
+    ``"sm.consolidation.step_size_ratio"``    ``"0"``                 The size ratio that two ("adjacent") fragments


Doesn't this mean the default config params cause consolidation to immediately terminate doing nothing?

The algorithm permits two fragments to be consolidated if their ratio (always min / max) is larger than sm.consolidation.step_size_ratio. I'll clarify in the docs.

jakebolewski · 2018-12-27T14:53:58Z

+    ``"sm.consolidation.step_size_ratio"``    ``"0"``                 The size ratio that two ("adjacent") fragments
+                                                                      must satisfy to be considered for consolidation in
+                                                                      a single step.
+    ``"sm.consolidation.steps"``              ``"4294967295"``        The number of consolidation steps to be performed


shouldn't this be 1 or a small number?

Again, this is up for discussion. A huge number means that consolidation will proceed recursively until there is a single fragment, or if there is no next fragment subset that is "consolidatable".

jakebolewski · 2018-12-27T15:30:42Z

  // Delete old fragment metadata. This makes the old fragments invisible
-  st = delete_old_fragment_metadata(old_fragment_uris);
+  st = delete_fragment_metadata(to_delete);
  if (!st.ok()) {


If deleting the fragment metadata fails, shouldn't the behavior be to not delete the fragment data? It seems like the array could quickly get in an inconsistent state if this operation fails.

It might be cleaner to delete fragment metadata + fragments at a time, that way the errors are correlated with data loss.

This one is tricky. Regardless of whether or not you delete the fragment data (after the fragment metadata deletion fails), the fragments whose metadata you did delete will not be visible to the read algorithm. The best idea would be to copy the fragment metadata in a temporary location, such that they can be recovered if this function fails. I would suggest we merge this PR and open a separate issue for this (i.e., on robustness/resilience), as testing will add complexity and more development time for this issue (which is already pretty large).

jakebolewski · 2018-12-27T15:47:17Z

+  return Status::Ok();
+}
+
+Status StorageManager::get_fragment_info(


Should we check the on-disk format version of the array here?

No, I don't think so, as this depends on format agnostic parameters. However, retrieving the timestamp from the fragment URI will have to be refactored when we swap the UUID and timestamp in a separate issue.

the format defines the binary layout + on disk organization, the two are coupled

Still I am not sure I understand why we would have to handle the format version here. We are not doing any parsing of the binary files in this function.

Well the filename example is something that will cause a format number increment (so that we can keep reading old arrays). So @jakebolewski might be correct that some checks should be added here, even though the binary format is not touched.

Regarding the fragment folder name format, this will be revisited when we swap the UUID with the timestamp. So we will put the necessary checks then. Right now, there is no violation of backwards compatibility.

jakebolewski · 2018-12-27T15:48:13Z

-    if (!open_array->fragment_metadata_exists(frag_uri) &&
-        frag_timestamp <= timestamp) {
+    auto metadata = open_array->fragment_metadata(frag_uri);
+    if (metadata == nullptr) {  // Fragment metadata does not exist - load it


check the on-disk format version here?

I think that any format-specific stuff will be handled directly by FragmentMetadata. Now, if we change completely the format to drop fragment metadata as a whole, we will need to revisit this (but let's punt for now).

jakebolewski · 2018-12-27T15:48:53Z

  return vfs_->move_dir(old_uri, new_uri);
 }

+Status StorageManager::get_fragment_info(


Should we check the on-disk format version of the array here?

Same as above, I don't think so for now.

jakebolewski · 2018-12-27T15:53:06Z

+      // fragment sets in the middle of the timeline may get consolidated,
+      // which will hinder the next step of consolidation (which will
+      // select some small and some big fragments).
+      if (min_size == UINT64_MAX || m[i][j] < (min_size / 1.25)) {


should we document that the consolidation algorithm biases older fragments?

Why are older fragments a good metric to bias? Given no domain overlap information each fragment would assume to contribute equally to degradation in read performance.

Great catch - I was sure you were going to see that. :)

This is to prevent a subtle but important case, which I encountered when I was performing some perf analysis locally. Suppose that you have 10 fragments, each of roughly equal size. I am saying roughly, because even if you write the exact same number of cells in each fragment, if you use compression the actual fragment sizes may be slightly different.

Suppose also that we consolidate 5 at a time. if the algorithm chooses to consolidate 2-6 first, then the algorithm will next choose 1, 2-6, 7, 8, 9 into 1-9 (or 2-6, 7, 8, 9,10 into 2-10), and then 1-9, 10. Observe the imbalance. The ideal scenario would have been 1-5, 6-10 and then 1-5, 6-10. This condition biases towards "alignment", rather than "old" fragments.

tdenniston · 2018-12-27T21:08:38Z

+    class T,
+    typename std::enable_if<!std::is_integral<T>::value, T>::type* = nullptr>
+uint64_t cell_num(const T* rect, unsigned dim_num) {
+  assert(false);


What is the point of implementing this function? There is no definition generated for cell_num if T is non-integral, so I believe it would be already be a compile time error if you tried e.g. cell_num<float>(...)

This is called in Consolidator::are_consolidatable, which applies to all T (integral and real). It takes proper care if all fragments are sparse (the only case where the domain might be real, as this is only applicable to sparse arrays). Therefore, the definition for non-integrals is needed. In general, a real domain can only be determined at run-time, so we need to provide function definitions for non-integral T in several places, but throw asserts to make sure the code never invokes them. I am open to alternatives if any, but let's address in a separate PR as this is not specific to consolidation (and may appear in other places as well).

tdenniston · 2018-12-27T21:59:06Z

+
+  // Check the encryption key. Note we always pass true for cache hit by
+  // definition of reopening an array.
+  auto st = check_array_encryption_key(


This status is not checked! You can reopen an array with an arbitrary encryption key with this bug.

tdenniston · 2018-12-27T22:04:03Z

+    RETURN_NOT_OK(vfs_->dir_size(uri.second, &size));
+
+    // Get fragment non-empty domain
+    auto metadata =


Don't need new and delete for this local object -- can just do FragmentMetadata metadata(...); to stack allocate.

tdenniston · 2018-12-27T22:05:54Z

+  return Status::Ok();
+}
+
+Status StorageManager::get_fragment_info(


Well the filename example is something that will cause a format number increment (so that we can keep reading old arrays). So @jakebolewski might be correct that some checks should be added here, even though the binary format is not touched.

tdenniston · 2018-12-27T22:06:17Z

+  RETURN_NOT_OK(vfs_->is_file(coords_uri, &sparse));
+
+  // Get fragment non-empty domain
+  auto metadata =


You should stack allocate this object as in the previous case.

tdenniston · 2018-12-27T22:34:27Z

+    return true;
+
+  // Check overlap of union with earlier fragments
+  for (int i = 0; i <= (int)start - 1; ++i) {


You can just do size_t i and i < start

tdenniston · 2018-12-27T22:37:05Z

+  auto domain_size = 2 * array_schema->coords_size();
+
+  // Allocate memory for union of non-empty domains of fragments to consolidate
+  auto union_non_empty_domains = (T*)std::malloc(domain_size);


Can we start using either stack allocations or std::unique_ptr<uint8_t> for these ad-hoc allocations? We shouldn't be introducing more malloc/frees than necessary.

tdenniston · 2018-12-27T22:38:24Z

-    storage_manager_->vfs()->remove_dir(new_fragment_uri);
+    bool is_dir;
+    auto st2 = storage_manager_->vfs()->is_dir(*new_fragment_uri, &is_dir);
+    if (is_dir)


st2 also doesn't appear to be checked anywhere here.

tdenniston · 2018-12-27T22:38:34Z

-    storage_manager_->vfs()->remove_dir(new_fragment_uri);
+    clean_up(buffer_num, buffers, buffer_sizes, query_r, query_w);
+    bool is_dir;
+    auto st2 = storage_manager_->vfs()->is_dir(*new_fragment_uri, &is_dir);


st2 not checked

These two places handle a previous error status. Since we do not provide an error stack (yet), checking st2 here is redundant, since we will report only st. However, we need to initialize is_dir to false to properly handle the if command immediately below.

tdenniston · 2018-12-27T22:42:19Z

+      } else if (i + j >= col_num) {  // Non-valid entries
+        m[i][j] = UINT64_MAX;
+      } else {  // Every other row is computed using the previous row
+        auto ratio = (float)fragments[i + (j - 1)].fragment_size_ /


Can this happen when j == 0? In that case we are doing i + (0 - 1).

In this else block, it is always i>0, since the case of i==0 is handled in the first if block above.

What about j? If it can be 0 then it will cause an OOB access into the fragments vector, since size_t is an unsigned type.

Yeah, you are right, the parenthesis there may be problematic. I think that even with overflow this would work (as integers "wrap around"), but I will remove the parenthesis anyway.

…onfigurable.

See TileDB-Inc/TileDB#1101.

stavrospapadopoulos added enhancement API Breakage refactor consolidation labels Dec 26, 2018

stavrospapadopoulos added this to the 1.5.0 milestone Dec 26, 2018

stavrospapadopoulos requested review from jakebolewski and tdenniston December 26, 2018 16:44

stavrospapadopoulos force-pushed the sp/52 branch from 037a723 to a337d7c Compare December 26, 2018 18:51

jakebolewski reviewed Dec 27, 2018

View reviewed changes

tdenniston reviewed Dec 27, 2018

View reviewed changes

stavrospapadopoulos force-pushed the sp/52 branch from bc231c6 to 9385576 Compare December 31, 2018 19:49

Refactored the consolidation algorithm, making it more flexible and c…

c9e57a4

…onfigurable.

stavrospapadopoulos force-pushed the sp/52 branch from 9385576 to c9e57a4 Compare December 31, 2018 21:35

stavrospapadopoulos merged commit fafd337 into dev Dec 31, 2018

stavrospapadopoulos deleted the sp/52 branch December 31, 2018 22:15

tdenniston added a commit to TileDB-Inc/TileDB-Java that referenced this pull request Jan 17, 2019

Update Array consolidation methods for new API.

2aae250

See TileDB-Inc/TileDB#1101.

tdenniston mentioned this pull request Jan 17, 2019

Update Array consolidation methods for new API. TileDB-Inc/TileDB-Java#104

Merged

tdenniston mentioned this pull request Mar 12, 2019

Consolidation performance on large arrays #1028

Closed

stavrospapadopoulos mentioned this pull request Mar 12, 2019

Consolidation hangs with KV map with many flushes #1029

Closed

Conversation

stavrospapadopoulos commented Dec 26, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

stavrospapadopoulos Dec 31, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

stavrospapadopoulos Dec 31, 2018 •

edited

Loading