Extent Allocation
MediumGreedy · Oracle
A tablespace is made of datafiles, listed in datafiles as [file_id, free_bytes] in their fixed scan order. Segments ask for space one request at a time; requests lists [segment_id, bytes] in the order they arrive.
Allocation is first fit: for each request, scan the datafiles from the start of the list and take the first one whose current free space is at least bytes. Subtract bytes from that file's free space (it stays in its position in the list). If no file has enough space, the request fails and nothing changes.
Return one row per request, in order: [segment_id, file_id] for a successful allocation, or [segment_id, "NONE"] if it failed.
Both lists can have up to 10^5 entries, so scanning every file for every request is too slow in the worst case.
Example 1
- Input:
- datafiles = [["users01", 40], ["users02", 100], ["users03", 70]], requests = [["s1", 50], ["s2", 30], ["s3", 60], ["s4", 75], ["s5", 10]]
- Output:
- [["s1", "users02"], ["s2", "users01"], ["s3", "users03"], ["s4", "NONE"], ["s5", "users01"]]
- Explanation
s1skipsusers01(40 free) and takes 50 fromusers02, leaving 50.s2fits inusers01(40 to 10).s3needs 60, more thanusers01(10) andusers02(50) have, so it goes tousers03, leaving 10. Nothing has 75 left, sos4fails.s5fits inusers01again.
Example 2
- Input:
- datafiles = [["f1", 5]], requests = [["a", 5], ["b", 1]]
- Output:
- [["a", "f1"], ["b", "NONE"]]
- Explanation
auses all 5 bytes off1, leaving 0, sobfails.
Example 3
- Input:
- datafiles = [], requests = [["x", 1]]
- Output:
- [["x", "NONE"]]
- Explanation
- With no datafiles every request fails.
Constraints
- 0 ≤ datafiles.length, requests.length ≤ 105
- 0 ≤ free_bytes ≤ 109
- 1 ≤ bytes ≤ 109
- File ids are distinct strings and never equal
"NONE"; segment ids are strings.