Native parallel batch indexing with shuffle

[jihoonson]

Motivation

General motivation for native batch indexing is described in #5543.

We now have the parallel index task, but it doesn't support perfect rollup yet because of lack of the shuffle system.

Proposed changes

I would propose to add a new mode for parallel index task which supports perfect rollup with two-phase shuffle.

Two phase partitioning with shuffle

Phase 1: each task partitions data by segmentGranularity and then by hash or range key of some dimensions.

Phase 2: each task reads a set of partitions created by the tasks of Phase 1 and creates a segment per partition.

PartitionsSpec support for IndexTask and ParallelIndexTask

PartitionsSpec is the way to define the secondary partitioning and is currently being used by HadoopIndexTask. This interface should be adjusted to be more general as below.

public interface PartitionsSpec
{
  @Nullable
  Integer getNumShards();
  
  @Nullable
  Integer getMaxRowsPerSegment(); // or getTargetRowsPerSegment()
  
  @Nullable
  List<String> getPartitionDimensions();
}

Hadoop tasks can use an extended interface which is more specialized for Hadoop.

public interface HadoopPartitionsSpec extends PartitionsSpec
{
  Jobby getPartitionJob(HadoopDruidIndexerConfig config);
  boolean isAssumeGrouped();
  boolean isDeterminingPartitions();
}

IndexTask currently provides duplicate configurations for partitioning in its tuningConfig such as maxRowsPerSegment, maxTotalRows, numShards, and partitionDimensions. These configurations will be deprecated and the indexTask will support PartitionsSpec instead.

To support maxRowsPerSegment and maxTotalRows, a new partitionsSpec could be introduced.

/**
 * PartitionsSpec for best-effort rollup
 */
public class DynamicPartitionsSpec implements PartitionsSpec
{
  private final int maxRowsPerSegment;
  private final int maxTotalRows;
}

This partitionsSpec will be supported as a new configuration in the tuningConfig of IndexTask and ParallelIndexTask.

New parallel index task runner to support secondary partitioning

ParallelIndexSupervisorTask is the supervisor task which orchestrates the parallel ingestion. It's responsible for spawning and monitoring sub tasks, and publishing created segments at the end of ingestion.

It uses ParallelIndexTaskRunner to run single-phase parallel ingestion without shuffle. To support two-phase ingestion, we can add a new implementation of ParallelIndexTaskRunner, TwoPhaseParallelIndexTaskRunner. ParallelIndexSupervisorTask will choose the new runner if partitionsSpec in tuningConfig is HashedPartitionsSpec or RangePartitionsSpec.

This new taskRunner does the followings:

• Add TwoPhasesParallelIndexTaskRunner as a new runner for the supervisor task
  • Spawns tasks for determining partitions (if numShards is missing in tuningConfig)
  • Spawns tasks for building partial segments (phase 1)
  • When all tasks of the phase 1 finish, spawns new tasks for building the complete segments (phase 2)
  • Each Phase 2 task is assigned one or multiple partitions
    • The assigned partition is represented as an HTTP URL
• Publish the segments reported by phase 2 tasks.
• Triggers intermediary data cleanup when the supervisor task is finished regardless of its last status.

The supervisor task provides an additional configuration in its tuningConfig, i.e., numSecondPhaseTasks or inputRowsPerSecondPhaseTask, to support control of parallelism of the phase 2. This will be improved to automatically determine the optimal parallelism in the future.

New sub task types

Partition determine task

• Similar to what indexTask or HadoopIndexTask do.
• Scan the whole input data and collect HyperLogLog per interval to compute approximate cardinality.
• numShards could be computed as below:

        numShards = (int) Math.ceil(
            (double) numRows / Preconditions.checkNotNull(maxRowsPerSegment, "maxRowsPerSegment")
        );

Phase 1 task

• Read data via the given firehose
• Partition data by segmentGranularity by hash or range (and aggregates if rollup)
• Should be able to access by (supervisorTaskId, timeChunk, partitionId)
• Write partitioned segments in local disk. Multiple disks can be configured, and each task would write partitions in a round-robin manner to utilize disk bandwidth efficiently

