Module: Familia::Features::Relationships::Indexing::RecordKeyOwnership

Defined in:
lib/familia/features/relationships/indexing/record_key_ownership.rb

Overview

Decides which record a key belongs to when several records of one Horreum class can claim it.

Record keys are "", and an identifier may itself contain the delimiter. So one key can parse as keys of several records, and a key under the bucket prefix of a multi_index can be another record's set field or bucket. The multi_index rebuild and audit use this module so that they leave such a key to the record it belongs to.

A record exists when its hash key holds a hash (see .existing_records). The methods that take a list of keys check the candidate records of their keys in pipelines that each hold at most MAX_CANDIDATE_BATCH_BYTES of identifiers, and a key with no candidate costs no command.

Constant Summary collapse

MAX_CANDIDATE_SPLITS =

The most candidate records checked for one key.

A candidate is a split of the key at a delimiter where the part after it is a set key name (see .candidate_split_offsets). An ordinary key has none. A key has one for each record whose identifier is a prefix of the key followed by such a name, and records nest like that rarely more than once or twice. A field value can repeat "" any number of times, though, and each candidate costs a copy of its identifier (up to the length of the key) and a TYPE command. This cap bounds the work for one key at that many copies and commands. A key with more candidates gets TOO_MANY_CANDIDATES instead of an owner.

8
TOO_MANY_CANDIDATES =

Returned in place of an owner for a key with more than MAX_CANDIDATE_SPLITS candidates, whose owner is not checked. The multi_index rebuild raises Familia::IndexBucketConflictError with this reason for such a key, and the multi_index audit reports it.

:too_many_candidate_owners
MAX_CANDIDATE_BATCH_BYTES =

The most bytes of record identifiers checked in one pipeline.

MAX_CANDIDATE_SPLITS bounds the candidates of one key, but the rebuild and audits pass keys in slices, and each candidate identifier can be as long as its key. The candidates of the keys in a slice are therefore checked in groups: a group is sent once adding the next key's candidates would pass this many bytes. .existing_records splits the identifiers of a group the same way, so an identifier longer than this is checked in a pipeline of its own.

1_048_576

Class Method Summary collapse

Class Method Details

.byte_bounded_groups(items) {|item| ... } ⇒ Array<Array>

Splits +items+ into consecutive groups whose sizes, as the block returns them, add up to at most MAX_CANDIDATE_BATCH_BYTES. An item larger than that forms a group of its own.

Parameters:

  • items (Array)

Yield Parameters:

  • item (Object)

Yield Returns:

  • (Integer) —

    the size of +item+ in bytes

Returns:

  • (Array<Array>)


98
99
100
101
102
103
104
105
106
107
108
109
110
111
# File 'lib/familia/features/relationships/indexing/record_key_ownership.rb', line 98

def byte_bounded_groups(items)
  groups = []
  group_bytes = 0
  items.each do |item|
    bytes = yield(item)
    if groups.empty? || group_bytes + bytes > MAX_CANDIDATE_BATCH_BYTES
      groups << []
      group_bytes = 0
    end
    groups.last << item
    group_bytes += bytes
  end
  groups
end

.bytes_after_prefix(key, prefix) ⇒ Object

Returns the bytes of +key+ after the binary +prefix+, or nil when +key+ does not start with it.



313
314
315
316
317
318
# File 'lib/familia/features/relationships/indexing/record_key_ownership.rb', line 313

def bytes_after_prefix(key, prefix)
  bkey = key.b
  return nil unless bkey.start_with?(prefix)

  bkey.byteslice(prefix.bytesize..)
end

.candidate_split_offsets(rest, delim, names, longer_than) ⇒ Object

Returns the splits of the binary string +rest+ (a key without the record prefix) whose identifier is longer than +longer_than+ bytes and whose name is a set key name from +names+ (see .record_set_key_names): a set field's name that ends the key, or an index name followed by the delimiter and a value (a bucket). A split is the offset of its delimiter in +rest+, which is also the length of its identifier, and the offsets are in increasing order. Returns TOO_MANY_CANDIDATES when there are more than MAX_CANDIDATE_SPLITS.

