You are viewing a plain text version of this content. The canonical link for it is here.
Posted to notifications@couchdb.apache.org by jaydoane <gi...@git.apache.org> on 2016/07/16 00:06:06 UTC
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
GitHub user jaydoane opened a pull request:
https://github.com/apache/couchdb-couch/pull/185
3061 adaptive header search
The current find_header algorithm performs one file read per block,
which can be inefficient when the most recent header is buried deeply in
a large file.
With default config params, this change essentially keeps current
behavior, reading each block into memory one at a time until a header is
found, or beginning of file is reached. However, by setting new config
params, it's possible to exponentially increase the number of blocks
read into a "chunk" of memory with a single read, up to a configurable
limit.
For example, the following settings begin with a chunk size of one
block, and then double in size each additional search step backward to a
maximum limit of 16GB:
[couchdb]
chunk_max_size = 4096*4096
chunk_exponent_base = 2
Measurements for a 12GB .couch.meta file with its last header at 4GB
shows a speed improvement of from 17x (server) to 27x (laptop).
COUCHDB-3061
You can merge this pull request into a Git repository by running:
$ git pull https://github.com/cloudant/couchdb-couch 3061-adaptive-header-search
Alternatively you can review and apply these changes as the patch at:
https://github.com/apache/couchdb-couch/pull/185.patch
To close this pull request, make a commit to your master/trunk branch
with (at least) the following in the commit message:
This closes #185
----
commit 1c3db513a029351af6af26b4dd1da1f72f978789
Author: Jay Doane <ja...@gmail.com>
Date: 2016-07-14T02:05:56Z
Rename function and variables:
- Drop "calculate_" prefix since all functions perform calculations
- Change "_len" to "_size" for better consistency
- Change TotalBytes to TotalSize for better consistency
commit abf1e76fa996327bb52ac038b3d4520662cbab15
Author: Jay Doane <ja...@gmail.com>
Date: 2016-07-15T23:29:02Z
Implement adaptive header search
The current find_header algorithm performs one file read per block,
which can be inefficient when the most recent header is buried deeply in
a large file.
With default config params, this change essentially keeps current
behavior, reading each block into memory one at a time until a header is
found, or beginning of file is reached. However, by setting new config
params, it's possible to exponentially increase the number of blocks
read into a "chunk" of memory with a single read, up to a configurable
limit.
For example, the following settings begin with a chunk size of one
block, and then double in size each additional search step backward to a
maximum limit of 16GB:
[couchdb]
chunk_max_size = 4096*4096
chunk_exponent_base = 2
Measurements for a 12GB .couch.meta file with its last header at 4GB
shows a speed improvement of from 17x (server) to 27x (laptop).
COUCHDB-3061
----
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r81775716
--- Diff: src/couch_file.erl ---
@@ -524,34 +529,83 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
-find_header(_Fd, -1) ->
- no_valid_header;
find_header(Fd, Block) ->
case (catch load_header(Fd, Block)) of
{ok, Bin} ->
{ok, Bin};
_Error ->
- find_header(Fd, Block -1)
+ ReadCount = config:get_integer(
+ "couchdb", "find_header_read_count", ?DEFAULT_READ_COUNT),
+ find_header(Fd, Block -1, ReadCount)
end.
load_header(Fd, Block) ->
{ok, <<1, HeaderLen:32/integer, RestBlock/binary>>} =
file:pread(Fd, Block * ?SIZE_BLOCK, ?SIZE_BLOCK),
- TotalBytes = calculate_total_read_len(5, HeaderLen),
- case TotalBytes > byte_size(RestBlock) of
- false ->
- <<RawBin:TotalBytes/binary, _/binary>> = RestBlock;
- true ->
- {ok, Missing} = file:pread(
- Fd, (Block * ?SIZE_BLOCK) + 5 + byte_size(RestBlock),
- TotalBytes - byte_size(RestBlock)),
- RawBin = <<RestBlock/binary, Missing/binary>>
+ load_header(Fd, Block * ?SIZE_BLOCK, HeaderLen, RestBlock).
+
+load_header(Fd, Pos, HeaderLen) ->
+ load_header(Fd, Pos, HeaderLen, <<>>).
+
+load_header(Fd, Pos, HeaderLen, RestBlock) ->
+ TotalBytes = calculate_total_read_len(?PREFIX_SIZE, HeaderLen),
+ RawBin = case TotalBytes =< byte_size(RestBlock) of
+ true ->
+ <<RawBin0:TotalBytes/binary, _/binary>> = RestBlock,
+ RawBin0;
+ false ->
+ ReadStart = Pos + ?PREFIX_SIZE + byte_size(RestBlock),
+ ReadLen = TotalBytes - byte_size(RestBlock),
+ {ok, Missing} = file:pread(Fd, ReadStart, ReadLen),
+ <<RestBlock/binary, Missing/binary>>
end,
<<Md5Sig:16/binary, HeaderBin/binary>> =
- iolist_to_binary(remove_block_prefixes(5, RawBin)),
+ iolist_to_binary(remove_block_prefixes(?PREFIX_SIZE, RawBin)),
Md5Sig = couch_crypto:hash(md5, HeaderBin),
{ok, HeaderBin}.
+
+%% Read multiple block locations using a single file:pread/2.
+-spec find_header(file:fd(), block_id(), non_neg_integer()) ->
+ {ok, binary()} | no_valid_header.
+find_header(_Fd, Block, _ReadCount) when Block < 0 ->
+ no_valid_header;
+find_header(Fd, Block, ReadCount) ->
+ FirstBlock = max(0, Block - ReadCount + 1),
+ BlockLocations = [?SIZE_BLOCK*B || B <- lists:seq(FirstBlock, Block)],
+ {ok, DataL} = file:pread(Fd, [{L, ?PREFIX_SIZE} || L <- BlockLocations]),
+ %% Since BlockLocations are ordered from oldest to newest, we rely
+ %% on lists:foldl/3 to reverse the order, making HeaderLocations
+ %% correctly ordered from newest to oldest.
+ HeaderLocations = lists:foldl(fun
+ ({Loc, <<1, HeaderSize:32/integer>>}, Acc) ->
+ [{Loc, HeaderSize} | Acc];
+ (_, Acc) ->
+ Acc
+ end, [], lists:zip(BlockLocations, DataL)),
+ case find_newest_header(Fd, HeaderLocations) of
+ {ok, _Location, HeaderBin} ->
+ {ok, HeaderBin};
+ _ ->
+ ok = file:advise(
+ Fd, hd(BlockLocations), ReadCount * ?SIZE_BLOCK, dont_need),
+ NextBlock = hd(BlockLocations) div ?SIZE_BLOCK - 1,
+ find_header(Fd, NextBlock, ReadCount)
+ end.
+
+-spec find_newest_header(file:fd(), [{location(), header_size()}]) ->
+ {ok, binary()} | not_found.
+find_newest_header(_Fd, []) ->
+ not_found;
+find_newest_header(Fd, [{Location, Size}|LocationSizes]) ->
--- End diff --
Missing whitespace around the | operator.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r81586171
--- Diff: src/couch_file.erl ---
@@ -531,27 +537,96 @@ find_header(Fd, Block) ->
{ok, Bin} ->
{ok, Bin};
_Error ->
- find_header(Fd, Block -1)
+ find_header_pread2(Fd, Block -1)
end.
load_header(Fd, Block) ->
{ok, <<1, HeaderLen:32/integer, RestBlock/binary>>} =
file:pread(Fd, Block * ?SIZE_BLOCK, ?SIZE_BLOCK),
- TotalBytes = calculate_total_read_len(5, HeaderLen),
- case TotalBytes > byte_size(RestBlock) of
+ TotalSize = total_read_size(5, HeaderLen),
+ case TotalSize > byte_size(RestBlock) of
false ->
- <<RawBin:TotalBytes/binary, _/binary>> = RestBlock;
+ <<RawBin:TotalSize/binary, _/binary>> = RestBlock;
true ->
{ok, Missing} = file:pread(
Fd, (Block * ?SIZE_BLOCK) + 5 + byte_size(RestBlock),
- TotalBytes - byte_size(RestBlock)),
+ TotalSize - byte_size(RestBlock)),
RawBin = <<RestBlock/binary, Missing/binary>>
end,
<<Md5Sig:16/binary, HeaderBin/binary>> =
iolist_to_binary(remove_block_prefixes(5, RawBin)),
Md5Sig = couch_crypto:hash(md5, HeaderBin),
{ok, HeaderBin}.
+
+%% Read a configurable number of block locations at a time using
+%% file:pread/2. At each block location, read ?PREFIX_SIZE (5) bytes;
+%% if the first byte is <<1>>, assume it's a header block, and the
+%% next 4 bytes hold the size of the header.
+-spec find_header_pread2(file:fd(), block_id()) ->
+ {ok, binary()} | no_valid_header.
+find_header_pread2(Fd, Block) ->
+ find_header_pread2(Fd, Block, read_count()).
+
+-spec find_header_pread2(file:fd(), block_id(), non_neg_integer()) ->
+ {ok, binary()} | no_valid_header.
+find_header_pread2(_Fd, Block, _ReadCount) when Block < 0 ->
+ no_valid_header;
+find_header_pread2(Fd, Block, ReadCount) ->
+ Locations = block_locations(Block, ReadCount),
+ {ok, DataL} = file:pread(Fd, [{L, ?PREFIX_SIZE} || L <- Locations]),
+ case locate_header(Fd, header_locations(Locations, DataL)) of
+ {ok, _Location, HeaderBin} ->
+ io:format("header at block ~p~n", [_Location div ?SIZE_BLOCK]), % TEMP
+ {ok, HeaderBin};
+ _ ->
+ ok = file:advise(
+ Fd, hd(Locations), ReadCount * ?SIZE_BLOCK, dont_need),
+ NextBlock = hd(Locations) div ?SIZE_BLOCK - 1,
+ find_header_pread2(Fd, NextBlock, ReadCount)
+ end.
+
+-spec read_count() -> non_neg_integer().
+read_count() ->
+ config:get_integer("couchdb", "find_header_read_count", ?DEFAULT_READ_COUNT).
+
+-spec block_locations(block_id(), non_neg_integer()) -> [location()].
+block_locations(Block, ReadCount) ->
+ First = max(0, Block - ReadCount + 1),
+ [?SIZE_BLOCK*B || B <- lists:seq(First, Block)].
+
+-spec header_locations([location()], [data()]) -> [{location(), header_size()}].
+header_locations(Locations, DataL) ->
+ lists:foldl(fun
+ ({Loc, <<1, HeaderSize:32/integer>>}, Acc) ->
+ [{Loc, HeaderSize} | Acc];
+ (_, Acc) ->
+ Acc
+ end, [], lists:zip(Locations, DataL)).
+
+-spec locate_header(file:fd(), [{location(), header_size()}]) ->
+ {ok, binary()} | not_found.
+locate_header(_Fd, []) ->
+ not_found;
+locate_header(Fd, [{Location, Size}|LocationSizes]) ->
+ case (catch load_header(Fd, Location, Size)) of
+ {ok, HeaderBin} ->
+ {ok, Location, HeaderBin};
+ _Error ->
+ locate_header(Fd, LocationSizes)
+ end.
+
+-spec load_header(file:fd(), location(), header_size()) ->
+ {ok, binary()} | no_return().
+load_header(Fd, Location, Size) ->
--- End diff --
How about something like this:
```erlang
load_header(Fd, Block) ->
{ok, <<1, HeaderLen:32/integer, RestBlock/binary>>} =
file:pread(Fd, Block * ?SIZE_BLOCK, ?SIZE_BLOCK),
load_header(Fd, Block * ?SIZE_BLOCK, HeaderLen, RestBlock).
load_header(Fd, Pos, HeaderLen) ->
load_header(Fd, Pos, HeaderLen, <<>>).
load_header(Fd, Pos, HeaderLen, RestBlock)
TotalBytes = calculate_total_read_len(?PREFIX_SIZE, HeaderLen),
RawBin = case TotalBytes =< byte_size(RestBlock) of
true->
<<RawBin0:TotalBytes/binary, _/binary>> = RestBlock,
RawBin0;
false ->
ReadStart = Pos + ?PREFIX_SIZE + byte_size(RestBlock),
ReadLen = TotalBytes - byte_size(RestBlock),
{ok, Missing} = file:pread(Fd, ReadStart, ReadLen),
<<RestBlock/binary, Missing/binary>>
end,
<<Md5Sig:16/binary, HeaderBin/binary>> =
iolist_to_binary(remove_block_prefixes(?PREFIX_SIZE, RawBin)),
Md5Sig = couch_crypto:hash(md5, HeaderBin),
{ok, HeaderBin}.
```
Also, for positioning, its fairly standard Erlang style to have the same function name but varying numbers of arguments to be located next to each other in the module since they're usually doing quite similar things. Like in this case they're both loading headers. Having them separate means you have to remember when reading the module that they do slightly different things and which arity version is which. If you think you need two different behaviors in two different places it'd be better to rename them to be more descriptive of their behavior. However this case can be simplified by having one function that services both uses with minor small changes. And they should be all in the same spot in the module since they're all related.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch issue #185: 3061 adaptive header search
Posted by jaydoane <gi...@git.apache.org>.
Github user jaydoane commented on the issue:
https://github.com/apache/couchdb-couch/pull/185
Thank you @davisp for the thorough review! I will address your points in turn:
> the timing numbers reported are in microseconds so I'm not super convinced on them. What size of file are you testing against and how far back is the header
You are correct that my previous example file `foo.couch` was tiny, and the timing numbers were of course too small to be useful. I've updated the sample benchmarks with one of the real .couch.meta files I've been using, and it shows a 17x speed improvement. Other files with deeply buried headers also show a consistently large speedup.
> you've added two exported functions for testing which really shouldn't be in the final PR
I agree. I left those for ease of testing, but they are now removed. Hmm, actually, it looks like they actually may need to be exposed based on the test failures I'm now seeing...
> The way the recursion works having the first iteration in find_last_header before moving to find_header_in_chunks seems wrong. That recursion should just be a single loop that expands its read-ahead starting with the initial values in find_last_header.
"Wrong" might be a bit strong (since it actually worked) but it was certainly _inelegant_. In any case, commit ce91605 eliminated that special case by setting the start position past the eof so it could essentially use the same algorithm for the whole file.
> the default appears to devolve into nearly exactly the same behavior as the current implementation
This was a deliberate decision in order to incur the least possible risk. I assumed we could roll this code out without too much worry and turn it on for selective cluster(s) via configuration. Once we were satisfied that it behaved well in isolation, the defaults could easily be changed to give everyone the adaptive behavior by default.
> it might be beneficial to look at using file:pread/2 which does vectored reads
We're already using `file:pread/2`, but it sounds like you're suggesting a somewhat different algorithm. I'm going to mull your last paragraph over as a possible further refinement, but for now, I think I've addressed your objections to the existing code.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r75903623
--- Diff: src/couch_file.erl ---
@@ -524,6 +528,214 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+find_last_header(Fd, FileSize) ->
+ find_header_in_chunks(Fd, start_pos(FileSize), 1).
+
+start_pos(FileSize) when FileSize rem ?SIZE_BLOCK =:= 0 ->
+ FileSize;
+start_pos(FileSize) ->
+ %% set position to nearest block boundary past eof
+ %% if file size isn't multiple of block size
+ (FileSize div ?SIZE_BLOCK) * ?SIZE_BLOCK + ?SIZE_BLOCK.
+
+chunk_max_size() ->
+ config:get_integer("couchdb", "chunk_max_size", ?DEFAULT_CHUNK_MAX_SIZE).
+
+%% chunk size exponentially increases by iteration, up to some maximum,
+%% and should never exceed the current position in the file
+chunk_size(Pos, Multiplier) ->
+ Size = min(Multiplier * ?SIZE_BLOCK, chunk_max_size()),
+ min(Pos, Size).
+
+multiplier(Size, Multiplier) ->
+ case Size < chunk_max_size() of
+ true ->
+ Multiplier * config:get_integer(
+ "couchdb", "chunk_exponent_base", ?DEFAULT_CHUNK_EXPONENT_BASE);
+ false ->
+ Multiplier
+ end.
+
+find_header_in_chunks(_Fd, Pos, _Multiplier) when Pos < 0 ->
+ no_valid_header;
+find_header_in_chunks(Fd, Pos, Multiplier) ->
+ Size = chunk_size(Pos, Multiplier),
+ case Size > 0 of
+ false ->
+ no_valid_header;
+ true ->
+ {ok, Chunk} = file:pread(Fd, Pos - Size, Size),
+ case find_header_in_chunk(Fd, Pos, Chunk, Size - ?SIZE_BLOCK) of
+ {ok, HeaderBin, _Offset} ->
+ %% io:format("found header at ~p multiplier ~p chunksize ~p~n",
+ %% [Pos - Size + _Offset, Multiplier, Size]),
--- End diff --
Remove debug logging and commented out code in PRs.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch issue #185: 3061 adaptive header search
Posted by jaydoane <gi...@git.apache.org>.
Github user jaydoane commented on the issue:
https://github.com/apache/couchdb-couch/pull/185
The following image adds vmpage_io.memory.in vmpage_io.memory.out to the experiment. All experiments were searching 4 files in parallel. The first starts around 23:48, using the current algorithm, and it is followed around 23:57, 23:59 and 00:03 using vectored reads.
<img width="1244" alt="screen shot 2016-09-21 at 5 06 22 pm" src="https://cloud.githubusercontent.com/assets/51209/18733383/5a83b6e8-801f-11e6-84f1-3a4fc074f9e1.png">
The most notable aspect of the graph to me is the consistently high vmpage_io.memory.in for the vectored read. Just eyeballing the graphs, it looks like the area under the curves for vmpage_io.memory.in are similar for both algorithms, which I think is what @theburge was expecting to see.
As for a more realistic MT scenario, I want to clarify something. It's my understanding that under normal circumstances when opening a couch file, the header is found at the end of the file. In such cases, the existing algorithm will be used (since it's been micro-optimized for this case by reading the entire remainder of the block in a single disk read operation). Only when the existing algorithm fails to find a header do we employ the vectored read algorithm.
The only scenario I know of for which we have deeply buried headers is that of .compact.meta files, and the number of those presumably is limited to the number of simultaneous compactions that occur at any time. My understanding is that concurrency is governed by smoosh, and typical numbers are on the order of 10. If all of those assumptions are true, a realistic scenario probably wouldn't have more than a handful of vectored searches happening at one time on any given node, and so my test case of 4 is not terribly unrealistic.
That said, the image below shows a series of 3 experiments using 8 parallel searches; the first with the current algorithm, and the other 2 using vectored reads. The main thing to note is that the speed improvement drops to "only" 4x the current algorithm.
<img width="1246" alt="screen shot 2016-09-21 at 6 11 04 pm" src="https://cloud.githubusercontent.com/assets/51209/18734223/076489da-8027-11e6-9517-844e741cd40b.png">
@davisp, I'm all for getting this wrapped up. What are some final tweaks you had in mind? Clearly, it should be squashed into a single commit. Are there other problems you'd like to see addressed?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch issue #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on the issue:
https://github.com/apache/couchdb-couch/pull/185
@jaydoane pointed out that its a WIP commit currently so I stopped iterating style points until he's finished.
Also, reading through this its getting complicated pretty quickly between spans and exponents and things. I'd drop all of that and make a much simpler first draft that just reads the last N header positions. Once that's working we can add tweaks to adjust the number of locations that are read dynamically if we find it to be an issue.
Also, the simplification should make the implementation quite easy. Something like:
find_header(Fd, Size) ->
Start = (Size div ?BLOCK_SIZE) * ?BLOCK_SIZE,
Locs = lists:foldl(fun(_, [Last | _] = Acc) ->
[Last - ?BLOCK_SIZE | Acc]
end, Start, lists:seq(1, 1024)),
LocLens = [{Loc, 5} || Loc <- Locs, Loc >= 0],
{ok, Bits} = file:pread(Fd#fd.fd, LocLens),
try
lists:foreach(fun(Data) ->
if Data is a valid header throw({found, Header})
end, Bits) of
ok -> find_header(Fd, hd(Locs))
catch throw:{found, Header} ->
{ok, Header}
end.
Or something to that effect.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch issue #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on the issue:
https://github.com/apache/couchdb-couch/pull/185
+1
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by theburge <gi...@git.apache.org>.
Github user theburge commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r71323695
--- Diff: src/couch_file.erl ---
@@ -524,6 +525,99 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+%% first try to read header at end, falling back to chunked reads on failure
+find_last_header(Fd, FileSize) ->
+ ok = file:advise(Fd, 0, FileSize, dont_need), % minimize disk cache pollution
+ Pos = (FileSize div ?SIZE_BLOCK) * ?SIZE_BLOCK,
+ case file:pread(Fd, Pos, FileSize - Pos) of
+ eof ->
+ no_valid_header;
+ {ok, Data} ->
+ try match_header(Fd, Pos, Data, 0) of
+ {ok, HeaderBin} ->
+ {ok, HeaderBin}
+ catch
+ error:{badmatch, _} ->
+ find_header_in_chunks(Fd, Pos, 1)
+ end
+ end.
+
+-define(DEFAULT_CHUNK_MAX_SIZE, ?SIZE_BLOCK).
+-define(DEFAULT_CHUNK_EXPONENT_BASE, 1).
+
+chunk_max_size() ->
+ config:get_integer("couchdb", "chunk_max_size", ?DEFAULT_CHUNK_MAX_SIZE).
+
+%% chunk size exponentially increases by iteration, up to some maximum,
+%% and should never exceed the current position in the file
+chunk_size(Pos, Multiplier) ->
+ Size = min(Multiplier * ?SIZE_BLOCK, chunk_max_size()),
+ min(Pos, Size).
+
+multiplier(Size, Multiplier) ->
+ case Size < chunk_max_size() of
+ true ->
+ Multiplier * config:get_integer(
+ "couchdb", "chunk_exponent_base", ?DEFAULT_CHUNK_EXPONENT_BASE);
+ false ->
+ Multiplier
+ end.
+
+find_header_in_chunks(_Fd, Pos, _Multiplier) when Pos < 0 ->
+ no_valid_header;
+find_header_in_chunks(Fd, Pos, Multiplier) ->
+ Size = chunk_size(Pos, Multiplier),
+ case Size > 0 of
+ false ->
+ no_valid_header;
+ true ->
+ {ok, Chunk} = file:pread(Fd, Pos - Size, Size),
+ case find_header_in_chunk(Fd, Pos, Chunk, Size) of
+ {ok, HeaderBin, _Offset} ->
+ %% io:format("found header at ~p multiplier ~p chunksize ~p~n",
+ %% [Pos - Size + _Offset, Multiplier, Size]),
+ {ok, HeaderBin};
+ not_found ->
+ NewMultiplier = multiplier(Size, Multiplier),
+ find_header_in_chunks(Fd, Pos - Size, NewMultiplier)
+ end
+ end.
+
+find_header_in_chunk(_Fd, _Pos, _Chunk, Offset) when Offset < 0 ->
--- End diff --
Is that guard correct? Or should it be `=<`?
If `Offset = ?SIZE_BLOCK`, it looks to me that it would attempt the second clause of`find_header_in_chunk` twice, and presumably lead to a badmatch in `match_header`.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r75903000
--- Diff: src/couch_file.erl ---
@@ -524,6 +528,214 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+find_last_header(Fd, FileSize) ->
+ find_header_in_chunks(Fd, start_pos(FileSize), 1).
+
+start_pos(FileSize) when FileSize rem ?SIZE_BLOCK =:= 0 ->
+ FileSize;
--- End diff --
Why not just rely on integer math below as per SOP on these sorts of calculations?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch issue #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on the issue:
https://github.com/apache/couchdb-couch/pull/185
Oh, and we'll want to squash this down into a single commit that has a good explanation of the change and the basics of how it works.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r81774779
--- Diff: src/couch_file.erl ---
@@ -524,34 +529,83 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
-find_header(_Fd, -1) ->
- no_valid_header;
find_header(Fd, Block) ->
case (catch load_header(Fd, Block)) of
{ok, Bin} ->
{ok, Bin};
_Error ->
- find_header(Fd, Block -1)
+ ReadCount = config:get_integer(
+ "couchdb", "find_header_read_count", ?DEFAULT_READ_COUNT),
+ find_header(Fd, Block -1, ReadCount)
end.
load_header(Fd, Block) ->
{ok, <<1, HeaderLen:32/integer, RestBlock/binary>>} =
file:pread(Fd, Block * ?SIZE_BLOCK, ?SIZE_BLOCK),
- TotalBytes = calculate_total_read_len(5, HeaderLen),
- case TotalBytes > byte_size(RestBlock) of
- false ->
- <<RawBin:TotalBytes/binary, _/binary>> = RestBlock;
- true ->
- {ok, Missing} = file:pread(
- Fd, (Block * ?SIZE_BLOCK) + 5 + byte_size(RestBlock),
- TotalBytes - byte_size(RestBlock)),
- RawBin = <<RestBlock/binary, Missing/binary>>
+ load_header(Fd, Block * ?SIZE_BLOCK, HeaderLen, RestBlock).
+
+load_header(Fd, Pos, HeaderLen) ->
+ load_header(Fd, Pos, HeaderLen, <<>>).
+
+load_header(Fd, Pos, HeaderLen, RestBlock) ->
+ TotalBytes = calculate_total_read_len(?PREFIX_SIZE, HeaderLen),
+ RawBin = case TotalBytes =< byte_size(RestBlock) of
+ true ->
+ <<RawBin0:TotalBytes/binary, _/binary>> = RestBlock,
+ RawBin0;
+ false ->
+ ReadStart = Pos + ?PREFIX_SIZE + byte_size(RestBlock),
+ ReadLen = TotalBytes - byte_size(RestBlock),
+ {ok, Missing} = file:pread(Fd, ReadStart, ReadLen),
+ <<RestBlock/binary, Missing/binary>>
end,
<<Md5Sig:16/binary, HeaderBin/binary>> =
- iolist_to_binary(remove_block_prefixes(5, RawBin)),
+ iolist_to_binary(remove_block_prefixes(?PREFIX_SIZE, RawBin)),
Md5Sig = couch_crypto:hash(md5, HeaderBin),
{ok, HeaderBin}.
+
+%% Read multiple block locations using a single file:pread/2.
+-spec find_header(file:fd(), block_id(), non_neg_integer()) ->
+ {ok, binary()} | no_valid_header.
+find_header(_Fd, Block, _ReadCount) when Block < 0 ->
+ no_valid_header;
+find_header(Fd, Block, ReadCount) ->
+ FirstBlock = max(0, Block - ReadCount + 1),
+ BlockLocations = [?SIZE_BLOCK*B || B <- lists:seq(FirstBlock, Block)],
+ {ok, DataL} = file:pread(Fd, [{L, ?PREFIX_SIZE} || L <- BlockLocations]),
+ %% Since BlockLocations are ordered from oldest to newest, we rely
+ %% on lists:foldl/3 to reverse the order, making HeaderLocations
+ %% correctly ordered from newest to oldest.
+ HeaderLocations = lists:foldl(fun
+ ({Loc, <<1, HeaderSize:32/integer>>}, Acc) ->
+ [{Loc, HeaderSize} | Acc];
+ (_, Acc) ->
+ Acc
+ end, [], lists:zip(BlockLocations, DataL)),
--- End diff --
This needs to be dedented one level.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch issue #185: 3061 adaptive header search
Posted by theburge <gi...@git.apache.org>.
Github user theburge commented on the issue:
https://github.com/apache/couchdb-couch/pull/185
@jaydoane Thanks for running and documenting those experiments, I think those results look very promising. Reducing time taken and user-space memory usage can only be good. :)
FWIW, I'm not convinced major faults is the metric of interest for identifying file reads on newly opened file in an empty cache scenario. (My thinking is that it shows faults for explicitly mapped ranges that are only available on-disk; whereas page ins show pages being pulled in for whatever reason via the VM itself. For laughs and demonstration purposes, run `sar -B 1` and try some experiments, like dropping cache and loading a `man` page. You'll typically see page in rate exceed major fault rate, once you do the conversation from pages/s to kB/s. In truth, it's probably most comprehensive to look at both fault types and page in/page out rates, but that gets trickier.)
The big surprise here for me is the difference in physical disk operations, since my understanding would be that the VM would fill complete OS pages to satisfy reads, so I can't see why reading N bytes on page boundaries would be much different (from an OS perspective) to reading 4kB. I'd love an explanation for that (although the user-space benefits are clear to see and very positive), just to be sure it's not some other effect.
My final suggestion would be to evaluate a more serious MT-esque scenario: how does the performance improvement of the new algorithm vary with with lots (10s to 100s) of files opening concurrently? (And maybe with higher background CPU/disk utilisation, if you can set-up the experiment.) Remember that that's the scenario where we see this as most relevant, and timeouts there are a big issue (file opening times out, compaction keels over, file handle remains, etc.), so if there's little or no wall clock time improvement in a highly concurrent setting, that'd be a shame and undermine some of the practical benefit. Obviously, I'd expect only positive things compared to the status quo based on the evaluation above, but performance expectations in varying scenarios don't always comply with common sense... :)
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by theburge <gi...@git.apache.org>.
Github user theburge commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r71321315
--- Diff: src/couch_file.erl ---
@@ -524,6 +525,99 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+%% first try to read header at end, falling back to chunked reads on failure
+find_last_header(Fd, FileSize) ->
+ ok = file:advise(Fd, 0, FileSize, dont_need), % minimize disk cache pollution
--- End diff --
I agree that calling it after use on a single chunk makes sense. FTR, http://man7.org/linux/man-pages/man2/posix_fadvise.2.html adds an additional note:
> Requests to discard partial pages are ignored. It is preferable to
> preserve needed data than discard unneeded data. If the application
> requires that data be considered for discarding, then offset and len
> must be page-aligned.
I don't the notes on dirty pages are significant to this case, I expect it's just pointing out the advisory nature of the call and the fact that unbacked storage won't be flushed by this call (vs. the reasonable expectation that it _does_ flush and obeys the advice).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r75903985
--- Diff: src/couch_file.erl ---
@@ -524,6 +528,214 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+find_last_header(Fd, FileSize) ->
+ find_header_in_chunks(Fd, start_pos(FileSize), 1).
+
+start_pos(FileSize) when FileSize rem ?SIZE_BLOCK =:= 0 ->
+ FileSize;
+start_pos(FileSize) ->
+ %% set position to nearest block boundary past eof
+ %% if file size isn't multiple of block size
+ (FileSize div ?SIZE_BLOCK) * ?SIZE_BLOCK + ?SIZE_BLOCK.
+
+chunk_max_size() ->
+ config:get_integer("couchdb", "chunk_max_size", ?DEFAULT_CHUNK_MAX_SIZE).
+
+%% chunk size exponentially increases by iteration, up to some maximum,
+%% and should never exceed the current position in the file
+chunk_size(Pos, Multiplier) ->
+ Size = min(Multiplier * ?SIZE_BLOCK, chunk_max_size()),
+ min(Pos, Size).
+
+multiplier(Size, Multiplier) ->
+ case Size < chunk_max_size() of
+ true ->
+ Multiplier * config:get_integer(
+ "couchdb", "chunk_exponent_base", ?DEFAULT_CHUNK_EXPONENT_BASE);
+ false ->
+ Multiplier
+ end.
+
+find_header_in_chunks(_Fd, Pos, _Multiplier) when Pos < 0 ->
+ no_valid_header;
+find_header_in_chunks(Fd, Pos, Multiplier) ->
+ Size = chunk_size(Pos, Multiplier),
+ case Size > 0 of
+ false ->
+ no_valid_header;
+ true ->
+ {ok, Chunk} = file:pread(Fd, Pos - Size, Size),
+ case find_header_in_chunk(Fd, Pos, Chunk, Size - ?SIZE_BLOCK) of
+ {ok, HeaderBin, _Offset} ->
+ %% io:format("found header at ~p multiplier ~p chunksize ~p~n",
+ %% [Pos - Size + _Offset, Multiplier, Size]),
+ {ok, HeaderBin};
+ not_found ->
+ %% tell kernel we don't need that chunk any more
+ %% to minimize disk cache pollution
+ ok = file:advise(Fd, Pos - Size, Size, dont_need),
+ NewMultiplier = multiplier(Size, Multiplier),
+ find_header_in_chunks(Fd, Pos - Size, NewMultiplier)
+ end
+ end.
+
+-define(DEFAULT_SPAN_MAX_SIZE, ?SIZE_BLOCK * ?SIZE_BLOCK).
+-define(DEFAULT_SPAN_EXPONENT_BASE, 2).
+-define(PREFIX_SIZE, 5).
+
+system_milli_seconds() ->
--- End diff --
Don't include debug functions in your PR
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r75904196
--- Diff: src/couch_file.erl ---
@@ -524,6 +528,214 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+find_last_header(Fd, FileSize) ->
+ find_header_in_chunks(Fd, start_pos(FileSize), 1).
+
+start_pos(FileSize) when FileSize rem ?SIZE_BLOCK =:= 0 ->
+ FileSize;
+start_pos(FileSize) ->
+ %% set position to nearest block boundary past eof
+ %% if file size isn't multiple of block size
+ (FileSize div ?SIZE_BLOCK) * ?SIZE_BLOCK + ?SIZE_BLOCK.
+
+chunk_max_size() ->
+ config:get_integer("couchdb", "chunk_max_size", ?DEFAULT_CHUNK_MAX_SIZE).
+
+%% chunk size exponentially increases by iteration, up to some maximum,
+%% and should never exceed the current position in the file
+chunk_size(Pos, Multiplier) ->
+ Size = min(Multiplier * ?SIZE_BLOCK, chunk_max_size()),
+ min(Pos, Size).
+
+multiplier(Size, Multiplier) ->
+ case Size < chunk_max_size() of
+ true ->
+ Multiplier * config:get_integer(
+ "couchdb", "chunk_exponent_base", ?DEFAULT_CHUNK_EXPONENT_BASE);
+ false ->
+ Multiplier
+ end.
+
+find_header_in_chunks(_Fd, Pos, _Multiplier) when Pos < 0 ->
+ no_valid_header;
+find_header_in_chunks(Fd, Pos, Multiplier) ->
+ Size = chunk_size(Pos, Multiplier),
+ case Size > 0 of
+ false ->
+ no_valid_header;
+ true ->
+ {ok, Chunk} = file:pread(Fd, Pos - Size, Size),
+ case find_header_in_chunk(Fd, Pos, Chunk, Size - ?SIZE_BLOCK) of
+ {ok, HeaderBin, _Offset} ->
+ %% io:format("found header at ~p multiplier ~p chunksize ~p~n",
+ %% [Pos - Size + _Offset, Multiplier, Size]),
+ {ok, HeaderBin};
+ not_found ->
+ %% tell kernel we don't need that chunk any more
+ %% to minimize disk cache pollution
+ ok = file:advise(Fd, Pos - Size, Size, dont_need),
+ NewMultiplier = multiplier(Size, Multiplier),
+ find_header_in_chunks(Fd, Pos - Size, NewMultiplier)
+ end
+ end.
+
+-define(DEFAULT_SPAN_MAX_SIZE, ?SIZE_BLOCK * ?SIZE_BLOCK).
+-define(DEFAULT_SPAN_EXPONENT_BASE, 2).
+-define(PREFIX_SIZE, 5).
+
+system_milli_seconds() ->
+ {Mega, Sec, Micro} = os:timestamp(),
+ (Mega*1000000 + Sec)*1000 + round(Micro/1000).
+
+last_block_pos(FileSize) when FileSize rem ?SIZE_BLOCK =:= 0 ->
+ FileSize - ?SIZE_BLOCK;
+last_block_pos(FileSize) ->
+ (FileSize div ?SIZE_BLOCK) * ?SIZE_BLOCK.
+
+span_max_size() ->
+ config:get_integer("couchdb", "span_max_size", ?DEFAULT_SPAN_MAX_SIZE).
--- End diff --
Its generally easier to read code if you organize it so that major sections for logic are grouped. Interspersing helpers like this between functions with actual logic gets a bit distracting. Specific for these trivial functions where the entire purpose is expressed succinctly in the function name.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r75903202
--- Diff: src/couch_file.erl ---
@@ -524,6 +528,214 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+find_last_header(Fd, FileSize) ->
+ find_header_in_chunks(Fd, start_pos(FileSize), 1).
+
+start_pos(FileSize) when FileSize rem ?SIZE_BLOCK =:= 0 ->
+ FileSize;
+start_pos(FileSize) ->
+ %% set position to nearest block boundary past eof
+ %% if file size isn't multiple of block size
+ (FileSize div ?SIZE_BLOCK) * ?SIZE_BLOCK + ?SIZE_BLOCK.
+
+chunk_max_size() ->
+ config:get_integer("couchdb", "chunk_max_size", ?DEFAULT_CHUNK_MAX_SIZE).
+
+%% chunk size exponentially increases by iteration, up to some maximum,
--- End diff --
User proper capitalization, grammar, and punctuation in comments.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch issue #185: 3061 adaptive header search
Posted by jaydoane <gi...@git.apache.org>.
Github user jaydoane commented on the issue:
https://github.com/apache/couchdb-couch/pull/185
@davisp, formatting fixed in latest commit.
Here's a proposed commit message:
> Current behavior attempts to read a header at each block, starting at the eof and working backwards one block at a time. Deeply buried headers can take a long time to find, depending on the depth of the header, server load, etc.
>
> This commit changes the behavior so that if the last block in the file does not contain a header, it switches to using a "vectored" approach where multiple candidate header prefixes (of 5 bytes) are read in a single operation, greatly speeding up the search. On a modern linux system with SSD, we see improvements up to 15x.
If this looks ok to you, should I rebase as well as squash?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by jaydoane <gi...@git.apache.org>.
Github user jaydoane commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r71462210
--- Diff: src/couch_file.erl ---
@@ -524,6 +525,99 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+%% first try to read header at end, falling back to chunked reads on failure
+find_last_header(Fd, FileSize) ->
+ ok = file:advise(Fd, 0, FileSize, dont_need), % minimize disk cache pollution
+ Pos = (FileSize div ?SIZE_BLOCK) * ?SIZE_BLOCK,
+ case file:pread(Fd, Pos, FileSize - Pos) of
+ eof ->
+ no_valid_header;
+ {ok, Data} ->
+ try match_header(Fd, Pos, Data, 0) of
+ {ok, HeaderBin} ->
+ {ok, HeaderBin}
+ catch
+ error:{badmatch, _} ->
+ find_header_in_chunks(Fd, Pos, 1)
+ end
+ end.
+
+-define(DEFAULT_CHUNK_MAX_SIZE, ?SIZE_BLOCK).
+-define(DEFAULT_CHUNK_EXPONENT_BASE, 1).
+
+chunk_max_size() ->
+ config:get_integer("couchdb", "chunk_max_size", ?DEFAULT_CHUNK_MAX_SIZE).
+
+%% chunk size exponentially increases by iteration, up to some maximum,
+%% and should never exceed the current position in the file
+chunk_size(Pos, Multiplier) ->
+ Size = min(Multiplier * ?SIZE_BLOCK, chunk_max_size()),
+ min(Pos, Size).
+
+multiplier(Size, Multiplier) ->
+ case Size < chunk_max_size() of
+ true ->
+ Multiplier * config:get_integer(
+ "couchdb", "chunk_exponent_base", ?DEFAULT_CHUNK_EXPONENT_BASE);
+ false ->
+ Multiplier
+ end.
+
+find_header_in_chunks(_Fd, Pos, _Multiplier) when Pos < 0 ->
+ no_valid_header;
+find_header_in_chunks(Fd, Pos, Multiplier) ->
+ Size = chunk_size(Pos, Multiplier),
+ case Size > 0 of
+ false ->
+ no_valid_header;
+ true ->
+ {ok, Chunk} = file:pread(Fd, Pos - Size, Size),
+ case find_header_in_chunk(Fd, Pos, Chunk, Size) of
+ {ok, HeaderBin, _Offset} ->
+ %% io:format("found header at ~p multiplier ~p chunksize ~p~n",
+ %% [Pos - Size + _Offset, Multiplier, Size]),
+ {ok, HeaderBin};
+ not_found ->
+ NewMultiplier = multiplier(Size, Multiplier),
+ find_header_in_chunks(Fd, Pos - Size, NewMultiplier)
+ end
+ end.
+
+find_header_in_chunk(_Fd, _Pos, _Chunk, Offset) when Offset < 0 ->
--- End diff --
An Offset of 0 means that it's attempting to match on the "first" byte of the chunk, which is definitely valid, and should not automatically result in `not_found`, which is what would occur if we changed that guard to `=<`. Just to prove it to myself, I tried changing it, and it broke the algorithm (by not finding the last header), so I'm pretty convinced that it's correct as is.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch issue #185: 3061 adaptive header search
Posted by jaydoane <gi...@git.apache.org>.
Github user jaydoane commented on the issue:
https://github.com/apache/couchdb-couch/pull/185
@davisp, thanks for the explanation. You were of course correct that I was confusing `pread/3` with `pread/2`. I think it makes sense to look at an alternate version of header search which, like you suggest, uses `pread/2` to look for header blocks en masse. Do you think we should hold off on this PR until I complete those additional tests? I'm also curious about the style points you alluded to before. Can you enumerate them?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r71465420
--- Diff: src/couch_file.erl ---
@@ -524,6 +525,99 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+%% first try to read header at end, falling back to chunked reads on failure
+find_last_header(Fd, FileSize) ->
+ ok = file:advise(Fd, 0, FileSize, dont_need), % minimize disk cache pollution
+ Pos = (FileSize div ?SIZE_BLOCK) * ?SIZE_BLOCK,
+ case file:pread(Fd, Pos, FileSize - Pos) of
+ eof ->
+ no_valid_header;
+ {ok, Data} ->
+ try match_header(Fd, Pos, Data, 0) of
+ {ok, HeaderBin} ->
+ {ok, HeaderBin}
+ catch
+ error:{badmatch, _} ->
+ find_header_in_chunks(Fd, Pos, 1)
+ end
+ end.
+
+-define(DEFAULT_CHUNK_MAX_SIZE, ?SIZE_BLOCK).
+-define(DEFAULT_CHUNK_EXPONENT_BASE, 1).
+
+chunk_max_size() ->
+ config:get_integer("couchdb", "chunk_max_size", ?DEFAULT_CHUNK_MAX_SIZE).
+
+%% chunk size exponentially increases by iteration, up to some maximum,
+%% and should never exceed the current position in the file
+chunk_size(Pos, Multiplier) ->
+ Size = min(Multiplier * ?SIZE_BLOCK, chunk_max_size()),
+ min(Pos, Size).
+
+multiplier(Size, Multiplier) ->
+ case Size < chunk_max_size() of
+ true ->
+ Multiplier * config:get_integer(
+ "couchdb", "chunk_exponent_base", ?DEFAULT_CHUNK_EXPONENT_BASE);
+ false ->
+ Multiplier
+ end.
+
+find_header_in_chunks(_Fd, Pos, _Multiplier) when Pos < 0 ->
+ no_valid_header;
+find_header_in_chunks(Fd, Pos, Multiplier) ->
+ Size = chunk_size(Pos, Multiplier),
+ case Size > 0 of
+ false ->
+ no_valid_header;
+ true ->
+ {ok, Chunk} = file:pread(Fd, Pos - Size, Size),
+ case find_header_in_chunk(Fd, Pos, Chunk, Size) of
+ {ok, HeaderBin, _Offset} ->
+ %% io:format("found header at ~p multiplier ~p chunksize ~p~n",
+ %% [Pos - Size + _Offset, Multiplier, Size]),
+ {ok, HeaderBin};
+ not_found ->
+ NewMultiplier = multiplier(Size, Multiplier),
+ find_header_in_chunks(Fd, Pos - Size, NewMultiplier)
+ end
+ end.
+
+find_header_in_chunk(_Fd, _Pos, _Chunk, Offset) when Offset < 0 ->
+ not_found;
+find_header_in_chunk(Fd, Pos, Chunk, Offset) ->
+ try match_header(Fd, Pos, Chunk, Offset) of
+ {ok, HeaderBin} ->
+ {ok, HeaderBin, Offset}
+ catch
+ error:{badmatch, _} ->
+ find_header_in_chunk(Fd, Pos, Chunk, Offset - ?SIZE_BLOCK)
+ end.
+
+read_size(Data, Offset) ->
+ min(size(Data), Offset + ?SIZE_BLOCK) - Offset.
+
+match_header(Fd, Pos, Data, Offset) ->
+ <<1, HeaderSize:32/integer-unsigned, RestBlock/binary>> =
+ binary:part(Data, Offset, read_size(Data, Offset)),
+ PrefixSize = 5, % 1 (version) + 4 (size) bytes
+ TotalSize = total_read_size(PrefixSize, HeaderSize),
+ HeaderPos = Pos - byte_size(Data) + Offset,
+ RawBin = raw_bin(Fd, HeaderPos, TotalSize, RestBlock),
+ <<Hash:16/binary, HeaderBin/binary>> =
+ iolist_to_binary(remove_block_prefixes(PrefixSize, RawBin)),
+ Hash = crypto:hash(md5, HeaderBin),
--- End diff --
On this I agree with @jaydoane, there's no reason to avoid try/catch in Erlang. They implemented it to be quick and usable for non-local returns as far as I'm aware. Its a common pattern for halting iterating for instance (our (couch's) usage of a `{Go, NewState}` iteration return pattern isn't idiomatic for instance).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch issue #185: 3061 adaptive header search
Posted by jaydoane <gi...@git.apache.org>.
Github user jaydoane commented on the issue:
https://github.com/apache/couchdb-couch/pull/185
I have simplified the pread/2 based header search, and hopefully addressed most of the issues raised against the previous implementations. For a simple speed comparison using the same file as before, the new algorithm was measured to be about 13x faster than the current algorithm. When 4 such files are searched in parallel, it's only about 7x faster. Nevertheless, it uses many fewer disk reads, imposes less load and even seems to use less memory, as shown in the graphs below. It also seems like the file:advise/4
This first image shows first a single search using the default algorithm starting around 19:27 and ending around 19:35, followed by a single search using the pread/2 algorithm from around 19:43 to 19:45
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by jaydoane <gi...@git.apache.org>.
Github user jaydoane commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r81645651
--- Diff: src/couch_file.erl ---
@@ -531,27 +537,96 @@ find_header(Fd, Block) ->
{ok, Bin} ->
{ok, Bin};
_Error ->
- find_header(Fd, Block -1)
+ find_header_pread2(Fd, Block -1)
end.
load_header(Fd, Block) ->
{ok, <<1, HeaderLen:32/integer, RestBlock/binary>>} =
file:pread(Fd, Block * ?SIZE_BLOCK, ?SIZE_BLOCK),
- TotalBytes = calculate_total_read_len(5, HeaderLen),
- case TotalBytes > byte_size(RestBlock) of
+ TotalSize = total_read_size(5, HeaderLen),
+ case TotalSize > byte_size(RestBlock) of
false ->
- <<RawBin:TotalBytes/binary, _/binary>> = RestBlock;
+ <<RawBin:TotalSize/binary, _/binary>> = RestBlock;
true ->
{ok, Missing} = file:pread(
Fd, (Block * ?SIZE_BLOCK) + 5 + byte_size(RestBlock),
- TotalBytes - byte_size(RestBlock)),
+ TotalSize - byte_size(RestBlock)),
RawBin = <<RestBlock/binary, Missing/binary>>
end,
<<Md5Sig:16/binary, HeaderBin/binary>> =
iolist_to_binary(remove_block_prefixes(5, RawBin)),
Md5Sig = couch_crypto:hash(md5, HeaderBin),
{ok, HeaderBin}.
+
+%% Read a configurable number of block locations at a time using
+%% file:pread/2. At each block location, read ?PREFIX_SIZE (5) bytes;
+%% if the first byte is <<1>>, assume it's a header block, and the
+%% next 4 bytes hold the size of the header.
+-spec find_header_pread2(file:fd(), block_id()) ->
+ {ok, binary()} | no_valid_header.
+find_header_pread2(Fd, Block) ->
+ find_header_pread2(Fd, Block, read_count()).
+
+-spec find_header_pread2(file:fd(), block_id(), non_neg_integer()) ->
+ {ok, binary()} | no_valid_header.
+find_header_pread2(_Fd, Block, _ReadCount) when Block < 0 ->
+ no_valid_header;
+find_header_pread2(Fd, Block, ReadCount) ->
+ Locations = block_locations(Block, ReadCount),
+ {ok, DataL} = file:pread(Fd, [{L, ?PREFIX_SIZE} || L <- Locations]),
+ case locate_header(Fd, header_locations(Locations, DataL)) of
+ {ok, _Location, HeaderBin} ->
+ io:format("header at block ~p~n", [_Location div ?SIZE_BLOCK]), % TEMP
+ {ok, HeaderBin};
+ _ ->
+ ok = file:advise(
+ Fd, hd(Locations), ReadCount * ?SIZE_BLOCK, dont_need),
+ NextBlock = hd(Locations) div ?SIZE_BLOCK - 1,
+ find_header_pread2(Fd, NextBlock, ReadCount)
+ end.
+
+-spec read_count() -> non_neg_integer().
+read_count() ->
+ config:get_integer("couchdb", "find_header_read_count", ?DEFAULT_READ_COUNT).
+
+-spec block_locations(block_id(), non_neg_integer()) -> [location()].
+block_locations(Block, ReadCount) ->
+ First = max(0, Block - ReadCount + 1),
+ [?SIZE_BLOCK*B || B <- lists:seq(First, Block)].
+
+-spec header_locations([location()], [data()]) -> [{location(), header_size()}].
+header_locations(Locations, DataL) ->
+ lists:foldl(fun
+ ({Loc, <<1, HeaderSize:32/integer>>}, Acc) ->
+ [{Loc, HeaderSize} | Acc];
+ (_, Acc) ->
+ Acc
+ end, [], lists:zip(Locations, DataL)).
+
+-spec locate_header(file:fd(), [{location(), header_size()}]) ->
+ {ok, binary()} | not_found.
+locate_header(_Fd, []) ->
+ not_found;
+locate_header(Fd, [{Location, Size}|LocationSizes]) ->
+ case (catch load_header(Fd, Location, Size)) of
+ {ok, HeaderBin} ->
+ {ok, Location, HeaderBin};
+ _Error ->
+ locate_header(Fd, LocationSizes)
+ end.
+
+-spec load_header(file:fd(), location(), header_size()) ->
+ {ok, binary()} | no_return().
+load_header(Fd, Location, Size) ->
--- End diff --
@davisp, thank you for your patience. Your solution seems fine, even though it somewhat obscures the simplicity of the vectored algorithm. But I agree it's more idiomatic and easier to maintain your way, so I made the change pretty much verbatim.
Finally, I noted that the `find_header/2` recursion termination clause is no longer being used, and removed it.
Do you see any other changes that need to be made?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by kxepal <gi...@git.apache.org>.
Github user kxepal commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r71322068
--- Diff: src/couch_file.erl ---
@@ -524,6 +525,99 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+%% first try to read header at end, falling back to chunked reads on failure
+find_last_header(Fd, FileSize) ->
+ ok = file:advise(Fd, 0, FileSize, dont_need), % minimize disk cache pollution
+ Pos = (FileSize div ?SIZE_BLOCK) * ?SIZE_BLOCK,
+ case file:pread(Fd, Pos, FileSize - Pos) of
+ eof ->
+ no_valid_header;
+ {ok, Data} ->
+ try match_header(Fd, Pos, Data, 0) of
+ {ok, HeaderBin} ->
+ {ok, HeaderBin}
+ catch
+ error:{badmatch, _} ->
+ find_header_in_chunks(Fd, Pos, 1)
+ end
+ end.
+
+-define(DEFAULT_CHUNK_MAX_SIZE, ?SIZE_BLOCK).
+-define(DEFAULT_CHUNK_EXPONENT_BASE, 1).
+
+chunk_max_size() ->
+ config:get_integer("couchdb", "chunk_max_size", ?DEFAULT_CHUNK_MAX_SIZE).
+
+%% chunk size exponentially increases by iteration, up to some maximum,
+%% and should never exceed the current position in the file
+chunk_size(Pos, Multiplier) ->
+ Size = min(Multiplier * ?SIZE_BLOCK, chunk_max_size()),
+ min(Pos, Size).
+
+multiplier(Size, Multiplier) ->
+ case Size < chunk_max_size() of
+ true ->
+ Multiplier * config:get_integer(
+ "couchdb", "chunk_exponent_base", ?DEFAULT_CHUNK_EXPONENT_BASE);
+ false ->
+ Multiplier
+ end.
+
+find_header_in_chunks(_Fd, Pos, _Multiplier) when Pos < 0 ->
+ no_valid_header;
+find_header_in_chunks(Fd, Pos, Multiplier) ->
+ Size = chunk_size(Pos, Multiplier),
+ case Size > 0 of
+ false ->
+ no_valid_header;
+ true ->
+ {ok, Chunk} = file:pread(Fd, Pos - Size, Size),
+ case find_header_in_chunk(Fd, Pos, Chunk, Size) of
+ {ok, HeaderBin, _Offset} ->
+ %% io:format("found header at ~p multiplier ~p chunksize ~p~n",
+ %% [Pos - Size + _Offset, Multiplier, Size]),
+ {ok, HeaderBin};
+ not_found ->
+ NewMultiplier = multiplier(Size, Multiplier),
+ find_header_in_chunks(Fd, Pos - Size, NewMultiplier)
+ end
+ end.
+
+find_header_in_chunk(_Fd, _Pos, _Chunk, Offset) when Offset < 0 ->
+ not_found;
+find_header_in_chunk(Fd, Pos, Chunk, Offset) ->
+ try match_header(Fd, Pos, Chunk, Offset) of
+ {ok, HeaderBin} ->
+ {ok, HeaderBin, Offset}
+ catch
+ error:{badmatch, _} ->
+ find_header_in_chunk(Fd, Pos, Chunk, Offset - ?SIZE_BLOCK)
+ end.
+
+read_size(Data, Offset) ->
+ min(size(Data), Offset + ?SIZE_BLOCK) - Offset.
+
+match_header(Fd, Pos, Data, Offset) ->
+ <<1, HeaderSize:32/integer-unsigned, RestBlock/binary>> =
+ binary:part(Data, Offset, read_size(Data, Offset)),
+ PrefixSize = 5, % 1 (version) + 4 (size) bytes
+ TotalSize = total_read_size(PrefixSize, HeaderSize),
+ HeaderPos = Pos - byte_size(Data) + Offset,
+ RawBin = raw_bin(Fd, HeaderPos, TotalSize, RestBlock),
+ <<Hash:16/binary, HeaderBin/binary>> =
+ iolist_to_binary(remove_block_prefixes(PrefixSize, RawBin)),
+ Hash = crypto:hash(md5, HeaderBin),
--- End diff --
Sounds like not a big deal?
```
match_header_size(Data, Offset) ->
case binary:part(Data, Offset, read_size(Data, Offset)) of
<<1, HeaderSize:32/integer-unsigned, RestBlock/binary>> ->
{HeaderSize, RestBlock};
_ ->
no_match
end.
match_header(Fd, Pos, Data, Offset) ->
case match_header_size(Data, Offset) ->
no_match -> no_match;
{HeaderSize, RestBlock} ->
PrefixSize = 5, % 1 (version) + 4 (size) bytes
TotalSize = total_read_size(PrefixSize, HeaderSize),
HeaderPos = Pos - byte_size(Data) + Offset,
RawBin = raw_bin(Fd, HeaderPos, TotalSize, RestBlock),
<<Hash:16/binary, HeaderBin/binary>> =
iolist_to_binary(remove_block_prefixes(PrefixSize, RawBin)),
case crypto:hash(md5, HeaderBin) ->
Hash -> {ok, HeaderBin};
_ -> no_match
end
end.
```
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r80057370
--- Diff: src/couch_file.erl ---
@@ -531,27 +537,96 @@ find_header(Fd, Block) ->
{ok, Bin} ->
{ok, Bin};
_Error ->
- find_header(Fd, Block -1)
+ find_header_pread2(Fd, Block -1)
end.
load_header(Fd, Block) ->
{ok, <<1, HeaderLen:32/integer, RestBlock/binary>>} =
file:pread(Fd, Block * ?SIZE_BLOCK, ?SIZE_BLOCK),
- TotalBytes = calculate_total_read_len(5, HeaderLen),
- case TotalBytes > byte_size(RestBlock) of
+ TotalSize = total_read_size(5, HeaderLen),
+ case TotalSize > byte_size(RestBlock) of
false ->
- <<RawBin:TotalBytes/binary, _/binary>> = RestBlock;
+ <<RawBin:TotalSize/binary, _/binary>> = RestBlock;
true ->
{ok, Missing} = file:pread(
Fd, (Block * ?SIZE_BLOCK) + 5 + byte_size(RestBlock),
- TotalBytes - byte_size(RestBlock)),
+ TotalSize - byte_size(RestBlock)),
RawBin = <<RestBlock/binary, Missing/binary>>
end,
<<Md5Sig:16/binary, HeaderBin/binary>> =
iolist_to_binary(remove_block_prefixes(5, RawBin)),
Md5Sig = couch_crypto:hash(md5, HeaderBin),
{ok, HeaderBin}.
+
+%% Read a configurable number of block locations at a time using
+%% file:pread/2. At each block location, read ?PREFIX_SIZE (5) bytes;
+%% if the first byte is <<1>>, assume it's a header block, and the
+%% next 4 bytes hold the size of the header.
+-spec find_header_pread2(file:fd(), block_id()) ->
+ {ok, binary()} | no_valid_header.
+find_header_pread2(Fd, Block) ->
+ find_header_pread2(Fd, Block, read_count()).
+
+-spec find_header_pread2(file:fd(), block_id(), non_neg_integer()) ->
+ {ok, binary()} | no_valid_header.
+find_header_pread2(_Fd, Block, _ReadCount) when Block < 0 ->
+ no_valid_header;
+find_header_pread2(Fd, Block, ReadCount) ->
+ Locations = block_locations(Block, ReadCount),
+ {ok, DataL} = file:pread(Fd, [{L, ?PREFIX_SIZE} || L <- Locations]),
+ case locate_header(Fd, header_locations(Locations, DataL)) of
+ {ok, _Location, HeaderBin} ->
+ io:format("header at block ~p~n", [_Location div ?SIZE_BLOCK]), % TEMP
--- End diff --
Remove debug logging.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch issue #185: 3061 adaptive header search
Posted by jaydoane <gi...@git.apache.org>.
Github user jaydoane commented on the issue:
https://github.com/apache/couchdb-couch/pull/185
@theburge, @kocolosk, @davisp, @eiri: can I get some feedback on this?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r75903091
--- Diff: src/couch_file.erl ---
@@ -524,6 +528,214 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+find_last_header(Fd, FileSize) ->
+ find_header_in_chunks(Fd, start_pos(FileSize), 1).
+
+start_pos(FileSize) when FileSize rem ?SIZE_BLOCK =:= 0 ->
+ FileSize;
+start_pos(FileSize) ->
+ %% set position to nearest block boundary past eof
+ %% if file size isn't multiple of block size
+ (FileSize div ?SIZE_BLOCK) * ?SIZE_BLOCK + ?SIZE_BLOCK.
+
+chunk_max_size() ->
--- End diff --
Missing second blank line
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r75902825
--- Diff: src/couch_file.erl ---
@@ -15,13 +15,16 @@
-vsn(2).
-include_lib("couch/include/couch_db.hrl").
+-compile(export_all).
--- End diff --
Remove this
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r80056486
--- Diff: src/couch_file.erl ---
@@ -531,27 +537,96 @@ find_header(Fd, Block) ->
{ok, Bin} ->
{ok, Bin};
_Error ->
- find_header(Fd, Block -1)
+ find_header_pread2(Fd, Block -1)
end.
load_header(Fd, Block) ->
{ok, <<1, HeaderLen:32/integer, RestBlock/binary>>} =
file:pread(Fd, Block * ?SIZE_BLOCK, ?SIZE_BLOCK),
- TotalBytes = calculate_total_read_len(5, HeaderLen),
--- End diff --
Undo the part of this PR that renames calculate_total_read_len to total_read_size. Its not a behavior change and shouldn't be included with this change as it just makes things harder to comprehend when looking through the history. If you feel strongly about it we can open another PR with this change for a separate readability improvement.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by asfgit <gi...@git.apache.org>.
Github user asfgit closed the pull request at:
https://github.com/apache/couchdb-couch/pull/185
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r80055417
--- Diff: src/couch_file.erl ---
@@ -16,13 +16,18 @@
-include_lib("couch/include/couch_db.hrl").
-
-define(INITIAL_WAIT, 60000).
-define(MONITOR_CHECK, 10000).
-define(SIZE_BLOCK, 16#1000). % 4 KiB
-define(READ_AHEAD, 2 * ?SIZE_BLOCK).
-define(IS_OLD_STATE(S), tuple_size(S) /= tuple_size(#file{})).
+-define(PREFIX_SIZE, 5).
+-define(DEFAULT_READ_COUNT, 1024).
+-type block_id() :: non_neg_integer().
+-type location() :: non_neg_integer().
+-type data() :: string() | binary() | eof.
+-type header_size() :: non_neg_integer().
--- End diff --
I'm personally not a fan of specs for module private functions but I won't go so far as to say to remove them.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r80063047
--- Diff: src/couch_file.erl ---
@@ -531,27 +537,96 @@ find_header(Fd, Block) ->
{ok, Bin} ->
{ok, Bin};
_Error ->
- find_header(Fd, Block -1)
+ find_header_pread2(Fd, Block -1)
end.
load_header(Fd, Block) ->
{ok, <<1, HeaderLen:32/integer, RestBlock/binary>>} =
file:pread(Fd, Block * ?SIZE_BLOCK, ?SIZE_BLOCK),
- TotalBytes = calculate_total_read_len(5, HeaderLen),
- case TotalBytes > byte_size(RestBlock) of
+ TotalSize = total_read_size(5, HeaderLen),
+ case TotalSize > byte_size(RestBlock) of
false ->
- <<RawBin:TotalBytes/binary, _/binary>> = RestBlock;
+ <<RawBin:TotalSize/binary, _/binary>> = RestBlock;
true ->
{ok, Missing} = file:pread(
Fd, (Block * ?SIZE_BLOCK) + 5 + byte_size(RestBlock),
- TotalBytes - byte_size(RestBlock)),
+ TotalSize - byte_size(RestBlock)),
RawBin = <<RestBlock/binary, Missing/binary>>
end,
<<Md5Sig:16/binary, HeaderBin/binary>> =
iolist_to_binary(remove_block_prefixes(5, RawBin)),
Md5Sig = couch_crypto:hash(md5, HeaderBin),
{ok, HeaderBin}.
+
+%% Read a configurable number of block locations at a time using
+%% file:pread/2. At each block location, read ?PREFIX_SIZE (5) bytes;
+%% if the first byte is <<1>>, assume it's a header block, and the
+%% next 4 bytes hold the size of the header.
+-spec find_header_pread2(file:fd(), block_id()) ->
+ {ok, binary()} | no_valid_header.
+find_header_pread2(Fd, Block) ->
+ find_header_pread2(Fd, Block, read_count()).
+
+-spec find_header_pread2(file:fd(), block_id(), non_neg_integer()) ->
+ {ok, binary()} | no_valid_header.
+find_header_pread2(_Fd, Block, _ReadCount) when Block < 0 ->
+ no_valid_header;
+find_header_pread2(Fd, Block, ReadCount) ->
+ Locations = block_locations(Block, ReadCount),
+ {ok, DataL} = file:pread(Fd, [{L, ?PREFIX_SIZE} || L <- Locations]),
+ case locate_header(Fd, header_locations(Locations, DataL)) of
--- End diff --
@rnewson points out that find_first_valid_header/2 is ambiguous since it depends on the order of the list (specifically, the "first" bit). Bouncing ideas around we came up with `find_newest_header/2` which matches the intent a lot better.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r80057274
--- Diff: src/couch_file.erl ---
@@ -531,27 +537,96 @@ find_header(Fd, Block) ->
{ok, Bin} ->
{ok, Bin};
_Error ->
- find_header(Fd, Block -1)
+ find_header_pread2(Fd, Block -1)
--- End diff --
Rename find_header_pread2 to find_header and then just call the find_header/3 version directly (and remove find_header_pread2/2). Alsos move that function to below this one so the ordering makes more sense.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by jaydoane <gi...@git.apache.org>.
Github user jaydoane commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r71463598
--- Diff: src/couch_file.erl ---
@@ -524,6 +525,99 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+%% first try to read header at end, falling back to chunked reads on failure
+find_last_header(Fd, FileSize) ->
+ ok = file:advise(Fd, 0, FileSize, dont_need), % minimize disk cache pollution
--- End diff --
I've addressed this in commit 03a76fd
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by jaydoane <gi...@git.apache.org>.
Github user jaydoane commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r71275114
--- Diff: src/couch_file.erl ---
@@ -524,6 +525,99 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+%% first try to read header at end, falling back to chunked reads on failure
+find_last_header(Fd, FileSize) ->
+ ok = file:advise(Fd, 0, FileSize, dont_need), % minimize disk cache pollution
--- End diff --
Here's what http://linux.die.net/man/2/posix_fadvise says:
"In kernels before 2.6.18, POSIX_FADV_NOREUSE had the same semantics as POSIX_FADV_WILLNEED. This was probably a bug; since kernel 2.6.18, this flag is a no-op.
POSIX_FADV_DONTNEED attempts to free cached pages associated with the specified region. This is useful, for example, while streaming large files. A program may periodically request the kernel to free cached data that has already been used, so that more useful cached pages are not discarded instead.
Pages that have not yet been written out will be unaffected, so if the application wishes to guarantee that pages will be released, it should call fsync(2) or fdatasync(2) first."
So, it does sounds like I'm using it incorrectly, and that it should presumably be called on the "chunk" after it's been read from if we want to tell the kernel we don't intend to use the data again. I'm not clear about whether the last paragraph is relevant, however, since we're only reading pages and not writing them.
@rnewson originally suggested using this flag, so I'd be interested in getting his feedback as well on this topic.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r75902863
--- Diff: src/couch_file.erl ---
@@ -124,7 +128,7 @@ append_term_md5(Fd, Term, Options) ->
append_binary(Fd, Bin) ->
ioq:call(Fd, {append_bin, assemble_file_chunk(Bin)}, erlang:get(io_priority)).
-
+
--- End diff --
remove white space only hunks
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch issue #185: 3061 adaptive header search
Posted by jaydoane <gi...@git.apache.org>.
Github user jaydoane commented on the issue:
https://github.com/apache/couchdb-couch/pull/185
I've been testing with this repl command:
```erlang
_time_find_header = fun(File, Algorithm) when is_list(File) ->
FileSize = filelib:file_size(File),
{ok, Fd} = file:open(File, [raw, read, binary]),
{Time, Result} = case Algorithm of
current ->
timer:tc(couch_file,find_header,[Fd, FileSize div 4096]);
default ->
timer:tc(couch_file,find_last_header,[Fd, FileSize]);
adaptive ->
ok = config:set_integer("couchdb", "chunk_max_size", 4096*4096),
ok = config:set_integer("couchdb", "chunk_exponent_base", 2),
Res = timer:tc(couch_file,find_last_header,[Fd, FileSize]),
ok = config:delete("couchdb", "chunk_max_size"),
ok = config:delete("couchdb", "chunk_exponent_base"),
Res
end,
ok = file:close(Fd),
case Result of
{ok, HeaderBin} ->
{Time, binary_to_term(HeaderBin)};
_ ->
{Time, Result}
end
end.
```
and use it like so:
```erlang
(node1@127.0.0.1)78> _time_find_header("/Users/jay/proj/ibm/sample-data/foo.couch", current).
{255,
{db_header,6,0,0,nil,nil,nil,0,nil,nil,1000,
<<"1ca5e7003114d27fa1dcfff52b10163f">>,
[{'node1@127.0.0.1',0}],
0}}
(node1@127.0.0.1)79> _time_find_header("/Users/jay/proj/ibm/sample-data/foo.couch", default).
{119,
{db_header,6,0,0,nil,nil,nil,0,nil,nil,1000,
<<"1ca5e7003114d27fa1dcfff52b10163f">>,
[{'node1@127.0.0.1',0}],
0}}
(node1@127.0.0.1)80> _time_find_header("/Users/jay/proj/ibm/sample-data/foo.couch", adaptive).
{138,
{db_header,6,0,0,nil,nil,nil,0,nil,nil,1000,
<<"1ca5e7003114d27fa1dcfff52b10163f">>,
[{'node1@127.0.0.1',0}],
0}}
```
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r80059337
--- Diff: src/couch_file.erl ---
@@ -531,27 +537,96 @@ find_header(Fd, Block) ->
{ok, Bin} ->
{ok, Bin};
_Error ->
- find_header(Fd, Block -1)
+ find_header_pread2(Fd, Block -1)
end.
load_header(Fd, Block) ->
{ok, <<1, HeaderLen:32/integer, RestBlock/binary>>} =
file:pread(Fd, Block * ?SIZE_BLOCK, ?SIZE_BLOCK),
- TotalBytes = calculate_total_read_len(5, HeaderLen),
- case TotalBytes > byte_size(RestBlock) of
+ TotalSize = total_read_size(5, HeaderLen),
+ case TotalSize > byte_size(RestBlock) of
false ->
- <<RawBin:TotalBytes/binary, _/binary>> = RestBlock;
+ <<RawBin:TotalSize/binary, _/binary>> = RestBlock;
true ->
{ok, Missing} = file:pread(
Fd, (Block * ?SIZE_BLOCK) + 5 + byte_size(RestBlock),
- TotalBytes - byte_size(RestBlock)),
+ TotalSize - byte_size(RestBlock)),
RawBin = <<RestBlock/binary, Missing/binary>>
end,
<<Md5Sig:16/binary, HeaderBin/binary>> =
iolist_to_binary(remove_block_prefixes(5, RawBin)),
Md5Sig = couch_crypto:hash(md5, HeaderBin),
{ok, HeaderBin}.
+
+%% Read a configurable number of block locations at a time using
+%% file:pread/2. At each block location, read ?PREFIX_SIZE (5) bytes;
+%% if the first byte is <<1>>, assume it's a header block, and the
+%% next 4 bytes hold the size of the header.
+-spec find_header_pread2(file:fd(), block_id()) ->
+ {ok, binary()} | no_valid_header.
+find_header_pread2(Fd, Block) ->
+ find_header_pread2(Fd, Block, read_count()).
+
+-spec find_header_pread2(file:fd(), block_id(), non_neg_integer()) ->
+ {ok, binary()} | no_valid_header.
+find_header_pread2(_Fd, Block, _ReadCount) when Block < 0 ->
+ no_valid_header;
+find_header_pread2(Fd, Block, ReadCount) ->
+ Locations = block_locations(Block, ReadCount),
+ {ok, DataL} = file:pread(Fd, [{L, ?PREFIX_SIZE} || L <- Locations]),
+ case locate_header(Fd, header_locations(Locations, DataL)) of
+ {ok, _Location, HeaderBin} ->
+ io:format("header at block ~p~n", [_Location div ?SIZE_BLOCK]), % TEMP
+ {ok, HeaderBin};
+ _ ->
+ ok = file:advise(
+ Fd, hd(Locations), ReadCount * ?SIZE_BLOCK, dont_need),
+ NextBlock = hd(Locations) div ?SIZE_BLOCK - 1,
+ find_header_pread2(Fd, NextBlock, ReadCount)
+ end.
+
+-spec read_count() -> non_neg_integer().
+read_count() ->
+ config:get_integer("couchdb", "find_header_read_count", ?DEFAULT_READ_COUNT).
+
+-spec block_locations(block_id(), non_neg_integer()) -> [location()].
+block_locations(Block, ReadCount) ->
+ First = max(0, Block - ReadCount + 1),
+ [?SIZE_BLOCK*B || B <- lists:seq(First, Block)].
+
+-spec header_locations([location()], [data()]) -> [{location(), header_size()}].
+header_locations(Locations, DataL) ->
+ lists:foldl(fun
+ ({Loc, <<1, HeaderSize:32/integer>>}, Acc) ->
+ [{Loc, HeaderSize} | Acc];
+ (_, Acc) ->
+ Acc
+ end, [], lists:zip(Locations, DataL)).
+
+-spec locate_header(file:fd(), [{location(), header_size()}]) ->
+ {ok, binary()} | not_found.
+locate_header(_Fd, []) ->
+ not_found;
+locate_header(Fd, [{Location, Size}|LocationSizes]) ->
+ case (catch load_header(Fd, Location, Size)) of
+ {ok, HeaderBin} ->
+ {ok, Location, HeaderBin};
+ _Error ->
+ locate_header(Fd, LocationSizes)
+ end.
+
+-spec load_header(file:fd(), location(), header_size()) ->
+ {ok, binary()} | no_return().
+load_header(Fd, Location, Size) ->
--- End diff --
You should move this function up under load_header/2 and then rearrange load_header/2 so that it calls this function. Scrolling back and forth between the two trying to figure out the difference was quite confusing.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by theburge <gi...@git.apache.org>.
Github user theburge commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r71482562
--- Diff: src/couch_file.erl ---
@@ -524,6 +525,99 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+%% first try to read header at end, falling back to chunked reads on failure
+find_last_header(Fd, FileSize) ->
+ ok = file:advise(Fd, 0, FileSize, dont_need), % minimize disk cache pollution
+ Pos = (FileSize div ?SIZE_BLOCK) * ?SIZE_BLOCK,
+ case file:pread(Fd, Pos, FileSize - Pos) of
+ eof ->
+ no_valid_header;
+ {ok, Data} ->
+ try match_header(Fd, Pos, Data, 0) of
+ {ok, HeaderBin} ->
+ {ok, HeaderBin}
+ catch
+ error:{badmatch, _} ->
+ find_header_in_chunks(Fd, Pos, 1)
+ end
+ end.
+
+-define(DEFAULT_CHUNK_MAX_SIZE, ?SIZE_BLOCK).
+-define(DEFAULT_CHUNK_EXPONENT_BASE, 1).
+
+chunk_max_size() ->
+ config:get_integer("couchdb", "chunk_max_size", ?DEFAULT_CHUNK_MAX_SIZE).
+
+%% chunk size exponentially increases by iteration, up to some maximum,
+%% and should never exceed the current position in the file
+chunk_size(Pos, Multiplier) ->
+ Size = min(Multiplier * ?SIZE_BLOCK, chunk_max_size()),
+ min(Pos, Size).
+
+multiplier(Size, Multiplier) ->
+ case Size < chunk_max_size() of
+ true ->
+ Multiplier * config:get_integer(
+ "couchdb", "chunk_exponent_base", ?DEFAULT_CHUNK_EXPONENT_BASE);
+ false ->
+ Multiplier
+ end.
+
+find_header_in_chunks(_Fd, Pos, _Multiplier) when Pos < 0 ->
+ no_valid_header;
+find_header_in_chunks(Fd, Pos, Multiplier) ->
+ Size = chunk_size(Pos, Multiplier),
+ case Size > 0 of
+ false ->
+ no_valid_header;
+ true ->
+ {ok, Chunk} = file:pread(Fd, Pos - Size, Size),
+ case find_header_in_chunk(Fd, Pos, Chunk, Size) of
+ {ok, HeaderBin, _Offset} ->
+ %% io:format("found header at ~p multiplier ~p chunksize ~p~n",
+ %% [Pos - Size + _Offset, Multiplier, Size]),
+ {ok, HeaderBin};
+ not_found ->
+ NewMultiplier = multiplier(Size, Multiplier),
+ find_header_in_chunks(Fd, Pos - Size, NewMultiplier)
+ end
+ end.
+
+find_header_in_chunk(_Fd, _Pos, _Chunk, Offset) when Offset < 0 ->
--- End diff --
In that case, I was going to point out that the [call site (L575)](https://github.com/apache/couchdb-couch/pull/185#discussion-diff-71323695R575) was a problem, since it identifies `Offset` with `Size`, but [you fixed it later](https://github.com/apache/couchdb-couch/pull/185/commits/20a2a1c6e09a70b9be83d960d82d519817f3d052). :)
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by nickva <gi...@git.apache.org>.
Github user nickva commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r71203185
--- Diff: src/couch_file.erl ---
@@ -524,6 +525,99 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+%% first try to read header at end, falling back to chunked reads on failure
+find_last_header(Fd, FileSize) ->
+ ok = file:advise(Fd, 0, FileSize, dont_need), % minimize disk cache pollution
--- End diff --
Ooh, nice!
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r80063112
--- Diff: src/couch_file.erl ---
@@ -531,27 +537,96 @@ find_header(Fd, Block) ->
{ok, Bin} ->
{ok, Bin};
_Error ->
- find_header(Fd, Block -1)
+ find_header_pread2(Fd, Block -1)
end.
load_header(Fd, Block) ->
{ok, <<1, HeaderLen:32/integer, RestBlock/binary>>} =
file:pread(Fd, Block * ?SIZE_BLOCK, ?SIZE_BLOCK),
- TotalBytes = calculate_total_read_len(5, HeaderLen),
- case TotalBytes > byte_size(RestBlock) of
+ TotalSize = total_read_size(5, HeaderLen),
+ case TotalSize > byte_size(RestBlock) of
false ->
- <<RawBin:TotalBytes/binary, _/binary>> = RestBlock;
+ <<RawBin:TotalSize/binary, _/binary>> = RestBlock;
true ->
{ok, Missing} = file:pread(
Fd, (Block * ?SIZE_BLOCK) + 5 + byte_size(RestBlock),
- TotalBytes - byte_size(RestBlock)),
+ TotalSize - byte_size(RestBlock)),
RawBin = <<RestBlock/binary, Missing/binary>>
end,
<<Md5Sig:16/binary, HeaderBin/binary>> =
iolist_to_binary(remove_block_prefixes(5, RawBin)),
Md5Sig = couch_crypto:hash(md5, HeaderBin),
{ok, HeaderBin}.
+
+%% Read a configurable number of block locations at a time using
+%% file:pread/2. At each block location, read ?PREFIX_SIZE (5) bytes;
+%% if the first byte is <<1>>, assume it's a header block, and the
+%% next 4 bytes hold the size of the header.
+-spec find_header_pread2(file:fd(), block_id()) ->
+ {ok, binary()} | no_valid_header.
+find_header_pread2(Fd, Block) ->
+ find_header_pread2(Fd, Block, read_count()).
+
+-spec find_header_pread2(file:fd(), block_id(), non_neg_integer()) ->
+ {ok, binary()} | no_valid_header.
+find_header_pread2(_Fd, Block, _ReadCount) when Block < 0 ->
+ no_valid_header;
+find_header_pread2(Fd, Block, ReadCount) ->
+ Locations = block_locations(Block, ReadCount),
+ {ok, DataL} = file:pread(Fd, [{L, ?PREFIX_SIZE} || L <- Locations]),
+ case locate_header(Fd, header_locations(Locations, DataL)) of
--- End diff --
Or `find_newest_valid_header/2` of course.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch issue #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on the issue:
https://github.com/apache/couchdb-couch/pull/185
Yep, +1 to squashing with that commit message
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r75903054
--- Diff: src/couch_file.erl ---
@@ -524,6 +528,214 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+find_last_header(Fd, FileSize) ->
+ find_header_in_chunks(Fd, start_pos(FileSize), 1).
+
+start_pos(FileSize) when FileSize rem ?SIZE_BLOCK =:= 0 ->
--- End diff --
Two blank lines between functions.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r80058806
--- Diff: src/couch_file.erl ---
@@ -531,27 +537,96 @@ find_header(Fd, Block) ->
{ok, Bin} ->
{ok, Bin};
_Error ->
- find_header(Fd, Block -1)
+ find_header_pread2(Fd, Block -1)
end.
load_header(Fd, Block) ->
{ok, <<1, HeaderLen:32/integer, RestBlock/binary>>} =
file:pread(Fd, Block * ?SIZE_BLOCK, ?SIZE_BLOCK),
- TotalBytes = calculate_total_read_len(5, HeaderLen),
- case TotalBytes > byte_size(RestBlock) of
+ TotalSize = total_read_size(5, HeaderLen),
+ case TotalSize > byte_size(RestBlock) of
false ->
- <<RawBin:TotalBytes/binary, _/binary>> = RestBlock;
+ <<RawBin:TotalSize/binary, _/binary>> = RestBlock;
true ->
{ok, Missing} = file:pread(
Fd, (Block * ?SIZE_BLOCK) + 5 + byte_size(RestBlock),
- TotalBytes - byte_size(RestBlock)),
+ TotalSize - byte_size(RestBlock)),
RawBin = <<RestBlock/binary, Missing/binary>>
end,
<<Md5Sig:16/binary, HeaderBin/binary>> =
iolist_to_binary(remove_block_prefixes(5, RawBin)),
Md5Sig = couch_crypto:hash(md5, HeaderBin),
{ok, HeaderBin}.
+
+%% Read a configurable number of block locations at a time using
+%% file:pread/2. At each block location, read ?PREFIX_SIZE (5) bytes;
+%% if the first byte is <<1>>, assume it's a header block, and the
+%% next 4 bytes hold the size of the header.
+-spec find_header_pread2(file:fd(), block_id()) ->
+ {ok, binary()} | no_valid_header.
+find_header_pread2(Fd, Block) ->
+ find_header_pread2(Fd, Block, read_count()).
+
+-spec find_header_pread2(file:fd(), block_id(), non_neg_integer()) ->
+ {ok, binary()} | no_valid_header.
+find_header_pread2(_Fd, Block, _ReadCount) when Block < 0 ->
+ no_valid_header;
+find_header_pread2(Fd, Block, ReadCount) ->
+ Locations = block_locations(Block, ReadCount),
+ {ok, DataL} = file:pread(Fd, [{L, ?PREFIX_SIZE} || L <- Locations]),
+ case locate_header(Fd, header_locations(Locations, DataL)) of
--- End diff --
There's a lot going on in this line. I'd inline header_locations since its also only used once and put a pretty big explanatory comment on how that works. Its super subtle that you're relying on the lists:foldl/3 down below to reverse your list of locations passed to locate_header/2.
Also, we should rename locate_header/2 to something like find_first_valid_header/2. Locate and load seem awfully close that my brain seems to lose the semantic difference as I review this.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by jaydoane <gi...@git.apache.org>.
Github user jaydoane commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r81490840
--- Diff: src/couch_file.erl ---
@@ -531,27 +537,96 @@ find_header(Fd, Block) ->
{ok, Bin} ->
{ok, Bin};
_Error ->
- find_header(Fd, Block -1)
+ find_header_pread2(Fd, Block -1)
end.
load_header(Fd, Block) ->
{ok, <<1, HeaderLen:32/integer, RestBlock/binary>>} =
file:pread(Fd, Block * ?SIZE_BLOCK, ?SIZE_BLOCK),
- TotalBytes = calculate_total_read_len(5, HeaderLen),
- case TotalBytes > byte_size(RestBlock) of
+ TotalSize = total_read_size(5, HeaderLen),
+ case TotalSize > byte_size(RestBlock) of
false ->
- <<RawBin:TotalBytes/binary, _/binary>> = RestBlock;
+ <<RawBin:TotalSize/binary, _/binary>> = RestBlock;
true ->
{ok, Missing} = file:pread(
Fd, (Block * ?SIZE_BLOCK) + 5 + byte_size(RestBlock),
- TotalBytes - byte_size(RestBlock)),
+ TotalSize - byte_size(RestBlock)),
RawBin = <<RestBlock/binary, Missing/binary>>
end,
<<Md5Sig:16/binary, HeaderBin/binary>> =
iolist_to_binary(remove_block_prefixes(5, RawBin)),
Md5Sig = couch_crypto:hash(md5, HeaderBin),
{ok, HeaderBin}.
+
+%% Read a configurable number of block locations at a time using
+%% file:pread/2. At each block location, read ?PREFIX_SIZE (5) bytes;
+%% if the first byte is <<1>>, assume it's a header block, and the
+%% next 4 bytes hold the size of the header.
+-spec find_header_pread2(file:fd(), block_id()) ->
+ {ok, binary()} | no_valid_header.
+find_header_pread2(Fd, Block) ->
+ find_header_pread2(Fd, Block, read_count()).
+
+-spec find_header_pread2(file:fd(), block_id(), non_neg_integer()) ->
+ {ok, binary()} | no_valid_header.
+find_header_pread2(_Fd, Block, _ReadCount) when Block < 0 ->
+ no_valid_header;
+find_header_pread2(Fd, Block, ReadCount) ->
+ Locations = block_locations(Block, ReadCount),
+ {ok, DataL} = file:pread(Fd, [{L, ?PREFIX_SIZE} || L <- Locations]),
+ case locate_header(Fd, header_locations(Locations, DataL)) of
+ {ok, _Location, HeaderBin} ->
+ io:format("header at block ~p~n", [_Location div ?SIZE_BLOCK]), % TEMP
+ {ok, HeaderBin};
+ _ ->
+ ok = file:advise(
+ Fd, hd(Locations), ReadCount * ?SIZE_BLOCK, dont_need),
+ NextBlock = hd(Locations) div ?SIZE_BLOCK - 1,
+ find_header_pread2(Fd, NextBlock, ReadCount)
+ end.
+
+-spec read_count() -> non_neg_integer().
+read_count() ->
+ config:get_integer("couchdb", "find_header_read_count", ?DEFAULT_READ_COUNT).
+
+-spec block_locations(block_id(), non_neg_integer()) -> [location()].
+block_locations(Block, ReadCount) ->
+ First = max(0, Block - ReadCount + 1),
+ [?SIZE_BLOCK*B || B <- lists:seq(First, Block)].
+
+-spec header_locations([location()], [data()]) -> [{location(), header_size()}].
+header_locations(Locations, DataL) ->
+ lists:foldl(fun
+ ({Loc, <<1, HeaderSize:32/integer>>}, Acc) ->
+ [{Loc, HeaderSize} | Acc];
+ (_, Acc) ->
+ Acc
+ end, [], lists:zip(Locations, DataL)).
+
+-spec locate_header(file:fd(), [{location(), header_size()}]) ->
+ {ok, binary()} | not_found.
+locate_header(_Fd, []) ->
+ not_found;
+locate_header(Fd, [{Location, Size}|LocationSizes]) ->
+ case (catch load_header(Fd, Location, Size)) of
+ {ok, HeaderBin} ->
+ {ok, Location, HeaderBin};
+ _Error ->
+ locate_header(Fd, LocationSizes)
+ end.
+
+-spec load_header(file:fd(), location(), header_size()) ->
+ {ok, binary()} | no_return().
+load_header(Fd, Location, Size) ->
--- End diff --
@davisp, I've implemented all the changes you suggested, except for this one. The problem is that `load_header/2` doesn't know whether it's reading a header block, and also doesn't already know the header size when its called (unlike `load_header/3`). So, as a "micro-optimization" (as stated in the commit message), `load_header/2` reads an entire block in one shot, trying to match on a header. Unfortunately, it may still need to read more data after that if the header exceeds a single block, which complicates the algorithm further.
In short, it's not clear how to "rearrange `load_header/2` so that it calls" `load_header/3`. However, it is certainly possible to factor `verify_checksum/1` from `load_header/2`, which does allow reuse of common code between the two.
I agree that it's confusing to understand the differences between the two, so I documented `load_header/2`, which is by far the more complicated of the two. I also don't think the best location for `load_header/3` is right after `load_header/2`, but right after where it's called, in in `find_newest_header/2`.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r80057664
--- Diff: src/couch_file.erl ---
@@ -531,27 +537,96 @@ find_header(Fd, Block) ->
{ok, Bin} ->
{ok, Bin};
_Error ->
- find_header(Fd, Block -1)
+ find_header_pread2(Fd, Block -1)
end.
load_header(Fd, Block) ->
{ok, <<1, HeaderLen:32/integer, RestBlock/binary>>} =
file:pread(Fd, Block * ?SIZE_BLOCK, ?SIZE_BLOCK),
- TotalBytes = calculate_total_read_len(5, HeaderLen),
- case TotalBytes > byte_size(RestBlock) of
+ TotalSize = total_read_size(5, HeaderLen),
+ case TotalSize > byte_size(RestBlock) of
false ->
- <<RawBin:TotalBytes/binary, _/binary>> = RestBlock;
+ <<RawBin:TotalSize/binary, _/binary>> = RestBlock;
true ->
{ok, Missing} = file:pread(
Fd, (Block * ?SIZE_BLOCK) + 5 + byte_size(RestBlock),
- TotalBytes - byte_size(RestBlock)),
+ TotalSize - byte_size(RestBlock)),
RawBin = <<RestBlock/binary, Missing/binary>>
end,
<<Md5Sig:16/binary, HeaderBin/binary>> =
iolist_to_binary(remove_block_prefixes(5, RawBin)),
Md5Sig = couch_crypto:hash(md5, HeaderBin),
{ok, HeaderBin}.
+
+%% Read a configurable number of block locations at a time using
+%% file:pread/2. At each block location, read ?PREFIX_SIZE (5) bytes;
+%% if the first byte is <<1>>, assume it's a header block, and the
+%% next 4 bytes hold the size of the header.
+-spec find_header_pread2(file:fd(), block_id()) ->
+ {ok, binary()} | no_valid_header.
+find_header_pread2(Fd, Block) ->
+ find_header_pread2(Fd, Block, read_count()).
+
+-spec find_header_pread2(file:fd(), block_id(), non_neg_integer()) ->
+ {ok, binary()} | no_valid_header.
+find_header_pread2(_Fd, Block, _ReadCount) when Block < 0 ->
+ no_valid_header;
+find_header_pread2(Fd, Block, ReadCount) ->
+ Locations = block_locations(Block, ReadCount),
--- End diff --
block_locations is a trivial funciton that's only used once. You should inline it here so that we don't have to reference back and forth as the ordering is important so having that here would be more useful.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch issue #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on the issue:
https://github.com/apache/couchdb-couch/pull/185
That seems fairly convincingly just all around better than the default implementation. The only real worry I had was RAM usage with the vectored reads but that appears to be a non issue (and even an improvement).
If you want to try the tests that @theburge suggested that'd be fine but I'd also be willing to start making final tweaks to get this merged.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by kxepal <gi...@git.apache.org>.
Github user kxepal commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r71205429
--- Diff: src/couch_file.erl ---
@@ -524,6 +525,99 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+%% first try to read header at end, falling back to chunked reads on failure
+find_last_header(Fd, FileSize) ->
+ ok = file:advise(Fd, 0, FileSize, dont_need), % minimize disk cache pollution
+ Pos = (FileSize div ?SIZE_BLOCK) * ?SIZE_BLOCK,
+ case file:pread(Fd, Pos, FileSize - Pos) of
+ eof ->
+ no_valid_header;
+ {ok, Data} ->
+ try match_header(Fd, Pos, Data, 0) of
+ {ok, HeaderBin} ->
+ {ok, HeaderBin}
+ catch
+ error:{badmatch, _} ->
+ find_header_in_chunks(Fd, Pos, 1)
+ end
+ end.
+
+-define(DEFAULT_CHUNK_MAX_SIZE, ?SIZE_BLOCK).
+-define(DEFAULT_CHUNK_EXPONENT_BASE, 1).
+
+chunk_max_size() ->
+ config:get_integer("couchdb", "chunk_max_size", ?DEFAULT_CHUNK_MAX_SIZE).
+
+%% chunk size exponentially increases by iteration, up to some maximum,
+%% and should never exceed the current position in the file
+chunk_size(Pos, Multiplier) ->
+ Size = min(Multiplier * ?SIZE_BLOCK, chunk_max_size()),
+ min(Pos, Size).
+
+multiplier(Size, Multiplier) ->
+ case Size < chunk_max_size() of
+ true ->
+ Multiplier * config:get_integer(
+ "couchdb", "chunk_exponent_base", ?DEFAULT_CHUNK_EXPONENT_BASE);
+ false ->
+ Multiplier
+ end.
+
+find_header_in_chunks(_Fd, Pos, _Multiplier) when Pos < 0 ->
+ no_valid_header;
+find_header_in_chunks(Fd, Pos, Multiplier) ->
+ Size = chunk_size(Pos, Multiplier),
+ case Size > 0 of
+ false ->
+ no_valid_header;
+ true ->
+ {ok, Chunk} = file:pread(Fd, Pos - Size, Size),
+ case find_header_in_chunk(Fd, Pos, Chunk, Size) of
+ {ok, HeaderBin, _Offset} ->
+ %% io:format("found header at ~p multiplier ~p chunksize ~p~n",
+ %% [Pos - Size + _Offset, Multiplier, Size]),
+ {ok, HeaderBin};
+ not_found ->
+ NewMultiplier = multiplier(Size, Multiplier),
+ find_header_in_chunks(Fd, Pos - Size, NewMultiplier)
+ end
+ end.
+
+find_header_in_chunk(_Fd, _Pos, _Chunk, Offset) when Offset < 0 ->
+ not_found;
+find_header_in_chunk(Fd, Pos, Chunk, Offset) ->
+ try match_header(Fd, Pos, Chunk, Offset) of
+ {ok, HeaderBin} ->
+ {ok, HeaderBin, Offset}
+ catch
+ error:{badmatch, _} ->
+ find_header_in_chunk(Fd, Pos, Chunk, Offset - ?SIZE_BLOCK)
+ end.
+
+read_size(Data, Offset) ->
+ min(size(Data), Offset + ?SIZE_BLOCK) - Offset.
+
+match_header(Fd, Pos, Data, Offset) ->
+ <<1, HeaderSize:32/integer-unsigned, RestBlock/binary>> =
+ binary:part(Data, Offset, read_size(Data, Offset)),
+ PrefixSize = 5, % 1 (version) + 4 (size) bytes
+ TotalSize = total_read_size(PrefixSize, HeaderSize),
+ HeaderPos = Pos - byte_size(Data) + Offset,
+ RawBin = raw_bin(Fd, HeaderPos, TotalSize, RestBlock),
+ <<Hash:16/binary, HeaderBin/binary>> =
+ iolist_to_binary(remove_block_prefixes(PrefixSize, RawBin)),
+ Hash = crypto:hash(md5, HeaderBin),
--- End diff --
It seems this is the main source of badmatch error. May be try to avoid exception with simpler case? And this will get rid all try / catch above.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch issue #185: 3061 adaptive header search
Posted by kocolosk <gi...@git.apache.org>.
Github user kocolosk commented on the issue:
https://github.com/apache/couchdb-couch/pull/185
Wow, great stuff @jaydoane
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch issue #185: 3061 adaptive header search
Posted by jaydoane <gi...@git.apache.org>.
Github user jaydoane commented on the issue:
https://github.com/apache/couchdb-couch/pull/185
@davisp, @theburge, et al, can you guys take a look?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch issue #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on the issue:
https://github.com/apache/couchdb-couch/pull/185
Good work and persistence, @jaydoane!
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r80056738
--- Diff: src/couch_file.erl ---
@@ -531,27 +537,96 @@ find_header(Fd, Block) ->
{ok, Bin} ->
{ok, Bin};
_Error ->
- find_header(Fd, Block -1)
+ find_header_pread2(Fd, Block -1)
end.
load_header(Fd, Block) ->
{ok, <<1, HeaderLen:32/integer, RestBlock/binary>>} =
file:pread(Fd, Block * ?SIZE_BLOCK, ?SIZE_BLOCK),
- TotalBytes = calculate_total_read_len(5, HeaderLen),
- case TotalBytes > byte_size(RestBlock) of
+ TotalSize = total_read_size(5, HeaderLen),
+ case TotalSize > byte_size(RestBlock) of
false ->
- <<RawBin:TotalBytes/binary, _/binary>> = RestBlock;
+ <<RawBin:TotalSize/binary, _/binary>> = RestBlock;
true ->
{ok, Missing} = file:pread(
Fd, (Block * ?SIZE_BLOCK) + 5 + byte_size(RestBlock),
- TotalBytes - byte_size(RestBlock)),
+ TotalSize - byte_size(RestBlock)),
RawBin = <<RestBlock/binary, Missing/binary>>
end,
<<Md5Sig:16/binary, HeaderBin/binary>> =
iolist_to_binary(remove_block_prefixes(5, RawBin)),
Md5Sig = couch_crypto:hash(md5, HeaderBin),
{ok, HeaderBin}.
+
+%% Read a configurable number of block locations at a time using
+%% file:pread/2. At each block location, read ?PREFIX_SIZE (5) bytes;
+%% if the first byte is <<1>>, assume it's a header block, and the
+%% next 4 bytes hold the size of the header.
--- End diff --
There's no assumption here. A header is by definition at any 4K boundary where the first byte is a 1. If we try and load a header and fail there its because of some sort of file corruption.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by jaydoane <gi...@git.apache.org>.
Github user jaydoane commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r71279401
--- Diff: src/couch_file.erl ---
@@ -524,6 +525,99 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+%% first try to read header at end, falling back to chunked reads on failure
+find_last_header(Fd, FileSize) ->
+ ok = file:advise(Fd, 0, FileSize, dont_need), % minimize disk cache pollution
+ Pos = (FileSize div ?SIZE_BLOCK) * ?SIZE_BLOCK,
+ case file:pread(Fd, Pos, FileSize - Pos) of
+ eof ->
+ no_valid_header;
+ {ok, Data} ->
+ try match_header(Fd, Pos, Data, 0) of
+ {ok, HeaderBin} ->
+ {ok, HeaderBin}
+ catch
+ error:{badmatch, _} ->
+ find_header_in_chunks(Fd, Pos, 1)
+ end
+ end.
+
+-define(DEFAULT_CHUNK_MAX_SIZE, ?SIZE_BLOCK).
+-define(DEFAULT_CHUNK_EXPONENT_BASE, 1).
+
+chunk_max_size() ->
+ config:get_integer("couchdb", "chunk_max_size", ?DEFAULT_CHUNK_MAX_SIZE).
+
+%% chunk size exponentially increases by iteration, up to some maximum,
+%% and should never exceed the current position in the file
+chunk_size(Pos, Multiplier) ->
+ Size = min(Multiplier * ?SIZE_BLOCK, chunk_max_size()),
+ min(Pos, Size).
+
+multiplier(Size, Multiplier) ->
+ case Size < chunk_max_size() of
+ true ->
+ Multiplier * config:get_integer(
+ "couchdb", "chunk_exponent_base", ?DEFAULT_CHUNK_EXPONENT_BASE);
+ false ->
+ Multiplier
+ end.
+
+find_header_in_chunks(_Fd, Pos, _Multiplier) when Pos < 0 ->
+ no_valid_header;
+find_header_in_chunks(Fd, Pos, Multiplier) ->
+ Size = chunk_size(Pos, Multiplier),
+ case Size > 0 of
+ false ->
+ no_valid_header;
+ true ->
+ {ok, Chunk} = file:pread(Fd, Pos - Size, Size),
+ case find_header_in_chunk(Fd, Pos, Chunk, Size) of
+ {ok, HeaderBin, _Offset} ->
+ %% io:format("found header at ~p multiplier ~p chunksize ~p~n",
+ %% [Pos - Size + _Offset, Multiplier, Size]),
+ {ok, HeaderBin};
+ not_found ->
+ NewMultiplier = multiplier(Size, Multiplier),
+ find_header_in_chunks(Fd, Pos - Size, NewMultiplier)
+ end
+ end.
+
+find_header_in_chunk(_Fd, _Pos, _Chunk, Offset) when Offset < 0 ->
+ not_found;
+find_header_in_chunk(Fd, Pos, Chunk, Offset) ->
+ try match_header(Fd, Pos, Chunk, Offset) of
+ {ok, HeaderBin} ->
+ {ok, HeaderBin, Offset}
+ catch
+ error:{badmatch, _} ->
+ find_header_in_chunk(Fd, Pos, Chunk, Offset - ?SIZE_BLOCK)
+ end.
+
+read_size(Data, Offset) ->
+ min(size(Data), Offset + ?SIZE_BLOCK) - Offset.
+
+match_header(Fd, Pos, Data, Offset) ->
+ <<1, HeaderSize:32/integer-unsigned, RestBlock/binary>> =
+ binary:part(Data, Offset, read_size(Data, Offset)),
+ PrefixSize = 5, % 1 (version) + 4 (size) bytes
+ TotalSize = total_read_size(PrefixSize, HeaderSize),
+ HeaderPos = Pos - byte_size(Data) + Offset,
+ RawBin = raw_bin(Fd, HeaderPos, TotalSize, RestBlock),
+ <<Hash:16/binary, HeaderBin/binary>> =
+ iolist_to_binary(remove_block_prefixes(PrefixSize, RawBin)),
+ Hash = crypto:hash(md5, HeaderBin),
--- End diff --
`match_header` can also raise a badmatch on line 601, especially since only header blocks start with a <<1>>. While I was tempted to avoid try ... catch and just use case statements, it seemed to make the code significantly more difficult to understand.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r75903240
--- Diff: src/couch_file.erl ---
@@ -524,6 +528,214 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+find_last_header(Fd, FileSize) ->
+ find_header_in_chunks(Fd, start_pos(FileSize), 1).
+
+start_pos(FileSize) when FileSize rem ?SIZE_BLOCK =:= 0 ->
+ FileSize;
+start_pos(FileSize) ->
+ %% set position to nearest block boundary past eof
+ %% if file size isn't multiple of block size
--- End diff --
Use proper capitalization, grammar, and punctuation in comments.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch issue #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on the issue:
https://github.com/apache/couchdb-couch/pull/185
I like the idea here but I think we need to rethink the implementation a bit. First, the timing numbers reported are in microseconds so I'm not super convinced on them. What size of file are you testing against and how far back is the header? I'd almost wager its only one or two blocks back and the timing is fairly random.
However I know you had a big file we found in production where the adaptive algorithm probably fared much better. Obviously we can't give that out but we can fake the data by creating files with successively more data after the last header fairly easily. I'd like to see a test/benchmark of that nature before we get too lost in the weeds.
On the implementation side, this is a fine proof of concept but needs a bit of cleaning up. First, you've added two exported functions for testing which really shouldn't be in the final PR. The way the recursion works having the first iteration in find_last_header before moving to find_header_in_chunks seems wrong. That recursion should just be a single loop that expands its read-ahead starting with the initial values in find_last_header.
Second, the default appears to devolve into nearly exactly the same behavior as the current implementation which makes the timing numbers surprising. It seems a bit odd to write an improvement that needs to be configured to be effective. Given that people are going to get hit by this unexpectedly it seems like a fairly obscure expert option to know when and how to change the config when a database or view has a timeout when being opened.
Reading this I also realized that it might be beneficial to look at using file:pread/2 which does vectored reads. Using that we can read five bytes at the last N header offsets and then only read the exact header size when checking each spot with the header flag set. Using pread/2 here would allow us to scan larger chunks of file at the cost of having a second read for every header flag that's set. Assuming that headers are relatively rare events it seems like preferring to seek backwards without reading the entire file into RAM would be faster than attempting to avoid any follow on reads (given that we stop at the first valid header and don't expect many invalid headers). However this is obviously something that needs to be tested before we can be sure.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by jaydoane <gi...@git.apache.org>.
Github user jaydoane commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r81476893
--- Diff: src/couch_file.erl ---
@@ -531,27 +537,96 @@ find_header(Fd, Block) ->
{ok, Bin} ->
{ok, Bin};
_Error ->
- find_header(Fd, Block -1)
+ find_header_pread2(Fd, Block -1)
--- End diff --
@davisp, I'm confused about this comment. There's already a `find_header/2` that's still being used to try to load a header at eof. If that fails, we fall back to the vectored read version, which is also arity 2, and so has to have some other name. How about `find_header_vectored/2`?
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r75904032
--- Diff: src/couch_file.erl ---
@@ -524,6 +528,214 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+find_last_header(Fd, FileSize) ->
+ find_header_in_chunks(Fd, start_pos(FileSize), 1).
+
+start_pos(FileSize) when FileSize rem ?SIZE_BLOCK =:= 0 ->
+ FileSize;
+start_pos(FileSize) ->
+ %% set position to nearest block boundary past eof
+ %% if file size isn't multiple of block size
+ (FileSize div ?SIZE_BLOCK) * ?SIZE_BLOCK + ?SIZE_BLOCK.
+
+chunk_max_size() ->
+ config:get_integer("couchdb", "chunk_max_size", ?DEFAULT_CHUNK_MAX_SIZE).
+
+%% chunk size exponentially increases by iteration, up to some maximum,
+%% and should never exceed the current position in the file
+chunk_size(Pos, Multiplier) ->
+ Size = min(Multiplier * ?SIZE_BLOCK, chunk_max_size()),
+ min(Pos, Size).
+
+multiplier(Size, Multiplier) ->
+ case Size < chunk_max_size() of
+ true ->
+ Multiplier * config:get_integer(
+ "couchdb", "chunk_exponent_base", ?DEFAULT_CHUNK_EXPONENT_BASE);
+ false ->
+ Multiplier
+ end.
+
+find_header_in_chunks(_Fd, Pos, _Multiplier) when Pos < 0 ->
+ no_valid_header;
+find_header_in_chunks(Fd, Pos, Multiplier) ->
+ Size = chunk_size(Pos, Multiplier),
+ case Size > 0 of
+ false ->
+ no_valid_header;
+ true ->
+ {ok, Chunk} = file:pread(Fd, Pos - Size, Size),
+ case find_header_in_chunk(Fd, Pos, Chunk, Size - ?SIZE_BLOCK) of
+ {ok, HeaderBin, _Offset} ->
+ %% io:format("found header at ~p multiplier ~p chunksize ~p~n",
+ %% [Pos - Size + _Offset, Multiplier, Size]),
+ {ok, HeaderBin};
+ not_found ->
+ %% tell kernel we don't need that chunk any more
+ %% to minimize disk cache pollution
+ ok = file:advise(Fd, Pos - Size, Size, dont_need),
+ NewMultiplier = multiplier(Size, Multiplier),
+ find_header_in_chunks(Fd, Pos - Size, NewMultiplier)
+ end
+ end.
+
+-define(DEFAULT_SPAN_MAX_SIZE, ?SIZE_BLOCK * ?SIZE_BLOCK).
+-define(DEFAULT_SPAN_EXPONENT_BASE, 2).
+-define(PREFIX_SIZE, 5).
+
+system_milli_seconds() ->
+ {Mega, Sec, Micro} = os:timestamp(),
+ (Mega*1000000 + Sec)*1000 + round(Micro/1000).
+
+last_block_pos(FileSize) when FileSize rem ?SIZE_BLOCK =:= 0 ->
+ FileSize - ?SIZE_BLOCK;
--- End diff --
This clause isn't needed.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by kocolosk <gi...@git.apache.org>.
Github user kocolosk commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r71254154
--- Diff: src/couch_file.erl ---
@@ -524,6 +525,99 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+%% first try to read header at end, falling back to chunked reads on failure
+find_last_header(Fd, FileSize) ->
+ ok = file:advise(Fd, 0, FileSize, dont_need), % minimize disk cache pollution
--- End diff --
I'm all for smarter use of `posix_fadvise`, but I'm confused about the advice being given here. On modern Linux systems doesn't this just tell the kernel to free all pages associated with this file descriptor?
Were you trying to tell the kernel not to cache the reads that you do? I think that's the intention behind the `no_reuse` setting, but as far as I know it was never implemented and setting that flag is a noop.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r75903860
--- Diff: src/couch_file.erl ---
@@ -524,6 +528,214 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+find_last_header(Fd, FileSize) ->
+ find_header_in_chunks(Fd, start_pos(FileSize), 1).
+
+start_pos(FileSize) when FileSize rem ?SIZE_BLOCK =:= 0 ->
+ FileSize;
+start_pos(FileSize) ->
+ %% set position to nearest block boundary past eof
+ %% if file size isn't multiple of block size
+ (FileSize div ?SIZE_BLOCK) * ?SIZE_BLOCK + ?SIZE_BLOCK.
+
+chunk_max_size() ->
+ config:get_integer("couchdb", "chunk_max_size", ?DEFAULT_CHUNK_MAX_SIZE).
+
+%% chunk size exponentially increases by iteration, up to some maximum,
+%% and should never exceed the current position in the file
+chunk_size(Pos, Multiplier) ->
+ Size = min(Multiplier * ?SIZE_BLOCK, chunk_max_size()),
+ min(Pos, Size).
+
+multiplier(Size, Multiplier) ->
+ case Size < chunk_max_size() of
+ true ->
+ Multiplier * config:get_integer(
+ "couchdb", "chunk_exponent_base", ?DEFAULT_CHUNK_EXPONENT_BASE);
+ false ->
+ Multiplier
+ end.
+
+find_header_in_chunks(_Fd, Pos, _Multiplier) when Pos < 0 ->
+ no_valid_header;
+find_header_in_chunks(Fd, Pos, Multiplier) ->
+ Size = chunk_size(Pos, Multiplier),
+ case Size > 0 of
+ false ->
+ no_valid_header;
+ true ->
+ {ok, Chunk} = file:pread(Fd, Pos - Size, Size),
+ case find_header_in_chunk(Fd, Pos, Chunk, Size - ?SIZE_BLOCK) of
+ {ok, HeaderBin, _Offset} ->
+ %% io:format("found header at ~p multiplier ~p chunksize ~p~n",
+ %% [Pos - Size + _Offset, Multiplier, Size]),
+ {ok, HeaderBin};
+ not_found ->
+ %% tell kernel we don't need that chunk any more
+ %% to minimize disk cache pollution
--- End diff --
Did we talk about whether this actually works or not? I seem to remember a conversation about fadvise ignoring various calls. I ask because we'd also want to see if this is supported on windows (or at least doesn't throw an error).
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by kxepal <gi...@git.apache.org>.
Github user kxepal commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r71203761
--- Diff: src/couch_file.erl ---
@@ -524,6 +525,99 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+%% first try to read header at end, falling back to chunked reads on failure
+find_last_header(Fd, FileSize) ->
+ ok = file:advise(Fd, 0, FileSize, dont_need), % minimize disk cache pollution
+ Pos = (FileSize div ?SIZE_BLOCK) * ?SIZE_BLOCK,
+ case file:pread(Fd, Pos, FileSize - Pos) of
+ eof ->
+ no_valid_header;
+ {ok, Data} ->
+ try match_header(Fd, Pos, Data, 0) of
+ {ok, HeaderBin} ->
+ {ok, HeaderBin}
+ catch
+ error:{badmatch, _} ->
+ find_header_in_chunks(Fd, Pos, 1)
+ end
+ end.
+
+-define(DEFAULT_CHUNK_MAX_SIZE, ?SIZE_BLOCK).
+-define(DEFAULT_CHUNK_EXPONENT_BASE, 1).
--- End diff --
Lets put these defines there the rest ones are located.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r80055495
--- Diff: src/couch_file.erl ---
@@ -40,6 +45,7 @@
-export([append_term/2, append_term/3, append_term_md5/2, append_term_md5/3]).
-export([write_header/2, read_header/1]).
-export([delete/2, delete/3, nuke_dir/2, init_delete_dir/1]).
+-export([find_header/2]).
--- End diff --
Remove this since it was just for testing.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch issue #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on the issue:
https://github.com/apache/couchdb-couch/pull/185
The implementation looks better. A few style issues I'll not nit pick on till later.
I only meant "wrong" in so much in that it was a common recursion error in pulling out an iteration into a separate function for no good reason.
To clarify the `file:pread/2` comment, I think you're confusing `file:pread/2` with `file:pread/3` which is totally understandable. I've collectively spent hours over the years poring over the file module and everything beneath it towards the kernel so I was probably a bit terse on that.
Currently in couch_file we use `file:pread/3` quite a lot. This call basically ends up being a direct translation to the POSIX `pread` call. That is, it's "read N bytes at position X". The `file:pread/2` call similar except that in one call through the Erlang IO layers you can say "read [{N bytes, at X pos} | ...]` to grab a whole bunch of bytes at different locations. I used to be under the impression that this translated to a POSIX `readv` call but now that I spelunk through the VM code it appears to just be calling pread multiple times (although at the C driver level, so it should be noticeably faster than using `file:pread/3` multiple times).
But in the end it'll depend on drives and various bits since our headers are only 4KiB apart. SSDs and the like have page reads in that range which means we may or may not be saving on IO bandwidth. I dunno when the hardware/kernel drops unwanted bytes. However under load we should at least prevent larger amounts of allocated RAM when searching files for headers as it'd be at most in the kernel. Your use of fadvise would also likely help though for that we'd want to investigate the note about page offsets and the like to make sure those calls are effective.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by jaydoane <gi...@git.apache.org>.
Github user jaydoane commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r71461794
--- Diff: src/couch_file.erl ---
@@ -524,6 +525,99 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+%% first try to read header at end, falling back to chunked reads on failure
+find_last_header(Fd, FileSize) ->
+ ok = file:advise(Fd, 0, FileSize, dont_need), % minimize disk cache pollution
+ Pos = (FileSize div ?SIZE_BLOCK) * ?SIZE_BLOCK,
+ case file:pread(Fd, Pos, FileSize - Pos) of
+ eof ->
+ no_valid_header;
+ {ok, Data} ->
+ try match_header(Fd, Pos, Data, 0) of
+ {ok, HeaderBin} ->
+ {ok, HeaderBin}
+ catch
+ error:{badmatch, _} ->
+ find_header_in_chunks(Fd, Pos, 1)
+ end
+ end.
+
+-define(DEFAULT_CHUNK_MAX_SIZE, ?SIZE_BLOCK).
+-define(DEFAULT_CHUNK_EXPONENT_BASE, 1).
+
+chunk_max_size() ->
+ config:get_integer("couchdb", "chunk_max_size", ?DEFAULT_CHUNK_MAX_SIZE).
+
+%% chunk size exponentially increases by iteration, up to some maximum,
+%% and should never exceed the current position in the file
+chunk_size(Pos, Multiplier) ->
+ Size = min(Multiplier * ?SIZE_BLOCK, chunk_max_size()),
+ min(Pos, Size).
+
+multiplier(Size, Multiplier) ->
+ case Size < chunk_max_size() of
+ true ->
+ Multiplier * config:get_integer(
+ "couchdb", "chunk_exponent_base", ?DEFAULT_CHUNK_EXPONENT_BASE);
+ false ->
+ Multiplier
+ end.
+
+find_header_in_chunks(_Fd, Pos, _Multiplier) when Pos < 0 ->
+ no_valid_header;
+find_header_in_chunks(Fd, Pos, Multiplier) ->
+ Size = chunk_size(Pos, Multiplier),
+ case Size > 0 of
+ false ->
+ no_valid_header;
+ true ->
+ {ok, Chunk} = file:pread(Fd, Pos - Size, Size),
+ case find_header_in_chunk(Fd, Pos, Chunk, Size) of
+ {ok, HeaderBin, _Offset} ->
+ %% io:format("found header at ~p multiplier ~p chunksize ~p~n",
+ %% [Pos - Size + _Offset, Multiplier, Size]),
+ {ok, HeaderBin};
+ not_found ->
+ NewMultiplier = multiplier(Size, Multiplier),
+ find_header_in_chunks(Fd, Pos - Size, NewMultiplier)
+ end
+ end.
+
+find_header_in_chunk(_Fd, _Pos, _Chunk, Offset) when Offset < 0 ->
+ not_found;
+find_header_in_chunk(Fd, Pos, Chunk, Offset) ->
+ try match_header(Fd, Pos, Chunk, Offset) of
+ {ok, HeaderBin} ->
+ {ok, HeaderBin, Offset}
+ catch
+ error:{badmatch, _} ->
+ find_header_in_chunk(Fd, Pos, Chunk, Offset - ?SIZE_BLOCK)
+ end.
+
+read_size(Data, Offset) ->
+ min(size(Data), Offset + ?SIZE_BLOCK) - Offset.
+
+match_header(Fd, Pos, Data, Offset) ->
+ <<1, HeaderSize:32/integer-unsigned, RestBlock/binary>> =
+ binary:part(Data, Offset, read_size(Data, Offset)),
+ PrefixSize = 5, % 1 (version) + 4 (size) bytes
+ TotalSize = total_read_size(PrefixSize, HeaderSize),
+ HeaderPos = Pos - byte_size(Data) + Offset,
+ RawBin = raw_bin(Fd, HeaderPos, TotalSize, RestBlock),
+ <<Hash:16/binary, HeaderBin/binary>> =
+ iolist_to_binary(remove_block_prefixes(PrefixSize, RawBin)),
+ Hash = crypto:hash(md5, HeaderBin),
--- End diff --
While I am generally not a big fan of gratuitous `try ... catch` syntax, in this case I think it's the superior option because:
- it results in less code
- it results in flatter code
- it's arguably easier to understand
This shows that the above implementation without `try` is almost 80% larger than the implementation you suggested:
```
$ git diff --stat src/couch_file.erl
src/couch_file.erl | 39 +++++++++++++++++++++++++--------------
1 file changed, 25 insertions(+), 14 deletions(-)
```
In short, I would prefer to keep the `try ... catch` unless there is strong objection otherwise.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch issue #185: 3061 adaptive header search
Posted by theburge <gi...@git.apache.org>.
Github user theburge commented on the issue:
https://github.com/apache/couchdb-couch/pull/185
Thanks for doing the additional investigation @jaydoane. I'm glad the performance remains consistently improved.
From memory, I've observed deeply buried headers frequently in MT, although admittedly not lots at once (usually a DB or two). However, they're not only on .meta files if memory serves, but also on view files (and I'm fairly sure on primary database files, although IIRC usually in correlation with some other odd behaviour -- so perhaps it shouldn't be considered _normal_ but it's certainly possible).
In any case, it's reassuring that the vectored approach is only tried if the basic approach fails, given the striking difference in page-in rate.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch issue #185: 3061 adaptive header search
Posted by theburge <gi...@git.apache.org>.
Github user theburge commented on the issue:
https://github.com/apache/couchdb-couch/pull/185
@jaydoane: One additional thought I had was that it's taking good care of the page cache with `posix_fadvise`, but perhaps not quite such good care of the BEAM's memory usage. Have you measured system memory usage when there's a lot of trawling for headers?
I think it's worth considering making an explicit garbage collection when the code finishes backtracking for headers, since it might have read a number of large, off-heap binaries.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by jaydoane <gi...@git.apache.org>.
Github user jaydoane commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r71463607
--- Diff: src/couch_file.erl ---
@@ -524,6 +525,99 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+%% first try to read header at end, falling back to chunked reads on failure
+find_last_header(Fd, FileSize) ->
+ ok = file:advise(Fd, 0, FileSize, dont_need), % minimize disk cache pollution
+ Pos = (FileSize div ?SIZE_BLOCK) * ?SIZE_BLOCK,
+ case file:pread(Fd, Pos, FileSize - Pos) of
+ eof ->
+ no_valid_header;
+ {ok, Data} ->
+ try match_header(Fd, Pos, Data, 0) of
+ {ok, HeaderBin} ->
+ {ok, HeaderBin}
+ catch
+ error:{badmatch, _} ->
+ find_header_in_chunks(Fd, Pos, 1)
+ end
+ end.
+
+-define(DEFAULT_CHUNK_MAX_SIZE, ?SIZE_BLOCK).
+-define(DEFAULT_CHUNK_EXPONENT_BASE, 1).
--- End diff --
Done
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r80055158
--- Diff: src/couch_file.erl ---
@@ -16,13 +16,18 @@
-include_lib("couch/include/couch_db.hrl").
-
--- End diff --
Remove whitespace only changes
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r75903529
--- Diff: src/couch_file.erl ---
@@ -524,6 +528,214 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+find_last_header(Fd, FileSize) ->
+ find_header_in_chunks(Fd, start_pos(FileSize), 1).
+
+start_pos(FileSize) when FileSize rem ?SIZE_BLOCK =:= 0 ->
+ FileSize;
+start_pos(FileSize) ->
+ %% set position to nearest block boundary past eof
+ %% if file size isn't multiple of block size
+ (FileSize div ?SIZE_BLOCK) * ?SIZE_BLOCK + ?SIZE_BLOCK.
+
+chunk_max_size() ->
+ config:get_integer("couchdb", "chunk_max_size", ?DEFAULT_CHUNK_MAX_SIZE).
--- End diff --
Seems sill to reconsult the config ets table multiple times for every iteration. Perhaps it would be cleaner to create a record for your current iteration state.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by davisp <gi...@git.apache.org>.
Github user davisp commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r71473312
--- Diff: src/couch_file.erl ---
@@ -524,6 +525,99 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+%% first try to read header at end, falling back to chunked reads on failure
+find_last_header(Fd, FileSize) ->
+ ok = file:advise(Fd, 0, FileSize, dont_need), % minimize disk cache pollution
+ Pos = (FileSize div ?SIZE_BLOCK) * ?SIZE_BLOCK,
+ case file:pread(Fd, Pos, FileSize - Pos) of
+ eof ->
+ no_valid_header;
+ {ok, Data} ->
+ try match_header(Fd, Pos, Data, 0) of
+ {ok, HeaderBin} ->
+ {ok, HeaderBin}
+ catch
+ error:{badmatch, _} ->
+ find_header_in_chunks(Fd, Pos, 1)
+ end
+ end.
+
+-define(DEFAULT_CHUNK_MAX_SIZE, ?SIZE_BLOCK).
+-define(DEFAULT_CHUNK_EXPONENT_BASE, 1).
+
+chunk_max_size() ->
+ config:get_integer("couchdb", "chunk_max_size", ?DEFAULT_CHUNK_MAX_SIZE).
+
+%% chunk size exponentially increases by iteration, up to some maximum,
+%% and should never exceed the current position in the file
+chunk_size(Pos, Multiplier) ->
+ Size = min(Multiplier * ?SIZE_BLOCK, chunk_max_size()),
+ min(Pos, Size).
+
+multiplier(Size, Multiplier) ->
+ case Size < chunk_max_size() of
+ true ->
+ Multiplier * config:get_integer(
+ "couchdb", "chunk_exponent_base", ?DEFAULT_CHUNK_EXPONENT_BASE);
+ false ->
+ Multiplier
+ end.
+
+find_header_in_chunks(_Fd, Pos, _Multiplier) when Pos < 0 ->
+ no_valid_header;
+find_header_in_chunks(Fd, Pos, Multiplier) ->
+ Size = chunk_size(Pos, Multiplier),
+ case Size > 0 of
+ false ->
+ no_valid_header;
+ true ->
+ {ok, Chunk} = file:pread(Fd, Pos - Size, Size),
+ case find_header_in_chunk(Fd, Pos, Chunk, Size) of
+ {ok, HeaderBin, _Offset} ->
+ %% io:format("found header at ~p multiplier ~p chunksize ~p~n",
+ %% [Pos - Size + _Offset, Multiplier, Size]),
+ {ok, HeaderBin};
+ not_found ->
+ NewMultiplier = multiplier(Size, Multiplier),
+ find_header_in_chunks(Fd, Pos - Size, NewMultiplier)
+ end
+ end.
+
+find_header_in_chunk(_Fd, _Pos, _Chunk, Offset) when Offset < 0 ->
+ not_found;
+find_header_in_chunk(Fd, Pos, Chunk, Offset) ->
+ try match_header(Fd, Pos, Chunk, Offset) of
+ {ok, HeaderBin} ->
+ {ok, HeaderBin, Offset}
+ catch
+ error:{badmatch, _} ->
+ find_header_in_chunk(Fd, Pos, Chunk, Offset - ?SIZE_BLOCK)
+ end.
+
+read_size(Data, Offset) ->
+ min(size(Data), Offset + ?SIZE_BLOCK) - Offset.
+
+match_header(Fd, Pos, Data, Offset) ->
+ <<1, HeaderSize:32/integer-unsigned, RestBlock/binary>> =
+ binary:part(Data, Offset, read_size(Data, Offset)),
+ PrefixSize = 5, % 1 (version) + 4 (size) bytes
+ TotalSize = total_read_size(PrefixSize, HeaderSize),
+ HeaderPos = Pos - byte_size(Data) + Offset,
+ RawBin = raw_bin(Fd, HeaderPos, TotalSize, RestBlock),
+ <<Hash:16/binary, HeaderBin/binary>> =
+ iolist_to_binary(remove_block_prefixes(PrefixSize, RawBin)),
+ Hash = crypto:hash(md5, HeaderBin),
--- End diff --
To narrow down that we can just throw specific terms rather than rely on general Erlang exceptions which keeps the code clean while not swallowing unexpected errors. Given the depth of these functions in the couch_file module I could see that if we don't add in-module tests that can exercise these functions more directly.
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---
[GitHub] couchdb-couch pull request #185: 3061 adaptive header search
Posted by kxepal <gi...@git.apache.org>.
Github user kxepal commented on a diff in the pull request:
https://github.com/apache/couchdb-couch/pull/185#discussion_r71470204
--- Diff: src/couch_file.erl ---
@@ -524,6 +525,99 @@ handle_info({'EXIT', _, Reason}, Fd) ->
{stop, Reason, Fd}.
+%% first try to read header at end, falling back to chunked reads on failure
+find_last_header(Fd, FileSize) ->
+ ok = file:advise(Fd, 0, FileSize, dont_need), % minimize disk cache pollution
+ Pos = (FileSize div ?SIZE_BLOCK) * ?SIZE_BLOCK,
+ case file:pread(Fd, Pos, FileSize - Pos) of
+ eof ->
+ no_valid_header;
+ {ok, Data} ->
+ try match_header(Fd, Pos, Data, 0) of
+ {ok, HeaderBin} ->
+ {ok, HeaderBin}
+ catch
+ error:{badmatch, _} ->
+ find_header_in_chunks(Fd, Pos, 1)
+ end
+ end.
+
+-define(DEFAULT_CHUNK_MAX_SIZE, ?SIZE_BLOCK).
+-define(DEFAULT_CHUNK_EXPONENT_BASE, 1).
+
+chunk_max_size() ->
+ config:get_integer("couchdb", "chunk_max_size", ?DEFAULT_CHUNK_MAX_SIZE).
+
+%% chunk size exponentially increases by iteration, up to some maximum,
+%% and should never exceed the current position in the file
+chunk_size(Pos, Multiplier) ->
+ Size = min(Multiplier * ?SIZE_BLOCK, chunk_max_size()),
+ min(Pos, Size).
+
+multiplier(Size, Multiplier) ->
+ case Size < chunk_max_size() of
+ true ->
+ Multiplier * config:get_integer(
+ "couchdb", "chunk_exponent_base", ?DEFAULT_CHUNK_EXPONENT_BASE);
+ false ->
+ Multiplier
+ end.
+
+find_header_in_chunks(_Fd, Pos, _Multiplier) when Pos < 0 ->
+ no_valid_header;
+find_header_in_chunks(Fd, Pos, Multiplier) ->
+ Size = chunk_size(Pos, Multiplier),
+ case Size > 0 of
+ false ->
+ no_valid_header;
+ true ->
+ {ok, Chunk} = file:pread(Fd, Pos - Size, Size),
+ case find_header_in_chunk(Fd, Pos, Chunk, Size) of
+ {ok, HeaderBin, _Offset} ->
+ %% io:format("found header at ~p multiplier ~p chunksize ~p~n",
+ %% [Pos - Size + _Offset, Multiplier, Size]),
+ {ok, HeaderBin};
+ not_found ->
+ NewMultiplier = multiplier(Size, Multiplier),
+ find_header_in_chunks(Fd, Pos - Size, NewMultiplier)
+ end
+ end.
+
+find_header_in_chunk(_Fd, _Pos, _Chunk, Offset) when Offset < 0 ->
+ not_found;
+find_header_in_chunk(Fd, Pos, Chunk, Offset) ->
+ try match_header(Fd, Pos, Chunk, Offset) of
+ {ok, HeaderBin} ->
+ {ok, HeaderBin, Offset}
+ catch
+ error:{badmatch, _} ->
+ find_header_in_chunk(Fd, Pos, Chunk, Offset - ?SIZE_BLOCK)
+ end.
+
+read_size(Data, Offset) ->
+ min(size(Data), Offset + ?SIZE_BLOCK) - Offset.
+
+match_header(Fd, Pos, Data, Offset) ->
+ <<1, HeaderSize:32/integer-unsigned, RestBlock/binary>> =
+ binary:part(Data, Offset, read_size(Data, Offset)),
+ PrefixSize = 5, % 1 (version) + 4 (size) bytes
+ TotalSize = total_read_size(PrefixSize, HeaderSize),
+ HeaderPos = Pos - byte_size(Data) + Offset,
+ RawBin = raw_bin(Fd, HeaderPos, TotalSize, RestBlock),
+ <<Hash:16/binary, HeaderBin/binary>> =
+ iolist_to_binary(remove_block_prefixes(PrefixSize, RawBin)),
+ Hash = crypto:hash(md5, HeaderBin),
--- End diff --
@jaydoane My main objection is that bad_match error is too broad and catching it may swallow some mistake which is actually not expected to be caught. Not yours, not today, but in future. And that code is quite important to have no hidden bugs.
I'm not about to always avoid try/catch all the time, but to use them only when they are really needed. And scope on where try/catch are applied should be as minimal as possible - that the rule that works for every language, not Erlang.
I'm not ready to have strong objections, so decision is up to you (:
---
If your project is set up for it, you can reply to this email and have your
reply appear on GitHub as well. If your project does not have this feature
enabled and wishes so, or if the feature is enabled but not working, please
contact infrastructure at infrastructure@apache.org or file a JIRA ticket
with INFRA.
---