Phase 2 task

• Download all partial segments from middleManagers where phase 1 tasks ran.
• Merge all fetched segments into a single segment per partitionId.
• Push the merged segments and report them to the supervisor task.

MiddleManager as Intermediary data server

MiddleManager (and new Indexer) should be responsible for serving intermediary data during shuffle.

Each phase 1 task partitions input data and generates partitioned segments. These partitioned segments are stored in local disk of middleManager (or indexer proposed in #7900). The partitioned segment location would be /configured/prefix/supervisorTaskId/ directory. The same configurations with StorageLocationConfig would be provided for intermediary segment location.

MiddleManagers and indexers would clean up intermediary segments using the below mechanism.

• MM will keep expiration time in memory. This expiration time is initialized with current time + configured timeout.
• MM periodically checks there are any new partitions created for new supervisorTasks and initializes the expiration time if it finds any.
• When a subtask accesses a partition, the expiration time for the supervisorTask is initialized or updated if it's already there.
• MM periodically checks those expiration times for supervisorTasks. If it finds any expired supervisorTask, then it will ask the overlord if the task is still running. If not, MM will remove all partitions for the supervisorTask.
• The overlord will also send a cleanup request to MM when the supervisorTask is finished. This will clean up the expiration time.

New API lists of MiddleManager

• GET /druid/worker/v1/shuffle/tasks/{supervisorTaskId}/partition?start={startTimeOfSegment}&end={endTimeOfSegment}&partitionId={partitionId}

Return all partial segments generated by sub tasks of the given supervisor task, falling in the given interval, and having the given partitionId.

• DELETE /druid/worker/v1/shuffle/tasks/{supervisorTaskId}

Removes all partial segments generated by sub tasks of the given supervisor task.

New metrics & task reports

• ingest/task/time: how long each task took
• ingest/task/bytes/processed: how large data each task processed
• ingest/shuffle/bytes: how large data each middleManager served
• ingest/shuffle/requests: how many requests each middleManager served

Task failure handling

Task failure handling is same with the current behavior.

• If the supervisorTask process is killed normally, stopGracefully method is called which kills all running subtasks. If it's killed abnormally, then parallel index task doesn't handle this case for now.
• SupervisorTask monitors subtask statuses and counts how many subtasks have failed to process the same input. If it notices more failures than configured maxRetry, it regards that input can't be processed and exists with an error. Otherwise, it respawns a new task which processes the same input.

Rationale

There could be two alternate designs for the shuffle system, especially for intermediary data server.

MiddleManager (or indexer) as intermediary data server is the simplest design. In an alternative design, phase 1 tasks could serve intermediary data for shuffle. In this alternate, phase 1 tasks should be guaranteed to run until the phase 2 is finished, which means task 1 resources should be held until the phase 2 is finished. This is rejected for better resource utilization.

Another alternate is a single set of tasks would process both phase 1 and phase 2. This design is rejected because it's not very flexible to use cluster resource efficiently.

Operational impact

maxRowsPerSegment, numShards, partitionDimensions, and maxTotalRows in tuningConfig will be deprecated for indexTask. partitionsSpec will be provided instead. The deprecated values will be removed in the next major release after the upcoming one.

Test plan

Unit tests and integration tests will be implemented. I will also test this with our internal cluster once it's ready.

Future work

• The optimal parallelism for the phase 2 should be able to be determined automatically by collecting statistics during the phase 1.
• To avoid "too many open files" problem, middleManager should be able to smoosh the intermediary segments into several large files.
• If rollup is set, it could be better to combine intermediate data in middleManager before sending them. It would be similar to Hadoop's combiner.
  • This could be implemented to support seamless incremental segment merge in middleManager.
• In Phase 1, tasks might skip index generation for faster shuffle. In this case, Phase 2 tasks should be able to generate the complete indexes.

[himanshug]

SGTM in general

When the supervisor task is finished (either succeeded or failed), the overlord sends cleanup requests with supervisorTaskId to all middleManagers (and indexers)

does overlord treat "supervisor" task as special task to be able to initiate cleanup requests? what if the MM is down temporarily or is cleanup fails for some reason ? In addition to overlord cleanup requests, It might be good for middleManagers to periodically check whether "supervisor" task is running or not and do the self cleanup.
also maybe have some MM level configuration around maximum disk space that can be utilized for intermediary data.

The supervisor task provides an additional configuration in its tuningConfig, i.e., numSecondPhaseTasks or inputRowsPerSecondPhaseTask, to support control of parallelism of the phase 2. This will be improved to automatically determine the optimal parallelism in the future.

I think a user defined upper limit could always exist in all "supervisor" tasks that spawn extra tasks so that user can plan worker capacity knowing how many tasks at a maximum would be running via parallel [shuffle] task.

[jihoonson]

@himanshug thanks for taking a look!

does overlord treat "supervisor" task as special task to be able to initiate cleanup requests? what if the MM is down temporarily or if cleanup fails for some reason ? In addition to overlord cleanup requests, It might be good for middleManagers to periodically check whether "supervisor" task is running or not and do the self cleanup.

Ah this is a good point. To handle middleManager failure, a sort of self-cleanup can be triggered when some amount of time is elapsed since the last access to any partition for a supervisorTask. Does this sound good?

also maybe have some MM level configuration around maximum disk space that can be utilized for intermediary data.

Thanks for reminding me of this. Forgot to add it to the proposal. I'm thinking to use the existing StorageLocationConfig for this. To fully utilize the disk bandwidth, the partitions of the same supervisorTaskId will be assigned in a round-robin fashion. Will update the proposal shortly.

I think a user defined upper limit could always exist in all "supervisor" tasks that spawn extra tasks so that user can plan worker capacity knowing how many tasks at a maximum would be running via parallel [shuffle] task.

This is already supported with maxNumSubTasks (https://druid.apache.org/docs/latest/ingestion/native_tasks.html#tuningconfig). maxNumSubTasks is to limit the total number of subtasks at any time while a parallel index task is running. numSecondPhaseTasks is somewhat different. It's the total number of phase 2 tasks and the supervisor task will regard the phase 2 is succeeded once numSecondPhaseTasks phase 2 tasks are succeeded.

[himanshug]

To handle middleManager failure, a sort of self-cleanup can be triggered when some amount of time is elapsed since the last access to any partition for a supervisorTask. Does this sound good?

anything is good as long as data is not left behind forever in error scenarios :) , that said it might be more work to track access time of the partition...

• are you planning on using the OS managed file access time ? note that many FS are configured to not update access time on reads due to associated IO overhead
• are you planning to track access time in MM memory ? what happens if MM process gets restarted for some reason and then it will lose track of that.
  I was imagining a simpler world where MM just periodically scans directories where partition files could be stored, accumulates a list of supervisor taskIds(for which some data is stored), makes a call to overlord to get state of all those tasks and then based on state(failed,completed etc) returned deletes data for those. that said, anything is fine really.

it would be extra nice to document the failure cases and expected behavior e.g.

• supervisor task process (or MM running it) crashed while phase1/2 tasks were running
• one or more of phase1 tasks crashed
• one or more of phase2 tasks crashed
  will we try to recover in some of those cases? for example if one or more phase1/2 tasks crashed, will supervisor task retry them ?are any/all of these tasks restorable i.e. return true for canRestore() ?

it is not necessary for things to be recoverable as most of this would be iterated upon later but we can just document what to expect in such failure scenarios.

[jihoonson]

does overlord treat "supervisor" task as special task to be able to initiate cleanup requests?

Oh, BTW, there's nothing special with supervisorTasks. I'm thinking to add a callback system to indexing service, like some callback functions can be executed at some predefined stage, e.g., after segments are published or some tasks are finished.

[jihoonson]

are you planning to track access time in MM memory ? what happens if MM process gets restarted for some reason and then it will lose track of that.

Yes, this is what I'm thinking. What I'm thinking is pretty similar to yours, but a bit additional stuffs.

• MM will keep expiration time in memory.
• This expiration time is initialized with current time + configured timeout.
• MM periodically checks there are any new partitions created for new supervisorTasks and initializes the expiration time if it finds any.
• When a subtask accesses a partition, the expiration time for the supervisorTask is initialized or updated if it's already there.
• MM periodically checks those expiration times for supervisorTasks. If it finds any expired supervisorTask, then it will ask the overlord if the task is still running. If not, MM will remove all partitions for the supervisorTask.
• The overlord will also send a cleanup request to MM when the supervisorTask is finished. This will clean up the expiration time.

I think it's not very complex, but will reduce the number of calls to overlord API, so it would be good.

it would be extra nice to document the failure cases and expected behavior e.g.

Ah, I didn't document them since it would be same with the existing parallel index task behavior.
Here are descriptions on how it handles failures currently.

supervisor task process (or MM running it) crashed while phase1/2 tasks were running

If the supervisorTask process is killed normally, stopGracefully method is called which kills all running subtasks. If it's killed abnormally, then parallel index task doesn't handle this case for now.

one or more of phase1/2 tasks crashed

SupervisorTask monitors subtask statuses and counts how many subtasks have failed to process the same input. If it notices more failures than configured maxRetry, it regards that input can't be processed and exists with an error. Otherwise, it respawns a new task which processes the same input.

I'll add these to the proposal.

are any/all of these tasks restorable i.e. return true for canRestore() ?

Good point. Any task is not restorable now, but I think it might be useful to support rolling update in the future. Parallel index tasks are supposed to run for a long time and so it would be nice if it can be stopped/restored during rolling update.

[himanshug]

thanks for the explanations.

I think it's not very complex, but will reduce the number of calls to overlord API, so it would be good.

that is fine and I am guessing it will batch task status call i.e. ask status of multiple supervisor tasks in one overlord api request.

If supervisorTask killed abnormally, then parallel index task doesn't handle this case for now.

will the worker tasks complete and exit eventually or they will be left running till manual intervention ?

we might consider making supervisor real "supervisor" like Kakfa instead of "task" so that they get special powers to manage things better ? but I think I am remembering some comment that they are made tasks because tasks are better equipped to work with locking framework available. one option could be to let spawned worker task do the locking , since all worker tasks would be in same group so multiple worker tasks trying to obtain same lock would still work..... this is unverified wishful thinking :)