An index name that ends the key makes no candidate. That is the key the factories name for a blank value (see MultiIndexGenerators.bucket_key_prefix), which is not index data of the scope it names: no multi_index method of that scope reads or writes it. When it is a set field of the same name, the field names already make it a candidate. Otherwise it stays with the owner whose bucket prefix it starts with, if any: a shorter scope, or the class for a class-level index.

The walk copies no part of +rest+. A set field name must be the whole rest of the key, so each field is compared at the one offset where it would start. An index name is searched for with String#index.



355
356
357
358
359
360
# File 'lib/familia/features/relationships/indexing/record_key_ownership.rb', line 355

def candidate_split_offsets(rest, delim, names, longer_than)
  offsets = field_split_offsets(rest, delim, names[:fields], longer_than)
  return TOO_MANY_CANDIDATES unless index_split_offsets(rest, delim, names[:indexes], longer_than, offsets)

  offsets.sort
end

.class_level_bucket?(key, owner_class) ⇒ Boolean

Whether +key+ is "" for a class-level multi_index declared on +owner_class+. Only the key's shape is checked, so the key may also be a key of a record whose identifier starts with "".

Parameters:

  • key (String)
  • owner_class (Class)

Returns:

  • (Boolean)


291
292
293
294
295
296
297
# File 'lib/familia/features/relationships/indexing/record_key_ownership.rb', line 291

def class_level_bucket?(key, owner_class)
  rest = key_after_record_prefix(key, owner_class)
  return false unless rest

  delim = Familia.delim.to_s.b
  class_level_index_names(owner_class).any? { |index| rest.start_with?(index + delim) }
end

.class_level_index_names(owner_class) ⇒ Array<String>

Names of the class-level multi_indexes declared on +owner_class+, whose buckets live under its record prefix, as binary strings.

Parameters:

  • owner_class (Class)

Returns:

  • (Array<String>)


326
327
328
329
330
# File 'lib/familia/features/relationships/indexing/record_key_ownership.rb', line 326

def class_level_index_names(owner_class)
  Familia.multi_indexes(class_level: true, owner: owner_class).map do |descriptor|
    descriptor.index_name.to_s.b
  end
end

.existing_records(owner_class, identifiers) ⇒ Array<Boolean>

Returns, for each of +identifiers+, whether a record of +owner_class+ with that identifier exists: whether its hash key holds a hash (Familia::Horreum::OBJECT_KEY_TYPE).

EXISTS is not enough. A multi_index bucket whose field value equals the class suffix sits at the hash key of a record named after the index: the bucket "customer:role_index:object" is a set, and no record "role_index" exists.

The TYPE commands go out in pipelines of at most MAX_CANDIDATE_BATCH_BYTES of identifiers each (one identifier longer than that gets a pipeline of its own). The hash keys are built from bytes, so an identifier with invalid UTF-8 does not raise Encoding::CompatibilityError against a prefix with non-ASCII characters.

Parameters:

  • owner_class (Class) —

    the Horreum class of the records

  • identifiers (Array<String>) —

    record identifiers

Returns:

  • (Array<Boolean>) —

    one flag per identifier, in order



79
80
81
82
83
84
85
86
87
88
# File 'lib/familia/features/relationships/indexing/record_key_ownership.rb', line 79

def existing_records(owner_class, identifiers)
  flags = []
  byte_bounded_groups(identifiers) { |identifier| identifier.to_s.bytesize }.each do |group|
    types = owner_class.dbclient.pipelined do |pipe|
      group.each { |identifier| pipe.type(record_hash_key(owner_class, identifier)) }
    end
    flags.concat(types.map { |type| type == Familia::Horreum::OBJECT_KEY_TYPE })
  end
  flags
end

.field_split_offsets(rest, delim, fields, longer_than) ⇒ Object

Offsets in +rest+ of the delimiter before a set field name that ends the key, after +longer_than+ bytes.



364
365
366
367
368
369
370
# File 'lib/familia/features/relationships/indexing/record_key_ownership.rb', line 364

def field_split_offsets(rest, delim, fields, longer_than)
  fields.filter_map do |field|
    split_at = rest.bytesize - field.bytesize - delim.bytesize
    split_at if split_at > longer_than &&
                rest.byteslice(split_at, delim.bytesize + field.bytesize) == delim + field
  end.uniq
end

.index_bucket_owner(key, owner_class, names: nil) ⇒ Class, ...

Returns the owner of +key+ when it is a multi_index bucket under the record prefix of +owner_class+, nil when it is not, or TOO_MANY_CANDIDATES.

The owner is +owner_class+ for a bucket of a class-level multi_index declared on +owner_class+ (""). For a bucket of an instance-scoped multi_index within +owner_class+ ("") it is the scope identifier, and only when a record with that identifier exists. When several splits of +key+ name existing scopes, the longest identifier wins, as in .other_record_key.

The audits of related fields and participation collections match "*" and read the part the wildcard matched as a record identifier. A field value equal to puts a bucket in that pattern, so they call this method to leave such a key to the index it belongs to. The multi_index audit and repair own buckets.

Parameters:

  • key (String) —

    a key returned by SCAN

  • owner_class (Class) —

    the Horreum class whose record prefix the key starts with

  • names (Hash) (defaults to: nil) —

    .record_set_key_names of +owner_class+, passed by callers that check many keys

Returns:

  • (Class, String, Symbol, nil)


242
243
244
# File 'lib/familia/features/relationships/indexing/record_key_ownership.rb', line 242

def index_bucket_owner(key, owner_class, names: nil)
  index_bucket_owners([key], owner_class, names: names).first
end

.index_bucket_owners(keys, owner_class, names: nil) ⇒ Array<Class, String, Symbol, nil>

.index_bucket_owner for each of +keys+. The candidate scopes are checked in pipelines of at most MAX_CANDIDATE_BATCH_BYTES (see .resolve_candidates).

Parameters:

  • keys (Array<String>)
  • owner_class (Class)
  • names (Hash, nil) (defaults to: nil)

Returns:

  • (Array<Class, String, Symbol, nil>) —

    one entry per key, in order



255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
# File 'lib/familia/features/relationships/indexing/record_key_ownership.rb', line 255

def index_bucket_owners(keys, owner_class, names: nil)
  names ||= record_set_key_names(owner_class)
  delim = Familia.delim.to_s.b
  prefix = record_prefix(owner_class)
  class_level = class_level_index_names(owner_class)
  # Only index names make a split a candidate here. The question
  # is whether the key is a bucket, and a set field of a scope
  # record is that record's own key, not a bucket of any index.
  bucket_names = { fields: [], indexes: names[:indexes] }
  owners = Array.new(keys.size)
  scopes = resolve_candidates(owner_class, keys, prefix.bytesize, delim) do |key, idx|
    rest = bytes_after_prefix(key, prefix)
    next nil unless rest

    if class_level.any? { |index| rest.start_with?(index + delim) }
      owners[idx] = owner_class
      next nil
    end
    candidate_split_offsets(rest, delim, bucket_names, 0)
  end
  owners.each_with_index.map do |owner, idx|
    next owner if owner

    scope = scopes[idx]
    scope.is_a?(Array) ? scope.first : scope
  end
end

.index_split_offsets(rest, delim, indexes, longer_than, offsets) ⇒ Object

Adds to +offsets+ the offsets in +rest+ of the delimiter before an index name that is followed by the delimiter, after +longer_than+ bytes. Returns false as soon as +offsets+ holds more than MAX_CANDIDATE_SPLITS, true otherwise.



376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
# File 'lib/familia/features/relationships/indexing/record_key_ownership.rb', line 376