[jihoonson]

that is fine and I am guessing it will batch task status call i.e. ask status of multiple supervisor tasks in one overlord api request.

Correct.

will the worker tasks complete and exit eventually or they will be left running till manual intervention ?

All subtasks report the pushed segments to the supervisor task at the end of indexing. So, if the supervisor task is not running, then they would end up being failed at this stage. However, this is still quite annoying since they will occupy middleManager resources unnecessarily. I guess we could add some health check to subtasks for the supervisor task.

we might consider making supervisor real "supervisor" like Kafka instead of "task" so that they get special powers to manage things better ? but I think I am remembering some comment that they are made tasks because tasks are better equipped to work with locking framework available. one option could be to let spawned worker task do the locking , since all worker tasks would be in same group so multiple worker tasks trying to obtain same lock would still work..... this is unverified wishful thinking :)

Yeah, my original intention was to add a "supervisor" like Kafka rather than a new task type, but I changed my mind to use the existing task lock type system. And now I'm inclined to keep the current design of supervisor task because

• "supervisor" is designed for more like stream ingestion for each dataSource. It runs forever once it's submitted and the history of its spec changes is recorded in metadata store.
• "supervisor" design is less scalable since the overlord handles all supervisors and requests/responses for their tasks. One of our customers already had some issue with this. They were running more than 1000 tasks for each Kafka supervisor. Kafka ingestion got stuck because their overlord couldn't handle too many HTTP requests from tasks in time.

For the second reason, I would upvote to even demote the Kafka/Kinesis supervisor to the supervisor task.

[himanshug]

thanks , that reasoning about supervisors makes sense.

I guess we could add some health check to subtasks for the supervisor task.

for their early termination, yes .

[jihoonson]

Thanks! I updated the proposal to include things discussed.