def index_split_offsets(rest, delim, indexes, longer_than, offsets)
  indexes.each do |index|
    needle = delim + index
    position = longer_than + 1
    while (split_at = rest.index(needle, position))
      after = split_at + needle.bytesize
      if rest.byteslice(after, delim.bytesize) == delim && !offsets.include?(split_at)
        offsets << split_at
        return false if offsets.size > MAX_CANDIDATE_SPLITS
      end
      position = split_at + 1
    end
  end
  offsets.size <= MAX_CANDIDATE_SPLITS
end

.key_after_record_prefix(key, owner_class) ⇒ Object

Returns the bytes of +key+ after "" of +owner_class+, or nil when +key+ does not start with them.



301
302
303
# File 'lib/familia/features/relationships/indexing/record_key_ownership.rb', line 301

def key_after_record_prefix(key, owner_class)
  bytes_after_prefix(key, record_prefix(owner_class))
end

.other_record_key(key, owner_class, own_identifier, names: nil) ⇒ Array(String, String), ...

Returns [identifier, name] when +key+ is the key +name+ of an existing record of +owner_class+ whose identifier is longer than +own_identifier+, nil when there is none, or TOO_MANY_CANDIDATES.

Record keys are "", and an identifier may itself contain the delimiter. So one key can parse as keys of several records. With records "c-9" and "c-9:dept_index", the key "company:c-9:dept_index:tags" is both a dept_index bucket of "c-9" and the +tags+ set of "c-9:dept_index". A split of +key+ at a delimiter names a record when the part after it is the name of a set field of the class or the bucket of an instance-scoped multi_index within the class, and a record with the identifier before it exists (see .existing_records).

Such a key is assigned to the existing record with the longest identifier. A class-level bucket has no identifier, so any existing record wins over it. The rule gives each key one owner, so the rebuilds of two scopes whose keys overlap do not both clear it, and the audit reads it for the scope whose rebuild clears it. The doc of Familia::Horreum.extract_identifier_from_key says "This is safe for compound identifiers that contain the delimiter character". This module assumes that a field value holding the delimiter followed by an index name is rarer than such an identifier, so it prefers the longest identifier.

Parameters:

  • key (String) —

    a key under +owner_class+'s record prefix

  • owner_class (Class) —

    the Horreum class of the records

  • own_identifier (String, nil) —

    identifier of the record the key is checked for, or nil for a class-level bucket

  • names (Hash) (defaults to: nil) —

    .record_set_key_names of +owner_class+

Returns:

  • (Array(String, String), Symbol, nil)


190
191
192
# File 'lib/familia/features/relationships/indexing/record_key_ownership.rb', line 190

def other_record_key(key, owner_class, own_identifier, names: nil)
  other_record_keys([key], owner_class, [own_identifier], names: names).first
end

.other_record_key_owner(key, owner, names: nil) ⇒ String, ...

Returns the hash key of the existing record, other than +owner+, that .other_record_key assigns +key+ to, nil when there is none, or TOO_MANY_CANDIDATES.

Parameters:

  • key (String) —

    a key under +owner+'s bucket prefix

  • owner (Familia::Horreum, Class) —

    the scope instance, or the indexed class for a class-level index

  • names (Hash) (defaults to: nil) —

    .record_set_key_names of +owner+'s class, passed by callers that check many keys

Returns:

  • (String, Symbol, nil)


134
135
136
# File 'lib/familia/features/relationships/indexing/record_key_ownership.rb', line 134

def other_record_key_owner(key, owner, names: nil)
  other_record_key_owners([key], owner, names: names).first
end

.other_record_key_owners(keys, owner, names: nil) ⇒ Array<String, Symbol, nil>

.other_record_key_owner for each of +keys+. The candidates are checked in pipelines of at most MAX_CANDIDATE_BATCH_BYTES (see .resolve_candidates).

Parameters:

  • keys (Array<String>)
  • owner (Familia::Horreum, Class)
  • names (Hash, nil) (defaults to: nil)

Returns:

  • (Array<String, Symbol, nil>) —

    one entry per key, in order



146
147
148
149
150
151
152
153
154
155
# File 'lib/familia/features/relationships/indexing/record_key_ownership.rb', line 146

def other_record_key_owners(keys, owner, names: nil)
  owner_class = owner_class_of(owner)
  own_identifier = owner.is_a?(Class) ? nil : owner.identifier
  records = other_record_keys(keys, owner_class, Array.new(keys.size, own_identifier), names: names)
  keys.zip(records).map do |key, record|
    next record unless record.is_a?(Array)

    record_hash_key(owner_class, record.first).force_encoding(key.encoding)
  end
end

.other_record_keys(keys, owner_class, own_identifiers, names: nil) ⇒ Array<Array(String, String), Symbol, nil>

.other_record_key for each of +keys+, with the matching entry of +own_identifiers+. The candidates are checked in pipelines of at most MAX_CANDIDATE_BATCH_BYTES (see .resolve_candidates).

Parameters:

  • keys (Array<String>)
  • owner_class (Class)
  • own_identifiers (Array<String, nil>) —

    one per key

  • names (Hash, nil) (defaults to: nil)

Returns:

  • (Array<Array(String, String), Symbol, nil>) —

    one entry per key, in order



204
205
206
207
208
209
210
211
212
213
214
# File 'lib/familia/features/relationships/indexing/record_key_ownership.rb', line 204

def other_record_keys(keys, owner_class, own_identifiers, names: nil)
  names ||= record_set_key_names(owner_class)
  delim = Familia.delim.to_s.b
  prefix = record_prefix(owner_class)
  resolve_candidates(owner_class, keys, prefix.bytesize, delim) do |key, idx|
    rest = bytes_after_prefix(key, prefix)
    next nil unless rest

    candidate_split_offsets(rest, delim, names, own_identifiers[idx].to_s.bytesize)
  end
end

.owner_class_of(owner) ⇒ Object

Returns the Horreum class whose records share key space with the buckets of +owner+: the scope class, or the indexed class itself for a class-level index.



468
469
470
# File 'lib/familia/features/relationships/indexing/record_key_ownership.rb', line 468

def owner_class_of(owner)
  owner.is_a?(Class) ? owner : owner.class
end

.record_hash_key(owner_class, identifier) ⇒ String

Returns the hash key of the record of +owner_class+ with +identifier+, as a binary String built from the bytes of its parts.

Parameters:

  • owner_class (Class)
  • identifier (String)

Returns:

  • (String)


120
121
122
# File 'lib/familia/features/relationships/indexing/record_key_ownership.rb', line 120

def record_hash_key(owner_class, identifier)
  record_prefix(owner_class) << identifier.to_s.b << Familia.delim.to_s.b << owner_class.suffix.to_s.b
end

.record_prefix(owner_class) ⇒ Object

Returns "" of +owner_class+ as a new binary String.



307
308
309
# File 'lib/familia/features/relationships/indexing/record_key_ownership.rb', line 307

def record_prefix(owner_class)
  Familia.join(owner_class.prefix, '').b
end

.record_set_key_names(owner) ⇒ Hash{Symbol => Array<String>}

Names that follow "" in the keys of a record of +owner_class+ that hold a set: the related set fields, and the instance-scoped multi_index names whose buckets live under the record.

The fields are read from related_fields_snapshot, so a field declared in another thread meanwhile does not make MRI raise "can't add a new key into hash during iteration".

Parameters:

Returns:

  • (Hash{Symbol => Array<String>}) —

    :fields and :indexes, as binary strings



484
485
486
487
488
489
490
491
492
493
494
495
496
# File 'lib/familia/features/relationships/indexing/record_key_ownership.rb', line 484

def record_set_key_names(owner)
  owner_class = owner_class_of(owner)
  fields = owner_class.related_fields_snapshot.each_value.filter_map do |definition|
    next if definition.opts[:dbkey]
    next unless definition.klass.is_a?(Class) && definition.klass <= Familia::UnsortedSet

    definition.name.to_s.b
  end
  indexes = Familia.multi_indexes(class_level: false).filter_map do |descriptor|
    descriptor.index_name.to_s.b if descriptor.scope_class == owner_class
  end
  { fields: fields, indexes: indexes }
end

.resolve_candidates(owner_class, keys, prefix_bytes, delim) {|key, idx| ... } ⇒ Array<Array(String, String), Symbol, nil>

Resolves the candidate splits of each of +keys+ to the one with the longest identifier of an existing record. The block returns the offsets of a key's candidate splits in the part of the key after its first +prefix_bytes+ bytes (see .candidate_split_offsets), TOO_MANY_CANDIDATES, or nil for a key that is not under the prefix.

The block runs for one key at a time, and only the offsets are kept. The identifiers are copied out of the key when their group is checked. A group is checked once adding the next key's candidates would pass MAX_CANDIDATE_BATCH_BYTES of identifiers, so the copies and the pipeline for one group stay within that many bytes, or within one key's candidates when they alone pass it. The identifier and name are returned in the encoding Familia.normalize_key_encoding gives each one's bytes (see .resolve_pending_candidates).

Parameters:

  • prefix_bytes (Integer) —

    bytesize of the record prefix

Yield Parameters:

  • key (String)
  • idx (Integer)

Yield Returns:

  • (Array<Integer>, Symbol, nil)

Returns:

  • (Array<Array(String, String), Symbol, nil>)


414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
# File 'lib/familia/features/relationships/indexing/record_key_ownership.rb', line 414

def resolve_candidates(owner_class, keys, prefix_bytes, delim)
  results = Array.new(keys.size)
  pending = []
  pending_bytes = 0
  keys.each_with_index do |key, idx|
    offsets = yield(key, idx)
    next results[idx] = offsets if offsets == TOO_MANY_CANDIDATES
    next if offsets.nil? || offsets.empty?

    bytes = offsets.sum
    if !pending.empty? && pending_bytes + bytes > MAX_CANDIDATE_BATCH_BYTES
      resolve_pending_candidates(owner_class, pending, prefix_bytes, delim, results)
      pending_bytes = 0
    end
    pending << [idx, key, offsets]
    pending_bytes += bytes
  end
  resolve_pending_candidates(owner_class, pending, prefix_bytes, delim, results) unless pending.empty?
  results
end

.resolve_pending_candidates(owner_class, pending, prefix_bytes, delim, results) ⇒ Object

Checks the candidates of the +pending+ [idx, key, offsets] entries with one call to .existing_records, stores each key's [identifier, name] or nil in +results+, and empties +pending+. The identifier and name are byte slices of the key, each in the encoding Familia.normalize_key_encoding gives its own bytes. The key is BINARY when any of its parts is not valid UTF-8, and the multi_index audit compares the identifier with the members of the scope class's instances and the value in the name with the indexed field's value, so a valid part must not keep the label of an invalid one.



445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
# File 'lib/familia/features/relationships/indexing/record_key_ownership.rb', line 445

def resolve_pending_candidates(owner_class, pending, prefix_bytes, delim, results)
  identifiers = pending.flat_map do |(_idx, key, offsets)|
    offsets.map { |split_at| key.byteslice(prefix_bytes, split_at) }
  end
  flags = existing_records(owner_class, identifiers)
  position = 0
  pending.each do |(idx, key, offsets)|
    last = flags[position, offsets.size].rindex(true)
    if last
      split_at = offsets[last]
      results[idx] = [
        Familia.normalize_key_encoding(identifiers[position + last]),
        Familia.normalize_key_encoding(key.byteslice((prefix_bytes + split_at + delim.bytesize)..)),
      ]
    end
    position += offsets.size
  end
  pending.clear
end